題干：

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

題目大意：

房間里有n堵墻，每面墻上有兩扇門，求從房間最左端中點到最右端中點的最短路徑?

解題報告：

把起點，終點，每個墻上的4個點分別看成圖的頂點，這樣一共就是4*n+2個點，我們把起點和終點當做第4*n+1和4*n+2這兩個點，其余的每四個點為一組讀數，讀完順便加邊。

然后就是把這個點和之前所有讀過的點連成一條邊（假設共能連cnt條邊），然后每條邊依次連好的邊（也就是墻）判斷是否相交，如果和所有的墻都不相交，那么就加邊（到dis數組中），然后跑floyd最短路就可以了。

寫代碼能力還是挫啊、、搞了一小時、、

?

AC代碼：

#include<iostream> #include<algorithm> #include<queue> #include<cstdio> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define ll long long #define pb push_back #define pm make_pair #define fi first #define se second using namespace std; const double eps = 1e-8; int sgn(double x) {if(fabs(x) < eps)return 0;if(x < 0) return -1;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;} } p[1005]; struct Line {Point s,e;Line() {}Line(Point s,Point e):s(s),e(e) {}pair<Point,int> operator &(const Line &b)const {Point res = s;if(sgn((s-e)^(b.s-b.e)) == 0) {if(sgn((b.s-s)^(b.e-s)) == 0)return make_pair(res,0);//兩直線重合else return make_pair(res,1);//兩直線平行}double t = ((s-b.s)^(b.s-b.e))/((s-e)^(b.s-b.e));res.x += (e.x - s.x)*t;res.y += (e.y - s.y)*t;return make_pair(res,2);//有交點，并返回交點} } line[1005]; inline double xmult(Point p0,Point p1,Point p2) { return (p1-p0)^(p2-p0);}//p0p1 X p0p2 bool Seg_inter_line(Line l1,Line l2) { return sgn(xmult(l2.s,l1.s,l1.e))*sgn(xmult(l2.e,l1.s,l1.e)) <= 0;}//判斷直線l1和線段l2是否相交 double dist(Point a,Point b) {return sqrt((b - a)*(b - a));} bool inter(Line l1,Line l2) {//判斷線段相交returnmax(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; } //兩線段相交判斷 //2 規范相交 //1 非規范相交 //0 不相交 int segcrossseg(Line l1,Line l2) {int d1 = sgn((l1.e-l1.s)^(l2.s-l1.s));int d2 = sgn((l1.e-l1.s)^(l2.e-l1.s));int d3 = sgn((l2.e-l2.s)^(l1.s-l2.s));int d4 = sgn((l2.e-l2.s)^(l1.e-l2.s));if( (d1^d2)==-2 && (d3^d4)==-2 )return 2;return (d1==0 && sgn((l2.s-l1.s)*(l2.s-l1.e))<=0) ||(d2==0 && sgn((l2.e-l1.s)*(l2.e-l1.e))<=0) ||(d3==0 && sgn((l1.s-l2.s)*(l1.s-l2.e))<=0) ||(d4==0 && sgn((l1.e-l2.s)*(l1.e-l2.e))<=0); } //直線和線段相交判斷 //-*this line -v seg //2 規范相交 //1 非規范相交 //0 不相交 int linecrossseg(Line l1,Line l2) {//l1直線，l2線段 int d1 = sgn((l1.e-l1.s)^(l2.s-l1.s));int d2 = sgn((l1.e-l1.s)^(l2.e-l1.s));if((d1^d2)==-2) return 2;return (d1==0||d2==0); } int totP,totL; int n; double dis[1005][1005]; void add(int num) {int up = num%4==0 ? num-4 : num-(num%4);//最多跑到哪個點 for(int i = 1; i<=up; i++) {int flag = 1;for(int j = 1; j<=totL; j++) {if(segcrossseg(Line(p[num],p[i]),line[j]) == 2) {flag=0;break;}}if(flag) {dis[i][num] = dis[num][i] = dist(p[i],p[num]);}}//與起點 int flag = 1;for(int j = 1; j<=totL; j++) {if(segcrossseg(Line(p[num],p[4*n+1]),line[j]) == 2) {flag=0;break;}}if(flag) {dis[4*n+1][num] = dis[num][4*n+1] = dist(p[4*n+1],p[num]);} } int main() {double y1,y2,y3,y4,x;while(~scanf("%d",&n)) {if(n == -1) break;//共4*n+1個頂點totP = 0;//因為起點 站了一個了 （還是起點單獨算吧、、、） totL = 0;p[4*n+1] = Point(0,5);p[4*n+2] = Point(10,5);for(int i = 1; i<=4*n+10; i++) {for(int j = 1; j<=4*n+10; j++) {dis[i][j] = 1000000000;}}for(int i = 1; i<=n; i++) {scanf("%lf%lf%lf%lf%lf",&x,&y1,&y2,&y3,&y4);p[++totP] = Point(x,y1);line[++totL] = Line(Point(x,0),p[totP]);p[++totP] = Point(x,y2);p[++totP] = Point(x,y3);line[++totL] = Line(p[totP-1],p[totP]);p[++totP] = Point(x,y4);line[++totL] = Line(p[totP],Point(x,10));add(totP);add(totP-1);add(totP-2);add(totP-3);}add(4*n+2); // dis[totP][4*n+2] = dis[4*n+2][totP] = dist(Point(totP),Point(p[4*n+2])); // dis[totP-1][4*n+2] = dis[4*n+2][totP] = dist(Point(totP),Point(p[4*n+2])); // dis[totP][4*n+2] = dis[4*n+2][totP] = dist(Point(totP),Point(p[4*n+2])); // dis[totP][4*n+2] = dis[4*n+2][totP] = dist(Point(totP),Point(p[4*n+2]));for(int k = 1; k<=totP+2; k++) {for(int i = 1; i<=totP+2; i++) {for(int j = 1; j<=totP+2; j++) {if(dis[i][k] + dis[k][j] < dis[i][j]) {dis[i][j] = dis[i][k] + dis[k][j];}}}}printf("%.2f\n",dis[4*n+1][4*n+2]);} } /* 1 7 3 4.5 6 7*/

總結：

? 說一下選定思路后開始敲代碼的歷程，首先模板沒的說，然后開始想讀入點的時候，用構造函數構造點，構造邊，是都需要記錄下來呢還是可以只構造點，然后遍歷的時候再? ?每兩個點連成一條邊? ? 來進行判斷，后來發現這樣不太好，也不太適合。因為你這樣會把? -每條墻的邊和矩形的邊框的邊的交點-? 那個點，也算在判斷的范圍中了，但是我們是不需要這個點的，也就是說不需要判斷這個點和其他點之間的關系，所以我們考慮也把每一條可以用到的邊都記錄下來，然后一邊讀入一邊存點存邊并且構圖（最短路的圖），剛開始想把起點存成id=1，終點存成id=4*n+2，但是發現這樣不太好，因為這樣就打亂了四條邊一組的這一不錯的關系，因為用這一關系（因為可以取模了啊 畢竟可以分組），我們可以用一個處理就得出了我們需要判斷的up的值，（如果不是這種存id的方法的話，那就是2,3,4,5是一組，6,7,8,9是一組，這樣就得寫一堆if else、、）然后寫add函數，剛開始直接up=num-(num%4)，后來發現第一個樣例都跑不出來，找bug，找到，改。這也是一個小trick啊以后別再犯了、、、找到這個bug的同時發現我沒有讓他和起點去連線（因為他的坐標是4*n+1啊所以肯定沒有被比較過）所以我們需要單獨讓他倆連線跑一次。

? ?然后第二個樣例沒過去，檢查后發現是最短路中應該是totP+2，我忘了+2了。。

? ?然后 dis數組初始化，本來想memset，，一想不對啊這是double類型，不能memset了，，然后最后寫了四行想讓終點和最后一個墻中的點都建圖，但是一想這樣寫不好，因為可能他和其他前面的墻也可以建圖呢。。所以直接add一下得了。。于是乎代碼出來了。。。然后一發AC、、

坑點

總結

以上是生活随笔為你收集整理的【POJ - 1556】The Doors （计算几何，线段相交）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。