求助
  • 板块灌水区
  • 楼主Kingna
  • 当前回复3
  • 已保存回复3
  • 发布时间2022/8/5 16:19
  • 上次更新2023/10/27 16:52:55
查看原帖
求助
411727
Kingna楼主2022/8/5 16:19

这个代码在本地过得去样例,但是atcoder上居然连样例都RE了,这是为什么?

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int N = 6005; 
int n, sx, sy, tx, ty;
int x[N], y[N], r[N], p[N];

int find(int x) {
	if (p[x] != x) p[x] = find(p[x]);
	return p[x];
}

int merge(int x, int y) {
	int f1 = find(x), f2 = find(y);
	if (f1 != f2)  p[f1] = f2;
}

signed main() {
	cin >> n >> sx >> sy >> tx >> ty;
	for (int i = 1; i <= n; i++) cin >> x[i] >> y[i] >> r[i];
	// (x - a) ^ 2 + (y - b) ^ 2 = r ^ 2
	for (int i = 0; i <= n + 1; i++) p[i] = i;
	int idx, idy;
	for (int i = 1; i <= n; i++) {
		if ((sx - x[i]) * (sx - x[i]) + (sy - y[i]) * (sy - y[i]) == r[i] * r[i]) {
			merge(0, i);
			idx = i;
		}
		if ((tx - x[i]) * (tx - x[i]) + (ty - y[i]) * (ty - y[i]) == r[i] * r[i]) {
			merge(n + 1, i);
			idy = i;
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = i + 1; j <= n; j++) {
			int d = (x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]);
			if (d > (r[i] + r[j]) * (r[i] + r[j]) || d < (r[i] - r[j]) * (r[i] - r[j])) continue;
			if (i == idx) merge(0, j);
			else if (j == idx) merge(i, 0);
			else if (i == idy) merge(n + 1, j);
			else if (j == idy) merge(i, n + 1);
			else merge(i, j);
		}
	}
	if (find(0) == find(n + 1)) puts("Yes");
	else puts("No"); 
}
2022/8/5 16:19
加载中...