题目大意:有n台电脑编号从1~n,都报废了,每台电脑有个坐标,如果两台电脑都是好的,他们距离小于d就能通讯了。有两种操作,O x表示修x号电脑,S x1 x2表示问你x1和x2能不能间接或直接的取得通讯。
解题思路:O和0傻傻分不清。。。并查集解,每修好一台电脑,就去尝试找可以通讯的电脑(同样未报废)。pre[i]=0表示电脑报废的。
ac代码:
#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
int n, d, a[505], temp, pre[1005], t1, t2;
char ch[10];
struct node{int x;int y;
}point[1005];
bool dis(int u, int v)
{double a=pow(1.0*(point[u].x-point[v].x), 2) + pow(1.0*(point[u].y-point[v].y), 2);a = sqrt(a);
return a <= d;
}
int find(int x)
{int r=x, temp;while (r != pre[r])r = pre[r];while (r != x){temp = pre[x];pre[x] = r;x = temp;}
return r;
}
void join(int x)
{for (int i=1; i<=n; i++)if (pre[i] && i != x && dis(i, x) && find(i) != find(x))pre[ find(i) ] = find(x);
}
int main()
{while (scanf("%d%d", &n, &d)!=EOF){for (int i=1; i<=n; i++)scanf("%d%d", &point[i].x, &point[i].y);getchar();memset(pre, 0, sizeof(pre));while (gets(ch)){if (ch[0] == 'O'){sscanf(ch, "O %d", &temp);pre[temp] = temp;join(temp); }else{sscanf(ch, "S %d %d", &t1, &t2);if (find(t1) == find(t2))printf("SUCCESS\n");elseprintf("FAIL\n"); }}}
return 0;
}