POJ 2069最小球覆蓋

1.給定N個三維點，要求覆蓋這些點的最小球半徑； 2.采用模擬淬火算法，隨機選取一個點作為初始解，然后不斷向當(dāng)前最遠的點靠近； 3.這是一個不斷調(diào)整的過程，對應(yīng)模擬淬火算法中不斷向內(nèi)能最低這一目標函數(shù)（半徑最小）逼近，溫度對應(yīng)控制變量

• 對于一個點，球心就是這個點，且半徑無窮小
• 對于兩個點，球心就是兩點線段的中點，半徑就是線段長度的一半
• 對于三個點，三點構(gòu)成的平面必為球的大圓，球心是三角形的外心，半徑就是球心到某個點的距離
• 對于四個點，若四點共面，則轉(zhuǎn)換到3點共面；若四點不共面，四面體可以唯一確定一個外接球
• 對于五個點及五個點以上，最小球必為某四個點的外接球

#include<iostream> #include<map> #include<string> #include<cstring> #include<vector> #include<algorithm> #include<set> #include<sstream> #include<cstdio> #include<cmath> #include<climits> #include<cstdlib> using namespace std; const double eps=1e-3; //POJ2069 最小球覆蓋 struct POINT{double x,y,z; }p[110];//N個點 POINT op;//最小球的球心 int n; inline double dist(POINT &a,POINT &b){//兩點距離return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)+(a.z-b.z)*(a.z-b.z)); } double solve(){double ret,delta=100.0;//溫度double maxDis,tempDis;int i,id;while(delta>eps){id=0;maxDis=dist(op,p[id]);for(i=1;i<n;i++){tempDis=dist(op,p[i]);if(tempDis>maxDis){maxDis=tempDis;id=i;}}ret=maxDis;op.x+=(p[id].x-op.x)/maxDis*delta;op.y+=(p[id].y-op.y)/maxDis*delta;op.z+=(p[id].z-op.z)/maxDis*delta;delta*=0.98;}return ret;//最小球半徑 } int main(){while(scanf("%d",&n)!=EOF&&n){for(int i=0;i<n;i++){scanf("%lf%lf%lf",&p[i].x,&p[i].y,&p[i].z);}printf("%lf\n", solve());}return 0; }

HDU3007最小圓覆蓋

給定N個二維點，求覆蓋這些點的最小圓半徑

#include<iostream> #include<map> #include<string> #include<cstring> #include<vector> #include<algorithm> #include<set> #include<sstream> #include<cstdio> #include<cmath> #include<climits> #include<cstdlib> using namespace std; const double eps=1e-8; //HDU3001 最小圓覆蓋 struct POINT{double x,y,z; }p[510]; POINT op;//最小圓的圓心 int n; inline double dist(POINT &a,POINT &b){return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); } void solve(){double ret,delta=100.0;double maxDis,tempDis;int i,id;while(delta>eps){id=0;maxDis=dist(op,p[id]);for(i=1;i<n;i++){tempDis=dist(op,p[i]);if(tempDis>maxDis){maxDis=tempDis;id=i;}}ret=maxDis;op.x+=(p[id].x-op.x)/maxDis*delta;op.y+=(p[id].y-op.y)/maxDis*delta;delta*=0.98;}printf("%.2lf %.2lf %.2lf\n",op.x,op.y,ret); } int main(){while(scanf("%d",&n)!=EOF){if(n==0) break;op.x=op.y=0;for(int i=0;i<n;i++){scanf("%lf%lf",&p[i].x,&p[i].y);op.x+=p[i].x;op.y+=p[i].y;}op.x/=n;op.y/=n;solve();}return 0; }

總結(jié)

以上是生活随笔為你收集整理的POJ 2069最小球覆盖 HDU3007最小圆覆盖【模拟淬火算法】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。