题目链接：The Doors - POJ 1556 - Virtual Judge https://vjudge.net/problem/POJ-1556
题意是叫我们计算从（0,5）到（10,5）的最短路，中间会给出n道墙，每道墙会有两扇门可以通过，第一行是数字n，接下来n行，每行有x，y1，y2，y3，y4，表示横坐标为x的门上的四个点坐标。
在这里主要是把图建出来，我的做法是先把所有点和墙存下来，然后枚举每两点，这两点要满足横坐标不同，并且两点的连线不经过在两点的横坐标之间的墙，假设我们有两个点p1，p2，有一道墙的横坐标是x，那么只要（p1.x-x）*(p2.x-x)<0，这两个点就在墙的左右两边，然后再判断和墙有没有交点，这个用叉积计算墙的两点是不是在我们两点连线的两边，把图建完就用floyd或者dijkstra计算一下最短路就可以了，可能讲的不是很清楚，看一下代码：
struct node{ double x,y; }p[1005]; //存点 struct ss{ node a,b; }wall[1005];//存墙
我写的有点麻烦：
p[0].x=0,p[0].y=5; p[1].x=10,p[1].y=5;//起点和终点分别存进去 cnt1=2; //点的数量 cnt2=0; //墙的数量 for(int i=0;i<n;i++) { double x,y; cin>>x; cin>>y; p[cnt1].x=x,p[cnt1].y=y; //第一个点 wall[cnt2].a=p[cnt1]; //第一道墙 wall[cnt2].b.x=x; wall[cnt2].b.y=0; cnt1++; cnt2++; cin>>y; p[cnt1].x=x,p[cnt1].y=y; //第二个点 cnt1++; cin>>y; p[cnt1].x=x,p[cnt1].y=y; //第三个点 wall[cnt2].a=p[cnt1]; wall[cnt2].b=p[cnt1-1]; //第二道墙 cnt1++; cnt2++; cin>>y; p[cnt1].x=x,p[cnt1].y=y; //第四个点和第三道墙，好麻烦 wall[cnt2].a=p[cnt1]; wall[cnt2].b.x=x; wall[cnt2].b.y=10; cnt1++; cnt2++; }
判断两点之间有没有墙
bool jug(int a,int b) { for(int i=0;i<cnt2;i++) { double x=wall[i].a.x; double k=(p[a].x-x)*(p[b].x-x); //判断墙在两点之间 double k1=cross(p[a],p[b],wall[i].a);//判断墙的两点是否在连点的直线两边 double k2=cross(p[a],p[b],wall[i].b); if(k<0&&k1*k2<eps) return true; } return false; }
完整代码：
#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> #include<cmath> using namespace std; #define eps 1e-10 #define inf 9999999 struct node{ double x,y; }p[1005]; struct ss{ node a,b; }wall[1005]; double map[1005][1005]; int n,m,k,t,cnt1,cnt2; double dis(node a,node b) { return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); } double cross(node a,node b,node c) { return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x); } bool jug(int a,int b) { for(int i=0;i<cnt2;i++) { double x=wall[i].a.x; double k=(p[a].x-x)*(p[b].x-x); double k1=cross(p[a],p[b],wall[i].a); double k2=cross(p[a],p[b],wall[i].b); if(k<0&&k1*k2<eps) return true; } return false; } void floyd() { for(int k=0;k<cnt1;k++) { for(int i=0;i<cnt1;i++) { for(int j=0;j<cnt1;j++) { if(i!=j&&map[i][j]>map[i][k]+map[k][j]) { map[i][j]=map[i][k]+map[k][j]; } } } } } int main() { while(cin>>n) { if(n<0) break; p[0].x=0,p[0].y=5; p[1].x=10,p[1].y=5; cnt1=2; cnt2=0; for(int i=0;i<n;i++) { double x,y; cin>>x; cin>>y; p[cnt1].x=x,p[cnt1].y=y; wall[cnt2].a=p[cnt1]; wall[cnt2].b.x=x; wall[cnt2].b.y=0; cnt1++; cnt2++; cin>>y; p[cnt1].x=x,p[cnt1].y=y; cnt1++; cin>>y; p[cnt1].x=x,p[cnt1].y=y; wall[cnt2].a=p[cnt1]; wall[cnt2].b=p[cnt1-1]; cnt1++; cnt2++; cin>>y; p[cnt1].x=x,p[cnt1].y=y; wall[cnt2].a=p[cnt1]; wall[cnt2].b.x=x; wall[cnt2].b.y=10; cnt1++; cnt2++; } for(int i=0;i<cnt1;i++) { for(int j=0;j<cnt1;j++) map[i][j]=inf; } for(int i=0;i<cnt1-1;i++) { for(int j=i+1;j<cnt1;j++) { if(i!=j&&p[i].x!=p[j].x&&!jug(i,j)) { map[i][j]=map[j][i]=dis(p[i],p[j]); } } } floyd(); printf("%.2f ",map[0][1]); } return 0; }