Description:


给定一个凸n边形,以及它的三角剖分。再给定q个询问,每个询问是一对凸多边行上的顶点(a,b),问点a最少经过多少条边(可以是多边形上的边,也可以是剖分上的边)可以到达点b。

Input:


第一行一个整数n(n <= 50000),代表有n个点。点1,2,3,…,n是凸多边形上是顺时针排布的。

接下来n-3行,每行两个整数(x,y),代表(x,y)之间有一条剖分边。

接下来是一个整数q(q <= 100000),代表有q组询问。

接下来q行是两个整数(a,b)。

Output:


输出q行,每行一个整数代表最少边数。

Sample Input:


Sample Output:


题解:


这道题真心难,AC的人并不多 [摊手]

对这个多边形二分,类似点分治的方法,但是真的非常难写( ⊙o⊙ )

代码如下: QAQ