Find new house 四边形费马点

3rd 吉林 省赛 E find new house 费马点

Edward had four friends living in X city, he was the only person among them who
live in Y city, five of them were very good friends, and he hoped that he would be
close to them. Now his wish can come true. His work is transferred to the X city, and
he also had the enough money to buy a house in the new city. But his friends hope
that the sum of distance from Edward¡¯s house to other four houses is the shortest
among all possible, so his friend would spend less time going to his house and
enjoying themselves. Can you help them?
Input
Each case consists of a line consists eight double numbers: x1, y1, x2, y2, x3, y3, x4,
y4, and xi, yi are the x- and y-coordinates of the i-th friend.
Output
For each case, output a single line containing the minimum sum of the distances from
his new house to other four friends. Keep two digits after the decimal point.
Sample Input
0 1 0 -1 1 0 -1 0
Sample Output
4.00
   一个平面几何题：求一点使得到平面中已知四点的距离之和最小。（所谓费马点）
   当四边形为凸四边形时，容易证明对角线交点即为费马点；当为凹四边形时，费马点为凹点。
   理论是这样，编程时也不用判断凹凸。代码见下

#include
#include
double _min(double a,double b){return a>b?b:a;}
struct Point
{
       double x,y;
};
int dblcmp(double d)
{
    if(fabs(d)<1e-8) return 0;
    return d>0?1:-1;
}
double det(double x1,double y1,double x2,double y2)
{
       return x1*y2-x2*y1;
}
double cross(Point a,Point b,Point c)
{
       return det(b.x-a.x,b.y-a.y,c.x-a.x,c.y-a.y);
}
int Segcross(Point a,Point b,Point c,Point d)
{
    return (dblcmp(cross(a,c,d))^dblcmp(cross(b,c,d)))==-2 &&
           (dblcmp(cross(c,a,b))^dblcmp(cross(d,a,b)))==-2;
}
double Seglen(Point a,Point b)
{
       return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
int main()
{
    Point f1,f2,f3,f4;
    while(scanf("%lf%lf%lf%lf%lf%lf%lf%lf",&f1.x,&f1.y,&f2.x,&f2.y,&f3.x,&f3.y,&f4.x,&f4.y)!=EOF)   
    {
           double ans=1<<30;
           if(Segcross(f1,f2,f3,f4))
           {
                 ans=_min(ans,Seglen(f1,f2)+Seglen(f3,f4));
           }
           if(Segcross(f1,f3,f2,f4))
           {
                 ans=_min(ans,Seglen(f1,f3)+Seglen(f2,f4));
           }
           if(Segcross(f1,f4,f2,f3))
           {
                 ans=_min(ans,Seglen(f1,f4)+Seglen(f2,f3));
           }
           ans=_min(ans,Seglen(f1,f2)+Seglen(f1,f3)+Seglen(f1,f4));
           ans=_min(ans,Seglen(f2,f1)+Seglen(f2,f3)+Seglen(f2,f4));
           ans=_min(ans,Seglen(f3,f1)+Seglen(f3,f2)+Seglen(f3,f4));
           ans=_min(ans,Seglen(f4,f1)+Seglen(f4,f2)+Seglen(f3,f4));
           printf("%.2lf/n",ans);
    }
}
     一句话：好好学数学。

---------------------------------------------------------------------------------------------

2010ACM/ICPC福州区域赛E题Fermat Point in Quadrangle

可以用模拟退火算法解

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！