27656번 - 양궁

평면 위에 $N$개의 점이 있다. 남은 점이 없을 때까지 다음 시행을 반복하여 과녁을 만든다.

• 남은 점들을 모두 포함하는 가장 작은 볼록 다각형을 얻는다.
• 볼록 다각형 경계에 있는 점들을 제거한다.

한 점이 남거나 남은 점들이 한 직선 위에 있는 경우는 없다. 또한, 볼록 다각형 경계에 있는 어느 세 점도 한 직선 위에 있지 않음이 보장된다.

얻은 도형을 순서대로 $P_{1}, P_{2}, \cdots, P_{k}$라 할 때, 화살의 점수는 화살이 꽂힌 위치가 $P_{1}$ 외부이면 $0,$ $P_{1}$ 내부이면서 $P_{2}$ 외부이면 $1,$ $\cdots,$ $P_{k-1}$ 내부이면서 $P_{k}$ 외부이면 $k-1,$ $P_{k}$ 내부이면 $k$이다. 도형의 내부는 경계를 포함한다.

$Q$번 화살을 쏠 때, 각각의 점수를 구하는 프로그램을 작성하시오.

첫째 줄에 점의 개수 $N$이 주어진다. $\left(3\leq N\leq 1\,000\right)$

둘째 줄부터 $N$개의 줄에 걸쳐 각 점의 좌표를 나타내는 $-10^9$ 이상 $10^9$ 이하의 두 정수가 공백을 사이에 두고 주어진다.

그다음 줄에 화살을 쏘는 횟수 $Q$가 주어진다. $\left(1\leq Q\leq 1\,000\,000\right)$

그다음 줄부터 $Q$개의 줄에 걸쳐 화살이 꽂힌 위치의 좌표를 나타내는 $-10^9$ 이상 $10^9$ 이하의 두 정수가 공백을 사이에 두고 주어진다.

화살의 점수를 한 줄에 하나씩 출력한다.