The Doors - POJ 1556 (线段相交)

题目大意：有一个房间（左上角（0，10），右下角（10,0）），然后房间里有N面墙，每面墙上都有两个门，求出来从初始点（0,5），到达终点（10，5）的最短距离。

 

分析：很明显根据两点之间直线最短，所以所走的路线一定是点之间的连线，只需要判断一下这两点间知否有墙即可。

 

代码如下：

======================================================================================================================================

#include<math.h>

#include<algorithm>

#include<stdio.h>

using namespace std;

const int MAXN = ;

const double oo = 1e9+;

const double EPS = 1e-;

struct point

{

    double x, y, len;

    point(double x=, double y=, double len=):x(x),y(y),len(len){}

    point operator - (const point &t) const{

        return point(x-t.x, y-t.y);

    }

    int operator *(const point &t) const{

        double c = x*t.y - y*t.x;

        if(c > EPS)return ;

        if(fabs(c)<EPS)return ;

        return -;

    }

};

struct Wall

{

    point A, B;

    Wall(point A=, point B=):A(A), B(B){}

};

bool CanLine(point a, point b, Wall w[], int N)

{

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

    {

        if( w[i].A.x < b.x || w[i].A.x > a.x )

            continue;

        int t = (a-b)*(w[i].A-b) + (a-b)*(w[i].B-b);

        if(t == )

            return false;

    }

    return true;

}

int main()

{

    int M;

    while(scanf("%d", &M) != EOF && M != -)

    {

        int i, j, nw=, np=;

        double x, y[];

        Wall w[MAXN]; point p[MAXN];

        p[] = point(, , );

        while(M--)

        {

            scanf("%lf%lf%lf%lf%lf", &x, &y[], &y[], &y[], &y[]);

            p[np++] = point(x, y[], oo), p[np++] = point(x, y[], oo);

            p[np++] = point(x, y[], oo), p[np++] = point(x, y[], oo);

            w[nw++] = Wall(point(x,   -), point(x, y[]));

            w[nw++] = Wall(point(x, y[]), point(x, y[]));

            w[nw++] = Wall(point(x, y[]), point(x,   ));

        }

        p[np++] = point(, , oo);

        for(i=; i<np; i++)

        for(j=; j<i;  j++)

        {

            point t = p[i] - p[j];

            t.len = sqrt(t.x*t.x+t.y*t.y);

            if(p[i].len > t.len + p[j].len && CanLine(p[i], p[j], w, nw) == true)

                p[i].len = t.len + p[j].len;

        }

        printf("%.2f\n", p[np-].len);

    }

    return ;

}