20306번 - 블랙홀 출처분류

평화로운 도시에 갑자기 블랙홀이 생겼다. 블랙홀은 점점 커지며 도시의 건물을 전부 집어삼킬 것이다.

블랙홀은 다음과 같은 특징이 있다.

• 블랙홀은 평면 위의 $N$개의 점을 꼭짓점으로 갖는 볼록다각형으로 나타낼 수 있다. $N$개의 점 중 어느 세 점도 한 직선 위에 있지 않다.
• 블랙홀 경계를 포함하지 않는 내부에는 특이점이 하나 존재하며, 처음에 블랙홀을 이루는 점들은 블랙홀이 생긴 지 $t$초가 되는 시점에 이 특이점으로부터 $\left(t+1\right)$배 멀어져 있다.
• 블랙홀은 블랙홀의 내부와 경계에 있는 건물을 집어삼킨다.

도시에는 $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$ 이하의 정수이다.

대피 시간을 정수로 출력한다.