解题思路:这是并查集的应用,如果是O就合并,else就查询,需要注意的是join有个条件,就是在d的距离之内才可以!!!
AC代码:
#include<iostream> #include<cstdio> #include<cstring> using namespace std; #define N 1110 int d; bool used[N]; struct node { int pre,x,y; }p[N]; int find(int x) { return x==p[x].pre?x:find(p[x].pre); } void join(const node p1,const node p2) { int root1,root2; root1=find(p1.pre); root2=find(p2.pre); if (root1!=root2) { if ((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y)<=d*d) { p[root2].pre=root1; } } } int main() { int num; int ok; int from,to; cin>>num>>d; for (int i=1;i<=num;i++) { p[i].pre=i; } memset(used,0,sizeof(used)); for (int i=1;i<=num;i++) { cin>>p[i].x>>p[i].y; } string ope; while(cin>>ope) { if (ope=="O") { cin>>ok; used[ok]=true; for (int i=1;i<=num;i++) { if (used[i]&&i!=ok) join(p[i],p[ok]); } }else { scanf("%d%d", &from, &to); if(find(from) == find(to)) printf("SUCCESS "); else printf("FAIL "); } } return 0; }