凸包最小外切圆（最小覆盖圆）

定义： 给出平面上的一些点，求覆盖这些点的最小圆。

具体问题可见hdu 2215

解决：
1.求这些离散点的凸包；
2.枚举凸包上任意3点形成的三角形，求这些三角形的外切圆，找出所有外切圆中半径最大的一个。

细节：
1.若枚举的三个点构成钝角三角形，则最大半径为最长边的一半否则，半径 r=a*b*c/(4*S) ，其中S为三角形面积，用叉积很好求。
2.钝角三角形判断：若最长边为c，则a*a+b*b<c*c（类比直角三角）

//n个点,每次输入一个点的x,y值,每个点有0.5大小的半径,求最小覆盖圆
#include<bits/stdc++.h>
#define ll long long
#define lf double
#define IOS std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define Rep(i,l,r) for(int i=(l);i<=(r);i++)
using namespace std;

int n;

struct Point
{
    double x,y,z;
};
typedef Point vector_t;

double Dot(vector_t A, vector_t B){
    return A.x*B.x + A.y*B.y;
}
double Length(vector_t A){
    return sqrt(Dot(A, A));
}

double Cross(const vector_t& x, const vector_t& y)
{
	double z = x.x * y.y - x.y * y.x;
	return z;
}

Point operator-(const Point&a,const Point&b)
{
    Point c;
    c.x=a.x-b.x;
    c.y=a.y-b.y;
    c.z=0;
    return c;
}

Point p[500];
int cmp(const Point&a,const Point&b){
    double d=Cross(a-p[0],b-p[0]);
    if(d>0)
        return 1;
    if(d==0 && Length(a-p[0])<=Length(b-p[0]))
        return 1;
    return 0;
}
int build(int n,Point *p,Point *s)
{
	//*p为散点,*s为凸包的点
    sort(p,p+n,cmp);
    int m = 0;
    for(int i = 0;i < n;i++)
    {
        while(m>1&&Cross((s[m-1]-s[m-2]),(p[i]-s[m-2]))<=0)m--;
        s[m++] = p[i];
    }
    int lim = m;
    for(int i = n-2;i >= 0;i--)
    {
        while(m>lim&&Cross((s[m-1]-s[m-2]),(p[i]-s[m-2]))<=0)m--;
        s[m++] = p[i];
    }
    if(m!=1)m--;
    return m;
}

Point s[500];

int main()
{
    while(cin>>n)
    {
        if(n==0)break;
        Rep(i,0,n-1){
            double x,y;
            cin>>x>>y;
            p[i].x=x;p[i].y=y;
        }
        if(n==1){
            printf("0.50\n");
            continue;
        }
        
        int m=build(n,p,s);
        double R=0;
        if(m<=2){
            double r=(Length(p[1]-p[0])+1)/2;
            R=max(R,r);
        }
        else{
            for(int i=0;i<m;i++){
                for(int j=i+1;j<m;j++){
                    for(int k=j+1;k<m;k++){
                        double len1=Length(s[j]-s[i]),len2=Length(s[k]-s[i]),len3=Length(s[k]-s[j]);
                        if(len1>len2)swap(len1,len2);
                        if(len2>len3)swap(len2,len3);
                        double r=1e9;
                        if((len1*len1)+(len2*len2)<(len3*len3)){
                            r=len3/2;
                        }
                        else{
                            double S=abs(Cross(s[j]-s[i],s[k]-s[i]));
                            r=len1*len2*len3/(2*S);
                        }
                        R=max(R,r+0.5);
                    }
                }
            }
        }
        printf("%.2lf\n",R);
    }
    return 0;
}