Easy Shortest Path Problem

Farmer John's ranch is unusually shaped. There are N stakes forming a convex polygon, and for each pair of stakes, a rope connects the two stakes with a straight segment. The ropes are tall, so cows find it hard to cross them. Alice and Bessie are best friends, but Farmer John has separated them, so they are now far apart. The figure above shows one example with N=4. There are 6 ropes in total. Alice wants to visit Bessie. Crossing a rope is not easy, so she wants to cross as few ropes as possible. In the case shown in the figure above, crossing 2 ropes is optimal. Farmer John often changes the positions of the two cows, so for each of Q position pairs, find the minimum number of ropes that must be crossed. Help Alice and Bessie solve this. Crossing at a point where two or more ropes intersect does not count as crossing them all at once. For example, crossing through a point where 3 ropes intersect counts as 3 crossings. Crossing the same rope several times counts each time.

The first line contains N (3 ≤ N ≤ 5,000), the number of stakes. The next N lines each contain two integers x and y, the coordinates of a stake. The stakes are given in counterclockwise order. The line after them contains Q (1 ≤ Q ≤ 10,000), the number of queries. Each of the next Q lines contains four integers x1, y1, x2, y2. (x1, y1) is Alice's coordinate and (x2, y2) is Bessie's coordinate. All coordinates have absolute values at most 10^8. The N stakes form a convex polygon with every interior angle less than 180 degrees. The cows' positions never lie on a rope. For each query, the N stakes and the two cows all have distinct coordinates.

For each query, print the minimum number of ropes that must be crossed on its own line, in the order the queries are given.