poj 1556 The Doors(最短路+幾何)

題意：有一個小屋，起點在(0,5)，重點在(10,5)，中間有0—18堵牆，每堵牆上有兩個門，求起點到終點最短路

思路：起點和終點和門的端點建圖求最短路，在求兩個端點之間的距離（直線距離）的時候要判斷兩個端點之間是否有牆隔着

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iomanip>
#include <cmath>
using namespace std;

const int MAXN = ;
const double INF = ;
const double precision = ;
struct Point
{
    double x,y;
    Point(){}
    Point(double xx, double yy):x(xx),y(yy){}
};
struct Line
{
    Point sp,ep;
    Line(){}
    Line(Point a, Point b):sp(a),ep(b){}
};
int n,pcnt,lcnt;
Point ps[MAXN];
Line ls[MAXN];
double g[MAXN][MAXN];
double dis[MAXN];
int book[MAXN];

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

int dblcmp(double d)
{
    if(fabs(d) < precision)
        return ;
    return d >  ?  : -;
}

double det(Point a, Point b, Point c)
{
    //b.x-a.x,b.y-a.y
    //c.x-a.x,c.y-a.y
    return (b.x-a.x)*(c.y-a.y) - (c.x-a.x)*(b.y-a.y);
}

bool intersect(Point a, Point b, Line p)
{
    int d1 = dblcmp(det(a,b,p.sp));
    int d2 = dblcmp(det(a,b,p.ep));
    int d3 = dblcmp(det(p.sp,p.ep,a));
    int d4 = dblcmp(det(p.sp,p.ep,b));
    if(d1*d2 <  && d3*d4 < )
        return true;
    return false;
}

bool check(int i, int j)
{
    for(int k = ; k < lcnt; ++k)
    {
        if(intersect(ps[i],ps[j],ls[k]))
            return false;
    }
    return true;
}

double dijkstra()
{
    memset(book,,sizeof(book));
    for(int i = ; i <= pcnt; ++i)
        dis[i] = g[][i];
    book[] = ;
    double minn;
    int u,v;
    for(int i = ; i <= pcnt-; ++i)
    {
        minn = INF;
        for(int j = ; j <= pcnt; ++j)
        {
            if(book[j] ==  &&  dis[j] < minn)
            {
                minn = dis[j];
                u = j;
            }
        }
        book[u] = ;
        for(v = ; v <= pcnt; ++v)
        {
            if(dis[v] > dis[u] + g[u][v])
                dis[v] = dis[u] + g[u][v];
        }
    }
    return dis[pcnt];
}

int main()
{
    double x,y;
    while(scanf("%d",&n) && n != -)
    {
        pcnt = ;
        lcnt = ;
        memset(g,,sizeof(g));
        ps[pcnt++] = Point(,);
        for(int i = ; i < n; ++i)
        {
            cin >> x;
            for(int k = ; k < ; ++k)
            {
                cin >> y;
                ps[pcnt++] = Point(x,y);
            }
            ls[lcnt++] = Line(Point(x,),ps[pcnt-]);
            ls[lcnt++] = Line(ps[pcnt-],ps[pcnt-]);
            ls[lcnt++] = Line(ps[pcnt-],Point(x,));
        }
        ps[pcnt] = Point(,);
        for(int i = ; i <= pcnt; ++i)
        {
            for(int j = ; j <= pcnt; ++j)
            {
                if(i == j) g[i][j] = ;
                else if(check(i,j)) g[i][j] = dist(ps[i],ps[j]);
                else g[i][j] = INF;
            }
        }
        double res = dijkstra();
//        for(int k = 1; k <= pcnt; ++k)
//        {
//            for(int i = 1; i <= pcnt; ++i)
//            {
//                for(int j = 1; j <= pcnt; ++j)
//                    if(g[i][k]+g[k][j] < g[i][j])
//                        g[i][j] = g[i][k] + g[k][j];
//            }
//        }
        cout << fixed << setprecision() << res << endl;
    }
    return ;
}