【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<bits/stdc++.h>
#define ll long long
#define N 150000
using 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<int,int>
#define mp(a,b) make_pair(a,b)
bool vis[N];
int dis1[N],dis2[N];
queue<int>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<int>V,vector<pr>E,vector<query>Q) {
if(!Q.size()) return ;
if(V.size()==3) {
for(int i=0;i<Q.size();i++) {
int x=Q[i].x,y=Q[i].y;
if(x==y) ans[Q[i].id]=0;
else ans[Q[i].id]=1;
}
return ;
}
int n=V.size(),m=E.size();
int mid=(n-2)>>1;
for(int i=0;i<n;i++) pre[V[i]]=0;
pre[V[0]]=1;
for(int i=1;i<n;i++) pre[V[i]]=pre[V[i-1]]+1;
int id;
int X=0,Y=0;
int MN=1e9;
for(int i=0;i<m;i++) {
int x=E[i].first,y=E[i].second;
int now=pre[y]-pre[x]-1;
if(max(now,n-2-now)<MN) {
MN=max(now,n-2-now);
X=x,Y=y;
}
}
vector<int>v1,v2;
vector<pr>e1,e2;
vector<query>q1,q2;
v1.clear(),e1.clear(),q1.clear();
v2.clear(),e2.clear(),q2.clear();
for(int i=0;i<n;i++) {
if(X<=V[i]&&V[i]<=Y) tag1[V[i]]=1;
if(V[i]>=Y||V[i]<=X) tag2[V[i]]=1;
}
for(int i=0;i<n;i++) {
if(tag1[V[i]]) v1.push_back(V[i]);
if(tag2[V[i]]) v2.push_back(V[i]);
}
for(int i=0;i<m;i++) {
int x=E[i].first,y=E[i].second;
if(tag1[x]&&tag1[y]) e1.push_back(E[i]);
if(tag2[x]&&tag2[y]) e2.push_back(E[i]);
}
for(int i=0;i<Q.size();i++) {
if(tag1[Q[i].x]&&tag1[Q[i].y]) q1.push_back(Q[i]);
if(tag2[Q[i].x]&&tag2[Q[i].y]) q2.push_back(Q[i]);
}
for(int i=0;i<n;i++) {
dis1[V[i]]=dis2[V[i]]=1e9+7;
vis[V[i]]=1;
}
bfs(X,dis1);
bfs(Y,dis2);
for(int i=0;i<Q.size();i++) {
int x=Q[i].x,y=Q[i].y,id=Q[i].id;
ans[id]=min(ans[id],dis1[x]+dis1[y]);
ans[id]=min(ans[id],dis2[x]+dis2[y]);
ans[id]=min(ans[id],dis1[x]+dis2[y]+1);
ans[id]=min(ans[id],dis2[x]+dis1[y]+1);
}
for(int i=0;i<n;i++) tag1[V[i]]=tag2[V[i]]=vis[V[i]]=0;
solve(v1,e1,q1),solve(v2,e2,q2);
}
vector<int>V;
vector<pr>E;
vector<query>Q;
int main() {
n=Get();
for(int i=1;i<n;i++) add(i,i+1),add(i+1,i);
add(1,n),add(n,1);
for(int i=1;i<=n-3;i++) {
int x=Get(),y=Get();
add(x,y),add(y,x);
if(x>y) swap(x,y);
E.push_back(mp(x,y));
}
memset(ans,0x3f,sizeof(ans));
for(int i=1;i<=n;i++) V.push_back(i);
m=Get();
for(int i=1;i<=m;i++) {
int x=Get(),y=Get();
if(x>y) swap(x,y);
Q.push_back((query) {x,y,i});
}
solve(V,E,Q);
for(int i=1;i<=m;i++) cout<<ans[i]<<"\n";
return 0;
}