poj1556 The Doors（叉积判断线段相交）

题目链接：https://vjudge.net/problem/POJ-1556

题意:在一个矩形内，起点(0,5)和终点(10,5)是固定的，中间有n个道墙(n<=18)，每道墙有两个門，求起点到终点的最短路。

思路：

　　最多有4*n+2个点，枚举所有点对(p1,p2)，用叉积判断线段p1p2和中间的墙是否相交，不相交那么更新距离为两点的距离，否则为inf。更新所有的边之后用floyd得到最短路。答案即dist[0][4*n+1]。时间复杂度O(n^3)。

AC code：

#include<cstdio>

#include<algorithm>

#include<cmath>

#include<cstdlib>

using namespace std;

const int maxn=;

const double eps=1e-;

const double inf=1e20;

int n;

double dist[maxn][maxn];

int sgn(double x){

    if(abs(x)<eps) return ;

    if(x<) return -;

    return ;

}

struct Point{

    double x,y;

    Point(){}

    Point(double xx,double yy):x(xx),y(yy){}

    Point operator + (const Point& b){

        return Point(x+b.x,y+b.y);

    }

    Point operator - (const Point& b){

        return Point(x-b.x,y-b.y);

    }

    double operator * (const Point& b){

        return x*b.x+y*b.y;

    }

    double operator ^ (const Point& b){

        return x*b.y-b.x*y;

    }

};

struct Line{

    Point s,e;

    Line(){}

    Line(Point ss,Point ee){

        s=ss,e=ee;

    }

}line[maxn];

bool inter(Line l1,Line l2){

    return

        max(l1.s.x,l1.e.x)>=min(l2.s.x,l2.e.x)&&

        max(l2.s.x,l2.e.x)>=min(l1.s.x,l1.e.x)&&

        max(l1.s.y,l1.e.y)>=min(l2.s.y,l2.e.y)&&

        max(l2.s.y,l2.e.y)>=min(l1.s.y,l1.e.y)&&

        sgn((l1.s-l2.s)^(l2.e-l2.s))*sgn((l1.e-l2.s)^(l2.e-l2.s))<=&&

        sgn((l2.s-l1.s)^(l1.e-l1.s))*sgn((l2.e-l1.s)^(l1.e-l1.s))<=;

}

double dis(Point a,Point b){

    return sqrt((b-a)*(b-a));

}

int main(){

    while(scanf("%d",&n),n!=-){

        double x,yy1,yy2,yy3,yy4;

        for(int i=;i<=n;++i){

            scanf("%lf%lf%lf%lf%lf",&x,&yy1,&yy2,&yy3,&yy4);

            line[*i-]=Line(Point(x,yy1),Point(x,yy2));

            line[*i]=Line(Point(x,yy3),Point(x,yy4));

        }

        for(int i=;i<=*n+;++i)

            for(int j=;j<=*n+;++j)

                if(i==j) dist[i][j]=;

                else dist[i][j]=inf;

        for(int i=;i<=*n;++i){

            int id=(i+)/;

            Point tmp;

            if(i&) tmp=line[(i+)/].s;

            else tmp=line[(i+)/].e;

            int flag=;

            for(int j=;j<id;++j)

                if(!inter(Line(Point(,),tmp),line[*j-])&&

                        !inter(Line(Point(,),tmp),line[*j])){

                    flag=;break;

                }

            if(flag) dist[][i]=dist[i][]=dis(Point(,),tmp);

            flag=;

            for(int j=id+;j<=n;++j)

                if(!inter(Line(tmp,Point(,)),line[*j-])&&

                        !inter(Line(tmp,Point(,)),line[*j])){

                    flag=;break;

                }

            if(flag) dist[*n+][i]=dist[i][*n+]=dis(tmp,Point(,));

        }

        for(int i=;i<=*n;++i)

            for(int j=i+;j<=*n;++j){

                int id1=(i+)/,id2=(j+)/;

                int flag=;

                Point p1,p2;

                if(i&) p1=line[(i+)/].s;

                else p1=line[(i+)/].e;

                if(j&) p2=line[(j+)/].s;

                else p2=line[(j+)/].e;

                for(int k=id1+;k<id2;++k)

                    if(!inter(Line(p1,p2),line[*k-])&&

                            !inter(Line(p1,p2),line[*k])){

                        flag=;break;

                    }

                if(flag) dist[i][j]=dist[j][i]=dis(p1,p2);

            }

        int flag=;

        for(int i=;i<=n;++i)

            if(!inter(Line(Point(,),Point(,)),line[*i-])&&

                    !inter(Line(Point(,),Point(,)),line[*i])){

                flag=;break;

            }

        if(flag) dist[][*n+]=dist[*n+][]=;

        for(int k=;k<=*n+;++k)

            for(int i=;i<=*n+;++i)

                for(int j=;j<=*n+;++j)

                    dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);

        printf("%.2f\n",dist[][*n+]);

    }

    return ;

}