Luogu

LOJ

分析

首先要会最小圆覆盖而且知道它是期望 $\mathcal{O}(n)$ 的。

显然可以二分答案，于是我们只要想办法判定能否分成最小圆覆盖半径都 $\leq mid$ 的 $\leq m$ 段即可。

显然最小圆覆盖半径是随着点的增多而不降的，所以每段的点越多越好。于是可以想到暴力找每段的右端点，然而可以卡成 $\mathcal{O}(n^2)$。还有一个想法是二分右端点，然而也可以卡到 $\mathcal{O}(n^2\log n)$。

根据一些交互题的套路可以想到先倍增出右端点可能落在的区间 $[i+2^{k-1}-1,i+2^k-1)$，然后再在其中二分，这样子就是 $\mathcal{O}(n\log n)$ 的了。

然而这题卡精度，我写 random_shuffle 只有 $97$ 分，换成 shuffle 才过 ...

代码

// ====================================
//   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)
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;
const double eps=1e-9;

int n,m;
vector<pair<int,int>> ans;
struct Point { double x,y; } p[N],t[N];

Point O; double R;
double CalcDis(Point A,Point B) {
    return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));
}
bool InCircle(Point A) {
    return CalcDis(A,O)<R+eps;
}
Point CalcO(Point A,Point B,Point C) {
    double a=B.x-A.x,b=B.y-A.y,c=C.x-B.x,d=C.y-B.y;
    double e=B.x*B.x+B.y*B.y-A.x*A.x-A.y*A.y;
    double f=C.x*C.x+C.y*C.y-B.x*B.x-B.y*B.y;
    return (Point){(f*b-e*d)/(c*b-a*d)/2,(a*f-e*c)/(a*d-b*c)/2};
}
void CalcCircle(int l,int r) {
    for (int i=l;i<=r;++i) t[i]=p[i];
    // 从某个网站上查来的写法
    unsigned seed=chrono::system_clock::now().time_since_epoch().count();
    shuffle(t+l,t+r+1,default_random_engine(seed));
    O=t[l],R=0;
    for (int i=l;i<=r;++i) {
        if (InCircle(t[i])) continue;
        O=t[i],R=0;
        for (int j=l;j<i;++j) {
            if (InCircle(t[j])) continue;
            O=(Point){(t[i].x+t[j].x)/2,(t[i].y+t[j].y)/2};
            R=CalcDis(t[i],t[j])/2;
            for (int k=l;k<j;++k) {
                if (InCircle(t[k])) continue;
                O=CalcO(t[i],t[j],t[k]),R=CalcDis(O,t[i]);
            }
        }
    }
}

bool check(double L) {
    ans.clear();
    for (int i=1,j,k;i<=n;i=j+1) {
        for (k=1;i+(1<<k)-1<=n;++k) {
            CalcCircle(i,i+(1<<k)-1);
            if (R>L) break;
        }
        int l=i+(1<<(k-1))-1,r=min(n,i+(1<<k)-1);
        while (l<r) {
            int mid=(l+r+1)>>1;
            CalcCircle(i,mid);
            if (R<L+eps) l=mid;
            else r=mid-1;
        }
        j=l;
        ans.emplace_back(make_pair(i,j));
        if ((int)ans.size()>m) return 0;
    }
    return 1;
}

int main() {
    n=read(),m=read();
    for (int i=1;i<=n;++i) p[i].x=read(),p[i].y=read();
    double L=0,R=1.42e6;
    while (R-L>1e-8) {
        double mid=(L+R)/2;
        if (check(mid)) R=mid;
        else L=mid;
    }
    printf("%.7lf\n",R);
    check(R);
    printf("%d\n",ans.size());
    for (auto i:ans) {
        CalcCircle(i.first,i.second);
        printf("%.7lf %.7lf\n",O.x,O.y);
    }
    return 0;
}