【POJ 1556】The Doors

【POJ 1556】The Doors

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

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

#include#include#include#include#include#include#includeconst 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;}vectorwall;vectorpot;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(){ queueq; 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;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。