POJ 3932 Groundhog Build Home（最小圆覆盖）

转载请注明出处，谢谢http://blog.csdn.net/acm_cxlove/article/details/7854526 by---cxlove

题目：用最小的圆覆盖所有的点

http://acm.hdu.edu.cn/showproblem.php?pid=3932

以下有两种方法。

首先是随机增量算法

------------------------------------------------------------------------------------

algorithm:

A、令Ci表示为前i个点的最小覆盖圆。当加入新点pi时如果pi不在Ci-1里那么pi必定在Ci的边界上。
B、再从新考虑这样一个问题，Ci为前i个点最小覆盖圆且p在Ci的的边界上！同理加入新点pi时如果p

i不在Ci-1里那么pi必定在Ci的边界上。这时我们就包含了两个点在这个最小圆的边界上。
C、再从新考虑这样一个问题，Ci为前i个点最小覆盖圆且有两个确定点再边界上！此时先让

O(N)的方法能够判定出最小圆。

------------------------------------------------------------------------------------

analysis:

现在来分析为什么是线性的。

C是线性的这是显然的。

B<-C的过程中。考虑pi 他在园内的概率为 (i-1)/i 。在圆外的概率为 1/i 所以加入pi的期望复杂度为：(1-i)/i*O(1) +(1/i)*O(i) {前者在园内那么不进入C，只用了O(1)。后者进入C用了O(i)的时间}这样分析出来，复杂度实际上仍旧

是线性的。

A<-B的过程中。考虑方法相同，这样A<-B仍旧是线性。于是难以置信的最小圆覆盖的复杂度变成了线性的。
-------------------------------------------------------------------------------------

#include<iostream>
#include<fstream>
#include<iomanip>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<string>
#include<vector>
#include<sstream>
#include<ctime>
#include<cassert>
#define LL long long
#define eps 1e-8
#define inf 999999.0
#define zero(a) fabs(a)<eps
#define N 20
#define pi acos(-1.0)
using namespace std;
double X,Y,R;
int n;
struct Point{
    double x,y;
    Point(){}
    Point(double tx,double ty){x=tx;y=ty;}
    bool check(){
        if(x+eps>0&&y+eps>0&&x<eps+X&&y<eps+Y) return true;
        return false;
    }
}p[1005],central;
//求三点的外接圆圆心
Point Circumcenter(Point a,Point b,Point c){
    double a1 = b.x - a.x, b1 = b.y - a.y, c1 = (a1*a1 + b1*b1)/2;
    double a2 = c.x - a.x, b2 = c.y - a.y, c2 = (a2*a2 + b2*b2)/2;
    double d = a1 * b2 - a2 * b1;
    return Point(a.x + (c1*b2 - c2*b1)/d,a.y + (a1*c2 - a2*c1)/d);
}
double dist(Point p1,Point p2){
    return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
}
void Min_cover_circle(){
    //将点随机化
    random_shuffle(p,p+n);
    central=p[0];R=0;
    for(int i=1;i<n;i++)
        if(dist(central,p[i])+eps>R){
            central=p[i];R=0;
            for(int j=0;j<i;j++)
                if(dist(central,p[j])+eps>R){
                    central.x=(p[i].x+p[j].x)/2;
                    central.y=(p[i].y+p[j].y)/2;
                    R=dist(central,p[j]);
                    for(int k=0;k<j;k++)
                        if(dist(central,p[k])+eps>R){
                            //3点确定圆
                            central=Circumcenter(p[i],p[j],p[k]);
                            R=dist(central,p[k]);
                        }
                }
        }
}
int main(){
    while(scanf("%lf%lf%d",&X,&Y,&n)!=EOF){
        for(int i=0;i<n;i++)
            scanf("%lf%lf",&p[i].x,&p[i].y);
        Min_cover_circle();
        printf("(%.1f,%.1f).\n%.1f\n",central.x,central.y,R);
    }
    return 0;
}

模拟退火算法。

随机选取若干个点，然后选定步长，从每个点随机走出去若干次，更新最优解。

将步长减小若干倍，直至达到一定的精度要求

好多地方随机，好多地方若干，这就和模拟退火的把握有关了。

在WA,TLE,AC之间徘徊，只刷到了800ms

#include<iostream>
#include<fstream>
#include<iomanip>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<string>
#include<vector>
#include<sstream>
#include<ctime>
#include<cassert>
#define LL long long
#define eps 1e-6
#define inf 999999.0
#define zero(a) fabs(a)<eps
#define N 20
#define pi acos(-1.0)
using namespace std;
double X,Y,best[N];
struct Point{
    double x,y;
    Point(){}
    Point(double tx,double ty){x=tx;y=ty;}
    bool check(){
        if(x+eps>0&&y+eps>0&&x<eps+X&&y<eps+Y) return true;
        return false;
    }
}p[1005],tp[N],pre,cur;
int n;
double dist(Point p1,Point p2){
    return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
}
double Get_Dist(Point cen){
    double ret=0;
    for(int i=0;i<n;i++)
        ret=max(ret,dist(p[i],cen));
    return ret;
}
Point Get_Rand(double X,double Y){
    return Point((rand()%1000+1)/1000.0*X,(rand()%1000+1)/1000.0*Y);
}
int main(){
    srand(time(NULL));
    while(scanf("%lf%lf%d",&X,&Y,&n)!=EOF){
        for(int i=0;i<n;i++)
            scanf("%lf%lf",&p[i].x,&p[i].y);
        //随机20个点
        for(int i=0;i<N;i++){
            tp[i]=Get_Rand(X,Y);
            best[i]=Get_Dist(tp[i]);
        }
        double step=max(X,Y);
        while(step>0.001){
            for(int i=0;i<N;i++){
                pre=tp[i];
                //走25步
                for(int j=0;j<25;j++){
                    //随机一个方向
                    double angle=(rand()%1000+1)/1000.0*2*pi;
                    cur.x=pre.x+cos(angle)*step;
                    cur.y=pre.y+sin(angle)*step;
                    if(!cur.check()) continue;
                    double dis=Get_Dist(cur);
                    if(dis<best[i]+eps){
                        best[i]=dis;
                        tp[i]=cur;
                    }
                }
            }
            //减小步长
            step*=0.8;
        }
        double ans=inf;
        int idx;
        for(int i=0;i<N;i++)
            if(best[i]<ans){
                ans=best[i];
                idx=i;
            }
        printf("(%.1f,%.1f).\n%.1f\n",tp[idx].x,tp[idx].y,ans);
    }
    return 0;
}