最小覆蓋圓算法地址：http://soft.cs.tsinghua.edu.cn/blog/?q=node/1066

平面點(diǎn)集的最小包圍圓
1、?????????? 問(wèn)題背景
?
考察固定在工作平臺(tái)上的一直機(jī)械手，要撿起散落在不同位置的多個(gè)零件，并送到別的地方。那么，這只機(jī)械手的底座應(yīng)該選在哪里呢？根據(jù)直覺(jué)，應(yīng)該選在機(jī)械手需夠著的那些位置的“中心”。準(zhǔn)確地講，也就是包圍這些點(diǎn)的那個(gè)最小圓的圓心----該位置的好處是，可使機(jī)械手的底座到它需要夠著的那些點(diǎn)的最大距離最小化。于是可得如下問(wèn)題：給定由平面上n個(gè)點(diǎn)所組成的一個(gè)集合P（對(duì)應(yīng)于機(jī)械手需要夠著的工作平臺(tái)的那些位置），試找出P的最小包圍圓（smallest enclosing disc）----亦即，包含P中所有點(diǎn)、半徑最小的那個(gè)圓。這個(gè)最小包圍圓必然是唯一的。
?
2、算法及原理
?
算法介紹：我們本次算法的設(shè)計(jì)是基于這樣一個(gè)簡(jiǎn)單直觀的性質(zhì)：在既定的給定點(diǎn)條件下，如果引入一張新的半平面，只要此前的最優(yōu)解頂點(diǎn)（即唯一確定最小包圍圓的幾個(gè)關(guān)鍵頂點(diǎn)）能夠包含于其中，則不必對(duì)此最優(yōu)解進(jìn)行修改，亦即此亦為新點(diǎn)集的最優(yōu)解；否則，新的最優(yōu)解頂點(diǎn)必然位于這個(gè)新的半空間的邊界上。
定理可以通過(guò)反證法證明。
于是，基于此性質(zhì)，我們便可得到一個(gè)類似于線性規(guī)劃算法的隨機(jī)增量式算法。定義Di為相對(duì)于pi的最小包圍圓。此算法實(shí)現(xiàn)的關(guān)鍵在于對(duì)于pi?Di-1時(shí)的處理。顯然，如果pi∈Di-1，則Di= Di-1；否則，需要對(duì)Di另外更新。而且，Di的組成必然包含了pi；因此，此種情況下的最小包圍圓是過(guò)pi點(diǎn)且覆蓋點(diǎn)集{ p1 ，p2 ，p3 ……pi-1}的最小包圍圓。則仿照上述處理的思路，Di={ p1 ，pi }，逐個(gè)判斷點(diǎn)集{ p2 ，p3 ……pi-1 }，如果存在pj? Di，則Di={pj，pi }。同時(shí)，再依次對(duì)點(diǎn)集{ p1 ，p2 ，p3 ……pj-1 }判斷是否滿足pk∈Di，若有不滿足，則Di={pk ，pj，pi }。由于，三點(diǎn)唯一地確定一個(gè)圓，故而，只需在此基礎(chǔ)上判斷其他的點(diǎn)是否位于此包圍圓內(nèi)，不停地更新pk。當(dāng)最內(nèi)層循環(huán)完成時(shí)，退出循環(huán)，轉(zhuǎn)而更新pj；當(dāng)次內(nèi)層循環(huán)結(jié)束時(shí)，退出循環(huán)，更新pi。當(dāng)i=n時(shí)，表明對(duì)所有的頂點(diǎn)均已處理過(guò) ，此時(shí)的Dn即表示覆蓋了給定n個(gè)點(diǎn)的最小包圍圓。

#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> #include<cmath> using namespace std;const double eps = 1e-8;struct node{double x,y; };struct node p[1005],central; double R; int n;double dist(struct node a,struct node b){return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); }//求外接圓圓心,根據(jù)三邊相等 struct node circumcenter(struct node a,struct node b,struct node 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;struct node tmp;tmp.x = a.x + (c1*b2-c2*b1)/d ;tmp.y = a.y+(a1*c2-a2*c1)/d;return tmp; }void min_cover_circle(){random_shuffle(p,p+n); central = p[0];int i,j,k;R=0;for(i=1;i<n;i++){if(dist(central,p[i])+eps>R){central = p[i];R=0;for(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(k=0;k<j;k++){if(dist(central,p[k])+eps>R){central=circumcenter(p[i],p[j],p[k]);R=dist(central,p[k]);}}}}}} }int main(){double x,y;while(scanf("%lf%lf%d",&x,&y,&n)!=EOF){int i;for(i=0;i<n;i++){scanf("%lf%lf",&p[i].x,&p[i].y);}min_cover_circle();printf("(%.1lf,%.1lf).\n%.1lf\n",central.x,central.y,R);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的平面点集的最小包围圆 hdu 3932的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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