[SPOJ CIRUT]CIRU2

求恰好被覆盖k次的圆面积并。

如果做过圆面积并（[SPOJ CIRU]The area of the union of circles）的话，那么这题就比较简单了。参考：。主要的区别就是：

  • 原先做线段覆盖，现在改为括号匹配（压栈）。原先计算没被覆盖的面积，现在计算至少覆盖k+1次的面积area[k+1]，答案就是area[k]-area[k+1]。
  • 如果一个圆被完全包含，原先直接扔掉，现在要加上去。

代码基本不变：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93

#include <cmath>
#include <cstdio>
#include <vector>
#include <algorithm>
using std::pair;
using std::vector;

inline double sqr(const double x) { return x*x; }
inline double dist(const double x1, const double y1, const double x2, const double y2)
  { return std::sqrt(sqr(x1-x2) + sqr(y1-y2)); }
inline double angle(const double A, const double B, const double C)
  { return std::acos((sqr(A)+sqr(B)-sqr(C))/(2*A*B)); }
inline int sign(const double x)
{
  static const double EPS = 1e-8;
  if (x > EPS) return 1;
  return x < -EPS ? -1 : 0;
}
const int MAXN = 1000;
const double PI = std::acos(-1.0);
int n;
bool covered[MAXN];
double R[MAXN], A[MAXN], B[MAXN], ans[MAXN];
vector< pair<double, double> > cover;
vector< pair<double, int> > bracket;
inline double getarea(const int i, const double lef, const double rig)
{
  double res = R[i] * R[i] * (rig-lef - std::sin(rig-lef));
  const double x1 = A[i] + R[i] * std::cos(lef), y1 = B[i] + R[i] * std::sin(lef);
  const double x2 = A[i] + R[i] * std::cos(rig), y2 = B[i] + R[i] * std::sin(rig);
  return res + x1*y2 - x2*y1;
}
int main()
{
  scanf("%d", &n);
  for (int i = 0; i < n; ++i)
    scanf("%lf%lf%lf", A+i, B+i, R+i);
  for (int i = 0; i < n; ++i)
  {
    bracket.clear();
    int cover = 0;
    for (int j = 0; j < n; ++j) if (i != j)
    {
      const double d = dist(A[i], B[i], A[j], B[j]);
      if (sign(R[j]-R[i]) >= 0 && sign(d-(R[j]-R[i])) <= 0)
        { ++cover; continue; }
      else if (sign(d-(R[j]+R[i])) >= 0 || sign(d-std::abs(R[j]-R[i])) <= 0)
        continue;

      const double alpha = std::atan2(B[j]-B[i], A[j]-A[i]);
      const double beta = angle(R[i], d, R[j]);
      pair<double, double> tmp(alpha-beta, alpha+beta);
      if (sign(tmp.first) <= 0 && sign(tmp.second) <= 0)
        tmp.first += 2*PI, tmp.second += 2*PI;

      if (sign(tmp.first) < 0)
      {
        bracket.push_back(pair<double, int>(2*PI+tmp.first, 1));
        bracket.push_back(pair<double, int>(2*PI, -1));
        bracket.push_back(pair<double, int>(0, 1));
        bracket.push_back(pair<double, int>(tmp.second, -1));
      }
      else
      {
        bracket.push_back(pair<double, int>(tmp.first, 1));
        bracket.push_back(pair<double, int>(tmp.second, -1));
      }
    }

    if (bracket.empty())
    {
      const double s = 2.0 * PI * R[i] * R[i];
      ans[cover] -= s;
      ans[cover+1] += s;
      continue;
    }

    bracket.push_back(pair<double, int>(0, 0));
    bracket.push_back(pair<double, int>(2*PI, 0));
    std::sort(bracket.begin(), bracket.end());
    int stack = cover;
    for (vector< pair<double, int> >::iterator iter = bracket.begin(); iter != bracket.end()-1; ++iter)
    {
      stack += iter->second;
      const double s = getarea(i, iter->first, (iter+1)->first);
      ans[stack] -= s;
      ans[stack+1] += s;
    }
  }

  for (int i = 1; i <= n; ++i)
    printf("[%d] = %.3f\n", i, ans[i]/2.0);
}

Comments