POJ 1556 The Doors
这道题我贡献了一个 WA, 原因第一个是我的 sgn 函数写错了，第二个是没有初始化一个变量，还好后来发现了。这道题思路上是没有错误的。
这题的计算几何方面的算法是很基础的，图论涉及到了最短路，也算是很基础的。
原题地址：http://poj.org/problem?id=1556
测试数据：http://mcpc.cigas.net/archives.html , 选择 Mid-Centrail USA 1996 相关的项来下载即可在压缩包中找到。
POJ 1556 门
题目描述
你需要找到一条通过一个有墙阻碍的房间的最短路。这个房间的四条边始终在 x = 0, x = 10, y = 0 和 y = 10 上。起点和终点始终在 (0, 5) 和 (10, 5) 上。墙的数量的范围是 0 ~ 18, 每堵墙上有两个门。下图展示了一个这样的房间，并且标出了从起点到终点的最短路。
输入数据
上图房间的输入数据如下：
2 4 2 7 8 9 7 3 4.5 6 7
第一行包含一个数字，表示墙的个数。接下来每行描述一堵墙，共 5 个数字。第一个数字是该墙的 x 坐标 (0 < x < 10), 剩下的 4 个数字是这堵墙的门的 4 个端点的 y 坐标。墙的 x 坐标会以升序给出，且每堵墙的门的端点 y 坐标也以升序给出。输入文件至少会包含一组数据。如果读到墙的数目是 -1, 那么说明输入数据结束。
输出数据
对于每组输入数据，输出一行。每行输出的数据是从起点到终点的最短路，四舍五入保留两位小数。不能有多余空格。
样例输入
1 5 4 6 7 8 2 4 2 7 8 9 7 3 4.5 6 7 -1
样例输出
10.00 10.06
解题思路
把门的每个端点存在一个点集 G 里，把墙的阻碍部分的线段存在一个线段集合 S 里。为了方便，点集中可以再增加两个点，起点和终点。然后，以点集中的点为顶点，构建一个图，图中每两个顶点的边权值先赋值为 +∞. 然后两两枚举顶点，设当前枚举到的顶点是 u, v, 判断这两个点确定的线段 (u ~ v) 与线段集合 S 中的任何线段是否相交，如果 (u ~ v) 与 S 中没有任何线段相交，那么就可以赋其边权值 (u, v) 为线段 (u ~ v) 的长度。之后在图 G 上求起点到终点的最短路。
源代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 | #include <cstdlib> #include <cstring> #include <cstdio> #include <cmath> using namespace std; const double inf = 1e+8; const double eps = 0.0; const size_t mxn = 5000; const size_t mxe = 250000; struct point { double x, y; inline point() { } inline point(double a, double b) : x(a), y(b) { } inline point operator-(const point &p) const { return point(x - p.x, y - p.y); } inline double magsqr() const { return x * x + y * y; } inline double mag() const { return sqrt(magsqr()); } }; struct line { point a, b; inline line() { } inline line(const point &x, const point &y) : a(x), b(y) { } inline line(double x, double y, double z, double w) : a(x, y), b(z, w) { } inline point vec() const { return b - a; } inline double len() const { return vec().mag(); } }; struct gmatrix { double w[mxn][mxn]; size_t n; void reset() { memset(w, 0, sizeof(w)); } void reset(double val) { for (size_t i = 0; i < n; ++i) for (size_t j = 0; j < n; ++j) w[i][j] = val; } }; struct dijkstra { double dist[mxn]; bool vs[mxn]; void reset(gmatrix &g, size_t s) { memset(vs, 0, sizeof(vs)); for (size_t i = 0; i < g.n; ++i) dist[i] = inf; dist[s] = 0.0; vs[s] = true; } double solve(gmatrix &g, size_t s, size_t t) { reset(g, s); for(size_t i = 1; i < g.n; ++i) { double val = inf; size_t k = -1; for (size_t j = 0; j < g.n; ++j) { if (vs[j]) continue; if (dist[j] > g.w[s][j] + dist[s]) dist[j] = g.w[s][j] + dist[s]; if (val > dist[j]) { val = dist[j]; k = j; } } if (k == -1) break; s = k; vs[k] = true; } return dist[t]; } }; inline int sgn(double a) { return a > eps ? 1 : a < -eps ? -1 : 0; } inline double cross(const point &a, const point &b) { return a.x * b.y - b.x * a.y; } inline int relps(const point &p, const line &s) { return sgn(cross(p - s.a, s.vec())); } inline int relss(const line &sa, const line &sb) { int a = relps(sa.a, sb), b = relps(sa.b, sb); int c = relps(sb.a, sa), d = relps(sb.b, sa); if (a * b == -1 && c * d == -1) return 0; return 1; } point ps[555]; size_t pc = 2; line ls[999]; size_t lc = 0; gmatrix gr; dijkstra dij; bool test() { size_t n; scanf("%lu", &n); if (n == -1) return false; pc = 2; ps[0] = point(0.0, 5.0); ps[1] = point(10.0, 5.0); lc = 0; while (n--) { double x, a, b, c, d; scanf("%lf%lf%lf%lf%lf", &x, &a, &b, &c, &d); ps[pc++] = point(x, a); ps[pc++] = point(x, b); ps[pc++] = point(x, c); ps[pc++] = point(x, d); if (sgn(a)) ls[lc++] = line(x, 0, x, a); if (sgn(d - 10.0)) ls[lc++] = line(x, d, x, 10.0); ls[lc++] = line(x, b, x, c); } gr.n = pc; gr.reset(inf); for (size_t i = 0; i < pc; ++i) { for (size_t j = i + 1; j < pc; ++j) { line seg(ps[i], ps[j]); for (size_t k = 0; k < lc; ++k) if (relss(seg, ls[k]) == 0) goto invalid_segment; gr.w[i][j] = gr.w[j][i] = seg.len(); invalid_segment: ; // Notice to add this. } } double result = dij.solve(gr, 0, 1); printf("%0.2f\n", result); return true; } int main(int, char *[]) { while (test()); return EXIT_SUCCESS; } |
原创文章，转载请注明来源：http://euyuil.com/2603/poj-1556-the-doors/
这…这…这不是那个HPY60题里边那个么…坑爹无极限，折腾了一下午也没弄出来
以前我怎么没写……