【NOI2018模拟5】三角剖分Bsh

Description

　　给定一个正 n 边形及其三角剖分，共 2n - 3 条边 (n条多边形的边和n-3 条对角线)，每条边的长度为 1。

　　共 q 次询问，每次询问给定两个点，求它们的最短距离。

Input

　　第一行一个整数 n ，表示多边形的点数；

　　接下来 n - 3 行，每行两个整数 ui，vi，表示一条 ai 和 bi 之间的对角线；

　　接下来一行一个整数 q，表示询问个数；

　　接下来 q 行，每行两个整数 xi，yi，表示第 i 次询问的起点和终点；

Output

　　对于每一个询问输出一个整数，表示答案。

Sample Input

6

1 5

2 4

5 2

5

1 3

2 5

3 4

6 3

6 6

Sample Output

2

1

1

3

0

\(n\leq 52000,1\leq q\leq 2n\)

因为这是个平面图，我们发现，选取一条边之后可以将图分为两个部分，两个部分之间的最短路一定经过了这条边的两个端点中至少一个。

又因为这是三角剖分，所以我们可以找到中间点使得左右两边的点数非常接近。所以我们可以分治。

代码：

#include
    
     #define ll long long#define N 150000using namespace std;inline int Get() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}while('0'<=ch&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;}int n,m;struct road {    int to,nxt;}s[N<<1];int h[N],cnt;void add(int i,int j) {s[++cnt]=(road) {j,h[i]};h[i]=cnt;}#define pr pair
     
      #define mp(a,b) make_pair(a,b)bool vis[N];int dis1[N],dis2[N];queue
      
       q;void bfs(int S,int *dis) {    q.push(S);    dis[S]=0;    while(!q.empty()) {        int v=q.front();        q.pop();        for(int i=h[v];i;i=s[i].nxt) {            int to=s[i].to;            if(!vis[to]) continue ;            if(dis[to]>1e9) {                dis[to]=dis[v]+1;                q.push(to);            }        }    }}struct query {int x,y,id;};int pre[N];int ans[N];int tag1[N],tag2[N];int tim;void solve(vector
       
        V,vector
        
         E,vector
         
          Q) { if(!Q.size()) return ; if(V.size()==3) { for(int i=0;i
          
           >1; for(int i=0;i