題意：

給出四邊形的四個頂點，讓你求出一個點，它到四個頂點的距離之和最小，輸出最小距離。

思路：

四邊形如果是凸四邊形，那么這個點一定是對角線交點，如果不是凸四邊形，那么這個點一定是四個頂點之一。所以每次只要對這五個點分別求一次答案，取最優的即可。

代碼：

#include<cstdio> #include<cstring> #include<iostream> #include<cstring> #include<cstdlib> #include<cmath> #include<string> #include<queue> #include<vector> #include<map> #include<stack> #include<climits> #include<sstream> #include<algorithm> #define eps 1e-8using namespace std;struct Point {double x,y; }point[10];double xmult(Point p1,Point p2,Point p0) {return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y); }Point intersection(Point p1,Point p2,Point p3,Point p4) {Point ret=p1;double t=((p1.x-p3.x)*(p3.y-p4.y)-(p1.y-p3.y)*(p3.x-p4.x))/((p1.x-p2.x)*(p3.y-p4.y)-(p1.y-p2.y)*(p3.x-p4.x));ret.x+=(p2.x-p1.x)*t;ret.y+=(p2.y-p1.y)*t;return ret; }vector<Point> _check; double ans=0.0000;double dis(Point a,Point b) {return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); }void check() {int len=_check.size();for(int i=0;i<len;i++){double tmp=0;for(int j=0;j<4;j++)tmp+=dis(point[j],_check[i]);if(ans-tmp>=eps)ans=tmp;}return ; }int main() {while(scanf("%lf%lf",&point[0].x,&point[0].y)){_check.push_back(point[0]);int flag=0;if(point[0].x==-1&&point[0].y==-1)flag=1;for(int i=1;i<=3;i++){scanf("%lf%lf",&point[i].x,&point[i].y);_check.push_back(point[i]);}if(flag==1&&point[1].x==-1&&point[2].x==-1&&point[3].x==-1&&point[1].y==-1&&point[2].y==-1&&point[3].y==-1)return 0;// for(int i=0;i<4;i++)// printf("%.5lf %.5lf\n",point[i].x,point[i].y);ans=1000000000.0;check();_check.clear();if(xmult(point[0],point[1],point[3])*xmult(point[2],point[1],point[3])<0){Point ans=intersection(point[0],point[2],point[1],point[3]);_check.push_back(ans);}if(xmult(point[1],point[2],point[3])*xmult(point[0],point[2],point[3])<0){Point ans=intersection(point[1],point[0],point[2],point[3]);_check.push_back(ans);}if(xmult(point[2],point[0],point[3])*xmult(point[1],point[0],point[3])<0){Point ans=intersection(point[2],point[1],point[0],point[3]);_check.push_back(ans);}check();printf("%.4lf\n",ans);_check.clear();}return 0; }

總結

以上是生活随笔為你收集整理的hdu3694(四边形的费马点)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。