题目链接：http://poj.org/problem?id=1556
题目大意：一个房间里有很多墙，每道墙上有两个门，求从房间左边中点到右边中点的最短距离。如图：
这道题目说起来就是一道最短路的题，但是两点之间是否能够走，需要判断一下两点之间的连线是不是跟墙有交点，就是计算几何的判断线段相交问题。两类典型的题合在一起了。
由于数据范围小的可怜，无脑暴力+floyd都能够过= =
AC代码：
#include <iostream> #include <cstdlib> #include <cstdio> #include <cstring> #include <cmath> #define MAXN 50 #define INF 1000000 using namespace std; struct Point { double x,y; Point(double x=0,double y=0):x(x),y(y){} }; typedef Point Vector; Vector operator + (Vector A,Vector B) {return Vector(A.x+B.x,A.y+B.y);} Vector operator - (Point A,Point B) {return Vector(A.x-B.x,A.y-B.y);} Vector operator * (Vector A,double p) {return Vector(A.x*p,A.y*p);} double Dot(Vector A,Vector B) {return A.x*B.x + A.y*B.y ;} double Length(Vector A) {return sqrt(Dot(A,A));} double Cross(Vector A,Vector B) {return A.x*B.y-A.y*B.x;} struct Line { Point P; Vector v; }; double GetLineIntersection(Line A,Line B) //返回交点相对P的t值 { Point P=A.P,Q=B.P; Vector v=A.v,w=B.v; Vector u=P-Q; double t=Cross(w,u) / Cross(v,w); return t; } //以上是计算几何基本内容 int n; Point points[4*MAXN];//记录点 double dis[4*MAXN][4*MAXN];//记录距离 Line lines[MAXN][3];//记录线段 int main() { Line l; Vector v,w; Point a,b; double x,t,t2; int i,j,k,o,mark; while(cin>>n) { if(n==-1) break; //初始化起点终点 points[n*4].x=0; points[n*4+1].x=10; points[n*4].y=points[n*4+1].y=5; for(i=0;i<n;i++) { cin>>x>>points[i*4+0].y>>points[i*4+1].y>>points[i*4+2].y>>points[i*4+3].y; a.x=b.x=points[i*4+0].x=points[i*4+1].x=points[i*4+2].x=points[i*4+3].x=x; a.y=0;b.y=10; //每道墙3条线 a-0 1-2 3-b lines[i][0].P=a; lines[i][0].v=points[i*4+0]-a; lines[i][1].P=points[i*4+1]; lines[i][1].v=points[i*4+2]-points[i*4+1]; lines[i][2].P=points[i*4+3]; lines[i][2].v=b-points[i*4+3]; } //设置距离初始值 for(i=0;i<4*n+2;i++) for(j=0;j<=i;j++) dis[i][j]=dis[j][i]=INF; //枚举两两点对 for(i=0;i<4*n+2;i++) for(j=0;j<i;j++) { if(points[i].x==points[j].x) continue; v=points[i]-points[j]; //给两点之间连线段赋值 l.P=points[j]; l.v=v; mark=0;//标记 //枚举所有的线段 for(k=0;k<n;k++) for(o=0;o<3;o++) { if(mark) break; t=GetLineIntersection(l,lines[k][o]); t2=GetLineIntersection(lines[k][o],l); if(t>0&&t<1&&t2>0&&t2<1)//如果交点在线段上，不能连 { mark=1; break; } } if(mark==0) dis[i][j]=dis[j][i]=Length(l.v);//可以连，更新距离 } //floyd跑最短路 for(k=0;k<4*n+2;k++) for(i=0;i<4*n+2;i++) for(j=0;j<4*n+2;j++) dis[i][j]=dis[i][j]<dis[i][k]+dis[k][j]?dis[i][j]:dis[i][k]+dis[k][j]; printf("%0.2f\n",dis[n*4+1][n*4+0]); } }
