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

题目：用最小的圆覆盖所有的点
以下有两种方法。
首先是随机增量算法
------------------------------------------------------------------------------------
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)的方法能够判定出最小圆。
------------------------------------------------------------------------------------
易做图ysis:
现在来分析为什么是线性的。
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仍旧是线性。于是难以置信的最小圆覆盖的复杂度变成了线性的。
-------------------------------------------------------------------------------------
[cpp]
#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
[cpp]
#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

补充：软件开发 , C++ ,