고퍼 II

면접 대비

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

요약

각 gopher는 s*v 미터 이내의 구멍 하나에만 들어갈 수 있고, 구멍마다 한 마리만 수용한다. 매칭을 최대로 잡아 굶주린 gopher 수를 최소로 줄인다.

난이도: 보통10점 중 6점
유형: 그래프, 유니온 파인드, 완전 탐색, 기하
정답자: 아직 제출이 없습니다

문제

땅다람쥐(고퍼) 가족은 개의 위협을 피했지만, 이제 새로운 포식자를 마주하게 되었습니다.

$n$ 마리의 고퍼와 $m$ 개의 고퍼 굴이 있으며, 각각 서로 다른 $(x, y)$ 좌표에 위치합니다. 매가 나타나면, $s$ 초 안에 굴에 도달하지 못한 고퍼는 잡아먹힐 위험에 놓입니다. 하나의 굴은 최대 한 마리의 고퍼만 숨겨 줄 수 있습니다. 모든 고퍼는 동일한 속력 $v$ 로 달립니다. 고퍼 가족은 위험에 놓이는 고퍼의 수를 최소화하는 탈출 전략을 세워야 합니다.

고퍼는 최대 $s \times v$ 미터까지 이동할 수 있으므로, 어떤 고퍼와 굴 사이의 거리가 $s \times v$ 이하이면 그 고퍼는 그 굴로 대피할 수 있습니다.

입력

입력은 여러 개의 테스트 케이스로 이루어집니다. 각 케이스의 첫 줄에는 $100$ 보다 작은 양의 정수 네 개 $n$ , $m$ , $s$ , $v$ 가 주어집니다. 이어지는 $n$ 개의 줄에는 고퍼들의 좌표가, 그다음 $m$ 개의 줄에는 굴들의 좌표가 주어집니다. 모든 거리의 단위는 미터, 시간의 단위는 초, 속력의 단위는 초당 미터입니다. 입력은 파일의 끝까지 계속됩니다.

출력

각 케이스마다 위험에 놓이는 고퍼의 수를 한 줄에 하나씩 출력합니다.

예제4

예제 1

입력

2 2 5 10
1.0 1.0
2.0 2.0
100.0 100.0
20.0 20.0

예상 출력

예제 2
입력
```
1 1 100 1
0.0 0.0
0.5 0.5
```
예상 출력
```
0
```
예제 3
입력
```
1 1 1 1
0.0 0.0
50.0 50.0
```
예상 출력
```
1
```

예제 4

입력

예상 출력