시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2.5 초 (언어별 추가 시간 없음) 1024 MB 15 5 5 50.000%

문제

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

새로 짓는 벽은 X국 외곽의 벽의 꼭짓점 둘을 잇는 선분 형태로만 지을 수 있고, 두 개의 벽은 외곽의 벽들이 이루는 꼭짓점이 아닌 곳에서는 만날 수 없다. 준원이는 N-3개의 벽을 더 지은 다음, 모든 2N-3개의 벽 가운데에 드나들 수 있는 문을 만들 것이다. 준원이는 M개의 집을 가지고 있는데, 그는 집 M개 중 하나에 대해서, X국 바깥에서 어떤 집으로 벽을 넘지 않고 최소 개수의 문을 통해서만 들어올 때, 가장 많은 문을 지나야 하도록 벽을 짓고자 한다.

준원이가 M개의 집 중 무슨 집을 보호할 지는 아직 정하지 않았다. 그러므로 각각의 집에 대해 답을 구해 보자.

입력

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

둘째 줄부터 N개의 줄에는 X국의 외곽을 이루는 벽의 꼭짓점의 좌표를 나타내는 두 실수 xi, yi가 시계 반대방향으로 주어진다. 외곽의 벽은 [(x1, y1), (x2, y2)], [(x2, y2), (x3, y3)], ..., [(xN, yN), (x1, y1)]의 N개의 선분으로 이루어진 볼록 N각형 형태이다.

그 다음 줄에는 준원이의 집의 개수 M이 주어진다. (1 ≤ M ≤ 5,000)

그 뒤 M개의 줄에는 준원이의 집의 좌표를 나타내는 두 실수 ai, bi가 주어진다. 이 좌표는 X국 안에 있으며, 어느 두 꼭짓점을 잇는 직선 위에도 있지 않다.

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

출력

벽을 모두 지은 뒤, 바깥에서 각 집으로 갈 때 지나야 하는 문의 개수의 최댓값을 구하여 입력에서 주어진 순서대로 한 줄에 하나씩 M개의 줄에 걸쳐 출력한다.
 

예제 입력 1

6
-0.5 -1.0
0.5 -1.0
1.0 0.0
0.5 1.0
-0.5 1.0
-1.0 0.0
2
0.0 -0.2
0.0 -0.8

예제 출력 1

2
1

출처

Contest > 웰노운컵 > 제2회 웰노운컵 Day 1 B번

  • 문제를 만든 사람: junie