关于刚才ABC的D
  • 板块学术版
  • 楼主迟暮天复明心華
  • 当前回复11
  • 已保存回复11
  • 发布时间2022/7/9 21:43
  • 上次更新2023/10/27 21:18:31
查看原帖
关于刚才ABC的D
222865
迟暮天复明心華楼主2022/7/9 21:43

用并查集维护,一直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;
}
2022/7/9 21:43
加载中...