16215번 - Build a Wall!

X국의 훌륭한 지도자 규민의 후임자로 새로 집권한 준원은 X국 안에 벽을 세우기로 한다. X국의 외곽에는 볼록 N각형 모양의 벽이 세워져 있다. 그럼에도 준원은 X국 안에 새로 건설할 본인의 자택을 보호하기 위해 X국 안에 추가로 벽을 설치하려 한다.

새로 짓는 벽은 X국 외곽에 있는 벽의 꼭짓점 둘을 잇는 선분 형태로만 지을 수 있다. 두 개의 벽은 끝 점이 아닌 위치에서 교차할 수 없다. 준원은 추가로 N-3개의 벽을 설치할 예정이다. 또한, 준원은 새로 건설할 자택의 후보지 Q개를 정해두었다. 각 후보지에 대해, 준원은 다음과 같은 의문을 해결하려 한다.

준원은 N-3개의 벽을 적절히 설치해서 X국의 바깥에서 이 후보지로 들어가기 위해 최소한 넘어야 하는 벽의 개수를 최대한 크게 만들려 한다. 이 때, 최소한 넘어야 하는 벽의 개수의 최댓값을 알고 싶다.

각 후보지에 대해서 준원이의 질문의 답을 구해 보자.

첫째 줄에는 양의 정수 N이 주어진다. (3 ≤ N ≤ 5,000)

이후 N개의 줄에는 X국의 외곽을 이루는 벽의 꼭짓점의 좌표를 나타내는 두 실수 x_i, y_i가 시계 반대방향으로 주어진다. 외곽의 벽은 [(x₁, y₁), (x₂, y₂)], [(x₂, y₂), (x₃, y₃)], ..., [(x_N, y_N), (x₁, y₁)]의 N개의 선분으로 이루어진 볼록 N각형 형태이다.

다음 줄에는 자택의 후보지의 개수 Q가 주어진다. (1 ≤ Q ≤ 5,000)

이후 Q개의 줄에는 각 후보지의 좌표를 나타내는 두 실수 a_i, b_i가 주어진다. 이 좌표는 X국 안에 있으며, 어느 두 꼭짓점을 잇는 직선 위에도 있지 않다.

주어지는 모든 좌표는 소숫점 여섯 자리 안으로 주어지며, 절댓값이 10⁸ 이하이다. 어떤 좌표가 10^-6 범위 안에서 바뀌어도 답이 변하지 않음이 보장된다.

Q개의 후보지에 대해, 최소한 넘어야 하는 벽의 개수의 최댓값을 순서대로 한 줄에 하나씩 출력한다.