hanzch   2년 전

인플루엔자 (Flu)

시간 제한 메모리 제한
1 초 1024 MB

문제

올해 JOI 국가에서는 인플루엔자의 대유행 조짐이 있다. JOI 국가에는 n개의 도시 P1, ..., Pn이 있으며, 도시 Pi의 위치는 좌표를 사용하여 Pi(xi, yi)로 표시된다. 서로 다른 도시가 같은 좌표를 가지는 경우는 없다. 즉, i ≠ j이면 (xi, yi) ≠ (xj, yj)이다. 또한, 도시 P1은 수도인 JOI시이다.

올해의 인플루엔자는 특별한 유형으로, 다음과 같은 특징이 있다:

1. 각 도시에서 인플루엔자의 유행은 정확히 m일간 지속된다. 즉, 도시 Pi에서 인플루엔자가 유행하기 시작하면, Pi에서의 인플루엔자 유행은 정확히 m일간 지속되고, m일 후에는 유행이 수그러든다.

2. 한 도시에서 한 번 인플루엔자가 유행하면, 그 도시의 시민들의 체내에 항체가 생긴다. 따라서, 인플루엔자가 한 도시에서 2회 이상 유행하는 일은 없다.

3. 인플루엔자는 날이 갈수록 도시에서 도시로 유행이 확산된다. 감염 가능 거리는 d이다. 만약 도시 Pi에서 인플루엔자가 유행하기 시작했다고 가정할 때, 도시 Pj와 Pi의 거리가 d 이하이고, 아직 Pj에서는 인플루엔자가 유행하지 않은 경우, 그 다음 날에는 도시 Pj에서 인플루엔자가 유행하기 시작한다. (도시 Pi(xi, yi)와 Pj(xj, yj) 사이의 거리는 √((xi - xj)² + (yi - yj)²)이다.)

4. 위에서 언급한 것 외의 경로로 인플루엔자가 확산되는 일은 없다.

또한, 각 i = 1, ..., n에 대해, 도시 Pi로부터의 거리가 d 이하인 Pi 이외의 도시의 수는 10개 이하이다.

어느 날, 인플루엔자의 유행이 JOI시 P1에서 시작되었다. JOI시 이외의 도시에서는 올해 아직 인플루엔자가 유행하지 않았다. JOI 국가에서는 치료에 필요한 백신을 효율적으로 준비하기 위해 인플루엔자의 유행 상황을 예측하기로 했다.

입력으로 도시의 수 n, 한 도시에서 인플루엔자의 유행이 지속되는 일수 m, 인플루엔자의 감염 가능 거리 d, 정수 k ≥ 1, 각 도시의 좌표가 주어졌을 때, JOI시에서 유행이 시작된 후 k일 후에 JOI 국가 내에서 인플루엔자가 유행하고 있는 도시의 수를 구하는 프로그램을 작성하시오.

입력

입력의 1번째 줄에는 JOI 국가의 도시 수 n (1 ≤ n ≤ 100,000)이 적혀있다. 2번째 줄에는 각 도시에서 유행이 지속되는 일수 m (1 ≤ m ≤ 100)이 적혀있다. 3번째 줄에는 감염 가능 거리 d (1 ≤ d ≤ 25)가 적혀있다. 4번째 줄에는 정수 k (1 ≤ k ≤ 100)가 적혀있다. 이어지는 n개의 줄 (5번째 줄~n+4번째 줄)은 도시 P1, ..., Pn의 위치를 나타낸다. i+4번째 줄 (1 ≤ i ≤ n)에는 2개의 정수 xi, yi (0 ≤ xi, yi < 1,000)가 공백으로 구분되어 적혀있으며, 도시 Pi의 좌표가 Pi(xi, yi)임을 의미한다.

출력

출력은 표준출력으로 한다. JOI시에서 유행이 시작된 후 k일 후에 JOI 국가 내에서 인플루엔자가 유행하고 있는 도시의 수를 나타내는 정수를 1줄로 출력하시오.

예제

예제 입력 1

9
2
2
3
1 3
3 3
2 2
3 1
0 0
0 3
0 5
3 5
5 5

예제 출력 1

4

힌트

이 입력 예시에서 도시의 수는 n = 9이다. 또한, 9개의 도시 P1, ..., P9의 좌표는 순서대로 P1(1, 3), P2(3, 3), P3(2, 2), P4(3, 1), P5(0, 0), P6(0, 3), P7(0, 5), P8(3, 5), P9(5, 5)로 주어진다. 인플루엔자의 감염 가능 거리는 d = 2이며, 각 도시에서 유행이 지속되는 일수는 m = 2이다. 또한, k = 3이다.

처음에는 인플루엔자가 유행하고 있는 곳은 JOI시 P1뿐이다. 1일 후에는 인플루엔자의 유행이 P1로부터의 거리가 2 이하인 도시 P2, P3, P6으로 확산된다. 또한, JOI시 P1에서의 유행은 아직 수그러들지 않는다. 2일 후에는 유행이 P4, P7, P8로 확산되고, JOI시 P1에서의 유행은 수그러든다. 3일 후에는 유행이 P9로 확산되고, P2, P3, P6에서의 유행은 수그러든다.

preview

따라서, JOI시에서 유행이 시작된 후 3일 후에 인플루엔자가 유행하고 있는 도시는 P4, P7, P8, P9의 4개이므로, 4를 출력하면 된다.

이 입력 예시에서는 도시 P5에서 인플루엔자가 유행하는 일은 없다.

댓글을 작성하려면 로그인해야 합니다.