并查集的简单应用
就是一点距离用平方免得浮点数
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
#define x first
#define y second
using namespace std;
const int N = 1005;
typedef pair<int, int> PII;
typedef long long ll;
PII pos[N];
bool st[N];
int p[N];
int n, m;
int find(int x) {
return x == p[x] ? x : p[x] = find(p[x]);
}
void uni(int a, int b) {
int pa = find(a), pb = find(b);
if (pa != pb) {
p[pa] = pb;
}
return;
}
bool check(int a, int b) {
/*cout << pow(abs(pos[a].x - pos[b].x), 2) +
pow(abs(pos[a].y - pos[b].y), 2) << endl;
*/
return pow(abs(pos[a].x - pos[b].x),2)+
pow(abs(pos[a].y - pos[b].y), 2)<=m;
}
int main()
{
cin >> n >> m;
m = m * m;
for (int i = 1; i <= n; i++) {
cin >> pos[i].x >> pos[i].y;
p[i] = i;
}
char op;
while (cin >> op) {
int a, b;
if (op == 'O') {
cin >> a;
st[a] = true;
for (int i = 1; i <= n; i++)
{
if (st[i]&&i!=a&&check(a,i)) {
uni(a, i);
}
}
}
else {
if (op == 'S')
{
cin >> a >> b;
int pa = find(a), pb = find(b);
if (pa == pb)puts("SUCCESS");
else puts("FAIL");
}
}
}
return 0;
}