題意

給N個(gè)點(diǎn)，求最小的圓將這N個(gè)點(diǎn)全部覆蓋，輸出圓心坐標(biāo)和半徑

分析

最小的圓肯定落在三個(gè)點(diǎn)上，因此暴力枚舉圓上的三個(gè)點(diǎn)即可，點(diǎn)增量算法O(n ^ 3),加入隨機(jī)化,平均復(fù)雜度可以降到O(n^2)

#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; //ZOJ1450 最小圓覆蓋 struct POINT{double x,y; }p[110]; 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)); } //求三點(diǎn)外接圓的圓心 POINT circumcenter(POINT &a,POINT &b,POINT &c){POINT ret;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;ret.x=a.x+(c1*b2-c2*b1)/d;ret.y=a.y+(a1*c2-a2*c1)/d;return ret; } //最小的圓肯定落在三個(gè)點(diǎn)上，因此暴力枚舉圓上的三個(gè)點(diǎn)即可 //點(diǎn)增量算法O(n^3),加入隨機(jī)化,平均復(fù)雜度可以降到O(n^2) void solve(){random_shuffle(p,p+n);//隨機(jī)化序列，std里的隨機(jī)函數(shù)POINT c;double r=0;for(int i=1;i<n;i++){//第一層if(dist(p[i],c)<=r) continue;c=p[i];r=0;for(int j=0;j<i;j++){//第二層if(dist(p[j],c)<=r) continue;c.x=(p[i].x+p[j].x)/2;c.y=(p[i].y+p[j].y)/2;r=dist(p[j],c);for(int k=0;k<j;k++){//第三層if(dist(p[k],c)<=r) continue;c=circumcenter(p[i],p[j],p[k]);r=dist(p[i],c);}}}printf("%.2lf %.2lf %.2lf\n",c.x,c.y,r); } int main(){while(scanf("%d",&n)!=EOF&&n){for(int i=0;i<n;i++){scanf("%lf%lf",&p[i].x,&p[i].y);}solve();}return 0; }

總結(jié)

以上是生活随笔為你收集整理的ZOJ - 1450 Minimal Circle HDU - 3007 Buried memory 最小圆覆盖模板 【随机函数】【增量法】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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