시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 1024 MB | 187 | 22 | 18 | 12.766% |
평화로운 도시에 갑자기 블랙홀이 생겼다. 블랙홀은 점점 커지며 도시의 건물을 전부 집어삼킬 것이다.
블랙홀은 다음과 같은 특징이 있다.
도시에는 $M$개의 건물이 있으며, 각 건물은 평면 상의 점으로 나타낼 수 있다.
당신은 매 초마다 블랙홀이 지금까지 집어삼킨 건물의 수를 세면서 블랙홀이 $K$개 이상의 건물을 집어삼켰으면 대피하려고 한다. 특이점, 블랙홀, 건물의 정보가 주어졌을 때에 대피하게 되는 시간을 구해보자.
첫째 줄에 정수 $N$, $M$, $K$가 주어진다. ($3 \le N \le 100\ 000$, $1 \le K \le M \le 100\ 000$)
둘째 줄에 블랙홀의 특이점의 좌표가 주어진다.
셋째 줄부터 $N$개 줄에 걸쳐 블랙홀의 꼭짓점들의 좌표가 반시계방향 순서로 주어진다.
다음 $M$개 줄에 걸쳐 각 건물의 좌표가 주어진다.
모든 점의 좌표는 $-10^9$ 이상 $10^9$ 이하의 정수이다.
대피 시간을 정수로 출력한다.
4 4 3 0 0 1 1 -1 1 -1 -1 1 -1 2 0 3 0 4 4 -5 5
3