Maple trees

Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1603    Accepted Submission(s): 495

There are a lot of trees in HDU. Kiki want to surround all the trees with the minimal required length of the rope . As follow,



To make this problem more simple, consider all the trees are circles in a plate. The diameter of all the trees are the same (the diameter of a tree is 1 unit). Kiki can calculate the minimal length of the rope , because it's so easy for this smart girl.
But we don't have a rope to surround the trees. Instead, we only have some circle rings of different radius. Now I want to know the minimal required radius of the circle ring. And I don't want to ask her this problem, because she is busy preparing for the examination.
As a smart ACMer, can you help me ?

2
1 0
-1 0
0

1.50

/*
HDOJ 2215 凸包+最小圆覆盖
刚开始以为找完凸包，距离最远的即可，别人举个等边三角形就不对了。。。
凸包 不说了
 
枚举任意3点找其最小覆盖圆
  1.当为钝角三角形时不是外接圆，而是以其最长边为直径的圆
  2.当为外接圆时，半径公式为r=abc/4s;
 	推导为如下：
 		由正弦定理，a/sinA=b/sinB=c/sinC=2R,得sinA=a/(2R),
 	   又三角形面积公式Ｓ=(bcsinA)/2,
 	   所以S=(abc)/(4R),故R=(abc)/(4S).
*/
#include<iostream>
#include<stdio.h>
#include<cmath>
#include<algorithm>
using namespace std;

struct point{
	int x,y;
};

int n,top;
point s[105],p[105];

double max(double a, double b) {
    return a > b ? a : b;
}

double multi(point a, point b, point c)
{
    return (b.x-a.x)*(c.y-a.y) - (b.y-a.y)*(c.x-a.x);
}
  
double dis(point a, point b)
{
    return sqrt(double((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y)));//要加double 
}

int cmp(const void *a,const void *b)
{
	point c=*(point *)a;
	point d=*(point *)b;
	double k=multi(p[0],c,d);
	if(k<0||k==0&&dis(c,p[0])>dis(d,p[0]))//排序  调换 
		return 1;
	return -1;
} 

void convex()
{
	int i;
	point t;
	
	for(i=1;i<n;i++)//寻找第一个点 y最小,y相同x最小 
	{
		if(p[i].y<p[0].y||(p[i].y==p[0].y&&p[i].x<p[0].x))
		{
			t=p[i];
			p[i]=p[0];
			p[0]=t;
		}
	}
	
	qsort(p+1,n-1,sizeof(p[0]),cmp);//对n-1个点按极角排序 第一个点除外 
	
	s[0]=p[0];
	s[1]=p[1];
	s[2]=p[2];
	top=2;
	
	for(i=3;i<n;i++)
	{
		while(top>=2&&multi(s[top-1],s[top],p[i])<0)
		//新加入的点，若与栈里2个点 极角<0,则顺时针方向，不符合，出栈 
			top--;
		s[++top]=p[i];//加入当前点 
	}
}

int main()
{
	int i,j,k;
	double r,x,y,z,maxR,area;
	
	//freopen("test.txt","r",stdin);
	while(scanf("%d",&n),n)
	{
		for(i=0;i<n;i++)
			scanf("%d%d",&p[i].x,&p[i].y);
		if(n==1)// 处理n=1，2情况 
		{
			printf("0.50\n");
			continue;
		}
		else if(n==2)
		{
			printf("%.2lf\n",dis(p[0],p[1])*0.50+0.50);
			continue;
		}
		
		convex();//凸包 
	
		maxR=-1;
		for(i=0;i<top;i++)
			for(j=i+1;j<top;j++)
				for(k=j+1;k<=top;k++)
				{
					x=dis(s[i],s[j]);
					y=dis(s[i],s[k]);
					z=dis(s[j],s[k]);
					if(x*x+y*y<z*z||x*x+z*z<y*y||z*z+y*y<x*x)//钝角  z*z+y*y==x*x直角 
						r=max(max(x,y),z)/2.0;
					else
					{
						area=fabs(multi(s[i],s[j],s[k]))/2.0;
						r=x*y*z/(area*4.0);
					}
					if(maxR<r)
						maxR=r;
				}
		printf("%.2lf\n",maxR+0.5);
	}
	return 0;
}