http://poj.org/problem?id=1556

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

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

Source

开始的时候真的是二逼了，

1、判断相交的函数写错了，我居然判断的是是不是跟源点和终点的直线相交。。。二逼啊，，，

2、然后改了之后还wa,因为判断里少了个！，，，，没取反，，，

3、极限的点，比如每道墙的最上沿和最下沿，这两个点不可达，就是说从源头到终点不能经过这两个点，开始的时候没排除，虽然那样的话也能AC,还是题目数据太弱了啊

我自己写的判断直线相交的模板：

/*==========================================================*||  判断点在直线上或直线相交
    1、函数值为0，表示在直线上；
    2、test(a,b,t1)*test(a,b,t2)<0表示直线ab和直线t1t2相交
\*==========================================================*/
double test(Point a,Point b, Point t)
{
    return (b.y-a.y)*(t.x-b.x)-(b.x-a.x)*(t.y-b.y);
}

思路还是比较顺的，就是最短路+判断直线相交

贴代码：

#include<cstdio>
#include<cstring>
#include <string>
#include <map>
#include <iostream>
#include <cmath>
using namespace std;
#define INF 10000
const double eps=1e-6;

const int MAXN = 1011;
#define Max(a,b) (a)>(b)?(a):(b)
int cntp;
int wn;
struct Point{
    Point(double x=0,double y=0):x(x),y(y){}
    double x,y;
    int id;
}p[MAXN];
struct Wall{
    double s1,e1;
    double s2,e2;
    double s3;
}w[20];//=0~~=wn
double e[MAXN][MAXN],dist[MAXN];

double dis(Point a, Point b)
{
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}

void init()
{
    cntp=1;
    for(int i=0;i<=MAXN;i++)
        for(int j=0;j<=MAXN;j++)
        {
            if(i == j)e[i][j]=0;
            else e[i][j]=INF;
        }
    p[0].x=0,p[0].y=5,p[0].id=0;
    for(int i=0;i<=MAXN;i++)dist[i]=INF;
}

double test(Point a,Point b, Point t)
{
    return (b.y-a.y)*(t.x-b.x)-(b.x-a.x)*(t.y-b.y);
}

bool Judge(Point a, Point b)
{
    if(a.id>b.id)
    {
        Point t=a;
        a=b;
        b=t;
    }
    //int flag=1;
    if(a.id>0)
        if(a.y -0.0 <=eps||10.0-a.y <=eps)
            return 0;
    if(b.id<cntp-1)
        if(b.y-0.0<=eps || 10.0-b.y<=eps)
            return 0;

    for(int i=a.id+1;i<b.id;i++)
    {
        Point p1(w[i].s1,w[i].e1),p2(w[i].s1,w[i].s2),p3(w[i].s1,w[i].e2),p4(w[i].s1,w[i].s3);

        if(!(
             test(a,b,p1)*test(a,b,p2)<0 ||
            test(a,b,p3)*test(a,b,p4)<0)
           )return 0;
    }
        /*for(int i=a.id+1;i<b.id;i++)
        {
            if(!(
                 (w[i].e1<5.0&&w[i].s2>5.0)
                || (w[i].e2<5.0&&w[i].s3>5.0)
                 )
               )return 0;
        }*/
    return 1;
}


void Build()
{
    for(int i=0;i<cntp;i++)
    {
        for(int j=i+1;j<cntp;j++)
        {
            //if(i == j)continue;
            if(p[i].id == p[j].id)continue;

            if(Judge(p[i],p[j]))
            {
                e[i][j]=min(e[i][j],dis(p[i],p[j]));
            }
        }
    }
}

void Bellman(int v0)
{
    int n=cntp;
    for(int i=0;i<cntp;i++)
    {
        dist[i]=e[v0][i];
        //if(i!=v0 && dist[i]<INF)
    }
    for(int k=2;k<n;k++)
    {
        for(int u=0;u<n;u++)
        {
            if(u!=v0)
            {
                for(int j=0;j<n;j++)
                {
                    if(e[j][u]!=INF && dist[j]+e[j][u]<dist[u])
                    {
                        dist[u]=dist[j]+e[j][u];
                    }
                }
            }
        }
    }
}


int main()
{
      //  freopen("poj1556.txt","r",stdin);
       while(~scanf("%d",&wn) && ~wn)
       {
           init();
           for(int i=1;i<=wn;i++)
           {
                scanf("%lf%lf%lf%lf%lf",&w[i].s1,&w[i].e1,&w[i].s2,&w[i].e2,&w[i].s3);
                p[cntp].id=p[cntp+1].id=p[cntp+2].id=p[cntp+3].id=p[cntp+4].id=p[cntp+5].id=i;
                p[cntp].x=p[cntp+1].x=p[cntp+2].x=p[cntp+3].x=p[cntp+4].x=p[cntp+5].x=w[i].s1;
                p[cntp].y=0.0,p[cntp+1].y=w[i].e1,p[cntp+2].y=w[i].s2,p[cntp+3].y=w[i].e2,p[cntp+4].y=w[i].s3,p[cntp+5].y=10.0;
                ////////////////
                //e[cntp+1][cntp+2]=w[i].s2-w[i].e1;
               // e[cntp+3][cntp+4]=w[i].s3-w[i].e2;
                cntp+=6;
           }
           p[cntp].x=10.0,p[cntp].y=5.0,p[cntp].id=++wn;
           cntp++;
           //if()
           Build();
           Bellman(0);
           printf("%.2lf\n",dist[cntp-1]);
           ///////////////////
          // for(int i=0;i<cntp;i++)
          //  printf("%d %lf\n",i,dist[i]);
       }
       return 0;
}