「bzoj4449」「Neerc2015」Distance on Triangulation / 「NOI2018模拟5」 三角剖分Bsh - 分治+最短路 | Bill Yang's Blog

「bzoj4449」「Neerc2015」Distance on Triangulation / 「NOI2018模拟5」 三角剖分Bsh - 分治+最短路

题目大意

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


题目分析

本题有两种方法:

  • 边分治+最短路
  • 对偶图+点分治

似乎第二种实现起来方便些。
然而我智障的写了第一种。

每次找到一个将点分割的最平均的对角线,沿着它分割点、边、询问。
计算所有当前范围的点到对角线两点的最短距离(两次BFS)。
用最短距离更新当前范围内的询问。

建议不要看我的代码,因为我写的相当的丑(比如必须先分治右边,且数组要开大一些,因为每层的点可能同时分到儿子结点的两层)。


代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#include<bits/stdc++.h>
using namespace std;
inline int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(!isdigit(x)) {if(x=='-')bj=-1;x=getchar();}
while(isdigit(x)) {num=num*10+x-'0';x=getchar();}
return num*bj;
}
const int maxn=110005;
struct Edge {int from,to;} edge[maxn],le[maxn],re[maxn];
struct Query {int x,y,id;} q[maxn<<1],lq[maxn<<1],rq[maxn<<1];
vector<int> edges[maxn];
int p[maxn],lp[maxn],rp[maxn];
void Bfs(int s,int pl,int pr,int *dist) {
queue<int> Q;
for(int i=pl; i<=pr; i++)dist[p[i]]=INT_MAX/2;
Q.push(s);
dist[s]=0;
while(!Q.empty()) {
int Now=Q.front();
Q.pop();
for(int Next:edges[Now]) {
if(!binary_search(p+pl,p+pr+1,Next))continue;
if(dist[Next]==INT_MAX/2) {
dist[Next]=dist[Now]+1;
Q.push(Next);
}
}
}
}
int dist1[maxn],dist2[maxn],ans[maxn];
void Binary(int xl,int xr,int pl,int pr,int ql,int qr) {
if(xl>xr||pl>pr||ql>qr)return;
int Min=INT_MAX/2,pos=0,len=pr-pl+1;
for(int i=xl; i<=xr; i++) {
int px=lower_bound(p+pl,p+pr+1,edge[i].from)-p-(pl-1),py=lower_bound(p+pl,p+pr+1,edge[i].to)-p-(pl-1);
if(px>py)swap(px,py);
if(max(py-px,px+len-py)<Min) {Min=max(py-px,px+len-py);pos=i;}
}
Bfs(edge[pos].from,pl,pr,dist1);
Bfs(edge[pos].to,pl,pr,dist2);
int lqpos=0,rqpos=0;
for(int i=ql; i<=qr; i++) { //询问
if(q[i].x==edge[pos].from&&q[i].y==edge[pos].to) {ans[q[i].id]=1;continue;}
ans[q[i].id]=min({ans[q[i].id],dist1[q[i].x]+dist1[q[i].y],dist2[q[i].x]+dist2[q[i].y],dist1[q[i].x]+1+dist2[q[i].y],dist1[q[i].y]+1+dist2[q[i].x]});
if(q[i].x>edge[pos].from&&q[i].y<edge[pos].to)lq[++lqpos]=q[i];
if((q[i].x<edge[pos].from||q[i].x>edge[pos].to)&&(q[i].y<edge[pos].from||q[i].y>edge[pos].to))rq[++rqpos]=q[i];
}
for(int i=1; i<=lqpos; i++)q[ql+i-1]=lq[i];
for(int i=1; i<=rqpos; i++)q[ql+lqpos+i-1]=rq[i];
int lppos=0,rppos=0;
for(int i=pl; i<=pr; i++) { //点
if(p[i]>=edge[pos].from&&p[i]<=edge[pos].to)lp[++lppos]=p[i];
if(p[i]<=edge[pos].from||p[i]>=edge[pos].to)rp[++rppos]=p[i];
}
for(int i=1; i<=lppos; i++)p[pl+i-1]=lp[i];
for(int i=1; i<=rppos; i++)p[pl+lppos+i-1]=rp[i];
int lepos=0,repos=0;
for(int i=xl; i<=xr; i++)if(i!=pos) { //剖分边
if(edge[i].from>=edge[pos].from&&edge[i].from<=edge[pos].to&&edge[i].to>=edge[pos].from&&edge[i].to<=edge[pos].to)le[++lepos]=edge[i];
else re[++repos]=edge[i];
}
for(int i=1; i<=lepos; i++)edge[xl+i-1]=le[i];
for(int i=1; i<=repos; i++)edge[xl+lepos+i-1]=re[i];
Binary(xl+lepos,xl+lepos+repos-1,pl+lppos,pl+lppos+rppos-1,ql+lqpos,ql+lqpos+rqpos-1);
Binary(xl,xl+lepos-1,pl,pl+lppos-1,ql,ql+lqpos-1);
}
int n,m;
int main() {
n=Get_Int();
for(int i=1; i<=n-3; i++) {
int x=Get_Int(),y=Get_Int();
if(x>y)swap(x,y);
edge[i]=(Edge) {x,y};
edges[x].push_back(y);
edges[y].push_back(x);
}
for(int i=1; i<n; i++)edges[i].push_back(i+1),edges[i+1].push_back(i);
edges[1].push_back(n),edges[n].push_back(1);
m=Get_Int();
for(int i=1; i<=m; i++) {
q[i].x=Get_Int();
q[i].y=Get_Int();
if(q[i].x>q[i].y)swap(q[i].x,q[i].y);
ans[i]=min(q[i].y-q[i].x,q[i].x+n-q[i].y);
q[i].id=i;
}
for(int i=1; i<=n; i++)p[i]=i;
Binary(1,n-3,1,n,1,m);
for(int i=1; i<=m; i++)printf("%d\n",ans[i]);
return 0;
}
0%