1 条题解

  • 1
    @ 2022-7-14 19:56:42
    #include <bits/stdc++.h>
    using namespace std;
    struct wall
    {
        double x,z[5];//存储墙的横坐标与每个点的纵坐标
    }w[22];
    int n;
    double e[101][101];
    bool hathes(int a,int b,int w1,int w2)
    {
        if (b-a<2) return 1;
        double x1=w[a].x,x2=w[b].x,y1=w[a].z[w1],y2=w[b].z[w2];
        double k=(y1-y2)/(x1-x2),t=y1-x1*k;
        for (int i=a+1;i<b;i++)
        {
            double y=k*w[i].x+t;
            if (y<w[i].z[1]||y>w[i].z[2]&&y<w[i].z[3]||y>w[i].z[4]) return 0;
        }
        return 1;
    }
    void addedge(int a,int b,int w1,int w2)
    {
        if (!hathes(a,b,w1,w2)) return;//判断中间是否有墙阻挡
        double x1=w[a].x,x2=w[b].x,y1=w[a].z[w1],y2=w[b].z[w2];
        e[a*4+w1][b*4+w2]=e[b*4+w2][a*4+w1]=sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));//计算两点间距离,建边
    }
    int main()
    {
        cin>>n;
        memset(e,127,sizeof(e));
        for (int i=1;i<=n;i++)
        {
            cin>>w[i].x;
            for (int j=1;j<5;j++) cin>>w[i].z[j];
        }
        w[0].x=0;w[++n].x=10;
        for (int i=1;i<5;i++) w[0].z[i]=w[n].z[i]=5;//初始化起点与终点
        for (int i=0;i<n;i++) for (int j=i+1;j<=n;j++) for (int k=1;k<5;k++) for (int l=1;l<5;l++) addedge(i,j,k,l);//循环建边
        for (int i=0;i<101;i++) e[i][i]=0;
        for (int k=1;k<=n*4+4;k++)
          for (int i=1;i<=n*4+4;i++)
            for (int j=1;j<=n*4+4;j++)
              e[i][j]=min(e[i][j],e[i][k]+e[k][j]);//floyd
        printf("%.2f\n",e[1][n*4+1]);
        return 0;
    }
    
    • 1

    信息

    ID
    355
    时间
    1000ms
    内存
    125MiB
    难度
    4
    标签
    递交数
    2
    已通过
    2
    上传者