BZOJ传送门
洛谷传送门
题解:
显然我们的可以按照x排序之后划分两部分算最小圆覆盖取max。
由于划分可能是斜的,考虑坐标旋转。
显然两边的最小圆覆盖随着点集的增加单调不减,考虑二分找出当前坐标下的最优x划分。
代码:
#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;
}