(POI) XVIII OI Round I Task Plot [最小圓覆蓋 隨機增量法]

https://szkopul.edu.pl/problemset/problem/mzrTn1kzVBOAwVYn55LUeAai/site/?key=statement

WARNING: this is not the AC solution. it got TLE on the online judge!!!

有最小圓覆蓋的模板~

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <iomanip>
#include <cstdlib>
using namespace std;

typedef long double ld;
const ld eps = 1e-9;

struct P
{
    ld x,y;
    P(){}
    P(ld _x,ld _y) : x(_x),y(_y){}
    void scan()
    {
        cin >> x >> y;
    }
};

P operator+(const P &p1,const P &p2)
{
    return P(p1.x+p2.x,p1.y+p2.y);
}

P operator-(const P &p1,const P &p2)
{
    return P(p1.x-p2.x,p1.y-p2.y);
}

P operator*(const ld &d,const P &p1)
{
    return P(p1.x*d,p1.y*d);
}

P operator*(const P &p1,const ld &d)
{
    return P(p1.x*d,p1.y*d);
}

ld dot(const P &p1,const P &p2)
{
    return p1.x*p2.x + p1.y*p2.y;
}

ld cross(const P &p1,const P &p2)
{
    return p1.x*p2.y - p1.y*p2.x;
}

ld dis(const P &p1,const P &p2)
{
    return sqrt(dot(p1-p2,p1-p2));
}

P Rotate(P p)
{
    return P(-p.y,p.x);
}

struct Line
{
    P x,v; //point x which has vector v
    Line() {}
    Line(P _x,P _v) : x(_x),v(_v){}
};

P inter(const Line &l1,const Line &l2)
{
    P p1=l1.x,p2=l1.x+l1.v;
    P q1=l2.x,q2=l2.x+l2.v;
    return p1 + (p2-p1)*(cross(q2-q1,p1-q1)/cross(p2-p1,q2-q1));
}

struct Circle
{
    P p;
    ld r;
    Circle() : p(P()),r(0) {}
    Circle(P _p,ld _r) : p(_p),r(_r) {}
};

bool in_cir(Circle c,P p)
{
    return dis(c.p,p) < c.r + eps;
}

const int N = 100006;

P p[N];
P a[N];

int n,m;

Circle min_cir_cover(int L,int R)
{
    int n=R-L+1;
    for (int i=1;n>=i;++i)
    {
        a[i] = p[L+i-1];
    }
    random_shuffle(a+1,a+n+1);
    Circle ans = Circle(P(0,0),0);
    for (int i=1;n>=i;++i)
    {
        if (!in_cir(ans,a[i]))
        {
            ans = Circle(a[i],0);
            for (int j=1;i>j;++j)
            {
                if (!in_cir(ans,a[j]))
                {
                    ans = Circle( (a[i] + a[j])*0.5,dis(a[i],a[j])*0.5 );
                    for (int k=1;j>k;++k)
                    {
                        if (!in_cir(ans,a[k]))
                        {
                            //get circle cover a_i, a_j, a_k
                            Line l1 = Line( (a[i]+a[j])*0.5,Rotate(a[i]-a[j]) );
                            Line l2 = Line( (a[i]+a[k])*0.5,Rotate(a[i]-a[k]) );
                            P tmp = inter(l1,l2);
                            ans = Circle(tmp,dis(tmp,a[i]));
                        }
                    }
                }
            }
        }
    }
    return ans;
}

int extend(int pos,ld limit)
{
    int i;
    for (i=1;;i = min(i<<1,n-pos+1))
    {
        Circle tmp = min_cir_cover(pos,pos+i-1);
        if (tmp.r > limit + eps) break;
        if (i == n-pos + 1) return n;  //till the end
    }
    int L = pos + (i>>1) - 1,R = pos+i-1;
    //L is the answer
    while (L + 1 < R)
    {
        int mid = (L+R) >> 1;
        Circle tmp = min_cir_cover(pos,mid);
        if (tmp.r < limit + eps) L = mid;
        else R = mid;
    }
    return L;
}

bool can(ld limit)
{
    int last,cnt=0;
    for (int i=1;n>=i;i=++last)
    {
        if (++cnt == m+1) return false;
        last = extend(i,limit);
    }
    return true;
}

ld solve()
{
    ld l=0,r=2828500;
    while (r-l > eps)
    {
        ld mid = (l+r)/2;
        if (can(mid)) r=mid;
        else l=mid;
    }
    return r;
}

P ans[N];

void show_ans(ld limit)
{
    int m=0;
    int i,last;
    for (i=1;n>=i;i=++last)
    {
        last = extend(i,limit);
        Circle tmp = min_cir_cover(i,last);
        ans[++m] = tmp.p;
    }
    cout << m << endl;
    for (int i=1;m>=i;i++)
    {
        cout << ans[i].x << ' ' << ans[i].y << endl;
    }
}

int main ()
{
    //srand(880301);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >>n >> m;
    for (int i=1;n>=i;++i)
    {
        p[i].scan();
    }
    ld ans = solve();
    cout << fixed << setprecision(15);
    cout << ans << endl;
    show_ans(ans);
}