题意:一个10*10的正方形房间内,有一些墙壁,这些墙壁会有两个通道,现在要从点(0 ,5)出发,到达(10,5)。求最短路径。

输入描述:第一行给出墙壁的数量n。接下来n行每行包括5个整数,x,y1,y2,y3,y4,分别代表墙的x坐标(给出的x坐标是递增序),以及两个通道两端的y坐标。当n等于-1时结束程序。


题解:我们把一个墙壁看作是三条线段的组成,起始、结束、以及每个墙壁两个通道的两端看作是点的集合。将每两个点连接起来变成一条直线,之后和所有的墙壁组成的直线做直线相交判断,若没有任何直线与其相连,那么这条边即为联通。然后自己建图,跑最短路即可。


代码:

StatusAccepted
Time16ms
Memory296kB
Length3317
LangC++
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
using namespace std;
const double eps=1e-8;
const int maxn=105;
const double inf=999999;
int dcmp(double x){
    if(fabs(x)<eps)return 0;return x>0?1:-1;
}
struct Point{
    double x, y;
    Point(){}
    Point(double _x, double _y){x=_x,y=_y;}
    Point operator -(const Point &b)const{
        return Point(x-b.x, y-b.y);
    }
    double operator ^(const Point &b)const{
        return x*b.y-y*b.x;
    }
    double operator *(const Point &b)const{
        return x*b.x+y*b.y;
    }
    double distance(Point p){return sqrt((x-p.x)*(x-p.x)+(y-p.y)*(y-p.y));}
};
struct Line{
    Point s, e;
    Line(){}
    Line(Point _s, Point _e){s=_s, e=_e;}
    int segCrossSeg(Line v){
        int d1=dcmp((e-s)^(v.s-s));
        int d2=dcmp((e-s)^(v.e-s));
        int d3=dcmp((v.e-v.s)^(s-v.s));
        int d4=dcmp((v.e-v.s)^(e-v.s));
        if((d1^d2)==-2&&(d3^d4)==-2)return 2;
        return (d1==0 && dcmp((v.s-s)*(v.s-e))<=0)||(d2==0 && dcmp((v.e-s)*(v.e-e)<=0))||(d3==0 && dcmp((s-v.s)*(s-v.e))<=0)||(d4==0&&dcmp((e-v.s)*(e-v.e))<=0);
    }
};
struct Spfa{
    double dis[maxn];
    int inq[maxn];
    vector<pair<int, double> > E[maxn];
    void init(){
        for(int i=0;i<maxn;i++){
            dis[i]=inf;E[i].clear();inq[i]=0;
        }
    }
    int spfa(int s){
        queue<int> Q;
        dis[s]=0;
        inq[s]=1;
        Q.push(s);
        while(!Q.empty()){
            int u=Q.front();
            Q.pop();
            inq[u]=0;
            for(int i=0;i<E[u].size();i++){
                int v=E[u][i].first;
                if(dis[v]>dis[u]+E[u][i].second){
                    dis[v]=dis[u]+E[u][i].second;
                    if(inq[v])continue;
                    Q.push(v);
                    inq[v]=1;
                }
            }
        }
    }
};
int n;
double px[maxn], py[maxn][maxn];
vector<Point> point;
vector<Line> line;
Spfa spfa;
void BuildGraph(){
    spfa.init();
    int sizeP=point.size();
    int sizeL=line.size();
    for(int u=0;u<sizeP;u++){
        for(int v=u+1;v<sizeP;v++){
            Line l1=Line(point[u], point[v]);
            int k=0;
            for(k;k<sizeL;k++)
                if(l1.segCrossSeg(line[k])==2)break;
            if(k==sizeL)
                spfa.E[u].push_back(make_pair(v, point[u].distance(point[v])));
        }
    }
}
int main()
{
    while(~scanf("%d", &n)&&n!=-1){
        point.clear();line.clear();
        point.push_back(Point(0, 5));
        for(int i=1;i<=n;i++){
            scanf("%lf", &px[i]);
            for(int j=1;j<5;j++){
                scanf("%lf", &py[i][j]);
                point.push_back(Point(px[i], py[i][j]));
            }
            line.push_back(Line(Point(px[i], 0), Point(px[i], py[i][1])));
            line.push_back(Line(Point(px[i], py[i][2]), Point(px[i], py[i][3])));
            line.push_back(Line(Point(px[i], py[i][4]), Point(px[i], 10)));
        }
        point.push_back(Point(10, 5));
        BuildGraph();
        spfa.spfa(0);
        double ans=spfa.dis[point.size()-1];
        printf("%.2f\n", ans==inf?-1:ans);
    }
    return 0;
}