POJ - 1556 The Doors

http://poj.org/problem?id=1556

几何+最短路

先算出所有的n*4+2个点和3*n个边界，然后每次从n*4+2个点中取两个点，判断一下这两个点构成的线段是否与3*n个边界相交，如果不相交，那么表示“这条路”是可以走的，就加边，否则不加边，然后跑一遍最短路。

poj输出要%f，%lf 会错。

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <vector>
#include <algorithm>
#include <string.h>
#include <queue>
const double eps = 1e-6;
const double PI = acos(-1.0); // PI = 180°= 3.14 
using namespace std;
//判断符号
int sign(double x)
{
	if (fabs(x) < eps)
		return 0;
	return x > 0 ? 1 : -1;
}

struct point
{
	double x;
	double y;
	point operator + (const point& other) { return point{ x + other.x, y + other.y }; }
	point operator - (const point& other) { return point{ x - other.x, y - other.y }; }
	point operator * (double k) { return point{ x * k, y * k }; }
	point operator / (double k) { return point{ x / k, y / k }; }
	bool operator == (const point& other)
	{
		return sign(x - other.x) == 0 && sign(y - other.y) == 0;
	}
	bool operator < (const point& other)
	{
		if (fabs(x - other.x) < eps)
			return y < other.y;
		return x < other.x;
	}
	void scan() { scanf("%lf%lf", &x, &y); }
	void print() { printf("%.2lf %.2lf\n", x, y); }
};
//点积
double dot(point a, point b)
{
	return a.x * b.x + a.y * b.y;
}
//叉积
double cross(point a, point b)
{
	return a.x * b.y - b.x * a.y;
}
//向量的长度 (可以计算两点距离
double getlen(point a)
{
	return sqrt(a.x * a.x + a.y * a.y);
}
//判断线段a1-a2 b1-b2是否相交
//严格（不包括端点相交），如果要不严格，最后两行删掉=号
bool segment_inter(point a1, point a2, point b1, point b2)
{
	return
		max(a1.x, a2.x) >= min(b1.x, b2.x) &&
		max(b1.x, b2.x) >= min(a1.x, a2.x) &&
		max(a1.y, a2.y) >= min(b1.y, b2.y) &&
		max(b1.y, b2.y) >= min(a1.y, a2.y) &&
		sign(cross(b1 - a1, a2 - a1)) * sign(cross(b2 - a1, a2 - a1)) < 0 &&
		sign(cross(a1 - b1, b2 - a1)) * sign(cross(a2 - b1, b2 - b1)) < 0;
}
struct line
{
	point a;
	point b;
	void scan() { a.scan(); b.scan(); }
	void print() { a.print(); b.print(); }
};
int n;
double in[15];
double a[15][4];
struct edge
{
	int to;
	double dis;
	int nex;
}e[1550];
int head[1550], tot = 1;
bool vis[1550];
void add(int in, int to, double dis)
{
	e[tot] = edge{ to,dis,head[in] };
	head[in] = tot++;
	//printf("%d %d %.2lf\n", in, to, dis);
}
double dis[1550];
#define Pair pair<double,int>
void dij()
{
	memset(vis, false, sizeof(vis));
	for (int i = 0; i < 1500; i++)
		dis[i] = 100005;
	priority_queue<Pair, vector<Pair>, greater<Pair> >q;
	q.push(Pair{ 0,1 });
	dis[1] = 0;
	while (!q.empty())
	{
		Pair t = q.top();
		q.pop();
		if (vis[t.second])
			continue;
		vis[t.second] = true;
		for (int i = head[t.second]; i + 1; i = e[i].nex)
		{
			int to = e[i].to;
			if (dis[to] > dis[t.second] + e[i].dis)
			{
				dis[to] = dis[t.second] + e[i].dis;
				q.push(Pair{ dis[to],to });
			}
		}
	}
}
point dots[1550];
line que[1550];
int main()
{
	while (true)
	{
		memset(head, -1, sizeof(head));
		int m, dotcnt = 1, cnt = 0;
		scanf("%d", &m);
		n = 4 * m + 2;
		if (m == -1)
			return 0;

		dots[dotcnt++] = point{ 0.0,5.0 };
		for (int i = 1; i <= m; i++)
		{
			scanf("%lf%lf%lf%lf%lf", &in[i], &a[i][0], &a[i][1], &a[i][2], &a[i][3]);
			que[cnt++] = line{ point{in[i],0.0}, point{in[i],a[i][0]} };
			que[cnt++] = line{ point{in[i],a[i][1]}, point{in[i],a[i][2]} };
			que[cnt++] = line{ point{in[i],a[i][3]}, point{in[i],10.0} };
			for (int j = 0; j < 4; j++)
				dots[dotcnt++] = point{in[i],a[i][j]};
		}
		dots[dotcnt++] = point{ 10.0,5.0 };

		for (int i = 1; i < dotcnt; i++)
		{
			for (int j = i + 1; j < dotcnt; j++)
			{
				for (int k = 0; k < cnt; k++)
				{
					if (segment_inter(dots[i], dots[j], que[k].a, que[k].b))
						goto qwe;
				}
				add(i, j, getlen(dots[i] - dots[j]));
				qwe:;
			}
		}

		dij();
		printf("%.2f\n", dis[n]);
	}
}