| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
纪念1AC 萌新水过#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: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator