POJ 1556 The Doors

Description

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

这道题改了好久，其实就是计算几何＋最短路，我定义的point还编译错误，只好改成POINT，然后……我发现多组数据忘清零了，????

#include<cstdio>
#include<cmath>
#include<iostream>
#include<cstring>
using namespace std;
typedef long long ll;
const int maxn=1010;
const double inf=999999999;
double eps=1e-8;
int n,cnt,visit[maxn];
double d[maxn],g[maxn][maxn];

struct POINT{
double x,y;
POINT(double a=0,double b=0) {x=a; y=b;}
}p[3*maxn];

struct segment{
    POINT s,e;
    segment(POINT a,POINT b) {s=a;e=b;}
    segment() {}
}s[3*maxn];
//叉积
double cross(POINT a,POINT b,POINT c){
    return (a.x-c.x)*(b.y-c.y)-(a.y-c.y)*(b.x-c.x);
}

//判断点在线段上
bool online(segment l,POINT p){
    return ((cross(l.e,p,l.s)==0) && (((p.x-l.s.x)*(p.x-l.e.x)<=0) && ((p.y-l.s.y)*(p.y-l.e.y)<=0)));
}
// 如果线段u和v相交(包括相交在端点处)时，返回true
bool intersect(segment u,segment v){
    return( (max(u.s.x,u.e.x)>=min(v.s.x,v.e.x))&&                     //排斥实验
   (max(v.s.x,v.e.x)>=min(u.s.x,u.e.x))&&
   (max(u.s.y,u.e.y)>=min(v.s.y,v.e.y))&&
   (max(v.s.y,v.e.y)>=min(u.s.y,u.e.y))&&
   (cross(v.s,u.e,u.s)*cross(u.e,v.e,u.s)>=0)&&         //跨立实验
   (cross(u.s,v.e,v.s)*cross(v.e,u.e,v.s)>=0));
}

//  (线段u和v相交)&&(交点不是双方的端点) 时返回true
bool Intersect(segment u,segment v)
{
 return ((intersect(u,v))&&
   (!online(u,v.s))&&
   (!online(u,v.e))&&
   (!online(v,u.e))&&
   (!online(v,u.s)));
}

double Distance(POINT p1,POINT p2){
return (sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y)));
}

void dijkstra(int s){
    fill(visit,visit+maxn,0);
    fill(d,d+maxn,inf);
    d[s]=0.0;
    for(int i=0;i<n;i++){
        int u=-1,minn=inf;
        for(int j=0;j<n;j++){
            if(!visit[j] && d[j]<minn){
                u=j;
                minn=d[j];
            }
        }
        if(u==-1) return ;
        visit[u]=1;
        for(int v=0;v<n;v++){
            if(!visit[v] && d[u]+g[u][v]<d[v])
                d[v]=d[u]+g[u][v];
        }
    }
}

void build(){
	for(int i=0;i<n;i++){
       for(int j=0;j<n;j++){
           if(i==j) {g[i][j]=0.0;continue;}
           else{
               int flag=1;
               segment L;
               L.s=p[i];L.e=p[j];
               int l=(i+1)/2,r=(j+1)/2;
               for(int k=0;k<cnt;k++){
                   if(Intersect(L,s[k])) {
                       flag=0;
                       break;
                   }
               }
               if(flag) g[i][j]=Distance(p[i],p[j]);
               else g[i][j]=inf;
           }
       }
   }
}

int main()
{
    int t;
    double x,y;
    while(cin>>t && t!=-1){
        n=cnt=0;
        p[n].x=0,p[n++].y=5;
        while(t--){
            POINT pp[6];
            segment L;
            scanf("%lf",&x);
            pp[0].x=pp[5].x=x;
            pp[0].y=0.0;pp[5].y=10.0;
            p[n++]=pp[0];
            for(int i=1;i<=4;i++){
                scanf("%lf",&y);
                pp[i].x=x;
                pp[i].y=y;
                if(i%2==1) {L.s=pp[i-1];L.e=pp[i];s[cnt++]=L;}
                p[n++]=pp[i];
            }
            p[n++]=pp[5];
            L.s=pp[4];L.e=pp[5];s[cnt++]=L;
        }
        p[n].x=10.0;p[n++].y=5.0;
        build();
        dijkstra(0);
        printf("%.2f\n",d[n-1]);
    }
    return 0;
}