【FJOI2015】【BZOJ4138】【洛谷P4586】最小覆盖双圆问题(坐标旋转)(二分)(最小圆覆盖)

BZOJ传送门

洛谷传送门


题解:

显然我们的可以按照xxx排序之后划分两部分算最小圆覆盖取maxmaxmax。

由于划分可能是斜的,考虑坐标旋转。

显然两边的最小圆覆盖随着点集的增加单调不减,考虑二分找出当前坐标下的最优xxx划分。


代码:

#include<bits/stdc++.h>
#define ll long long
#define re register
#define cs const

cs double PI=acos(-1),eps=1e-4;
cs double angle=PI/100,si=sin(angle),co=cos(angle);
struct Point{
	double x,y;
	Point(){}
	Point(double _x,double _y):x(_x),y(_y){}
	friend Point operator+(cs Point &a,cs Point &b){return Point(a.x+b.x,a.y+b.y);}
	friend Point operator-(cs Point &a,cs Point &b){return Point(a.x-b.x,a.y-b.y);}
	friend Point operator*(cs Point &a,double b){return Point(a.x*b,a.y*b);}
	friend double operator*(cs Point &a,cs Point &b){return a.x*b.y-b.x*a.y;}
	inline double norm()cs{return x*x+y*y;}
	inline Point rotate(){return Point(x*co-y*si,x*si+y*co);}
	friend bool operator<(cs Point &a,cs Point &b){return a.x<b.x;}
};

inline double dist(cs Point &a,cs Point &b){return sqrt((a-b).norm());}

struct Cir{
	Point O;double r;
	Cir(){}
	Cir(cs Point &_O,double _r):O(_O),r(_r){}
	inline bool in(cs Point &p){return r+eps>dist(O,p);}
};

inline Cir get_Cir(cs Point &p1,cs Point &p2,cs Point &p3){
	if(fabs((p1-p2)*(p2-p3))<eps){
		if(fabs(p1.y-p2.y)<eps){
			if((p1.x<p2.x)==(p2.x<p3.x))return Cir((p1+p3)*0.5,dist(p1,p3)*0.5);
			if((p1.x<p3.x)==(p3.x<p2.x))return Cir((p1+p2)*0.5,dist(p1,p2)*0.5);
			return Cir((p2+p3)*0.5,dist(p2,p3)*0.5);
		}
		else {
			if((p1.y<p2.y)==(p2.y<p3.y))return Cir((p1+p3)*0.5,dist(p1,p3)*0.5);
			if((p1.y<p3.y)==(p3.y<p2.y))return Cir((p1+p2)*0.5,dist(p1,p2)*0.5);
			return Cir((p2+p3)*0.5,dist(p2,p3)*0.5);
		}
	}
	double a=p2.x-p1.x,b=p2.y-p1.y,c=p3.x-p2.x,d=p3.y-p2.y;
	double e=p2.norm()-p1.norm(),f=p3.norm()-p2.norm();
	Point O=Point(0.5*(b*f-d*e)/(b*c-a*d),0.5*(a*f-c*e)/(a*d-b*c));
	return Cir(O,dist(O,p1));
}

cs int N=1e3+5;

Point p[N],q[N];
Cir C;

inline double solve(int l,int r){
	if(l>r)return 0;
	static int n;n=0;
	for(int re i=l;i<=r;++i)q[++n]=p[i];
	std::random_shuffle(q+1,q+n+1);
	C=Cir(q[1],0);
	for(int re i=1;i<=n;++i)if(!C.in(q[i])){
		C.O=q[i];
		for(int re j=1;j<i;++j)if(!C.in(q[j])){
			C.O=(q[i]+q[j])*0.5;
			C.r=dist(C.O,q[i]);
			for(int re k=1;k<j;++k)if(!C.in(q[k]))C=get_Cir(q[i],q[j],q[k]);
		}
	}
	return C.r;
}

signed main(){
#ifdef zxyoi
	freopen("double.in","r",stdin);
#endif
	srand(time(0));
	int n;
	while(scanf("%d",&n),n!=0){
		for(int re i=1;i<=n;++i)scanf("%lf%lf",&p[i].x,&p[i].y);
		double ans=1e9;
		for(int re t=0;t<100;++t){
			for(int re i=1;i<=n;++i)p[i]=p[i].rotate();
			std::sort(p+1,p+n+1);
			int l=1,r=n;
			while(l<=r){
				int mid=l+r>>1;
				double r1=solve(1,mid),r2=solve(mid+1,n),tmp=std::max(r1,r2);
				if(std::min(r1,r2)>=ans)break;
				ans=std::min(ans,tmp);
				(r1>r2)?r=mid-1:l=mid+1;
			}
		}
		printf("%.2f\n",ans);
	}
	return 0;
}
上一篇:学Python能干嘛?用 Pyecharts 可视化微信好友,酷炸了


下一篇:c – 朋友类的部分模板专业化?