題目：用最小的圓覆蓋所有的點
以下有兩種方法。
首先是隨機增量算法
------------------------------------------------------------------------------------
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<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(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;
}
