The Doors
You are to find the length of the shortest path through a chamber containing obstructing walls. The chamber will always have sides at x = 0, x = 10, y = 0, and y = 10. The initial and final points of the path are always (0, 5) and (10, 5). There will also be from 0 to 18 vertical walls inside the chamber, each with two doorways. The figure below illustrates such a chamber and also shows the path of minimal length.
Input
The input data for the illustrated chamber would appear as follows.
2
4 2 7 8 9
7 3 4.5 6 7
The first line contains the number of interior walls. Then there is a line for each such wall, containing five real numbers. The first number is the x coordinate of the wall (0 < x < 10), and the remaining four are the y coordinates of the ends of the doorways in that wall. The x coordinates of the walls are in increasing order, and within each line the y coordinates are in increasing order. The input file will contain at least one such set of data. The end of the data comes when the number of walls is -1.
Output
The output should contain one line of output for each chamber. The line should contain the minimal path length rounded to two decimal places past the decimal point, and always showing the two decimal places past the decimal point. The line should contain no blanks.
Sample Input
1
5 4 6 7 8
2
4 2 7 8 9
7 3 4.5 6 7
-1
Sample Output
10.00
10.06
Source
题目类型：线段相交+最短路
算法分析：由题易知只有每次走门的端点而不是走中间才能保证两点之间的边是最短的。枚举任意两点构造线段判断是否与图中的竖墙的分隔线段相交，分类讨论之后在满足条件的点之间连边，最后跑一个最短路即可
|
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 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 |
/************************************************* Author :supermaker Created Time :2016/1/29 18:24:35 File Location :C:\Users\abcd\Desktop\TheEternalPoet **************************************************/ #pragma comment(linker, "/STACK:102400000,102400000") #include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> using namespace std; #define CFF freopen ("aaa.txt", "r", stdin) #define CPPFF ifstream cin ("aaa.txt") #define DB(ccc) cout << #ccc << " = " << ccc << endl #define PB push_back #define MP(A, B) make_pair(A, B) typedef long long LL; typedef unsigned long long ULL; typedef double DB; typedef pair <int, int> PII; typedef pair <int, bool> PIB; const int INF = 0x7F7F7F7F; const int MOD = 1e9 + 7; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int maxn = 100 + 66; int sgn (double val) { if (fabs (val) < EPS) return 0; else if (val < 0) return -1; return 1; } struct Point { double x, y; Point () {} Point (double xx, double yy) : x (xx), y (yy) {} Point operator - (const Point &a) const { return Point (x - a.x, y - a.y); } double operator ^ (const Point &a) const { return x * a.y - y * a.x; } double operator * (const Point &a) const { return x * a.x + y * a.y; } }; struct Line { Point s, e; Line () {} Line (Point ss, Point ee) : s (ss), e (ee) {} }; Point p[maxn]; Line l[maxn]; int n; double edge[maxn][maxn], dis[maxn];; double Dist (Point p1, Point p2) { return sqrt ((p2 - p1) * (p2 - p1)); } bool inter (Line l1, Line l2) { return max (l1.s.x, l1.e.x) >= min (l2.s.x, l2.e.x) && max (l2.s.x, l2.e.x) >= min (l1.s.x, l1.e.x) && max (l1.s.y, l1.e.y) >= min (l2.s.y, l2.e.y) && max (l2.s.y, l2.e.y) >= min (l1.s.y, l1.e.y) && sgn ((l2.s - l1.e) ^ (l1.s - l1.e)) * sgn ((l2.e - l1.e) ^ (l1.s - l1.e)) <= 0 && sgn ((l1.s - l2.e) ^ (l2.s - l2.e)) * sgn ((l1.e - l2.e) ^ (l2.s - l2.e)) <= 0; } void Dij (int s) { fill (dis, dis + maxn, INF); dis[s] = 0; priority_queue <pair <int, double>, vector <pair <int, double> >, greater <pair <int, double> > > qu; qu.push (pair <int, double> (s, 0)); while (!qu.empty ()) { pair <int, double> tt = qu.top (); qu.pop (); int ta = tt.first; double tb = tt.second; if (sgn (dis[ta] - tb) < 0) continue; for (int i = 1; i <= 4 * n + 2; i++) if (i != s && edge[ta][i] < INF && dis[i] > edge[ta][i] + dis[ta]) { dis[i] = edge[ta][i] + dis[ta]; qu.push (pair <int, double> (i, dis[i])); } } } int main() { //CFF; //CPPFF; while (scanf ("%d", &n) != EOF) { if (n == -1) break; p[1] = Point (0, 5); p[4*n+2] = Point (10, 5); int tota = 1, totb = 0; for (int i = 1; i <= n; i++) { double x, y; scanf ("%lf", &x); for (int j = 1; j <= 4; j++) { scanf ("%lf", &y); p[++tota] = Point (x, y); if (j == 1) l[++totb] = Line (Point (x, 0), Point (x, y)); else if (j == 3) l[++totb] = Line (Point (p[tota-1].x, p[tota-1].y), Point (x, y)); else if (j == 4) l[++totb] = Line (Point (x, y), Point (x, 10)); } } for (int i = 0; i < maxn; i++) for (int j = 0; j < maxn; j++) edge[i][j] = INF; for (int i = 1; i <= 4 * n + 2; i++) for (int j = i + 1; j <= 4 * n + 2; j++) { int cnt = 0; for (int k = 1; k <= 3 * n; k++) { Line tt = Line (p[i], p[j]); if (inter (tt, l[k])) cnt++; } if (i == 1 && j < 4 * n + 2 && cnt == 1) edge[i][j] = edge[j][i] = Dist (p[i], p[j]); if (i == 1 && j == 4 * n + 2 && cnt == 0) edge[i][j] = edge[j][i] = Dist (p[i], p[j]); if (i != 1 && j < 4 * n + 2 && cnt == 2) edge[i][j] = edge[j][i] = Dist (p[i], p[j]); if (i != 1 && j == 4 * n + 2 && cnt == 1) edge[i][j] = edge[j][i] = Dist (p[i], p[j]); } for (int i = 1; i <= n; i++) { int ta = 4 * i - 2, tb = ta + 1; edge[ta][ta+2] = edge[ta+2][ta] = INF; edge[tb][tb+2] = edge[tb+2][tb] = INF; } Dij (1); //for (int i = 1; i <= 4 * n + 2; i++) // { // for (int j = 1; j <= 4 * n + 2; j++) // if (edge[i][j] < INF) // cout << "i:" << i << " j:" << j << " edge[i][j]:" << edge[i][j] << endl; // } printf ("%.2f\n", dis[4*n+2]); } return 0; } |
- « 上一篇：poj3111
- poj2653：下一篇 »