这一题的大意：在救灾当中需要用网络，这堆人就用笔记本建了一个无线网，但是来，互相通信都是有距离限制的，一台电脑只能和距离他为d的电脑通信，然后一台电脑也可以通过几台电脑搭成线这样通信。然后就是输入每台电脑的坐标，然后准备好了的电脑，询问两台电脑是否可以连通，可以输出"SUCCESS"，不行输出"FAIL"
这一题是带有计算几何的并查集问题。还是有点小技巧的。
最开始，我想的就是把修好的电脑弄成一个集合，然后计算距离就可以了(开始没注意到还可以通过n个连接来通信，还以为最长两个呢)，但是发现多台电脑来通信非常难求距离。
然后就发现其实可以将可以通信的电脑合并成一个集合，即计算一个新来的电脑和前面修好的每台电脑的距离，如果他们距离小于d,则就将这个新电脑连到那个电脑所在的集合上，判断两台电脑能否通信，只要计算两台电脑是否在一个集合即可。
上代码：
#include<iostream> #include<cmath> using namespace std; int father[1002]; int rank[1002]; int xcor[1002]; int ycor[1002]; int map[1002][1002]; //用于记录两点距离是否可以通信 int Get_Set(int x) { if(father[x]!=x) return father[x]=Get_Set(father[x]); else return x; } void Union(int x,int y) { x=Get_Set(x); y=Get_Set(y); if(x==y) return; else{ if(rank[x]>rank[y]) father[y]=x; else{ father[x]=y; if(rank[x]==rank[y]) rank[y]++; } } } bool dist(int i,int j,int d) { if(pow(float(xcor[i]-xcor[j]),2)+pow(float(ycor[i]-ycor[j]),2)<=d*d) return true; else return false; } int main() { int N,d,i,j,k,xv,yv; scanf("%d%d",&N,&d); for(i=1;i<=N;i++) { scanf("%d%d",&xv,&yv); xcor[i]=xv; ycor[i]=yv; father[i]=-1; rank[i]=0; } memset(map,0,sizeof(map)); for(i=1;i<=N;i++) for(j=i;j<=N;j++) { if(dist(i,j,d)) { map[i][j]=map[j][i]=1; } } char oper; while(cin>>oper) { if(oper=='O') { scanf("%d",&k); father[k]=k; for(i=1;i<=N;i++) if(father[i]!=-1) { if(map[k][i]) Union(k,i); //和每个修好的电脑比较，如果可以通信就合并 } } if(oper=='S') { scanf("%d%d",&j,&k); if(Get_Set(j)==Get_Set(k)) printf("SUCCESS "); else printf("FAIL "); } } return 0; }