poj1556 The Doors

poj1556 The Doors

​​ You are to find the length of the shortest path through a chamber containing obstructing walls. The chamber will always have sides at x = 0, x = 10, y = 0, and y = 10. The initial and final points of the path are always (0, 5) and (10, 5). There will also be from 0 to 18 vertical walls inside the chamber, each with two doorways. The figure below illustrates such a chamber and also shows the path of minimal length.

Input

The input data for the illustrated chamber would appear as follows.

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 The output should contain one line of output for each chamber. The line should contain the minimal path length rounded to two decimal places past the decimal point, and always showing the two decimal places past the decimal point. The line should contain no blanks.

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

这里用了叉乘判断相交的解法，本来死活过不去，后来随便改改等于号什么的就过了。。对这个叉乘什么的还不太会，留坑待填，另外%lf 在Poj上g++会有问题

#include #include #include #include #include #define N 110using namespace std;struct node{ int y,next;double z;}data[55000];struct pp{ double x,y;}point[110];struct lli{ pp pa,pb;}line[110];int h[N<<2],num,cnt,m;inline void cl(double x1,double y1,double x2,double y2){line[++m].pa.x=x1;line[m].pa.y=y1;line[m].pb.x=x2;line[m].pb.y=y2;}inline double calc(pp a,pp b){ return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}inline void insert1(int x,int y,double z){ data[++cnt].y=y;data[cnt].next=h[x];data[cnt].z=z;h[x]=cnt; data[++cnt].y=x;data[cnt].next=h[y];data[cnt].z=z;h[y]=cnt;}inline double multiply(pp a,pp b,pp c){ return (a.x-c.x)*(b.y-c.y)-(b.x-c.x)*(a.y-c.y);}inline bool cross(lli line1,lli line2){ pp aa=line1.pa,bb=line1.pb,cc=line2.pa,dd=line2.pb; if (max(aa.x,bb.x) q;memset(flag,0,sizeof(flag));flag[1]=true;q.push(1);memset(f,0x7f,sizeof(f));f[1]=0; while (!q.empty()){ int x=q.front();q.pop();flag[x]=false; for (int i=h[x];i;i=data[i].next){ int y=data[i].y;double z=data[i].z; if (f[x]+z

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。