【POJ 1556】The Doors

1.​​题目链接​​。首先这个题目的输入有点迷，为了把问题描述清楚也是不容易。然后就是POJ的小数问题，输出采用%.2f,%.2lf依然是错的。

2.具体的做法就是把每个点拿出来，然后跑最短路。我们需要判断线段之间是不是相交，这中间可以采用一个小技巧，我们把每一堵墙中间的空隙拿出来存着，然后对于每一条路判断是不是与这些空隙相交，如果相交，说明这条路是可用的，否则不可用。这样看来其实spfa是很合适来求这个最短路的。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<stdio.h>
#include<cmath>
#include<queue>
const double eps = 1e-8;
using namespace std;
const int maxn = 1e6 + 10;
const int inf = 1e9;
#pragma warning(disable:4996)
struct Point
{
int num;
double x, y;
Point() {};
Point(double x, double y) :x(x), y(y) {};
Point(double x, double y, int num) :x(x), y(y), num(num) {};
Point operator-(const Point&b)const
{
return Point(x - b.x, y - b.y);;
}
Point operator+(const Point&b)const
{
return Point(x + b.x, y + b.y);
}
};
struct Segment {
Point s, e;
Segment() {};
Segment(Point s, Point e) :s(s), e(e) {};
};
struct Wall
{
double x;
Segment a, b;
Wall() {};
Wall(double x, Segment a, Segment b) :x(x), a(a), b(b) {};
};
double length(Point a, Point b)
{
return sqrt(pow(a.x - b.x, 2) + pow(a.y - b.y, 2));
}
double Cross(Point a, Point b) {
return a.x*b.y - a.y*b.x;
}
double dcmp(double x)
{
if (fabs(x) < eps)return 0;
else return x > 0 ? 1 : -1;
}
vector<Wall>wall;
vector<Point>pot;
int N;
bool vis[maxn];
double dis[maxn];
bool JudgeSegmentInter(Segment a, Segment b)
{
double c1 = Cross(a.e - a.s, b.s - a.s);
double c2 = Cross(a.e - a.s, b.e - a.s);
double c3 = Cross(b.e - b.s, a.s - b.s);
double c4 = Cross(b.e - b.s, a.e - b.s);
return dcmp(c1)*dcmp(c2) < 0 && dcmp(c3)*dcmp(c4) < 0;
}
bool JudgeRoad(Point a, Point b)
{
for (int i = 0; i < wall.size(); i++)
{
if (a.x < wall[i].x&&wall[i].x< b.x)
if (!JudgeSegmentInter(Segment(a, b), wall[i].a) &&!JudgeSegmentInter(Segment(a, b), wall[i].b))return 0;
}
return 1;
}
void Spfa()
{
queue<Point>q;
Point now;
int i, j;
memset(vis, 0, sizeof(vis));
for (i = 0; i < pot.size(); ++i)dis[i] = 100000;
q.push(pot[0]), vis[0] = 1, dis[0] = 0;
while (!q.empty())
{
now = q.front();
q.pop();
vis[now.num] = 0;
for (i = now.num; i < pot.size(); ++i)
{
if (pot[i].x > now.x&&JudgeRoad(now, pot[i]))
{
if (dis[pot[i].num] > dis[now.num] + length(pot[i], now))
{
dis[pot[i].num] = dis[now.num] + length(pot[i], now);
if (!vis[pot[i].num])
{
vis[pot[i].num] = 1;
q.push(pot[i]);
}
}
}
}
}
printf("%.2f\n", dis[pot.size() - 1]);
}
int main()
{
double a, b, c, d, e;
int N;
while (~scanf("%d", &N))
{
if (N == -1)break;
wall.clear();
pot.clear();
int len = 0;
pot.push_back(Point(0, 5, len++));
for (int i = 0; i < N; i++)
{
scanf("%lf %lf %lf %lf %lf", &a, &b, &c, &d, &e);
pot.push_back(Point(a, b, len++));
pot.push_back(Point(a, c, len++));
pot.push_back(Point(a, d, len++));
pot.push_back(Point(a, e, len++));
wall.push_back(Wall(a, Segment(Point(a, b), Point(a, c)), Segment(Point(a, d), Point(a, e))));
}
pot.push_back(Point(10, 5, len++));
Spfa();
}
return 0;
}