15939번 - 쉬운 최단경로 문제

농부 John의 목장은 특이하게 생겼다. 볼록 다각형을 이루는 N개의 말뚝이 있고, 각 말뚝 쌍에 대해 두 말뚝을 선분으로 잇는 밧줄이 존재한다. 이 밧줄은 높이가 상당해서 소들이 넘어 다니기 어렵다.

소 Alice와 Bessie는 서로의 가장 친한 친구이다. 하지만 농부 John이 그들을 떨어뜨려 놓았기 때문에 현재는 멀리 위치해 있다.

위 그림은 N=4일때의 한 예를 그림으로 나타낸 것이다. 총 6개의 밧줄이 존재한다.

Alice는 Bessie가 있는 곳으로 놀러 가려고 한다. 하지만 밧줄을 넘는 것은 쉽지 않기 때문에, 넘는 밧줄의 개수를 최소로 하여 가려고 한다.

위 그림의 경우, 밧줄을 2번 넘어서 가는 것이 최적임을 알 수 있다.

농부 John이 두 소의 위치를 자주 바꾸기 때문에, Q개의 위치 쌍에 대해 각각의 경우 넘어야 하는 밧줄의 최소 개수를 구하고자 한다. Alice와 Bessie를 도와 문제를 해결해주자.

두 개 이상의 밧줄이 교차하는 점을 통해 넘어가는 것은 한꺼번에 넘은 것으로 인정되지 않는다. 예를 들어 3개 밧줄이 교차하는 점을 통해 한꺼번에 넘어도 3번으로 센다. 또한, 같은 밧줄을 여러 번 넘는 것은 여러 번 센다.

첫 번째 줄에 말뚝의 수 N(3 ≤ N ≤ 5,000)이 주어진다. 두 번째 줄부터 N개의 줄에는 2개의 정수 x와 y가 주어진다. 이는 말뚝들의 좌표를 나타낸다. 말뚝의 정보는 반시계방향 순서대로 주어진다.

N+2번째 줄에 쿼리의 개수 Q(1 ≤ Q ≤ 10,000)가 주어진다. N+3번째 줄부터 Q개의 줄에는 4개의 정수 x1, y1, x2, y2가 주어진다. (x1, y1)은 Alice의 좌표를, (x2, y2)은 Bessie의 좌표를 나타낸다.

주어지는 모든 좌표의 절댓값은 10⁸ 이하이다.

N개의 말뚝은 내각이 180도 미만인 볼록 다각형을 이루고 있으며, 주어지는 소들의 위치는 밧줄 위에 있지 않다. 또한, 각 쿼리에 대해 N개의 말뚝 및 두 소의 좌표는 서로 다르다.

쿼리가 주어진 순서대로 Q개의 줄에 걸쳐 각 줄에 그 쿼리에 대한 답을 출력한다.