P3517 [POI 2011] WYK-Plot 题解

总体思路：

首先我们考虑，给定一些固定的点 $P$，点 $Q$ 要在什么坐标上，才能和里它最远的点 $P$ 离的最近。

可以看出，其实这是一个最小圆覆盖问题，也就是给出若干个点，让你画一个最小的包含所有点的圆。对应到题目中，圆心就是点 $Q$，$r$ 也就是从 $Q$ 到离 $Q$ 最远的点的最短距离。

然后我们来说一下最小圆覆盖问题的做法，首先看到 $n \le 10 ^ 5$，那么可以想到，我们需要使用随机增量法。

做法：给定 $n$ 个点，我们将这些点都随机打乱前后顺序。然后考虑，在覆盖了前 $i - 1$ 个点的圆的基础上，我们加入一个新的点 $P_i$，如果这个圆并没有覆盖到 $P_i$，那么前 $i$ 个点的最小圆中，$P_i$ 必定在圆的边界上。

那么就从只覆盖 $P_i$，半径为 $0$，然后开始尝试覆盖 $P_j$，其中 $P_j$ 表示前 $i - 1$ 个点。如果覆盖不了，则说明 $P_j$ 一定在目前覆盖圆的边界上。那么尝试求出以 $P_i, P_j$ 作为直径的圆，尝试覆盖 $P_k$，如果覆盖不了，则 $P_k$ 一定在覆盖圆的边界上。而三点确定一个圆，然后继续查找后面的 $k$ 即可。

每一次，他进入下一层循环的概率为 $\frac{i}{3}$，期望时间复杂度为 $O(n)$。

接着，我们回到原问题，我们要最小化最大距离，最小值最大，最大值最小，我们很容易想到二分。

对于我们现在二分点 $mid$，那么我们从 $P_1$ 开始，找到最大的 $x$，是的覆盖 $P_1, P_2, ..., P_x$ 的圆，半径不超过 $mid$。接着我们把点 $Q$，放在这个圆的圆心上，以此类推。

如果最终的点 $Q$ 数目，不超过 $m$，则 $mid$ 可行，否则 $mid$ 不可行。

那么关键是，我们如何从 $P_i$，查询最大的 $x$，使得覆盖 $P_i, P_{i + 1}, ..., P_x$ 的圆，半径不超过 $mid$。

那么我们可以考虑二分 $x$，这样只需要判断一个固定集合的最小圆覆盖即可。但是存在问题，我们二分的范围可能相比于最终划分的段过于大，导致每次二分复杂度特别的高。

那么我们考虑倍增，尝试从 $P_i$ 开始，看看是否能覆盖后面 $2 ^ 0, 2 ^ 1, 2 ^ 2, ..., 2 ^ x$，如果覆盖不了 $2 ^ x$ 个点，则答案在 $2 ^ {x - 1}$ 到 $2 ^ x$ 之间，然后我们在这个范围内二分查找即可。

最终复杂度 $O(n \log ^ 2 n)$，可以通过。

代码实现：

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 3e5 + 10;
const double eps = 1e-9;
struct arr{double x, y;}a[N], ar[N], arrr[N];
int n, m, tp;
arr center;
double r, le, ri;
inline bool check(arr x, arr y)
{
    return sqrt((x.x - y.x) * (x.x - y.x) + (x.y - y.y) * (x.y - y.y)) - r > eps;
}
inline void circle(int x, int y)
{
    int tot = 0;
    r = 0;
    for (register int i = x;i <= y; i = -~i) ar[ ++ tot] = a[i];
    random_shuffle(ar + 1, ar + tot + 1); center = ar[1];//初始定位圆心坐标
    for (register int i = 2;i <= tot; i = -~i)
    {
        if (check(ar[i], center))
        {
            r = 0;
            center.x = ar[i].x, center.y = ar[i].y;
            for (register int j = 1;j < i ;j = -~j)
            {
                if (check(ar[j], center))
                {
                    center.x = (ar[j].x + ar[i].x) / 2, center.y = (ar[j].y + ar[i].y) / 2;
                    r = sqrt((ar[j].x - center.x) * (ar[j].x - center.x) + (ar[j].y - center.y) * (ar[j].y - center.y));
                    for (register int k = 1;k < j; k = -~k)
                    {
                        if (check(ar[k], center))
                        {
                            center.y = (((ar[k].x * ar[k].x + ar[k].y * ar[k].y - ar[i].x * ar[i].x - ar[i].y * ar[i].y) * (ar[i].x - ar[j].x)) - ((ar[j].x * ar[j].x + ar[j].y * ar[j].y - ar[i].x * ar[i].x - ar[i].y * ar[i].y) * (ar[i].x - ar[k].x))) / ((ar[i].x - ar[k].x) * (ar[i].y - ar[j].y) * 2 - (ar[i].x - ar[j].x) * (ar[i].y - ar[k].y) * 2);
                            center.x = (((ar[k].x * ar[k].x + ar[k].y * ar[k].y - ar[i].x * ar[i].x - ar[i].y * ar[i].y) * (ar[i].y - ar[j].y)) - ((ar[j].x * ar[j].x + ar[j].y * ar[j].y - ar[i].x * ar[i].x - ar[i].y * ar[i].y) * (ar[i].y - ar[k].y))) / ((ar[i].x - ar[j].x) * (ar[i].y - ar[k].y) * 2 - (ar[i].x - ar[k].x) * (ar[i].y - ar[j].y) * 2);
                            r = sqrt((ar[k].x - center.x) * (ar[k].x - center.x) + (ar[k].y - center.y) * (ar[k].y - center.y));
                        }
                    }
                }
            }
        }
    }
}
inline bool check(double x)
{
    tp = 0;
    int res = 0;
    for (register int i = 1;i <= n; i = -~i)
    {
        res = i;
        int j = 0;
        for (j = 1; (1 << j) + i - 1 <= n; j = -~j)
        {
            circle(i, (1 << j) + i - 1);
            if (r - x > eps){break;}
        }
        int lef = (1 << (j - 1)) + i - 1, rig = (1 << j) + i - 1;
        rig = min(n, rig);
        while (lef <= rig)
        {
            int mid = lef + rig >> 1;
            circle(i, mid);
            if (r - x >= eps) rig = mid - 1;
            else lef = mid + 1, res = mid;
        }
        circle(i, res); i = res;
        arrr[ ++ tp] = center;
        if (tp > m) return 0;
    }
    return 1;
}
signed main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for (register int i = 1;i <= n; i = -~i) cin >> a[i].x >> a[i].y;
    circle(1, n);
    ri = r;
    int cnt = 1;
    if (m <= 1)
    {
        check(ri);
        cout << fixed << setprecision(8) << r << "\n" << tp << "\n";
        for (register int i = 1;i <= tp; i = -~i) cout << fixed << setprecision(8) << arrr[i].x << " " << arrr[i].y << "\n";
        return 0;
    }
    while (ri - le > eps && cnt <= 50)
    {
        double mid = (ri + le) / 2;
        ++ cnt;
        if (check(mid)) ri = mid;
        else le = mid; 
    }
    check(ri);
    cout << fixed << setprecision(8) << ri << "\n" << tp << "\n";
    for (register int i = 1;i <= tp; i = -~i) cout << fixed << setprecision(8) << arrr[i].x << " " << arrr[i].y << "\n";
    return 0;
}

然后这道题目就完成啦！！！