POJ 3932 Groundhog Build Home（最小圆覆盖） - c++编程基础

题目：用最小的圆覆盖所有的点
以下有两种方法。
首先是随机增量算法
------------------------------------------------------------------------------------
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仍旧是线性。于是难以置信的最小圆覆盖的复杂度变成了线性的。
-------------------------------------------------------------------------------------
[cpp]
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define LL long long
#define eps 1e-8
#define inf 999999.0
#define zero(a) fabs(a) #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 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 if(dist(central,p[i])+eps>R){
central=p[i];R=0;

for(int j=0;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 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 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
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define LL long long
#define eps 1e-6
#define inf 999999.0
#define zero(a) fabs(a) #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 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 ret=max(ret,dist(p[i],cen)

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