洛谷P3297 题解

发表于
调了好久的计算几何题

感觉思维挺小清新的，除了有个神秘的 $n=0$ 的数据以外也不怎么毒瘤(?)

容易发现每两个点的分界线就是他们的中垂线。

于是就有以下思路：

1.对于每个点，枚举第二个点得到一条中垂线。这些中垂线的半平面交就是该点的势力范围。然后可以找到范围相邻的点。

2.相邻的点连边跑弗洛伊德最短路就行。

实现上有点小细节：监视点可能在矩形边界外。我们可以在求半平面交的时候发现没有势力范围直接跳过即可。

除了计算几何的板子以外的代码如下：

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
int dis[605][605],ed[605],inf=0x3f3f3f3f,stnode;
void solve(int zc){//求半平面交与加边
	sort(sg+1,sg+cnt+1,cmp);
	int hd=1,tl=0;
	que[++tl]=sg[1];
	for(int i=2;i<=cnt;i++){
		while(hd<tl&&((sg[i].t-sg[i].s)^(jd[tl-1]-sg[i].s))<=0)tl--;
		while(hd<tl&&((sg[i].t-sg[i].s)^(jd[hd]-sg[i].s))<=0)hd++;
		que[++tl]=sg[i];
		if(fabs((que[tl].t-que[tl].s)^(que[tl-1].t-que[tl-1].s))<eps){
			tl--;
			if(((que[tl].t-que[tl].s)^(sg[i].t-que[tl].s))>=0)que[tl]=sg[i];
		}
		if(hd<tl)jd[tl-1]=get_jd(que[tl],que[tl-1]);
	}
	while(hd<tl&&((que[hd].t-que[hd].s)^(jd[tl-1]-que[hd].s))<=0)tl--;
	if(hd+1>=tl)return;
	if(hd+1<tl)jd[tl]=get_jd(que[hd],que[tl]);
	for(int i=hd;i<=tl;i++){
		if(que[i].id!=-1){
			dis[zc][que[i].id]=1;
		}
		else ed[zc]=1;//该点可以作为终点，打上标记
	}
	bool chk=1;
	for(int i=hd;i<=tl;i++){
		if(((que[i].t-que[i].s)^(st-que[i].s))<0){
			chk=0;
			break;
		}
	}
	if(chk)stnode=zc;
}
double topx,topy;
signed main(){
	cin>>t;
	while(t--){
		cin>>n;
		cin>>topx>>topy>>st.x>>st.y;
		for(int i=1;i<=n;i++){
			cin>>jsd[i].x>>jsd[i].y;
			ed[i]=0;
		}
		if(!n){
			puts("0");
			continue;
		}
		memset(dis,inf,sizeof(dis));
		for(int i=1;i<=n;i++){
			cnt=0,dis[i][i]=0;
			for(int j=1;j<=n;j++){//枚举周围的点加边，注意直线是有向的！
				if(i==j)continue;
				cnt++;
				sg[cnt].s=rotate(jsd[i],mid(jsd[i],jsd[j]),pi/2);
				sg[cnt].t=rotate(jsd[j],mid(jsd[i],jsd[j]),pi/2);
				sg[cnt].id=j;
			}
			sg[++cnt].s=node{0,topy},sg[cnt].t=node{0,0},sg[cnt].id=-1;
			sg[++cnt].s=node{0,0},sg[cnt].t=node{topx,0},sg[cnt].id=-1;
			sg[++cnt].s=node{topx,topy},sg[cnt].t=node{0,topy},sg[cnt].id=-1;
			sg[++cnt].s=node{topx,0},sg[cnt].t=node{topx,topy},sg[cnt].id=-1;
			solve(i);
		}
		for(int k=1;k<=n;k++){
			for(int i=1;i<=n;i++){
				for(int j=1;j<=n;j++){
					dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);//Floyd最短路
				}
			}
		}
		int ans=inf;
		for(int i=1;i<=n;i++){
			if(ed[i])ans=min(ans,dis[stnode][i]+1);
		}
		cout<<ans<<endl;
	}
	return 0;
}