[日常摸鱼]UVA393 The Doors 简单计算几何+最短路

The Boy Next Doors

题意：给定一个固定大小的房间（$x,y$的范围都是$[0,10]$），有$n$个墙壁作为障碍（都与横坐标轴垂直），每个墙壁都有两扇门分别用四个点来描述，起点终点固定在$(0,5)$和$(10,5)$，求起点到终点的最短路长度，$n<=18$

题解：

我们把每堵墙的每一“段”作为一条线段，对任意两点$u,v$，如果两点间的连线不和其他线段相交，那我们从$u$走到$v$的最短距离就是他们的欧几里得距离，对所有点对都这么做一遍，处理出所有能够直接到达的点之间的距离

如果不能直接从$u$到$v$，那么既然是最短路，那走直线一定比走曲线要好，也就是一定是经过他们中间的某些点然后到达的，然后对所有点跑一次最短路就好了

这题范围很小Floyd也能过…

  1 #include<cstdio>

  2 #include<cmath>

  3 #include<cstring>

  4 #include<algorithm>

  5 using namespace std;

  6

  7 const double precision=10e-6;

  8

  9 const double INF=(~0u>>2);

 10

 11 const int N=105;

 12

 13 struct Point

 14 {

 15     double x,y;

 16 }p[N];

 17

 18 struct Line

 19 {

 20     Point a,b;

 21 }l[N];

 22

 23 int n,cnt_point,cnt_line;

 24

 25 double dist[N][N];

 26

 27 inline int dblcmp(double d)

 28 {

 29     if(fabs(d)<precision)

 30         return 0;

 31     return (d>0?1:-1);

 32 }

 33

 34 inline double det(double x1,double y1,double x2,double y2)

 35 {

 36     return x1*y2-x2*y1;

 37 }

 38

 39 inline double cross(Point a,Point b,Point c)

 40 {

 41     return det(b.x-a.x,b.y-a.y,c.x-a.x,c.y-a.y);

 42 }

 43

 44 inline bool SegCrossSimple(Point a,Point b,Point c,Point d)

 45 {

 46     return (dblcmp(cross(c,a,b))^dblcmp(cross(d,a,b)))==-2&&(dblcmp(cross(a,c,d))^dblcmp(cross(b,c,d)))==-2;

 47 }

 48

 49 inline double sqr2(double x)

 50 {

 51     return x*x;

 52 }

 53

 54 inline double dis(int i,int j)

 55 {

 56     return sqrt(sqr2(p[i].x-p[j].x)+sqr2(p[i].y-p[j].y));

 57 }

 58

 59 inline void addPoint(double x,double y)

 60 {

 61     p[++cnt_point]=(Point){x,y};

 62 }

 63

 64 inline void addLine(double x1,double y1,double x2,double y2)

 65 {

 66     l[++cnt_line]=(Line){(Point){x1,y1},(Point){x2,y2}};

 67 }

 68

 69 inline void init()

 70 {

 71     memset(p,0,sizeof(p));

 72     memset(l,0,sizeof(l));

 73     cnt_point=cnt_line=0;

 74     addPoint(0,5);addPoint(10,5);

 75 }

 76

 77 inline void solve()

 78 {

 79     init();

 80

 81     double x,y1,y2,y3,y4;

 82     for(register int i=1;i<=n;i++)

 83     {

 84         scanf("%lf%lf%lf%lf%lf",&x,&y1,&y2,&y3,&y4);

 85         addPoint(x,y1);addPoint(x,y2);

 86         addPoint(x,y3);addPoint(x,y4);

 87         addLine(x,0,x,y1);addLine(x,y2,x,y3);addLine(x,y4,x,10);

 88     }

 89

 90     for(register int i=1;i<=cnt_point;i++)dist[i][i]=0;

 91

 92     for(register int i=1;i<=cnt_point;i++)

 93     {

 94         for(register int j=i+1;j<=cnt_point;j++)

 95         {

 96             bool flag=1;

 97             for(register int k=1;k<=cnt_line;k++)

 98             {

 99                 if(SegCrossSimple(p[i],p[j],l[k].a,l[k].b))

100                 {

101                     flag=0;

102                     break;

103                 }

104             }

105             if(flag)

106                 dist[i][j]=dis(i,j);

107             else

108                 dist[i][j]=INF;

109

110             dist[j][i]=dist[i][j];

111         }

112     }

113

114     for(register int k=1;k<=cnt_point;k++)

115         for(register int i=1;i<=cnt_point;i++)

116             for(register int j=1;j<=cnt_point;j++)if(dist[i][k]!=INF&&dist[k][j]!=INF)

117                 dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);

118

119     printf("%.2lf\n",dist[1][2]);

120 }

121

122 int main()

123 {

124     while(scanf("%d",&n)==1)

125     {

126         if(n==-1)break;

127         solve();

128     }

129     return 0;

130 }

巴特西

[日常摸鱼]UVA393 The Doors 简单计算几何+最短路

最新文章

热门文章