시간 제한
메모리 제한
시간 제한
2초
메모리 제한
128 MB
2차원 평면 위에 들쥐 N마리와 땅굴 M개가 있다. 각 들쥐와 각 땅굴의 위치는 평면 위의 한 점으로 주어지며, 한 땅굴에는 들쥐 한 마리만 들어갈 수 있다.
매는 지금부터 S초 뒤에 땅에 도착한다. 모든 들쥐는 초당 V만큼 이동할 수 있다. 어떤 들쥐가 S초 이내에 어떤 땅굴에 도착할 수 있으면 그 들쥐는 그 땅굴로 숨을 수 있다. 도착 시간이 정확히 S초인 경우도 숨을 수 있다.
들쥐들은 잡아먹히는 수를 최소로 만들도록 땅굴을 선택하려고 한다. 들쥐와 땅굴의 위치, 매가 도착하기까지의 시간, 들쥐의 속도가 주어질 때 잡아먹히는 들쥐 수의 최솟값을 구하라.
첫째 줄에 네 정수 N, M, S, V가 주어진다. 1 <= N, M, S, V <= 100이다.
다음 N개의 줄에는 각 들쥐의 x좌표와 y좌표가 주어진다. 이어지는 M개의 줄에는 각 땅굴의 x좌표와 y좌표가 주어진다.
모든 좌표는 절댓값이 1,000을 넘지 않는 실수이며, 소수점 셋째 자리까지 주어질 수 있다.
잡아먹히는 들쥐 수의 최솟값을 한 줄에 출력한다.