POJThe Doors AND NYIST 有趣的问题

题目链接：Click Here~

题目分析：

给你横纵坐标分别表示门所在的位置。叫你求出从起点到终点的最短距离。

算法分析：

该题好像有多种解法，我仅仅说我做的。

我用的是几何+图论。

建模分析：

1、先推断两个点之间能否够连接。

2、推断两个点能否够链接的方法是用是否推断墙与这两点连成的线段是否相交。

3、假设没有相交则直接连接。

4、最后最短路求出结果就好了

    #include <iostream>
    #include <algorithm>
    #include <queue>
    #include <cstdio>
    #include <cstring>
    #include <cmath>
    using namespace std;

    const double eps = 1e-8;
    const double INF = 9999999;
    const int MAXN = 200;
    struct Point{
        double x,y;
    }p[MAXN];
    struct Segment{
        Point A,B;
    }seg[MAXN];
    double graph[MAXN][MAXN];
    double Dist(const Point &a,const Point &b)
    {
        return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
    }
    int dblcmp(double x)
    {
        if(fabs(x)<eps)
            return 0;
        return x>0?
1:-1;
    }
    double det(double x1,double y1,double x2,double y2)
    {
        return x1*y2-x2*y1;
    }
    double cross(const Point &a,const Point &b,const Point &c)
    {
        return det(a.x-c.x,a.y-c.y,b.x-c.x,b.y-c.y);
    }
    bool segcross(const Point &a,const Point &b,const Segment &s)
    {
        int d1,d2,d3,d4;
        d1 = dblcmp(cross(s.A,s.B,a));
        d2 = dblcmp(cross(s.A,s.B,b));
        d3 = dblcmp(cross(a,b,s.A));
        d4 = dblcmp(cross(a,b,s.B));
        if((d1^d2)==-2&&(d3^d4)==-2)
            return true;
        return false;

    }
    bool Check(int i,int j,int k)
    {
          if(p[i].x!=p[j].x&&p[i].x!=seg[k].A.x&&p[j].x!=seg[k].A.x&&segcross(p[i],p[j],seg[k]))
            return true;
          return false;
    }
    double Spfa(int s,int e)
    {
        bool inq[MAXN];
        double d[MAXN];
        for(int i = 0;i <= e;++i){
            inq[i] = false;
            d[i] = INF;
        }
        d[s] = 0; inq[s] = true;

        queue<int> Q;
        Q.push(s);
        while(!Q.empty()){
            int u = Q.front();
            Q.pop();
            inq[u] = false;
            for(int i = 0;i <= e;++i){
               if(d[i] > d[u]+graph[u][i]){
                   d[i] = d[u] + graph[u][i];
                   if(!inq[i]){
                      inq[i] = true;
                      Q.push(i);
                   }
               }
            }
        }
        return d[e];
    }
    int main()
    {
        int n,t;
        while(scanf("%d",&n),n+1)
        {
            t = 4*n+1;
            p[0].x = 0; p[0].y = 5;
            p[t].x = 10; p[t].y = 5;
            double x,a,b,c,d;
            for(int i = 0;i < n;++i){
                scanf("%lf%lf%lf%lf%lf",&x,&a,&b,&c,&d);
                p[i*4+1].x = x; p[i*4+1].y = a;
                p[i*4+2].x = x; p[i*4+2].y = b;
                p[i*4+3].x = x; p[i*4+3].y = c;
                p[i*4+4].x = x; p[i*4+4].y = d;
                //把墙分成三个线段
                seg[i*3].A.x = x; seg[i*3].A.y = 0;
                seg[i*3].B.x = x; seg[i*3].B.y = a;
                seg[i*3+1].A.x = x; seg[i*3+1].A.y = b;
                seg[i*3+1].B.x = x; seg[i*3+1].B.y = c;
                seg[i*3+2].A.x = x; seg[i*3+2].A.y = d;
                seg[i*3+2].B.x = x; seg[i*3+2].B.y = 10;
            }
            for(int i = 0;i <= t;++i)
                for(int j = 0;j <= t;++j)
                   graph[i][j] = INF;
            for(int i = 0;i < t;++i){
                for(int j = i+1;j <= t;++j){
                    bool flag = true;
                    for(int k = 0;k < 3*n;++k){
                        if(Check(i,j,k)){
                            flag = false;
                            break;
                        }
                    }
                    if(flag){
                        graph[i][j] = Dist(p[i],p[j]);
                    }
                }
            }
            printf("%.2lf
",Spfa(0,t));
        }
        return 0;
    }