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=100;
const double eps=1e-8;
const double inf=1e20;
int n;
double dist[maxn][maxn];

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

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))<=0&&
        sgn((l2.s-l1.s)^(l1.e-l1.s))*sgn((l2.e-l1.s)^(l1.e-l1.s))<=0;
}

double dis(Point a,Point b){
    return sqrt((b-a)*(b-a));
}

int main(){
    while(scanf("%d",&n),n!=-1){
        double x,yy1,yy2,yy3,yy4;
        for(int i=1;i<=n;++i){
            scanf("%lf%lf%lf%lf%lf",&x,&yy1,&yy2,&yy3,&yy4);
            line[2*i-1]=Line(Point(x,yy1),Point(x,yy2));
            line[2*i]=Line(Point(x,yy3),Point(x,yy4));
        }
        for(int i=0;i<=4*n+1;++i)
            for(int j=0;j<=4*n+1;++j)
                if(i==j) dist[i][j]=0;
                else dist[i][j]=inf;
        for(int i=1;i<=4*n;++i){
            int id=(i+3)/4;
            Point tmp;
            if(i&1) tmp=line[(i+1)/2].s;
            else tmp=line[(i+1)/2].e;
            int flag=1;
            for(int j=1;j<id;++j)
                if(!inter(Line(Point(0,5),tmp),line[2*j-1])&&
                        !inter(Line(Point(0,5),tmp),line[2*j])){
                    flag=0;break;
                }
            if(flag) dist[0][i]=dist[i][0]=dis(Point(0,5),tmp);
            flag=1;
            for(int j=id+1;j<=n;++j)
                if(!inter(Line(tmp,Point(10,5)),line[2*j-1])&&
                        !inter(Line(tmp,Point(10,5)),line[2*j])){
                    flag=0;break;
                }
            if(flag) dist[4*n+1][i]=dist[i][4*n+1]=dis(tmp,Point(10,5));
        }
        for(int i=1;i<=4*n;++i)
            for(int j=i+1;j<=4*n;++j){
                int id1=(i+3)/4,id2=(j+3)/4;
                int flag=1;
                Point p1,p2;
                if(i&1) p1=line[(i+1)/2].s;
                else p1=line[(i+1)/2].e;
                if(j&1) p2=line[(j+1)/2].s;
                else p2=line[(j+1)/2].e;
                for(int k=id1+1;k<id2;++k)
                    if(!inter(Line(p1,p2),line[2*k-1])&&
                            !inter(Line(p1,p2),line[2*k])){
                        flag=0;break;
                    }
                if(flag) dist[i][j]=dist[j][i]=dis(p1,p2);
            }
        int flag=1;
        for(int i=1;i<=n;++i)
            if(!inter(Line(Point(0,5),Point(10,5)),line[2*i-1])&&
                    !inter(Line(Point(0,5),Point(10,5)),line[2*i])){
                flag=0;break;
            }
        if(flag) dist[0][4*n+1]=dist[4*n+1][0]=10;
        for(int k=0;k<=4*n+1;++k)
            for(int i=0;i<=4*n+1;++i)
                for(int j=0;j<=4*n+1;++j)
                    dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);
        printf("%.2f
",dist[0][4*n+1]);
    }
    return 0;
}