首页 > 代码库 > hdu3694 Fermat Point in Quadrangle 求四边形费马点
hdu3694 Fermat Point in Quadrangle 求四边形费马点
http://acm.hdu.edu.cn/showproblem.php?pid=3694
Fermat Point in Quadrangle
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 1973 Accepted Submission(s): 361
Problem Description
In geometry the Fermat point of a triangle, also called Torricelli point, is a point such that the total distance from the three vertices of the triangle to the point is the minimum. It is so named because this problem is first raised by Fermat in a private letter. In the following picture, P0 is the Fermat point. You may have already known the property that:
Alice and Bob are learning geometry. Recently they are studying about the Fermat Point.
Alice: I wonder whether there is a similar point for quadrangle.
Bob: I think there must exist one.
Alice: Then how to know where it is? How to prove?
Bob: I don’t know. Wait… the point may hold the similar property as the case in triangle.
Alice: It sounds reasonable. Why not use our computer to solve the problem? Find the Fermat point, and then verify your assumption.
Bob: A good idea.
So they ask you, the best programmer, to solve it. Find the Fermat point for a quadrangle, i.e. find a point such that the total distance from the four vertices of the quadrangle to that point is the minimum.
Alice and Bob are learning geometry. Recently they are studying about the Fermat Point.
Alice: I wonder whether there is a similar point for quadrangle.
Bob: I think there must exist one.
Alice: Then how to know where it is? How to prove?
Bob: I don’t know. Wait… the point may hold the similar property as the case in triangle.
Alice: It sounds reasonable. Why not use our computer to solve the problem? Find the Fermat point, and then verify your assumption.
Bob: A good idea.
So they ask you, the best programmer, to solve it. Find the Fermat point for a quadrangle, i.e. find a point such that the total distance from the four vertices of the quadrangle to that point is the minimum.
Input
The input contains no more than 1000 test cases.
Each test case is a single line which contains eight float numbers, and it is formatted as below:
x1 y1 x2 y2 x3 y3 x4 y4
xi, yi are the x- and y-coordinates of the ith vertices of a quadrangle. They are float numbers and satisfy 0 ≤ xi ≤ 1000 and 0 ≤ yi ≤ 1000 (i = 1, …, 4).
The input is ended by eight -1.
Each test case is a single line which contains eight float numbers, and it is formatted as below:
x1 y1 x2 y2 x3 y3 x4 y4
xi, yi are the x- and y-coordinates of the ith vertices of a quadrangle. They are float numbers and satisfy 0 ≤ xi ≤ 1000 and 0 ≤ yi ≤ 1000 (i = 1, …, 4).
The input is ended by eight -1.
Output
For each test case, find the Fermat point, and output the total distance from the four vertices to that point. The result should be rounded to four digits after the decimal point.
Sample Input
0 0 1 1 1 0 0 1 1 1 1 1 1 1 1 1 -1 -1 -1 -1 -1 -1 -1 -1
Sample Output
2.8284 0.0000
Source
2010 Asia Fuzhou Regional Contest
题意:给个四边形我,问一个点到四边形四个点距离最小的距离和是多少。
分析:如果是凸四边形,费马点就是对角线的交点,距离就是对角线长度。这个很好证明。。
如果是凹多边形,费马点就是那个凹点,看图:
首先CD上的任意点距离肯定大于D点的。然后对于任意点E,它的距离和大于F的。
一个是FA+FD+FC+FB 一个是EA+EB+ED+EC 由三角形两边和大于第三边EA+EB>FA+FB EA=EF+FA EF+EB>FB得证。。
具体实现的时候弱求了个凸包,由于有重点等的情况当凸包点数<=3时枚举的点求最小距离。
/** * @author neko01 */ //#pragma comment(linker, "/STACK:102400000,102400000") #include <cstdio> #include <cstring> #include <string.h> #include <iostream> #include <algorithm> #include <queue> #include <vector> #include <cmath> #include <set> #include <map> using namespace std; typedef long long LL; #define min3(a,b,c) min(a,min(b,c)) #define max3(a,b,c) max(a,max(b,c)) #define pb push_back #define mp(a,b) make_pair(a,b) #define clr(a) memset(a,0,sizeof a) #define clr1(a) memset(a,-1,sizeof a) #define dbg(a) printf("%d\n",a) typedef pair<int,int> pp; const double eps=1e-8; const double pi=acos(-1.0); const int INF=0x7fffffff; const LL inf=(((LL)1)<<61)+5; int dcmp(double x) { if(fabs(x)<eps) return 0; if(x>0) return 1; return -1; } struct point{ double x,y; point(double x=0,double y=0):x(x),y(y) {} }; point operator +(const point &a,const point &b){ return point(a.x+b.x,a.y+b.y); } point operator -(const point &a,const point &b){ return point(a.x-b.x,a.y-b.y); } point operator *(const point &a,const double &p){ return point(a.x*p,a.y*p); } point operator /(const point &a,const double &p){ return point(a.x/p,a.y/p); } bool operator < (const point &a,const point &b){ return a.x<b.x||(a.x==b.x&&a.y<b.y); } double dot(point A,point B){ return A.x*B.x+A.y*B.y; } double cross(point A,point B){ return A.x*B.y-A.y*B.x; } double Length(point A){ return sqrt(dot(A,A)); } int graham(point *p,int n,point *ch) //凸包 { sort(p,p+n); int m=0; for(int i=0;i<n;i++) { while(m>1&&cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0) m--; ch[m++]=p[i]; } int k=m; for(int i=n-2;i>=0;i--) { while(m>k&&cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0) m--; ch[m++]=p[i]; } if(n>1) m--; return m; } int main() { point p[5],ch[5]; while(true) { for(int i=0;i<4;i++) scanf("%lf%lf",&p[i].x,&p[i].y); if(p[0].x==-1) break; int m=graham(p,4,ch); double ans=1.0*INF; if(m<=3) { for(int i=0;i<4;i++) { double sum=0; for(int j=0;j<4;j++) { if(j==i) continue; sum+=Length(p[i]-p[j]); } if(sum<ans) ans=sum; } } else ans=Length(ch[0]-ch[2])+Length(ch[1]-ch[3]); printf("%.4lf\n",ans); } return 0; }
hdu3694 Fermat Point in Quadrangle 求四边形费马点
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。