POJ 1556 The Doors(线段交+最短路)
The poj 线段 短路
2023-09-27 14:26:07 时间
The Doors
Time Limit: 1000MS | Memory Limit: 10000K | |
Total Submissions: 5210 | Accepted: 2124 |
Description
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.
![](http://poj.org/images/1556_1.jpg)
![](http://poj.org/images/1556_1.jpg)
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.
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
总共4*n+1个点个点。
根据线段交去判断会不会冲突,可以直接连的就建立一条路径。
然后求最短路。
因为点很小,所以无论哪种最短路算法都可使用。
/************************************************************ * Author : kuangbin * Email : kuangbin2009@126.com * Last modified : 2013-07-14 10:47 * Filename : POJ1556TheDoors.cpp * Description : * *********************************************************/ #include <iostream> #include <stdio.h> #include <string.h> #include <algorithm> #include <queue> #include <map> #include <vector> #include <set> #include <string> #include <math.h> using namespace std; const double eps = 1e-8; int sgn(double x) { if(fabs(x) < eps)return 0; if(x < 0) return -1; else return 1; } struct Point { double x,y; Point(){} Point(double _x,double _y) { x = _x;y = _y; } Point operator -(const Point &b)const { return Point(x - b.x,y - b.y); } double operator ^(const Point &b)const { return x*b.y - y*b.x; } double operator *(const Point &b)const { return x*b.x + y*b.y; } }; struct Line { Point s,e; Line(){} Line(Point _s,Point _e) { s = _s;e = _e; } }; //判断线段相交 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.s)^(l1.e-l1.s))*sgn((l2.e-l1.s)^(l1.e-l1.s)) <= 0 && sgn((l1.s-l2.s)^(l2.e-l2.s))*sgn((l1.e-l2.s)^(l2.e-l2.s)) <= 0; } double dist(Point a,Point b) { return sqrt((b-a)*(b-a)); } const int MAXN = 100; Line line[MAXN]; double dis[MAXN][MAXN]; const double INF = 1e20; int main() { //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); int n; double x,y1,y2,y3,y4; while(scanf("%d",&n) == 1) { if(n == -1) break; for(int i = 1;i <= n;i++) { scanf("%lf%lf%lf%lf%lf",&x,&y1,&y2,&y3,&y4); line[2*i-1] = Line(Point(x,y1),Point(x,y2)); line[2*i] = Line(Point(x,y3),Point(x,y4)); } for(int i = 0;i <= 4*n+1;i++) for(int j = 0;j <= 4*n+1;j++) { if(i == j)dis[i][j] = 0; else dis[i][j] = INF; } for(int i = 1;i <= 4*n;i++) { int lid = (i+3)/4; bool flag = true; Point tmp; if(i&1)tmp = line[(i+1)/2].s; else tmp = line[(i+1)/2].e; for(int j = 1;j < lid;j++) if(inter(line[2*j-1],Line(Point(0,5),tmp)) == false && inter(line[2*j],Line(Point(0,5),tmp)) == false) flag = false; if(flag)dis[0][i] =dis[i][0] = dist(Point(0,5),tmp); flag = true; for(int j = lid+1;j <= n;j++) if(inter(line[2*j-1],Line(Point(10,5),tmp)) == false && inter(line[2*j],Line(Point(10,5),tmp)) == false) flag = false; if(flag)dis[i][4*n+1] =dis[4*n+1][i] = dist(Point(10,5),tmp); } for(int i = 1;i <= 4*n;i++) for(int j = i+1;j <=4*n;j++) { int lid1 = (i+3)/4; int lid2 = (j+3)/4; bool flag = true; Point p1,p2; if(i&1)p1 = line[(i+1)/2].s; else p1 = line[(i+1)/2].e; if(j&1)p2 = line[(j+1)/2].s; else p2 = line[(j+1)/2].e; for(int k = lid1+1;k < lid2;k++) if(inter(line[2*k-1],Line(p1,p2)) == false && inter(line[2*k],Line(p1,p2)) == false) flag = false; if(flag) dis[i][j] = dis[j][i] = dist(p1,p2); } bool flag = true; for(int i = 1;i <= n;i++) if(inter(line[2*i-1],Line(Point(0,5),Point(10,5))) == false && inter(line[2*i],Line(Point(0,5),Point(10,5))) == false) flag = false; if(flag)dis[0][4*n+1] = dis[4*n+1][0] = 10; for(int k = 0;k <= 4*n+1;k++) for(int i = 0;i <= 4*n+1;i++) for(int j = 0;j <= 4*n+1;j++) if(dis[i][k] + dis[k][j] < dis[i][j]) dis[i][j] = dis[i][k] + dis[k][j]; printf("%.2lf\n",dis[0][4*n+1]); } return 0; }
相关文章
- what are the values in _ga cookie?
- What are the benefits of using Dependency Injection and IoC Containers?
- How-To-Ask-Questions-The-Smart-Way提问的技巧 提问的智慧
- What are the differences between WebAPI and WebAPI 2
- What's the difference between returning void and returning a Task?
- 【CF809D】Hitchhiking in the Baltic States(Splay,动态规划)
- poj-2996 Help Me with the Game
- POJ 2388:Who's in the Middle
- Andrew Ng -- What is Ai? the first week
- POJ 2752 Seek the Name, Seek the Fame
- POJ 1426 Find The Multiple
- POJ 1679 The Unique MST
- ECSHOP报错误Deprecated: preg_replace(): The /e modifier is depr
- This request has been blocked; the content must be served over HTTPS.
- POJ 3311 Hie with the Pie (状压DP)
- POJ 3174 Alignment of the Planets (暴力求解)
- HDU 4355 Party All the Time (三分求极值)
- POJ 1426 Find The Multiple
- 【POJ 2942】Knights of the Round Table(点双连通分量,二分图染色)
- poj 1274 The Perfact Stall
- [ACM] POJ 2151 Check the difficulty of problems (概率+DP)
- POJ3262 Protecting the Flowers 【贪心】
- poj 3696 The Luckiest number 欧拉函数在解a^x=1modm的应用
- POJ 3267 The Cow Lexicon
- pat 1144 The Missing Number(20 分)
- poj 1679 The Unique MST (次小生成树(sec_mst)【kruskal】)
- C - The Suspects POJ - 1611(并查集)