POJ - 2236 Wireless Network 并查集模版浮点数精度

本文主要是介绍POJ - 2236 Wireless Network 并查集模版浮点数精度，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接

POJ-2236

题意

给出n个电脑的坐标和d，距离在d以内的可以互相通信，现在电脑全部坏掉了，给出多个指令，维修某个电脑或者询问两个电脑是否能联通。

思路

裸的并查集，每次维修电脑后遍历每个结点，将可以通信的加入并查集。注意两点

只有被维修过的节点才能通信，所以维护一个bool数组记录
d和坐标都是整数，比较距离直接使用平方比较，开方转为浮点数会损失精度，可能导致WA

代码

#include<iostream>  
#include<cmath>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl "\n"
using namespace std;typedef long long ll;const int maxn=1005;const int inf=0x3f3f3f3f;int fa[maxn*3];int ra[maxn];bool bl[maxn];//是否维修过 int n,d;void init(){for(int i=0;i<maxn;i++){fa[i]=i;ra[i]=0; }return ;}int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}void unite(int x,int y){x=find(x); y=find(y);if(x==y)return ;else if(ra[x]<ra[y]){fa[x]=y;} else{fa[y]=x;if(ra[x]==ra[y])ra[x]++;}}//存放点坐标 struct Node{int x,y;}node[maxn];//判断两点距离 bool ju(int i,int j){if((node[i].x-node[j].x)*(node[i].x-node[j].x)+(node[i].y-node[j].y)*(node[i].y-node[j].y)<=d*d)return 1;return 0;}int main(){IOSinit();cin>>n>>d;for(int i=1;i<=n;i++)cin>>node[i].x>>node[i].y;char ch;while(cin>>ch){if(ch==' '||ch=='\n')cin>>ch;if(ch=='O'){int t;cin>>t;bl[t]=1;int fa=find(t);for(int i=1;i<=n;i++){if(bl[i]&&find(i)!=fa&&ju(t,i))unite(t,i);}}else{int t1,t2;cin>>t1>>t2;if(find(t1)==find(t2))cout<<"SUCCESS"<<endl;elsecout<<"FAIL"<<endl;}}		}