学步园

题目链接：POJ 1556 The Doors

几何+最短路，把起点，终点和不在边界上的点记录下，枚举这些点，枚举所有墙，判断两个点是否被墙相隔，其实就是判断线段是否规范相交，不相隔的点算出来两点间的直线距离赋值给对应dis，相隔的点对应的dis设为最大值，这道题不能用memset把dis数组设为0x3f，因为double不是四个字节的。统计好dis后跑一遍dijkstra。

poj上输出浮点数时候，g++交需要这么写： printf("%.2f\n", d[4 * n + 1])，c++交lf和f都可以。

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>

using namespace std;

const double eps = 1e-10;
const int MAX_N = 100;
const int INF = 0x3f3f3f3f;

struct Point
{
	double x, y;
	Point(double x=0, double y=0):x(x),y(y) { }
};

typedef Point Vector;

Vector operator + (const Vector& A, const Vector& B)
{
    return Vector(A.x+B.x, A.y+B.y);
}

Vector operator - (const Point& A, const Point& B)
{
    return Vector(A.x-B.x, A.y-B.y);
}

Vector operator * (const Vector& A, double p)
{
    return Vector(A.x*p, A.y*p);
}

bool operator < (const Point& a, const Point& b)
{
	return a.x < b.x || (a.x == b.x && a.y < b.y);
}

int dcmp(double x)
{
    if(fabs(x) < eps)
        return 0;
    else
        return x < 0 ? -1 : 1;
}

bool operator == (const Point& a, const Point &b)
{
	return dcmp(a.x-b.x) == 0 && dcmp(a.y-b.y) == 0;
}


double Cross(const Vector& A, const Vector& B)
{
    return A.x*B.y - A.y*B.x;
}


bool SegmentProperIntersection(const Point& a1, const Point& a2, const Point& b1, const Point& b2)
{
	double c1 = Cross(a2-a1,b1-a1), c2 = Cross(a2-a1,b2-a1),
		c3 = Cross(b2-b1,a1-b1), c4=Cross(b2-b1,a2-b1);
	return dcmp(c1)*dcmp(c2)<0 && dcmp(c3)*dcmp(c4)<0;
}

int n;
Point p[MAX_N];
double dis[MAX_N][MAX_N];
double d[MAX_N];
int vis[MAX_N];

void dijkstra()
{
    memset(vis, 0, sizeof(vis));
    for(int i = 1; i <= 4 * n + 1; i++)
        d[i] = INF;
    d[0] = 0;
    for(int i = 0; i <= 4 * n + 1; i++)
    {
        int x, m = INF;
        for(int y = 0; y <= 4 * n + 1; y++)
        {
            if(!vis[y] && d[y] <= m)
                m = d[x = y];
        }
        vis[x] = 1;
        for(int y = 0; y <= 4 * n + 1; y++)
        {
            if(!vis[y] && d[y] > d[x] + dis[x][y])
                d[y] = d[x] + dis[x][y];
        }
    }
}
int main()
{
    //freopen("in.txt", "r", stdin);
    while(scanf("%d", &n), n != -1)
    {
        double x, y;
        p[0].x = 0, p[0].y = 5;
        p[4 * n + 1].x = 10, p[4 * n + 1].y = 5;
        for(int i = 0; i < n; i++)
        {
            scanf("%lf", &x);
            for(int j = 1; j <= 4; j++)
            {
                scanf("%lf", &y);
                p[4 * i + j].x = x;
                p[4 * i + j].y = y;
            }
        }
        bool flag = true;
        for(int i = 0; i <= 4 * n + 1; i++)
        {
            for(int j = i + 1; j <= 4 * n + 1; j++)
            {
                flag = true;
                for(int k = 0; flag && k < n; k++)
                {
                    for(int l = 0; flag && l < 3; l++)
                    {
                        if(l == 0)
                        {
                            if(SegmentProperIntersection(p[i], p[j], Point(p[4 * k].x, 0), p[4 * k + 1]))
                                flag = false;
                        }
                        else if(l == 1)
                        {
                            if(SegmentProperIntersection(p[i], p[j], p[4 * k + 2], p[4 * k + 3]))
                                flag = false;
                        }
                        else
                        {
                            if(SegmentProperIntersection(p[i], p[j], Point(p[4 * k].x, 10.0), p[4 * k + 4]))
                                flag = false;
                        }
                    }
                }
                if(flag)
                    dis[i][j] = dis[j][i] = sqrt((p[i].x - p[j].x) * (p[i].x - p[j].x) +
                                                 (p[i].y - p[j].y) * (p[i].y - p[j].y));
                else
                    dis[i][j] = dis[j][i] = INF;
            }
        }
        dijkstra();
        //printf("%.2lf\n", d[4 * n + 1]); // c++
        printf("%.2f\n", d[4 * n + 1]); // g++
    }
    return 0;
}