7.1.6 Maple trees

Problem Description

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 ?

Input

The input contains one or more data sets. At first line of each input data set is number of trees in this data set n （1 <= n <= 100）, it is followed by n coordinates of the trees. Each coordinate is a pair of integers, and each integer is in [-1000, 1000], it means the position of a tree’s center. Each pair is separated by blank.
Zero at line for number of trees terminates the input for your program.

Output

Minimal required radius of the circle ring I have to choose. The precision should be 10^-2.

Sample Input

Sample Output

1.50

思路：最小圆覆盖

有两种方法：一种是随机增量法，另一种是求凸包，再求三角形的最小覆盖圆，我用的是前者

http://blog.sina.com.cn/s/blog_6e63f59e010120dl.html （这篇文章讲的很好，尤其是对于怎么求三角形的外心）

http://blog.csdn.net/lthyxy/article/details/6661250 （这篇是代码，但缺少一个很重要的就是对于三点共线的判断（虽然在随机情况下很少见））

随机增量法简单的来说：假设我已经做出了一个圆，在1-n中选取第一个不在当前圆里的点，命名为i

重复以上步骤，假设又以i为圆周上的点，选择了一个1至i-1里的点作为圆，又有一个点k，它不在这个圆内，分析当前这三点，很明显，k点跟i,j不可能构成钝角三角形（如果是钝角三角形），k已经包含在以i，j为直径的圆里了

所以（当三点不共线时）求三角形外接圆，否则已知k点是最远点，取k与i，j距离最大为直径，算法结束，至于为什么是线性的，首先，一个点不在当前圆内的概率是3/i，

有3/i的概率做到k，因为是三重循环，所以到i的期望复杂度是（3/i*3/i*i*i）=O(9)，总共重复n此，期望9*O(n);

  1 #include <cmath>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <cstring>
  5 #include <string>
  6 #include <cstdlib>
  7 using namespace std;
  8 
  9 typedef double dd;
 10 const int maxn=1210;
 11 const dd eps=1E-10;
 12 dd A1,B1,C1,A2,B2,C2,t;
 13 struct point
 14 {
 15     dd x,y,r;
 16 } p[maxn],o,h;
 17 dd x[20],y[20];
 18 int n;
 19 
 20 void close()
 21 {
 22 exit(0);
 23 }
 24 
 25 dd sqr(dd t)
 26 {
 27     return t*t;
 28 }
 29 
 30 int dblcmp(dd t)
 31 {
 32     if (fabs(t)<eps)
 33         return 0;
 34     if (t>0) return 1;
 35     return -1;
 36 }
 37 
 38 dd dist(point a,point b)
 39 {
 40     return sqrt( (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y) );
 41 }
 42 
 43 bool judge(int i)
 44 {
 45     if (dblcmp(dist(p[i],o)-o.r)==1)
 46         return false;
 47     return true;
 48 }
 49 
 50 dd mul(point a,point b,point c)
 51 {
 52     return ( (b.x-a.x)*(c.y-a.y) - (b.y-a.y)*(c.x-a.x) );
 53 }
 54 
 55 void update(int i,int j,int k)
 56 {
 57     if (dblcmp(mul(p[i],p[j],p[k]))==0)
 58     {
 59         if (dblcmp( dist(p[k],p[i])-dist(p[k],p[j]) ) >=0 )
 60             h=p[i];    else h=p[j];
 61         o.x=(h.x+p[k].x)/2.0;
 62         o.y=(h.y+p[k].y)/2.0;
 63         o.r=dist(o,p[k]);
 64         return;
 65     }
 66     x[1]=p[i].x; y[1]=p[i].y;
 67     x[2]=p[j].x; y[2]=p[j].y;
 68     A1 = (x[2]-x[1]);
 69     B1 = (y[2]-y[1]);
 70     C1=(sqr(x[2])-sqr(x[1]) + sqr(y[2])-sqr(y[1]))/2.0;
 71     ///////////////////////////////////////////////
 72     x[1]=p[i].x; y[1]=p[i].y;
 73     x[2]=p[k].x; y[2]=p[k].y;
 74     A2 = (x[2]-x[1]);
 75     B2 = (y[2]-y[1]);
 76     C2=(sqr(x[2])-sqr(x[1]) + sqr(y[2])-sqr(y[1]))/2.0;
 77     ///////////////////////////////////////////////
 78     t=A1*B2-A2*B1;
 79     o.x=(C1*B2-C2*B1)/t;
 80     o.y=(A1*C2-C1*A2)/t;
 81     o.r=dist(o,p[i]);    
 82 }
 83 
 84 void work()
 85 {
 86     o.r=0;
 87     o.x=p[1].x;
 88     o.y=p[1].y;
 89     for (int i=2;i<=n;i++)
 90     {
 91         if (judge(i)) continue;
 92         o=p[i];
 93         o.r=0;
 94         for (int j=1;j<=i-1;j++)
 95         {
 96             if (judge(j)) continue;
 97             o.x = (p[i].x + p[j].x) / 2;
 98             o.y = (p[i].y + p[j].y) / 2;
 99             o.r=dist(p[i],o);
100             for (int k=1;k<=j-1;k++)//这里的循环很重要，一定是j-1,因为我是要保证做到i,j这个位置时，min(i,j)前面的k这三点构成最小圆，不能提前越界了
101             {
102                 if (judge(k)) continue;
103                 update(i,j,k);
104             }
105         }
106     }
107 //    printf("x:%lf y:%lf
",o.x,o.y);
108 }
109 
110 void init()
111 {
112     while(scanf("%d",&n)!=EOF)
113     {
114         if (n==0) break;
115         for (int i=1;i<=n;i++)
116             scanf("%lf %lf",&p[i].x,&p[i].y);
117         work();
118 //        printf("%.2lf %.2lf ",o.x,o.y);
119         printf("%.2lf
",(o.r+0.5));
120     }
121 }
122 
123 int main ()
124 {
125     init();
126     close();
127     return 0;
128 }