给出一系列点p_1, p_2, … , p_n,将其分成不多余m个连续的段,第i段内求一个点q_i,使得q_i到这段内点的距离的最大值的最大值最小

最大值最小,先二分答案。
再从每个开始点二分,用随机增量法的最小圆覆盖判断最长能扩展长度,段数是不是$<=m$。
但是有个问题。
如果m=n的话,每段长度都是1。
这样做是$O(n^2lgn)$的。

于是在每次判断最长能扩展长度时先倍增一下,把可能长度卡到某个 $2^i 到 2^{i+1}$ 之间。这样复杂度算下来就是$O(nlgn)$的了。
(雾,300s的题卡评测姬就是爽..
ps. vfk神犇代码 http://paste.ubuntu.com/10627230/

code:

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
typedef double ld;
int n,m;
struct Point{
	ld x,y;
	void read(){
		double a,b;
		scanf("%lf%lf",&a,&b);
		x=a,y=b;
	}
}a[100005],p[100005],o,ans[100005];
ld R;
int Ans;
const ld eps=1e-10;
ld dist(Point x,Point y){
	return sqrt((x.x-y.x)*(x.x-y.x)+(x.y-y.y)*(x.y-y.y));
}
Point geto(Point a,Point b,Point c){
	ld A=a.x*a.x-b.x*b.x+a.y*a.y-b.y*b.y;
	ld B=c.x*c.x-b.x*b.x+c.y*c.y-b.y*b.y;
	Point ret;
	ret.x=(A*(c.y-b.y)-B*(a.y-b.y))/((b.x-c.x)*(a.y-b.y)-(b.x-a.x)*(c.y-b.y))/2;
	ret.y=(A*(c.x-b.x)-B*(a.x-b.x))/((b.y-c.y)*(a.x-b.x)-(b.y-a.y)*(c.x-b.x))/2;
	return ret;
}


void calc(int n){
	random_shuffle(p+1,p+n+1);
	o=p[1];R=0;
	long long tot=0;
	for(int i=1;i<=n;i++){
		if(dist(o,p[i])<=R+eps) continue;
		o.x=(p[1].x+p[i].x)/2,o.y=(p[1].y+p[i].y)/2,R=dist(o,p[i]);
		for(int j=2;j<i;j++){
			if(dist(o,p[j])<=R+eps) continue;
			o.x=(p[j].x+p[i].x)/2,o.y=(p[j].y+p[i].y)/2,R=dist(p[i],p[j])/2;
			for(int k=1;k<j;k++){
				tot++;
				if(dist(p[k],o)<=R+eps) continue;
				o=geto(p[i],p[j],p[k]);
				R=dist(p[i],o);
			}
		}
	}
}
bool Judge(int l,int r,ld mx){
	for(int i=l;i<=r;i++) p[i-l+1]=a[i];
	calc(r-l+1);
	if(R<=mx) return 1;
	else return 0;
}
bool print;
bool judge(ld x){
	int now=1;
	int cnt=0;
	while(now<=n){
		int lg=0;
		for(;now+(1<<lg)-1<=n&&Judge(now,now+(1<<lg)-1,x);lg++);lg--;
		int l=now+(1<<lg)-1,r=min(now+(1<<(lg+1)),n+1);
		while(r-l>1){
			int mid=(l+r)/2;
			if(Judge(now,mid,x)) l=mid;
			else r=mid;
		}
		if(print){
			Judge(now,l,x);
			ans[Ans++]=o;
		}
		cnt++;
		now=l+1;
		if(cnt>m){
			return 0;
		}
	}
	return 1;
}
int main(){
	srand(401794301);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) a[i].read();
	ld l=0,r=4000000;
	for(int i=0;i<=50;i++){
		ld mid=(l+r)/2;
		if(judge(mid)) r=mid;
		else l=mid;
	}
	printf("%.10f\n",(double)r);
	print=1;
	judge(r+1e-10);
	printf("%d\n",Ans);
	for(int i=0;i<Ans;i++){
		printf("%.10f %.10f\n",(double)ans[i].x,(double)ans[i].y);
	}
	return 0;
}