Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

纪念1AC 萌新水过

Posted by 18477329 at 2020-10-16 19:32:50 on Problem 2236
```#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
#define MAX_N 1005

int par[MAX_N]; //父节点
int rank[MAX_N]; //树的深度
int n,d;
typedef pair<int,int> P;
P map[MAX_N];
int used[MAX_N];
int num=0;

void init()
{
for(int i=0;i<n;i++)
{
par[i]=i;
rank[i]=0;
}
}

int find(int x)
{
if(par[x]==x)
return x;
else
return par[x]=find(par[x]);
}

bool same(int x,int y)
{
return find(x)==find(y);
}

void unite(int x,int y)
{
x=find(x);
y=find(y);
if(rank[x]<rank[y])
par[x]=y;
else
{
par[y]=x;
if(rank[x]==rank[y]) rank[x]++;
}
}

void fun(int t)  //判断要不要加入并查集
{
for(int i=0;i<num-1;i++) //最后一个是自己
{
double ans;
int x1=map[used[i]].first,x2=map[t].first;
int y1=map[used[i]].second,y2=map[t].second;
ans=sqrt(pow(x1-x2,2)+pow(y1-y2,2));
if(ans<=d)
{
unite(t,used[i]);
}
}
}

void solve()
{
int s,t;
char c;
init();
fill(used,used+n,0);
while(cin>>c)
{
if(c=='O')
{
cin>>t;
used[num]=t;
num++;
fun(t);
}
if(c=='S')
{
cin>>s>>t;
if(same(s,t))
cout<<"SUCCESS"<<endl;
else
cout<<"FAIL"<<endl;
}
}
return ;
}

int main()
{
cin>>n>>d;
for(int i=1;i<=n;i++)
{
cin>>map[i].first>>map[i].second;
}
solve();
return 0;
}```

Followed by: