The Doors POJ 1556：计算几何与最短路问题

The Doors POJ - 1556
分类： 计算几何 +判断线段交叉+最短路

   题外话：痛苦的领悟，找bug半天，发现是自己定义两个名称一样的变量，导致后面的错了，maye，找了一个小时。多次事实告诉我，不要定义两个重名的

   思路：保存点的 信息 ，墙信息，给两两个点之间符合条件（不与线段(墙)交叉）建立边，最短路直接Floyd找答案。

//没两点建立边，跑最短路。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<stdlib.h>
using namespace std;
const double minn=1e-8;
const int maxn=110;
const int inf=0x7f7f7f7f;
double map[maxn][maxn];
int cnt,tot,n;
struct  point
{
    double x,y;
    point(){}
    point(double _x,double _y){x=_x;y=_y;}
}p[maxn];
struct egde
{
    point start,end;//
    egde(){}
    egde(point a,point b){
       start=a;end=b;}
}egdes[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));
}
//判断线段相交
double multi(point p1,point p2,point p0)
{
    return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}
bool intAcross(egde v1,egde v2)
{
    if(max(v1.start.x,v1.end.x)>=min(v2.start.x,v2.end.x)&&
        max(v2.start.x,v2.end.x)>=min(v1.start.x,v1.end.x)&&
        max(v1.start.y,v1.end.y)>=min(v2.start.y,v2.end.y)&&
        multi(v2.start,v1.end,v1.start)*multi(v1.end,v2.end,v1.start)>0&&
        multi(v1.start,v2.end,v2.start)*multi(v2.end,v1.end,v2.start)>0) return 1;//相交
    return 0;
}
//判断线段相交
bool judge(point a,point b)//线段ab与ede
{
   for(int i=0;i<tot;i++)
    if(intAcross(egde(a,b),egdes[i])) return 0;
    return 1;
}

int main()
{
    double a,b,c,d,e;
    while(~scanf("%d",&n)&&n!=-1)
    {
        memset(map,inf,sizeof(map));
        cnt=0;tot=0;
        p[cnt++]=point(0,5);// x=0,p[cnt++].y=5;
        for(int i=0;i<n;i++)
        {
            scanf("%lf%lf%lf%lf%lf",&a,&b,&c,&d,&e);
            p[cnt++]=point(a,b);
            p[cnt++]=point(a,c);
            p[cnt++]=point(a,d);
            p[cnt++]=point(a,e);
            egdes[tot++]=egde(point(a,0),point(a,b));
            egdes[tot++]=egde(point(a,c),point(a,d));
            egdes[tot++]=egde(point(a,e),point(a,10));
        }
        p[cnt++]=point(10,5);
        for(int i=0;i<cnt;i++)//建立边
        {
            for(int j=i+1;j<cnt;j++)
            {
                if(fabs(p[i].x-p[j].x)<minn) continue;
                if(judge(p[i],p[j]))
                {
                    //printf("%f %f %f %f --- %f\n",p[i].x, p[i].y, p[j].x, p[j].y,abs(p[i].x-p[j].x));
                    map[i][j]=map[j][i]=dis(p[i],p[j]);
                }
            }
        }
        for(int k=0;k<cnt;k++)
        for(int i=0;i<cnt;i++)
        for(int j=0;j<cnt;j++)
            map[i][j]=min(map[i][j],map[i][k]+map[k][j]);
        printf("%.2f\n",map[0][cnt-1]);
    }
    return 0;
}


免责声明：本文系网络转载或改编，未找到原创作者，版权归原作者所有。如涉及版权，请联系删