루미 알고리즘

#1466플래티넘Forest Fire

PO 2019 결선코딩출제 Nils Gustafsson영어 원문이 문제가 어렵다면 — 배우는 순서 보기

영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

Problem

A fire has broken out in the integer forest! The integer forest consists of an infite two-dimensional plane where there is a tree at each point with integer coordinates. Currently, N of these trees are on fire. Each minute, the fire spreads from every burning tree to its four neighbours (the trees immediately north, east, west and south). To stop the fire, the fire marshals have chopped down M trees. A chopped-down tree can not catch fire, so these points act like a kind of wall to the flames. You are interested in the damage that the fire will cause. In T minutes, there will be a great rain storm that will put out the entire fire. Therefore, you want to know how many trees are on fire after T minutes.

Input

The first line contains three integers:

  • the number of burning trees N (1 ≤ N ≤ 100),
  • the number of chopped-down trees M (0 ≤ M ≤ 100),
  • and the number of minutes to the great rain storm T (0 ≤ T ≤ 10^9).

The following N lines contains two integers x_i,y_i (0 ≤ x_i, y_i < 10^5), the coordinates of the burning trees.

The following M lines contains two integers x_i,y_i (0 ≤ x_i, y_i < 10^5), the coordinates of the chopped-down trees.

No two trees, either burning or chopped down, will have the same coordinates.

Output

Output a single integer, the number of trees that are on fire after T minutes.

Scoring

Your solution will be tested on a set of test case groups. To get the points for a group, you need to pass all the test cases in the group.

GroupPointsConstraints
15N = 1, M = 0
29T ≤ 100, M = 0, x_i, y_i < 100
310T ≤ 400, x_i, y_i < 100
411M = 0, x_i, y_i < 100
521x_i, y_i < 100
615M = 0
729No further constraints

Explanations of samples

In sample 1 the fire spreads to (0,2), (1,3) and (2,2). In total, there will be 4 burning trees.

In sample 2 the only burning tree is surrounded by chopped-down trees. There is thus only a single burning tree, despite T being large.

In sample 3 the fire does not have time to spread since T = 0, so the answer is 4.

예제

예제 1

입력
1 1 1
1 2
1 1
출력
4

예제 2

입력
1 4 12345678
2 2
1 2
2 1
2 3
3 2
출력
1

예제 3

입력
4 1 0
1 1
1 2
2 3
3 4
7 7
출력
4

예제 4

입력
1 2 100000
0 0
2 1
1 2
출력
20000199999

출처 표기

출처: Programmeringsolympiaden 2019년 결선 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.