「POJ1556」The Doors
Description

Input
2
4 2 7 8 9
7 3 4.5 6 7
The first line contains the number of interior walls. Then there is a line for each such wall, containing five real numbers. The first number is the x coordinate of the wall (0 < x < 10), and the remaining four are the y coordinates of the ends of the doorways in that wall. The x coordinates of the walls are in increasing order, and within each line the y coordinates are in increasing order. The input file will contain at least one such set of data. The end of the data comes when the number of walls is -1.
Output
Sample Input
|
1 2 3 4 5 6 |
1 5 4 6 7 8 2 4 2 7 8 9 7 3 4.5 6 7 -1 |
Sample Output
|
1 2 |
10.00 10.06 |
题解
此题只要将图中线段的端点拿出来连边即可,需要判断是否不于其它线段相交
然后随便做个最短路
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 |
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #define eps 1e-5 #define inf 1e10 using namespace std; int n,m,k,cnt,head[201],q[201]; bool inq[201]; double d[201]; struct point{double x,y;}p[101]; struct line{point a,b;}l[101]; struct edge{int to,next;double v;}e[50001]; double sqr(double x){return x*x;} double dis(point a,point b) {return sqrt(sqr(a.x-b.x)+sqr(a.y-b.y));} void ins(int u,int v,double w) {e[++cnt].to=v;e[cnt].v=w;e[cnt].next=head[u];head[u]=cnt;} void insert(int u,int v,double w) {ins(u,v,w);ins(v,u,w);} void con(double x1,double y1,double x2,double y2) { m++;l[m].a.x=x1;l[m].a.y=y1; l[m].b.x=x2;l[m].b.y=y2; } point sub(point a,point b) {point t;t.x=a.x-b.x;t.y=a.y-b.y;return t;} double cmul(point a,point b) {return a.x*b.y-a.y*b.x;} double turn(point p1,point p2,point p3) {return cmul(sub(p3,p1),sub(p2,p1));} bool cross(line a,line b) { if(turn(a.a,a.b,b.a)*turn(a.a,a.b,b.b)>=0)return 0; if(turn(b.a,b.b,a.a)*turn(b.a,b.b,a.b)>=0)return 0; return 1; } bool jud(point a,point b) { line t;t.a=a;t.b=b; for(int i=1;i<=m;i++) if(cross(l[i],t))return 0; return 1; } void build() { for(int i=1;i<=k;i++) for(int j=i+1;j<=k;j++) if(jud(p[i],p[j]))insert(i,j,dis(p[i],p[j])); } void spfa() { for(int i=1;i<=k;i++)d[i]=inf; int t=0,w=1; q[0]=1;d[1]=0;inq[1]=1; while(t!=w) { int now=q[t];t++;if(t==201)t=0; for(int i=head[now];i;i=e[i].next) { if(d[now]+e[i].v<d[e[i].to]) { d[e[i].to]=d[now]+e[i].v; if(!inq[e[i].to]) {inq[e[i].to]=1;q[w++]=e[i].to;if(w==201)w=0;} } } inq[now]=0; } } int main() { while(scanf("%d",&n)&&n!=-1) { memset(head,0,sizeof(head)); m=k=cnt=0; p[++k].x=0;p[k].y=5; for(int i=1;i<=n;i++) { double x,y1,y2,y3,y4; scanf("%lf%lf%lf%lf%lf",&x,&y1,&y2,&y3,&y4); p[++k].x=x;p[k].y=y1; p[++k].x=x;p[k].y=y2; p[++k].x=x;p[k].y=y3; p[++k].x=x;p[k].y=y4; con(x,0,x,y1);con(x,y2,x,y3);con(x,y4,x,10); } p[++k].x=10;p[k].y=5; build(); spfa(); if(d[k]==inf)printf("-1\n"); else printf("%.2lf\n",d[k]); } return 0; } |