程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU 3694 Fermat Point in Quadrangle （費馬定理求四邊形的費馬點）

HDU 3694 Fermat Point in Quadrangle （費馬定理求四邊形的費馬點）

編輯：C++入門知識

題意：給你四個點，找出一個點到四個點的距離最小

四邊形的費馬點：凸邊形是兩對角線的交點，凹邊形式凹點。

PS：

三角形的費馬點：

1.若三角形3個內角均小於120°，那麼3條距離連線正好三等分費馬點所在的周角，即該點所對三角形三邊的張角相等，均為120°。所以三角形的費馬點也稱為三角形的等角中心。

2.若三角形有一內角大於等於120°，則此鈍角的頂點就是距離和最小的點。

#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
const int kind = 26;
const int maxn = 250*1000; //注意RE,單詞長度*單詞個數
const int M = 5100000;
struct Point    
{    
    double x,y;    
};    
//小於0,說明向量p0p1的極角大於p0p2的極角    
double multiply(Point p1,Point p2,Point p0)    
{    
    return((p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y));    
}    
    
double dis(Point p1,Point p2)    
{    
    return(sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y)));    
}    
void Graham_scan(Point PointSet[],Point ch[],int n,int &len)    
{    
    int i,j,k=0,top=2;    
    Point tmp;    
    
    //找到最下且偏左的那個點    
    for(i=1;i0)    
                ||((multiply(PointSet[j],PointSet[k],PointSet[0])==0)    
                    &&(dis(PointSet[0],PointSet[j])=0) top--;    
        //當前點與棧內所有點滿足向左關系,因此入棧.    
        ch[++top]=PointSet[i];    
    }    
    len=top+1;    
}    
Point intersection(Point u1,Point u2,Point v1,Point v2)
{
    Point ret=u1;
    double t=((u1.x-v1.x)*(v1.y-v2.y)-(u1.y-v1.y)*(v1.x-v2.x))
        /((u1.x-u2.x)*(v1.y-v2.y)-(u1.y-u2.y)*(v1.x-v2.x));
    ret.x+=(u2.x-u1.x)*t;
    ret.y+=(u2.y-u1.y)*t;
    return ret;
}
Point p[4],ch[4],point;
int len;
int main()
{
    int x1, y1, x2, y2, x3, y3, x4, y4;
    int x[4],y[4];
    while(scanf("%lf%lf",&p[0].x,&p[0].y))
    {
        int flag=0;
        if(p[0].x!=-1||p[0].y!=-1) flag=1;
        for(int i=1;i<4;i++)
        {
            scanf("%lf%lf",&p[i].x,&p[i].y);
            if(p[i].x!=-1||p[i].y!=-1)
                flag=1;
        }
        if(!flag) break;
        double minn=10000000,ans=0.0;
        int k=0;
        Graham_scan(p,ch,4,len);
        for(int i=0;i<4;i++)
        {
            ans=0.0;
            for(int j=0;j<4;j++)
            {
                ans+=dis(p[i],p[j]);
            }
            if(ans