2011年计算机等级考试二级C辅导实例编程(20)

会计考友

　最小圆覆盖 随机增量算法　　最小圆覆盖。神奇的随机算法。当点以随机的顺序加入时期望复杂度是线性的。
$ \7 l, W+ u3 u$ Z3 ?+ W5 M　　------------------------------------------------------------------------------------
　　algorithm:
　　A、令Ci表示为前i个点的最小覆盖圆。当加入新点pi时如果pi不在Ci-1里那么pi必定在Ci的边界上。
　　B、再从新考虑这样一个问题，Ci为前i个点最小覆盖圆且p在Ci的的边界上!同理加入新点pi时如果p
　　i不在Ci-1里那么pi必定在Ci的边界上。这时我们就包含了两个点在这个最小圆的边界上。
/ o: d. W( [9 e7 g0 A　　C、再从新考虑这样一个问题，Ci为前i个点最小覆盖圆且有两个确定点再边界上!此时先让
; ?( M1 w, V6 M" a. v4 x　　O(N)的方法能够判定出最小圆。
　　------------------------------------------------------------------------------------
3 o  G- D! j4 O　　analysis:
　　现在来分析为什么是线性的。
/ r5 q" X4 a& c; J9 e3 `0 Q　　C是线性的这是显然的。

　　B

会计考友

10 node p[200000];　　11 double r;
　　12 node O;
+ u* [# X. e( |7 J) W" @! [　　13 double dist(node a,node b)
　　14 {
　　15 return sqrt( (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y) );
3 N8 Z, r. P, W5 W$ U5 W9 I9 Z　　16 }
  v4 Y- o, r" `6 ]; p9 w　　17 void calc(double a,double b,double c,double d,double e,double f) //给出两条直线ax+by+c=0,dx+ey+f=0 求交点
　　18 { //注意到三角形里两条中垂线不可能平行，所以不会产生除0错误
　　19 O.y=(c*d-f*a)/(b*d-e*a);
# O* }6 K2 A/ b" M  s　　20 O.x=(c*e-f*b)/(a*e-b*d);
　　21 }
  q$ Y2 M) f3 ?' W: Q) Z% Q　　22 int main()
1 R  M$ Z2 U* E4 b$ o% X( W4 F% f# ?　　23 {
　　24 freopen("HYOJ1337.in","r",stdin);
　　25 freopen("HYOJ1337.out","w",stdout);
　　26 scanf("%d",&n);

　　27 for (int i=1;i