hhhhhhhhhhhxswl
Q：如果可以，你希望获得 LOL 中哪个英雄的能力？
A：妮蔻，变成美女，让兄弟们爽爽
兄弟们准备开始的时候，变成厄加特
（转自知乎）
一开始一个很森破的想法是，枚举分界点，左右两边分别做最小圆覆盖。
但是怎么分？以横坐标排序假的一批，样例都过不去。
原因是分界点可能不是竖着一刀劈，而是斜着砍。
于是可以转一转坐标系，每次转一下，最后转满一个$\pi$。
这时复杂度不太对劲。实际上这个分界点不用枚举，可以二分。
经过实测，每次转$\frac{\pi}{100}$能过。少一点都不行，所以我猜std就是转这么多。。。
复杂度$O(100Tn\log n)$。
代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <vector>
#include <time.h>
#define maxn 1005
const double eps = 1e-11;
const double inf = 1e18;
const double pi = acos(-1.0);
using namespace std;
inline int read(){
int x=0,y=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')y=1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return y?-x:x;
}
inline int cmp(double a,double b){return (a-b>eps)-(a-b<-eps);}
struct point{
double x,y;
point(double X=0,double Y=0){x=X,y=Y;}
point operator + (const point &a){return point(x+a.x,y+a.y);}
point operator - (const point &a){return point(x-a.x,y-a.y);}
point operator * (const double &a){return point(x*a,y*a);}
point operator / (const double &a){return point(x/a,y/a);}
bool operator < (const point &a)const{return !cmp(x,a.x)?cmp(y,a.y)==-1:cmp(x,a.x)==-1;}
double alpha(){return atan2(y,x);}
}p[maxn],q[maxn];
struct line{
point a,b;
double an;
line(point A=point(0,0),point B=point(0,0)){a=A,b=B,an=(b-a).alpha();}
};
struct circle{
point c;
double r;
circle(point C=point(0,0),double R=0){c=C,r=R;}
circle(point A,point B,point C){
#define sqr(x) ((x)*(x))
double a=sqr(A.x)-sqr(B.x)+sqr(A.y)-sqr(B.y),b=sqr(B.x)-sqr(C.x)+sqr(B.y)-sqr(C.y),_c=A.x-B.x,d=A.y-B.y,e=B.x-C.x,f=B.y-C.y,m=2*(_c*f-d*e);
c=point((a*f-b*d)/m,(b*_c-a*e)/m);
r=sqrt(sqr(A.x-c.x)+sqr(A.y-c.y));
#undef sqr
}
};
typedef vector<point> polygon;
inline double abs2(point a){return a.x*a.x+a.y*a.y;}
inline double abs(point a){return sqrt(abs2(a));}
inline double dis(point &a,point &b){return abs(a-b);}
inline double dot(point a,point b){return a.x*b.x+a.y*b.y;}
inline double cross(point a,point b){return a.x*b.y-a.y*b.x;}
inline double angle(line &a){return (a.b-a.a).alpha();}
inline point rotate(point a,double b){return point(a.x*cos(b)-a.y*sin(b),a.x*sin(b)+a.y*cos(b));}
inline point inter(line a,line b){
point A=a.b-a.a,B=b.b-b.a;
return a.a+A*cross(B,a.a-b.a)/cross(A,B);
}
inline point project(line a,point b){
point c=a.b-a.a;
return a.a+c*dot(c,b-a.a)/abs2(c);
}
inline double area(polygon &a){
double ans=0;
for(register int i=0,j=a.size()-1;i<a.size();j=i++)ans+=cross(a[j],a[i]);
return ans/2.0;
}
inline bool contain(point &a,circle &b){return cmp(abs2(b.c-a),b.r*b.r)<=0;}
inline double mini_circle(int n){
random_shuffle(p+1,p+1+n);
circle ans;
for(register int i=1;i<=n;++i){
if(!contain(p[i],ans)){
ans=circle(p[i],0);
for(register int j=1;j<i;++j)
if(!contain(p[j],ans)){
ans=circle((p[i]+p[j])/2,dis(p[i],p[j])/2);
for(register int k=1;k<j;++k)
if(!contain(p[k],ans))ans=circle(p[i],p[j],p[k]);
}
}
}
return ans.r;
}
int main(){
srand(time(0));
int n;
while(n=read()){
for(register int i=1;i<=n;++i)scanf("%lf%lf",&q[i].x,&q[i].y);
double ans=inf;
for(register int a=1;a<=100;++a){
for(register int i=1;i<=n;++i)q[i]=rotate(q[i],pi/100);
sort(q+1,q+1+n);
int l=1,r=n;
double r1,r2;
while(l<=r){
int mid=l+r>>1;
for(register int i=1;i<=mid;++i)p[i]=q[i];
r1=mini_circle(mid);
for(register int i=mid+1;i<=n;++i)p[i-mid]=q[i];
r2=mini_circle(n-mid);
ans=min(ans,max(r1,r2));
if(cmp(r1,r2)==-1)l=mid+1;
else r=mid-1;
}
}
printf("%.2lf\n",ans);
}
}
