题解 P3844 【[TJOI2007]圆】

ikka · 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;
}