狂T 只能去%Po姐 http://blog.csdn.net/popoqqq/article/details/45100989
直接上二分是不可取的，因为我们要求m次，如果每次都验证一遍[1,n/2]直接就炸了
我们可以这么搞
首先判断[pos,pos+1-1]是否满足要求
然后判断[pos,pos+2-1]是否满足要求
然后判断[pos,pos+4-1]是否满足要求
然后判断[pos,pos+8-1]是否满足要求
...
直到找到一个不满足要求2^k的为止，然后我们在[2^(k-1),2^k]区间内二分
这样可以保证复杂度为O(nlognlog(limit/eps)) 不过常数巨大。。。。
虽然还是不知道怎么保证复杂度的
被卡精度 还是不得已动用了不愿用的long double
另外 白天不要交此题 否则RP--
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<ctime>
using namespace std;
typedef long double ld;
const ld eps=1e-9;
inline int dcmp(ld a,ld b)
{
if (fabs(a-b)<eps) return 0;
if (a<b) return -1; return 1;
}
inline ld sqr(ld x){
return x*x;
}
const int N=100005;
struct Point{
ld x,y;
Point(ld x=0,ld y=0):x(x),y(y) { }
void read(){
double ix,iy;
scanf("%lf%lf",&ix,&iy); x=ix; y=iy;
}
friend ld Dist(Point A,Point B){
return sqrt(sqr(A.x-B.x)+sqr(A.y-B.y));
}
}P[N],p[N];
struct abcd{
Point c; ld r;
abcd() { }
abcd(Point _c,ld _r){
c=_c; r=_r;
}
}Q[N];
int K;
inline Point Get(Point a,Point b,Point c)
{
ld a1,a2,b1,b2,c1,c2;
Point ans;
a1=2*(b.x-a.x),b1=2*(b.y-a.y),c1=sqr(b.x)-sqr(a.x)+sqr(b.y)-sqr(a.y);
a2=2*(c.x-a.x),b2=2*(c.y-a.y),c2=sqr(c.x)-sqr(a.x)+sqr(c.y)-sqr(a.y);
if(!dcmp(a1,0))
ans.y=c1/b1,ans.x=(c2-ans.y*b2)/a2;
else if(!dcmp(b1,0))
ans.x=c1/a1,ans.y=(c2-ans.x*a2)/b2;
else
ans.x=(c2*b1-c1*b2)/(a2*b1-a1*b2),
ans.y=(c2*a1-c1*a2)/(b2*a1-b1*a2);
return ans;
}
inline Point Get(Point A,Point B)
{
return Point((A.x+B.x)/2,(A.y+B.y)/2);
}
inline abcd MinCover(int l,int r)
{
int n=r-l+1;
for (int i=l;i<=r;i++) p[i-l+1]=P[i];
random_shuffle(p+1,p+n+1);
Point _C=p[1]; ld _R=0;
for (int i=2;i<=n;i++)
if (dcmp(Dist(p[i],_C),_R)>0)
{
_C=p[i],_R=0;
for (int j=1;j<=i;j++)
if (dcmp(Dist(p[j],_C),_R)>0)
{
_C=Get(p[i],p[j]),_R=Dist(_C,p[i]);
for (int k=1;k<=j;k++)
if (dcmp(Dist(p[k],_C),_R)>0)
_C=Get(p[i],p[j],p[k]),_R=Dist(_C,p[i]);
}
}
return abcd(_C,_R);
}
int n,m;
ld L,R,MID;
inline int calc(int s,int k){
int i;
for(i=1;;i=min(i<<1,n-s+1))
{
if(dcmp(MinCover(s,s+i-1).r,MID)>0)
break;
if(i==n-s+1) return n;
}
int l=s+(i>>1)-1,r=s+i-1,mid; abcd ret;
while (l+1<r)
{
if (dcmp(MinCover(s,mid=(l+r)>>1).r,MID)>0)
r=mid;
else
l=mid;
}
return l;
}
inline bool check()
{
K=0;
for (int s=1,t;s<=n && K<=m;s=t+1)
{
K++;
t=calc(s,K);
}
return K<=m;
}
inline void Bin(){
L=0,R=MinCover(1,n).r;
while (R-L>1e-10)
{
MID=(L+R)/2;
if (check())
R=MID;
else
L=MID;
}
MID=R;
K=0;
for (int s=1,t;s<=n;s=t+1)
{
K++;
t=calc(s,K); Q[K]=MinCover(s,t);
}
printf("%.15lf\n%d\n",(double)R,K);
for (int i=1;i<=K;i++)
printf("%.15lf %.15lf\n",(double)Q[i].c.x,(double)Q[i].c.y);
}
int main()
{
srand(10086);
freopen("t.in","r",stdin);
freopen("t.out","w",stdout);
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++) P[i].read();
Bin();
return 0;
}