题目大意:
Wireless Network
在二维平面上,给你n个点,和一个距离d
O+数字表示激活该台电脑
S+数字+数字,表示连通两台电脑,在d距离之内就能连通,能连通输出SUCCESS,不行就输出FAIL
思路:
每次有电脑被激活的时候,就遍历一次可以连接到的电脑,对于同一个集合(即连接了的电脑)使用并查集维护一下就可以了
AC Code:
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
#define endl '\n'
#define INF 0x3f3f3f3f
#define int long long
// #define TDS_ACM_LOCAL
const int N=1e3+9;
int n, d, idx1, idx2;
int fa[N];
char s;
struct node{
int x, y;
bool flag;
}a[N];
int dis(node a, node b){
return (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y);
}
int find(int u){
if(fa[u]==u) return u;
return fa[u]=find(fa[u]);
}
void link(int q){
int now=find(q);
for(int i=1; i<=n; i++){
if(a[i].flag && dis(a[q],a[i])<=d*d){
int next=find(i);
fa[next]=now;
}
}
return ;
}
void solve(){
cin>>n>>d;
for(int i=1; i<=n; i++) fa[i]=i;
for(int i=1; i<=n; i++){
cin>>a[i].x>>a[i].y;
a[i].flag=false;
}
while(cin>>s){
if(s=='O'){
cin>>idx1;
a[idx1].flag=true;
link(idx1);
}
else{
cin>>idx1>>idx2;
if(find(idx1)==find(idx2)) cout<<"SUCCESS"<<endl;
else cout<<"FAIL"<<endl;
}
}
return ;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
#ifdef TDS_ACM_LOCAL
freopen("D:\\VS code\\.vscode\\testall\\in.txt", "r", stdin);
freopen("D:\\VS code\\.vscode\\testall\\out.txt", "w", stdout);
#endif
solve();
return 0;
}
Comments | NOTHING