自动搬运

查看原文

来自洛谷，原作者为

	ikka 菜

搬运于2025-08-24 21:53:19，当前版本为作者最后更新于2018-10-13 08:20:33，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

可以发现，画圆的顺序对答案并没有影响，所以我们可以考虑按照圆的半径排序。

对于每一个圆$X$，找到半径最小的圆$Y$，使得圆$X$在圆$Y$内部，然后根据圆$Y$的颜色确定圆$X$的颜色并计算对答案的贡献。

时间复杂度$O(n^{2})$，对于这题数据随便跑就好。

#include <bits/stdc++.h>
const int maxn = 111;
const double pi = acos(-1);

struct cir {
  int x, y, r;   // 坐标和半径
  int c;     // 颜色
  inline bool operator < (cir const &rhs) const {
    return this -> r > rhs.r;
  }      // 重载<便于排序
} c[maxn];

template<typename T> T inline sqr(T x) {
  return x * x;
}      // 平方

double inline eucdis(cir x, cir y) {
  return sqrt(sqr(x.x - y.x) + sqr(x.y - y.y));
}      // 欧几里得距离

bool inline isincir(cir x, cir y) {
  return eucdis(x, y) < x.r + y.r;
}      // 根据题目性质没有圆相交，判断x是否在y内。

int main() {
  int n;
  static int ans;
  scanf("%d", &n);
  c[0] = (cir) { 0, 0, 10000, 1 };
  for (int i = 1; i <= n; ++i) scanf("%d%d%d", &c[i].x, &c[i].y, &c[i].r);
  std::sort(c + 1, c + n + 1);
  for (int i = 1; i <= n; ++i) {
    for (int j = i - 1; ~j; --j) {
      if (isincir(c[i], c[j])) {
        c[i].c = -c[j].c;
        // 确定圆的颜色
        ans += c[j].c * sqr(c[i].r);
        // 计算对答案的贡献
        break;
      }
    }
  }
  printf("%.2lf\n", pi * ans);
  return 0;
}