The Doors
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 5 4 6 7 8 2 4 2 7 8 9 7 3 4.5 6 7 -1
Sample Output
10.00 10.06
题目就是说,给你一个10*10的正方形房间,里面会用一些垂直与x轴的墙隔开.每个墙上有两个门,然后给你门的两个端点坐标,要求求出从(0,5)走到(10,5)的最短路；
那其实本质上就是最短路,如果没有墙隔开,就单单这几个点,那就很水了.现在还要求判断一下,某两点之间是否可以直达.所谓直达,就是,这两点的连线不与其他任何墙相交(交于端点是允许的).
至此,题目解完了.
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#define INF 10000000
using namespace std;
;
int n;
][];
];
],o;
double dis(point a,point b){return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}
:x>eps;}
double cross(point a,point b){return a.x*b.y-a.y*b.x;}
point operator - (point a,point b){point ret; ret.x=a.x-b.x,ret.y=a.y-b.y; return ret;}
int Intersect(point a,point b,point c,point d){
double s1,s2,s3,s4;
int d1,d2,d3,d4;
d1=dcmp(s1=cross(a-c,b-c));
d2=dcmp(s2=cross(a-d,b-d));
d3=dcmp(s3=cross(c-a,d-a));
d4=dcmp(s4=cross(c-b,d-b));
&&(d3^d4)==-) ;
;
}
int main(){
; scanf("%d",&n)){
,cnt0=; P[].x=,P[].y=;
; i<n; i++){
double x,y1,y2,y3,y4;
scanf("%lf%lf%lf%lf%lf",&x,&y1,&y2,&y3,&y4);
P[cnt].x=x,P[cnt++].y=y1;
P[cnt].x=x,P[cnt++].y=y2;
P[cnt].x=x,P[cnt++].y=y3;
P[cnt].x=x,P[cnt++].y=y4;
seg[cnt0].a.x=x,seg[cnt0].a.y=,seg[cnt0].b.x=x,seg[cnt0++].b.y=y1;
seg[cnt0].a.x=x,seg[cnt0].a.y=y2,seg[cnt0].b.x=x,seg[cnt0++].b.y=y3;
seg[cnt0].a.x=x,seg[cnt0].a.y=y4,seg[cnt0].b.x=x;seg[cnt0++].b.y=;
}
P[cnt].x=,P[cnt].y=;
; i<=cnt; i++){
; j<=cnt; j++) cost[i][j]=INF; cost[i][i]=;
}
; i<=cnt; i++){
; j<=cnt; j++) if (j!=i){
o.a.x=P[i].x,o.a.y=P[i].y,o.b.x=P[j].x,o.b.y=P[j].y;
;
; k<cnt0; k++) ){flag=; break;}
) cost[i][j]=dis(P[i],P[j]);
}
}
; k<=cnt; k++)
; i<=cnt; i++)
; j<=cnt; j++) if (cost[i][k]+cost[k][j]<cost[i][j]) cost[i][j]=cost[i][k]+cost[k][j];
printf(][cnt]);
}
;
}