#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>

using namespace std;

#define inf 20000000000
#define M 150

struct Point
{
    double x;
    double y;
}p[M];

struct edge
{
    int u;
    int v;
}e[10050];

int n;//房间的数目
int pSize; //点的数目
double wX[20];//墙的X坐标
double pY[20][4];//Y的坐标
double map[M][M];//邻接矩阵
int eSize; //边的数目
int i,j;

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

double Cross(double x1,double y1,double x2,double y2,double x3,double y3) //判断点是否在直线的上方还是下方
{
    return (x2-x1)*(y3-y1) - (x3-x1)*(y2-y1);
}
bool Ok(Point a,Point b) //判断在构造有向网的时候两点能否连边
{
    if(a.x>=b.x) return false;
    bool flag = true;
    int i = 0;
    while(wX[i]<=a.x&&i<n){
        i++;
    }
    while(wX[i]<b.x&&i<n){
        if(Cross(a.x,a.y,b.x,b.y,wX[i],0)*Cross(a.x,a.y,b.x,b.y,wX[i],pY[i][0])<0
           ||
           Cross(a.x,a.y,b.x,b.y,wX[i],pY[i][1])*Cross(a.x,a.y,b.x,b.y,wX[i],pY[i][2])<0
           ||
           Cross(a.x,a.y,b.x,b.y,wX[i],pY[i][3])*Cross(a.x,a.y,b.x,b.y,wX[i],10)<0){
            flag = false;
            break;
           }
           i++;
    }
    return flag;
}
double bellman(int beg,int end)
{
    double dist[M];
    int i,j;
    for(i=0;i<M;i++){
        dist[i] = inf;
    }
    dist[beg] = 0;
    bool ex = true;
    for(i=0;i<pSize&&ex;i++){
            ex = false;
            for(j=0;j<eSize;j++){
                if(dist[e[j].u]<inf&&(dist[e[j].v]>(dist[e[j].u]+map[e[j].u][e[j].v]))){
                    dist[e[j].v] = dist[e[j].u]+map[e[j].u][e[j].v];
                    ex = true;
            }
        }
    }
    return dist[end];
}

void solve()
{
    p[0].x = 0;
    p[0].y = 5;
    pSize = 1;
    for(i=0;i<n;i++){
        scanf("%lf",&wX[i]);
        for(j=0;j<4;j++){
            p[pSize].x = wX[i];
            scanf("%lf",&p[pSize].y);
            pY[i][j] = p[pSize].y;
            pSize++;
        }
    }
    p[pSize].x=10;
    p[pSize].y=5;

    pSize++;
    for(i=0;i<pSize;i++){
            for(j=0;j<pSize;j++){
                map[i][j] = inf;
            }
    }
    eSize = 0;
    for(i=0;i<pSize;i++){
        for(j=i+1;j<pSize;j++){
            if(Ok(p[i],p[j])){
                map[i][j] = Dis(p[i],p[j]);
                e[eSize].u = i;
                e[eSize].v = j;
                eSize++;
            }
        }
    }
    printf("%.2lf\n",bellman(0,pSize-1));

}

int main ()
{
    while(scanf("%d",&n)!=EOF){
        if(n==-1) break;
        solve();
    }
    return 0;
}

• Re:建图建醉了 最后提交G++ WA c++AC 这TM的是为什么？ (55) dtxm 2017-02-11 17:42:21