首页 > 代码库 > POJ 1556 The Doors

POJ 1556 The Doors

2024-11-13 18:30:01   202人阅读

题目大意：

你将通过一个包含障碍墙的房间，找到最短路径的长度。房间在x＝0，x＝10，y＝0，y＝10时都有边。路径的起始点和最后点总是（0, 5）和（10, 5）。

室内也有0至18个垂直墙，每个墙有两个门道。下图显示了这样一个腔室，并显示了最小长度的路径。

技术分享

输入
所示的输入数据如下所示。
2
4 2 7 8 9
7 3 4.5 6 7
第一行包含内墙的数目。然后每一个这样的墙有一条线，包含五个实数。第一个数字是墙的x坐标（0<x<10），剩下的四个是墙门口的Y坐标。墙壁的x坐标是递增的，并且在每一行中y坐标都在递增。输入文件将包含至少一个这样的数据集。数据的结尾是墙的数量是1。
输出
每个腔室的输出应包含一行输出。该行应该包含小数点前舍入到小数点后两个小数点的最小路径长度，并且始终显示小数点后小数点后的两个小数点。该行不应包含空格。

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
题解:计算几何+SPFA
两个点之间能直达就建边，能否直达用叉积判断，将两点构成线段与每一个墙做跨立实验
建好边后，做SPFA求出1号点(0,5)和npoint号点(10,5)之间的最短路
  1 #include<cstdio>
  2 #include<algorithm>
  3 #include<cstring>
  4 #include<iostream>
  5 #include<cmath>
  6 using namespace std;
  7 struct Node
  8 {
  9     int next,to;
 10     double dis;
 11 } edge[200001];
 12 struct Line
 13 {
 14     double x1,y1,x2,y2;
 15 } line[10001];
 16 struct Point
 17 {
 18     double x,y;
 19 } point[10001];
 20 int num,head[10001],nline,npoint,n;
 21 double dist[10001];
 22 bool vis[10001];
 23 void add(int u,int v,double d)
 24 {
 25     //cout<<u<<‘ ‘<<v<<‘ ‘<<d<<endl;
 26     num++;
 27     edge[num].next=head[u];
 28     head[u]=num;
 29     edge[num].to=v;
 30     edge[num].dis=d;
 31 }
 32 void add_line(double x,double y1,double y2)
 33 {
 34     nline++;
 35     line[nline].x1=x;
 36     line[nline].x2=x;
 37     line[nline].y1=y1;
 38     line[nline].y2=y2;
 39 }
 40 void add_point(double x,double y)
 41 {
 42     npoint++;
 43     point[npoint].x=x;
 44     point[npoint].y=y;
 45 }
 46 double distan(int i,int j)
 47 {
 48     return sqrt((point[i].x-point[j].x)*(point[i].x-point[j].x)+(point[i].y-point[j].y)*(point[i].y-point[j].y));
 49 }
 50 bool judge(int l,int r,int i)
 51 {
 52     double x1=point[l].x,x2=point[r].x,y1=point[l].y,y2=point[r].y;
 53     double x3=line[i].x1,x4=line[i].x2,y3=line[i].y1,y4=line[i].y2;
 54     if (x1==x2&&x2==x3&&x3==x4) return 0;
 55     if (max(x1,x2)<min(x3,x4)) return 1;
 56     if (max(x3,x4)<min(x1,x2)) return 1;
 57     if (max(y3,y4)<min(y1,y2)) return 1;
 58     if (max(y1,y2)<min(y3,y4)) return 1;
 59     double dx=x1-x3,dy=y1-y3;double qx=x4-x3,qy=y4-y3;double px=x2-x3,py=y2-y3;
 60     if ((dx*qy-dy*qx)*(qx*py-px*qy)<=0) return 1;
 61      dx=x3-x1,dy=y3-y1;qx=x2-x1,qy=y2-y1;px=x4-x1,py=y4-y1;
 62     if ((dx*qy-dy*qx)*(qx*py-px*qy)<=0) return 1;
 63     return 0;
 64 }
 65 bool exam(int l,int r)
 66 {
 67     int i;
 68     for (i=1; i<=nline; i++)
 69         if (judge(l,r,i)==0) return 0;
 70     return 1;
 71 }
 72 void SPFA()
 73 {
 74     int q[100001],h,t,i;
 75     q[1]=1;
 76     dist[1]=0;
 77     h=0;
 78     t=1;
 79     while (h<t)
 80     {
 81         h++;
 82         int u=q[h];
 83         vis[u]=0;
 84         for (i=head[u]; i; i=edge[i].next)
 85         {
 86             int v=edge[i].to;
 87             if (dist[v]>dist[u]+edge[i].dis)
 88             {
 89                 dist[v]=dist[u]+edge[i].dis;
 90                 if (vis[v]==0)
 91                 {
 92                     t++;
 93                     q[t]=v;
 94                     vis[v]=1;
 95                 }
 96             }
 97         }
 98     }
 99 }
100 int main()
101 {
102     int i,j;
103     double x,y1,y2,y3,y4;
104     while (cin>>n&&n!=-1)
105     {
106         num=0;
107         npoint=0;
108         nline=0;
109         memset(head,0,sizeof(head));
110         memset(edge,0,sizeof(edge));
111         add_point(0,5);
112         for (i=1; i<=n; i++)
113         {
114             scanf("%lf%lf%lf%lf%lf",&x,&y1,&y2,&y3,&y4);
115             add_line(x,0,y1);
116             add_line(x,y2,y3);
117             add_line(x,y4,10);
118             add_point(x,y1);
119             add_point(x,y2);
120             add_point(x,y3);
121             add_point(x,y4);
122         }
123         add_point(10,5);
124         for (i=1; i<=npoint; i++)
125             dist[i]=200000000;
126         for (i=1; i<npoint; i++)
127         {
128             for (j=i+1; j<=npoint; j++)
129             {
130                 if (exam(i,j))
131                     add(i,j,distan(i,j));
132             }
133         }
134         SPFA();
135         printf("%.2lf\n",dist[npoint]);
136     }
137 }

 

POJ 1556 The Doors


联系
我们