題目鏈接：點擊查看

題目大意：給出四個點，求出該四邊形的費馬點，費馬點是求得一個點，到這四個點的距離最小，最后輸出距離，

題目分析：三分套三分，外層三分x，內(nèi)層三分y即可，不過就是目前來說遇到的所有三分問題都過于玄學(xué)，有時候樣例過不了卻A了，有時候自認(rèn)為沒問題卻WA了數(shù)十發(fā)，這里要改一下以前的書寫習(xí)慣，以前總喜歡這樣寫：

double mid=(l+r)/2;

double mmid=(mid+r)/2;

到目前為止，已經(jīng)因為這樣寫WA了兩個題目了，需要改成這樣寫才能A：

double mid=l+(r-l)/3;

double mmid=r-(r-l)/3;?

嘛。。背過就好了三分就要有三分的樣子，就不要整二分+二分勉強(qiáng)湊三分的那樣寫了，這個題目也算裸題了，一個玄學(xué)裸題，好像也可以用費馬點的方法來求，我在vj上掛的題已經(jīng)T了四發(fā)了，感覺三分也不是那么靠譜。。等學(xué)完了費馬點再把新的代碼掛上：

還有注意一下這個題的eps要設(shè)成1e-7，多了會T少了會WA

三分套三分：

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> #define Pi acos(-1.0) using namespace std;typedef long long LL;const LL inf=0x3f3f3f3f3f3f3f3f;const int N=50;const double eps=1e-7;struct Pos {double x,y; }node[5];double dis(double x,double y) {double ans=0;for(int i=0;i<4;i++)ans+=sqrt((node[i].x-x)*(node[i].x-x)+(node[i].y-y)*(node[i].y-y));return ans; }double check(double x) {double l,r=1000;double ans;while(fabs(l-r)>eps){double mid=l+(r-l)/3;double mmid=r-(r-l)/3;double ans1=dis(x,mid);double ans2=dis(x,mmid);if(ans1>ans2){l=mid;ans=ans2;}else{r=mmid;ans=ans1;}}return ans; }int main() { // freopen("input.txt","r",stdin);while(1){for(int i=0;i<4;i++)scanf("%lf%lf",&node[i].x,&node[i].y);if(node[0].x<0)break;double l=0,r=1000;double ans;while(fabs(l-r)>eps){double mid=l+(r-l)/3;double mmid=r-(r-l)/3;double ans1=check(mid);double ans2=check(mmid);if(ans1>ans2){l=mid;ans=ans2;}else{r=mmid;ans=ans1;}}printf("%.4f\n",ans);}return 0; }

好了我又回來了，學(xué)了一波凸包，大概會用板子了，把poj的那個數(shù)據(jù)比較強(qiáng)的也A掉了

先來說一下費馬點的結(jié)論：

若四邊形為凸邊形，則費馬點為對角線交點

若四邊形為凹邊形，則費馬點為四邊形的其中一個頂點

有了這個結(jié)論就好辦了，我們可以先用Graham算法判斷一下該四邊形是否為凸邊形，若是的話求出對角線距離，不是的話枚舉每一個點到其他三個點的距離，取最小即可

直接求費馬點：

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> #define Pi acos(-1.0) using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=10;int n=4,tot;struct node {double x,y; }a[N],p[N];double dis(node A,node B) //距離 {return sqrt((B.x-A.x)*(B.x-A.x)+(B.y-A.y)*(B.y-A.y)); }double x(node A,node B,node C) //叉積公式 {return (B.x-A.x)*(C.y-A.y)-(C.x-A.x)*(B.y-A.y); }bool cmp(node A,node B) //極角排序 {double pp=x(A,B,a[0]);if(pp>0)return true;if(pp<0) return false;return dis(a[0],A)<dis(a[0],B); }int Graham() //Graham算法 {int k=0;for(int i=1;i<n;i++)if(a[i].y<a[k].y||(a[i].y==a[k].y&&a[i].x<a[k].x))k=i;swap(a[0],a[k]);sort(a+1,a+n,cmp);tot=2;p[0]=a[0],p[1]=a[1];for(int i=2;i<n;i++){while(tot>0&&x(p[tot-2],p[tot-1],a[i])<=0) tot--; //不帶共線的！p[tot++]=a[i];}return tot; }int main() { // freopen("input.txt","r",stdin);while(1){for(int i=0;i<4;i++)scanf("%lf%lf",&a[i].x,&a[i].y);if(a[0].x<0)break;double ans;if(Graham()==4){ans=dis(p[0],p[2])+dis(p[1],p[3]);}else{ans=1e18;for(int i=0;i<4;i++){double temp=0;for(int j=0;j<4;j++)if(i==j)continue;elsetemp+=dis(a[i],a[j]);ans=min(ans,temp);}}printf("%.4f\n",ans);}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的HDU - 3694 Fermat Point in Quadrangle(三分套三分/凸包)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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