HDOJ 3694 Fermat Point in Quadrangle

求四边形的费马点

费马点的定义：在平面上的到四边形四个顶点A，B，C，D的点

当ABCD为凸四边形的时候

可以证明M点是费马点，M是对角线的交点

当ABCD为凹四边形的时候

在ABCD四点中有某一个点为费马点

所以，这个点就是个计算几何的模板题啦~~~~~~

我们也不需要判断四边形的凹凸性

把六条线段算出来，判断是不是有交点就好，然后暴力枚举每一个可能性

#include<bits/stdc++.h>
using namespace std;

const double eps=1e-6;
const double inf=1e20;
const double pi=acos(-1.0);
const int maxp=1010;

int sgn(double x){
    if (fabs(x)<eps) return 0;
    if (x<0) return -1;
    else return 1;
}

double sqr(double x){
    return x*x;
}

struct Point{
    double x,y;
    Point(){}
    Point(double _x,double _y){
        x=_x;
        y=_y;
    }
    void input(){
        scanf("%lf%lf",&x,&y);
    }
    void output(){
        printf("%.2lf %.2lf\n",x,y);
    }
    double operator ^ (const Point &b) const{
        return x*b.y-y*b.x;
    }
    double operator * (const Point &b) const{
        return x*b.x+y*b.y;
    }
    double len2(){
        return x*x+y*y;
    }
    double len(){
        return sqrt(x*x+y*y);
    }
    double distance(Point p){
        return hypot(x-p.x,y-p.y);
    }
    Point operator - (const Point &b) const{
        return Point(x-b.x,y-b.y);
    }
    Point operator + (const Point &b) const{
        return Point(x+b.x,y+b.y);
    }
    Point operator * (const double &k) const{
        return Point(x*k,y*k);
    }
    Point operator / (const double &k) const{
        return Point(x/k,y/k);
    }
};

struct Line{
    Point s,e;
    Line(){}
    Line(Point _s,Point _e){
        s=_s;
        e=_e;
    }
    Line(Point p,double angle){
        s=p;
        if (sgn(angle-pi/2)==0) e=(s+Point(0,1));
        else e=(s+Point(1,tan(angle)));
    }
    Line(double a,double b,double c){
        if (sgn(a)==0){
            s=Point(0,-c/b);
            e=Point(1,-c/b);
        }
        else if (sgn(b)==0){
            s=Point(-c/a,0);
            e=Point(-c/a,1);
        }
        else{
            s=Point(0,-c/b);
            e=Point(1,(-c-a)/b);
        }
    }
    void input(){
        s.input();
        e.input();
    }
    int segcrossseg(Line v){
        int d1=sgn((e-s)^(v.s-s));
        int d2=sgn((e-s)^(v.e-s));
        int d3=sgn((v.e-v.s)^(s-v.s));
        int d4=sgn((v.e-v.s)^(e-v.s));
        if ((d1^d2)==-2 && ((d3^d4)==-2) ) return 2;
        return ((d1==0&&sgn((v.s-s)*(v.s-e))<=0) ||
                (d2==0&&sgn((v.e-s)*(v.e-e))<=0) ||
                (d3==0&&sgn((s-v.s)*(s-v.e))<=0) ||
                (d4==0&&sgn((e-v.s)*(e-v.e))<=0));
    }
    Point crosspoint(Line v){
        double a1=(v.e-v.s)^(s-v.s);
        double a2=(v.e-v.s)^(e-v.s);
        return Point((s.x*a2-e.x*a1)/(a2-a1),(s.y*a2-e.y*a1)/(a2-a1));
    }
};

Point A,B,C,D,M;
Line AB,CD,AC,BD,AD,BC;
double ans;

double calc(Point x){
    return A.distance(x)+B.distance(x)+C.distance(x)+D.distance(x);
}

int main(){
    //freopen("input.txt","r",stdin);
    while(1){
        A.input();B.input();C.input();D.input();
        if (A.x==-1&&A.y==-1&&B.x==-1&&B.y==-1&&C.x==-1&&C.y==-1&&D.x==-1&&D.y==-1) break;
        ans=inf;
        ans=min(ans,calc(A));
        ans=min(ans,calc(B));
        ans=min(ans,calc(C));
        ans=min(ans,calc(D));
        AB=Line(A,B);
        CD=Line(C,D);
        if (AB.segcrossseg(CD)>0){
            M=AB.crosspoint(CD);
            ans=min(ans,calc(M));
        }
        AC=Line(A,C);
        BD=Line(B,D);
        if (AC.segcrossseg(BD)>0){
            M=AC.crosspoint(BD);
            ans=min(ans,calc(M));
        }
        AD=Line(A,D);
        BC=Line(B,C);
        if (AD.segcrossseg(BC)>0){
            M=AD.crosspoint(BC);
            ans=min(ans,calc(M));
        }
        printf("%.4lf\n",ans);
    }
    return 0;
}