POJ 1556 The Doors(计算几何+最短路)

梦里梦外; 2022-05-18 06:07 159阅读 0赞

[题目链接][Link 1]

题目大意：有一个10\*10的正方形房间中间用墙隔开，每个墙上有两个门给出门的两个端点的坐标求从左边中点走到右边中点所需要的最短路程。

分析：计算每个墙的端点和其他墙的端点的距离(包括起点和终点)，如果中间没有墙挡住。则它们的距离就是它们的直线距离，如果中间有墙挡住，则它们之间的距离，设置为无法到达，然后用最短路跑一遍求得左边中点到右边中点的距离。

#include<map>
    #include<set>
    #include<cmath>
    #include<queue>
    #include<stack>
    #include<cstdio>
    #include<vector>
    #include<iomanip>
    #include<utility>
    #include<cctype>
    #include<cstring>
    #include<cstdlib>
    #include<iostream>
    #include<algorithm>
    #define inf 0x3f3f3f3f
    #define Clear(x) memset(x,0,sizeof(x))
    #define fup(i,a,b) for(int i=a;i<b;i++)
    #define rfup(i,a,b) for(int i=a;i<=b;i++)
    #define fdn(i,a,b) for(int i=a;i>b;i--)
    #define rfdn(i,a,b) for(int i=a;i>=b;i--)
    typedef long long ll;
    using namespace std;
    const double pi=acos(-1.0);
    const int maxn = 1e2+7;
    const double eps = 1e-8;
    int vis[maxn];
    double dis[maxn],mp[maxn][maxn];
    int pcnt,lcnt;
     
    int sgn(double x)
    {
        if(fabs(x)<eps) return 0;
        else return x<0?-1:1;
    }
     
    struct Point{
        double x,y;
        Point(){}
        Point (double _x,double _y){x=_x;y=_y;}
    }p[maxn];
     
    struct Line{
        Point s,e;
        Line(){}
        Line(Point _s,Point _e){s=_s;e=_e;}
    }line[maxn];
     
    double cross(Point a,Point b,Point c)
    {
        a.x-=c.x;a.y-=c.y;
        b.x-=c.x;b.y-=c.y;
        return a.x*b.y-a.y*b.x;
    }
     
    double dist(Point a,Point b)
    {
        return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
    }
     
    bool intersect(Point a,Point b,Line l1)
    {
        int d1=sgn(cross(l1.e,b,a));
        int d2=sgn(cross(l1.s,b,a));
        int d3=sgn(cross(b,l1.s,l1.e));
        int d4=sgn(cross(a,l1.s,l1.e));
        if(d1*d2<0&&d3*d4<0)
            return true;
        return false;
    }
     
    bool check(int x,int y)
    {
        for(int i=0;i<lcnt;i++)
        {
            if(intersect(p[x],p[y],line[i]))
                return false;
        }
        return true;
    }
     
    double dijkstra()
    {
        Clear(vis);
        for(int i=0;i<=pcnt;i++)
            dis[i]=mp[0][i];
        vis[0]=1;
        int u;
        for(int i=0;i<=pcnt-1;i++)
        {
            double mmin = inf;
            for(int j=0;j<=pcnt;j++)
            {
                if(!vis[j]&&dis[j]<mmin)
                {
                    mmin=dis[j];
                    u=j;
                }
            }
            vis[u]=1;
            for(int j=0;j<=pcnt;j++)
            {
                if(dis[j]>dis[u]+mp[u][j])
                    dis[j]=dis[u]+mp[u][j];
            }
        }
        return dis[pcnt];
    }
     
    int main()
    {
        int n;
        double x,y1,y2,y3,y4;
        while(scanf("%d",&n)&&n!=-1)
        {
            Clear(mp);
            pcnt=0,lcnt=0;
            p[pcnt++]=Point(0,5);
            for(int i=0;i<n;i++)
            {
                scanf("%lf%lf%lf%lf%lf",&x,&y1,&y2,&y3,&y4);
                p[pcnt++]=Point(x,y1),p[pcnt++]=Point(x,y2),p[pcnt++]=Point(x,y3),p[pcnt++]=Point(x,y4);
                line[lcnt++]=Line(Point(x,0),p[pcnt-4]);
                line[lcnt++]=Line(p[pcnt-3],p[pcnt-2]);
                line[lcnt++]=Line(p[pcnt-1],Point(x,10));
            }
            p[pcnt]=Point(10,5);
            for(int i=0;i<=pcnt;i++)
            {
                for(int j=0;j<=pcnt;j++)
                {
                    if(i==j) mp[i][j]=0;
                    else if(check(i,j)) mp[i][j]=dist(p[i],p[j]);
                    else mp[i][j]=inf;
                }
            }
            printf("%.2f\n",dijkstra());
        }
        return 0;
    }

[Link 1]: http://poj.org/problem?id=1556