Luogu

分析

首先考虑给你两个圆怎么算交的面积。

设两圆心距离为 $d$，可以算出交弦所对的圆心角 $\theta = 2\arccos \frac{d}{2r}$，然后两个扇形的面积为 $\theta r^2$、菱形的面积为 $\sin\theta r^2$，因此交面积为 $(\theta - \sin\theta)r^2$。

考虑 DP。设 $f_{i, j}$ 表示前 $i$ 个圆选了 $j$ 个的最大面积，$S_0 = \pi r^2$，$s(j, i)$ 为圆 $i, j$ 的交面积，那么有转移
$$
f_{i, k} = \max\left\{f_{i, k - 1}, \max_{j < i}\left\{f_{j, k - 1} + S_0 - s(j, i)\right\}\right\}
$$
这样子是 $\mathcal{O}(n^2k)$ 的。

可以证明 $s(j, i)$ 满足四边形不等式，因此这个 DP 每层具有决策单调性，即 $p_{i - 1, k} \leq p_{i, k}$。这样子就可以优化到 $\mathcal{O}(nk\log n)$。

根据这篇文章我们可以知道这个 DP 是凸的，因此可以直接套一个 WQS 二分，变为每选一个就会付出 $mid$ 的额外代价。并且这仍然满足决策单调性，因此可以做到 $\mathcal{O}(n\log n\log \epsilon^{-1})$。

一个优化：注意到 $s(j, i) \neq 0$ 的不同的 $d$ 只有 $\mathcal{O}(r)$ 个，可以把这些值全部预处理出来，能够有效地减小常数。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)
#define debug(...) fprintf(stderr, __VA_ARGS__)
using namespace std;
typedef long long ll;

int read() {
    int X = 0, w = 1; char c = getchar();
    while (c < '0' || c > '9') { if (c == '-') w = -1; c = getchar(); }
    while (c >= '0' && c <= '9') X = X * 10 + c - '0', c = getchar();
    return X * w;
}

const int N = 100000 + 10;

int n, k, r, x[N];
double S0, o[N];
int Q[N], h, t, p[N];
pair<double, int> f[N];

double s(int j, int i) {
    int d = x[i] - x[j];
    return d >= 2 * r ? 0 : o[d];
}

int find(int i, int j) {
    int L = j, R = n + 1;
    while (L < R) {
        int mid = (L + R) >> 1;
        if (f[i].first - s(i, mid) <= f[j].first - s(j, mid)) R = mid;
        else L = mid + 1;
    }
    return L;
}

pair<double, int> calc(double mid) {
    Q[h = t = 1] = 0;
    for (int i = 1; i <= n; ++i) {
        while (h < t && p[h] <= i) ++h;
        f[i].first = f[Q[h]].first + S0 - s(Q[h], i) - mid;
        f[i].second = f[Q[h]].second + 1;
        while (h < t && p[t - 1] >= find(Q[t], i)) --t;
        p[t] = find(Q[t], i), Q[++t] = i;
    }
    return f[n];
}

int main() {
    n = read(), k = read(), r = read(), S0 = M_PI * r * r;
    x[0] = -1e9;
    for (int i = 1; i <= n; ++i) x[i] = read();
    for (int i = 0; i < r << 1; ++i) {
        double theta = 2 * acos(i / 2.0 / r);
        o[i] = (theta - sin(theta)) * r * r;
    }
    double L = 0, R = 1e9;
    for (int _ = 1; _ <= 50; ++_) {
        double mid = (L + R) / 2;
        auto res = calc(mid);
        if (res.second >= k) L = mid;
        else R = mid;
    }
    auto res = calc(L);
    printf("%.8lf\n", res.first + k * L);
    return 0;
}