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);
}
