POJ2236 Wireless Network 并查集

时间:2022-11-17 18:40:18

水题

#include<cstdio>
#include<cstring>
#include<queue>
#include<set>
#include<cstdlib>
#include<algorithm>
#include<vector>
#include<cmath>
using namespace std;
typedef long long LL;
typedef pair<int,int>pii;
const int N=1e3+;
const int INF=0x3f3f3f3f;
pii o[N];
bool vis[N];
int fa[N];
int find(int x){
return fa[x]==x?x:fa[x]=find(fa[x]);
}
int dis(int i,int j){
return (o[i].first-o[j].first)*(o[i].first-o[j].first)+(o[i].second-o[j].second)*(o[i].second-o[j].second);
}
int main(){
int n,d,x,y;
scanf("%d%d",&n,&d);
for(int i=;i<=n;++i)
scanf("%d%d",&o[i].first,&o[i].second),fa[i]=i;
char s[];
while(~scanf("%s",s)){
if(s[]=='O'){
scanf("%d",&x);
if(vis[x])continue;
for(int i=;i<=n;++i){
if(!vis[i]||dis(x,i)>d*d)continue;
int u=find(x),v=find(i);
if(u!=v)fa[u]=v;
}
vis[x]=true;
}
else {
scanf("%d%d",&x,&y);
x=find(x),y=find(y);
if(x==y)printf("SUCCESS\n");
else printf("FAIL\n");
}
}
return ;
}