题意是发生了地震把电脑都震坏了,然后要修复这些电脑,先输入n,d,表示有编号为1-n的这么多电脑,d表示两台电脑的距离不大于d时可以连接,然后输入n行x,y,表示编号为1-n的电脑的坐标,然后输入'O'或'S',当输入'O'以后再输入m,表示编号为m的电脑修好了,输入'S'后在输入a,b,表示询问a和b能否成功连接,能的话输出SUCCESS,否则FAIL。
思路是当输入为'O'的时候,然后标记一下这个点,然后遍历1-n,如果第i台电脑已经修好了,而且他们两个距离也小于d就把他们连起来。并查集不懂的可以看下这篇博客传送门。
AC代码:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
const int MAXN = 1005;
int pre[MAXN];
struct Node{
double x,y;
}Edge[MAXN];
bool vis[MAXN];
int n,d,m;
char ch;
double dist(Node a,Node b){
double temp = (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
return sqrt(temp);
}
void init(){
for(int i=1;i<=n;i++){
pre[i] = i;
}
}
int Find(int x){
if(x != pre[x]){
pre[x] = Find(pre[x]);
}
return pre[x];
}
void merge(int x,int y){
int fx = Find(x);
int fy = Find(y);
if(fx != fy && dist(Edge[x],Edge[y]) <= d){
pre[fy] = fx;
}
}
int main()
{
memset(vis,0,sizeof(vis));
scanf("%d%d",&n,&d);
init();
for(int i=1;i<=n;i++){
scanf("%lf%lf",&Edge[i].x,&Edge[i].y);
}
while(cin>>ch){ // 用cin比scanf方便
if(ch == 'O'){
scanf("%d",&m);
vis[m] = 1;
for(int i=1;i<=n;i++){
if(vis[i] && i != m){
merge(m,i);
}
}
}
else{
int a,b;
scanf("%d%d",&a,&b);
if(Find(a) == Find(b)){
printf("SUCCESS\n");
}
else{
printf("FAIL\n");
}
}
}
return 0;
}