34702번 - 볼록껍질과 쿼리

문제

$N$개의 꼭짓점을 갖는 볼록다각형 $P$가 있다. $P$의 꼭짓점은 반시계 방향 순으로 $P_1$부터 $P_N$까지 번호가 매겨져 있다. 또한 $P$의 경계 위에 있지 않은 서로 다른 $M$개의 점 $Q_1,Q_2,...,Q_M$가 있다. 이때 다음 쿼리를 수행하는 프로그램을 작성해 보자.

• $i$ $j$: $P_1,P_2,...,P_N$과 $Q_i,Q_j$ 총 $N+2$개의 점에 대하여 볼록껍질을 이루는 점의 개수를 출력한다. 한 변 위에 점이 3ドル$개 이상 있는 경우, 양 끝점을 제외한 나머지 점은 포함하지 않는다.

입력

첫째 줄에 $N,ドル $M,ドル $K$가 공백으로 구분되어 주어진다. $(3\leq N \leq 30,000円$; 3ドル \leq M, K \leq 200,000円)$

다음 $N$개의 줄의 $p$번째 줄에 $P_p$의 좌표 $(x_p,y_p)$가 공백으로 구분되어 주어진다. $(-10^{6} \leq x_p,y_p \leq 10^{6};$ $N$개의 점 중 어느 세 점도 한 직선 위에 있지 않다.$)$

다음 $M$개의 줄의 $q$번째 줄에 $Q_q$의 좌표 $(x_q, y_q)$가 공백으로 구분되어 주어진다. $(-10^{6} \leq x_q,y_q \leq 10^{6})$

다음 $K$개의 줄에 쿼리 $i,j$가 공백으로 구분되어 주어진다. $(1 \leq i,j \leq m$; $i \neq j)$

입력으로 주어지는 모든 좌표는 서로 다르며, 입력으로 주어지는 모든 수는 정수이다.

출력

$Q$개의 줄에 걸쳐 각 쿼리의 결과를 순서대로 한 줄에 하나씩 출력한다.

제한

노트