http://acm.pku.edu.cn/JudgeOnline/problem?id=1556

挺有意思的一个题。

题目大意如上图，有一个房间，要从(0,5)走到(10,5),房间内有一些竖直的墙壁，现在要求最短的路径长度。

首先，很直观很显然的，要使路径达到最短，我们每次都是沿着墙的端点按直线走，也就是从一个墙的端点走到另一个墙的端点，这样问题就可以转换为图论中的最短路问题了，设上图中有n个端点，这样可以建立一个n+2个点的有向带权图g,g[i][j]表示从端点i到端点j的长度。

下面是关于怎么构图：枚举2个端点i和j,如果线段Pi->Pj于横坐标处于Xi,Xj之间的墙壁都没有相交的话，则可以从端点i直线走到端点j,在图g中假如一条由i指向j的边，权值为distance(Pi,Pj)。

这样，最构造出来的图求最短路就可以得到最后问题的解了。

#include <iostream>
#include <string>
#include <cstdio>
#include <cmath>
using namespace std;
#define EPS 1.0e-6struct Point {
    double x,y;
};int dblcmp(double r) {
    if(fabs(r)<EPS) return 0;
    return r>0?1:-1;
}double dot(double x1,double y1,double x2,double y2) {
    return x1*y2-x2*y1;
}double cross(Point a,Point b,Point c) {
    return dot(b.x-a.x,b.y-a.y,c.x-a.x,c.y-a.y);
}
//判断线段(a,b)和(c,d)是否相交（不算端点）
bool lineseg(Point a,Point b,Point c,Point d) {
    return (((dblcmp(cross(a,b,c))^dblcmp(cross(a,b,d)))==-2)
                &&((dblcmp(cross(c,d,a))^dblcmp(cross(c,d,b)))==-2));
}
double mydist(Point a,Point b) {
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}double g[200][200];    //图的临街矩阵
int s,t;
int n;
Point line[200][2];    //存储墙
Point pts[200];        //存储墙2端的端点

int main() {
    double x,y1,y2,y3,y4;
    while(cin>>n) {
        if(n==-1) break;
        s=0,t=4*n+1;
        pts[0].x=0;
        pts[0].y=5;
        pts[t].x=10;
        pts[t].y=5;for(int i=0;i<n;i++) {
            cin>>x>>y1>>y2>>y3>>y4;
        
            line[i*3][0].x=x;
            line[i*3][0].y=0;
            line[i*3][1].x=x;
            line[i*3][1].y=y1;

            line[i