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