POJ 1556

枚举每两点的直线,看连线中是否存在线段交点,若存在,即这两点的直线不存在。建图,DIJK就可以了。

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <cmath>
  5 #include <algorithm>
  6 using namespace std;
  7
  8 const int Max=100;
  9 const int M=3000;
 10 const int inf=10000;
 11 typedef struct pt{
 12     double x,y;
 13     int belong;
 14 }Point;
 15
 16 typedef struct pl{
 17     Point start,end;
 18 }Pleg;
 19 int how_point,how_pleg;
 20 Point pot[Max];
 21 Pleg edge[Max];
 22
 23 double multi(Point p1, Point p2,Point p0){
 24     return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
 25 }
 26 int head[Max],tot;
 27 struct {
 28     int u,v;
 29     double w;
 30     int next;
 31 }de[M];
 32 double dis[Max];
 33 bool vis[Max];
 34
 35 bool tested(Pleg v1,Point s,Point t){
 36     Pleg v2; v2.start=s; v2.end=t;
 37     if(max(v1.start.x,v1.end.x)>=min(v2.start.x,v2.end.x)&&
 38        max(v2.start.x,v2.end.x)>=min(v1.start.x,v1.end.x)&&
 39        max(v1.start.y,v1.end.y)>=min(v2.start.y,v2.end.y)&&
 40        multi(v2.start,v1.end,v1.start)*multi(v1.end,v2.end,v1.start)>0&&
 41        multi(v1.start,v2.end,v2.start)*multi(v2.end,v1.end,v2.start)>0)
 42        return false;
 43        return true;
 44 }
 45
 46 void addedge(int u,int v,double w){
 47     de[tot].u=u;
 48     de[tot].v=v;
 49     de[tot].w=w;
 50     de[tot].next=head[u];
 51     head[u]=tot++;
 52 }
 53
 54 void dijk(int s,int t){
 55     vis[s]=true; dis[s]=0;
 56     for(int i=head[s];i!=-1;i=de[i].next){
 57         int v=de[i].v;
 58         if(dis[v]>de[i].w)
 59         dis[v]=de[i].w;
 60     }
 61     for(int i=0;i<=how_point;i++){
 62         int p=s; double min=inf;
 63         for(int j=0;j<=how_point;j++){
 64             if(dis[j]<min&&!vis[j]){
 65                 min=dis[j]; p=j;
 66             }
 67         }
 68         if(p==s) return ;
 69         vis[p]=true;
 70         for(int k=head[p];k!=-1;k=de[k].next){
 71             int v=de[k].v;
 72             if(min+de[k].w<dis[v]&&!vis[v]){
 73                 dis[v]=min+de[k].w;
 74             }
 75         }
 76     }
 77 }
 78
 79 int main(){
 80     pot[0].x=0; pot[0].y=5;
 81     int n; double a,b,c,d,e; Point tmp;
 82     while(scanf("%d",&n)!=EOF){
 83         if(n==-1) break;
 84         how_pleg=0;how_point=0;
 85         memset(head,-1,sizeof(head)); tot=0;
 86         memset(vis,false,sizeof(vis));
 87         for(int i=0;i<Max;i++)
 88         dis[i]=inf;
 89         for(int i=1;i<=n;i++){
 90             scanf("%lf%lf%lf%lf%lf",&a,&b,&c,&d,&e);
 91             how_pleg++;    how_point++;
 92             tmp.x=a; tmp.y=0; tmp.belong=how_pleg;
 93             pot[how_point].x=a; pot[how_point].y=b; pot[how_point].belong=how_pleg;
 94             edge[how_pleg].start=tmp; edge[how_pleg].end=pot[how_point];
 95             how_point++; how_pleg++;
 96             pot[how_point].x=a; pot[how_point].y=c; pot[how_point].belong=how_pleg;
 97             how_point++;
 98             pot[how_point].x=a; pot[how_point].y=d; pot[how_point].belong=how_pleg;
 99             edge[how_pleg].start=pot[how_point-1]; edge[how_pleg].end=pot[how_point];
100             how_point++;  how_pleg++;
101             pot[how_point].x=a; pot[how_point].y=e; pot[how_point].belong=how_pleg;
102             tmp.x=a; tmp.y=10; tmp.belong=how_pleg;
103             edge[how_pleg].start=pot[how_point]; edge[how_pleg].end=tmp;
104         }
105         how_point++;
106         pot[how_point].x=10; pot[how_point].y=5;pot[how_point].belong=how_pleg+1;
107         for(int i=0;i<=how_point;i++){
108             for(int j=i+1;j<=how_point;j++){
109                 int e=pot[j].belong;
110                 bool flag=true;
111                 for(int k=1;k<e;k++){
112                     if(!tested(edge[k],pot[i],pot[j])){
113                         flag=false;
114                         break;
115                     }
116                 }
117                 if(flag){
118                     double x=pot[i].x-pot[j].x;
119                     double y=pot[j].y-pot[i].y;
120                     double d=sqrt(x*x+y*y);
121                     addedge(i,j,d);
122                 }
123             }
124         }
125         dijk(0,how_point);
126         printf("%0.2lf\n",dis[how_point]);
127     }
128 }

POJ 1556,布布扣,bubuko.com

时间: 07-23

POJ 1556的相关文章

Poj 1556 The Doors 计算几何+最短路

其实本题非常的无脑,无脑拍完1A,写到blog里只因为TM无脑拍也拍了很久啊= = #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #include <climits> #include <string> #include <iostream> #include <map> #include <cstdl

POJ 1556 - The Doors 线段相交不含端点

POJ 1556 - The Doors题意:    在 10x10 的空间里有很多垂直的墙,不能穿墙,问你从(0,5) 到 (10,5)的最短距离是多少.    分析:        要么直达,要么一定是墙的边缘点之间以及起始点.终点的连线.        所以先枚举墙上每一点到其他点的直线可达距离,就是要判定该线段是否与墙相交(不含端点).        然后最短路. 1 #include <iostream> 2 #include <cstdio> 3 #include &l

最短路+线段交 POJ 1556 好题

1 // 最短路+线段交 POJ 1556 好题 2 // 题意:从(0,5)到(10,5)的最短距离,中间有n堵墙,每堵上有两扇门可以通过 3 // 思路:先存图.直接n^2来暴力,不好写.分成三部分,起点 终点和之间的点:中间点之间:起点和终点的距离 4 // n最大为18所以直接n^3最短路 5 6 7 #include <cstdio> 8 #include <cstring> 9 #include <iostream> 10 #include <algo

POJ 2263 POJ 1556

2263 题目意思是求起点城市到终点城市的途径中的最大载重量,可以用Dijkstra或者floyd 来解决,我是用的floyd 感觉更直观 因为只需要将递推式改成w[i][j] = Max(w[i][j],Min(w[i][k],w[k][j]));便可得到答案,而且floyd写法比较简单但是复杂度为n的3次方,不过此题还是能AC Source Code Problem: 2263 User: lyz963254 Memory: 760K Time: 32MS Language: G++ Res

POJ 1556 The Doors

计算几何+最短路 枚举线段是否相交建图,然后跑最短路 #include<cstdio> #include<cstring> #include<vector> #include<cmath> #include<queue> #include<algorithm> using namespace std; const int maxn=1000+10; const double eps=1e-8; int n; int totP,totL

POJ 1556 The Doors(线段交+最短路)

#include <iostream> #include <stdio.h> #include <string.h> #include <algorithm> #include <queue> #include <map> #include <vector> #include <set> #include <string> #include <math.h> using namespac

POJ 1556 The Doors --几何,最短路

题意: 给一个正方形,从左边界的中点走到右边界的中点,中间有一些墙,问最短的距离是多少. 解法: 将起点,终点和所有墙的接触到空地的点存下来,然后两两之间如果没有线段(墙)阻隔,就建边,最后跑一个最短路SPFA,即可得出答案. 代码: #include <iostream> #include <cstdio> #include <cstring> #include <cstdlib> #include <cmath> #include <a

The Doors - POJ 1556 (线段相交)

题目大意:有一个房间(左上角(0,10),右下角(10,0)),然后房间里有N面墙,每面墙上都有两个门,求出来从初始点(0,5),到达终点(10,5)的最短距离. 分析:很明显根据两点之间直线最短,所以所走的路线一定是点之间的连线,只需要判断一下这两点间知否有墙即可. 代码如下: =============================================================================================================

简单几何(线段相交+最短路) POJ 1556 The Doors

题目传送门 题意:从(0, 5)走到(10, 5),中间有一些门,走的路是直线,问最短的距离 分析:关键是建图,可以保存所有的点,两点连通的条件是线段和中间的线段都不相交,建立有向图,然后用Dijkstra跑最短路.好题! /************************************************ * Author :Running_Time * Created Time :2015/10/24 星期六 09:48:49 * File Name :POJ_1556.cpp