题解：P6376 [PA 2010] The Goat

· · 题解

数 ❤ 值 ❤ 积 ❤ 分 ❤ 真 ❤ 是 ❤ 杂 ❤ 鱼 ❤ 呢

对于平面上的某个点 P，设有 m 个圆包含它，那么 k 次操作后 P 至少被覆盖一次的概率即为 f(m)=1-\left(1-\dfrac mn\right)^k，面积并的期望即为概率对整个平面的二重积分。

设平面上至少被 m 个圆覆盖的面积为 W_m，那么答案即为 E=\displaystyle\sum_{m=1}^n(f(m)-f(m-1))W_m，考虑如何算出 W_m。根据格林公式，区域面积 A 可以通过其正向边界 \partial A 的线积分求得：

A=\frac 12\oint_{\partial A}(x\text dy-y\text dx)

而区域 W_m 的边界是由被其它圆包含 m-1 次的圆弧构成的，因此枚举每个圆上的每段圆弧，用格林公式对其积分，乘上对应的系数累加到答案里即可，注意一些边界的情况。

时间复杂度为 \mathcal O(n^2\log n)。

#include <bits/stdc++.h>
using namespace std;
#define il inline
const int N = 1e3 + 5; const double pi = acos(-1);
double x[N], y[N], f[N], g[N], e;
il double qpow(double a, int b) { double c = 1; while (b) { if (b & 1) c *= a; a *= a, b >>= 1; } return c; }
int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n, k; double r; cin >> n >> k >> r;
    for (int i = 1; i <= n; i++) cin >> x[i] >> y[i], f[i] = 1 - qpow(1 - (double)i / n, k);
    for (int i = 0; i < n; i++) g[i] = f[i + 1] - f[i];
    for (int i = 1; i <= n; i++) {
        typedef pair<double, int> node;
        basic_string<node> v; int c = 0; v += {pi, 0};
        for (int j = 1; j <= n; j++) if (i ^ j) {
            if (x[i] == x[j] && y[i] == y[j]) { c += j > i; continue; }
            double dx = x[j] - x[i], dy = y[j] - y[i], d = hypot(dx, dy); if (d >= 2 * r) continue;
            double t = atan2(dy, dx), dt = acos(d / (2 * r)), l = t - dt, r = t + dt;
            if (l <= -pi) c++, v += {r, -1}, v += {l + 2 * pi, 1};
            else if (r > pi) c++, v += {r - 2 * pi, -1}, v += {l, 1};
            else v += {l, 1}, v += {r, -1};
        } sort(v.begin(), v.end(), [](const node &a, const node &b) { return a.first < b.first; });
        auto H = [&](double t) -> double { return (r * r * t + r * x[i] * sin(t) - r * y[i] * cos(t)) * 0.5; };
        int cc = c; double ct = -pi, cs = 0;
        for (auto [t, w] : v) { if (cc >= 0 && cc < n) cs += g[cc] * (H(t) - H(ct)); ct = t, cc += w; } e += cs;
    } cout << fixed << setprecision(15) << e;
}