用并查集维护,一直WA两个点。调eps无效。代码:
int n;
int fa[6010];
std::vector<int> cs, ce;
struct circ {
double x, y, r;
} c[6010];
int find(int u) {
return u == fa[u] ? u : fa[u] = find(fa[u]);
}
void merge(int u, int v) {
u = find(u);
v = find(v);
if(u != v) fa[u] = v;
}
double sq(double u) {
return u * u;
}
double dis(double cx, double cy, double ex, double ey) {
return sqrt(sq(cx - ex) + sq(cy - ey));
}
signed main() {
read(n);
double sx, sy, ex, ey;
scanf("%lf %lf %lf %lf", &sx, &sy, &ex, &ey);
rep(i, 1, n + 1) {
fa[i] = i;
scanf("%lf%lf%lf", &c[i].x, &c[i].y, &c[i].r);
double D = dis(c[i].x, c[i].y, sx, sy);
if(fabs(D - c[i].r) < 1e-18) cs.push_back(i);
D = dis(c[i].x, c[i].y, ex, ey);
if(fabs(D - c[i].r) < 1e-18) ce.push_back(i);
}
rep(i, 1, n + 1) rep(j, 1, n + 1) {
double D = dis(c[i].x, c[i].y, c[j].x, c[j].y);
if(D - (c[i].r * 1.0 + c[j].r) < 1e-18 && D - abs(c[i].r * 1.0 - c[j].r) > -1e-18) merge(i, j);
}
for(int i : cs) for(int j : ce) {
if(find(i) == find(j) || i == j) {
puts("Yes");
goto end;
}
}
puts("No");
return 0;
}