注册 登录  
 加关注

网易博客网站关停、迁移的公告:

将从2018年11月30日00:00起正式停止网易博客运营
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

zxj015

 
 
 

日志

 
 

poj 1556 The Doors 线段相交判断+最短路  

2011-04-30 18:13:37|  分类: 计算几何 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
求点(0,5)到(10,5)的最短距离。
图中任意两点(x座标不同)连线若没有与墙相交,则求出两点之间的距离加入最短路矩阵中,否则为无穷大。接下来用 dijkstra法求最短路即可。本题主要建图比较繁琐一点。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<iostream>
#include<cmath>
using namespace std;
struct point
{
double x,y;
};
struct line
{
point a,b;
};
struct door
{
double x,q[4];
}p[2000];
double multi(point p0,point p1,point p2)
{
return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}

bool is(point s1,point e1,point s2,point e2) //判断线段是否相交 
{
return (max(s1.x,e1.x)>=min(s2.x,e2.x))&&
  (max(s2.x,e2.x)>=min(s1.x,e1.x))&&
  (max(s1.y,e1.y)>=min(s2.y,e2.y))&&
  (max(s2.y,e2.y)>=min(s1.y,e1.y))&&
  (multi(s1,s2,e1)*multi(s1,e1,e2)>0)&&
  (multi(s2,s1,e2)*multi(s2,e2,e1)>0);
}
double dis(point p1,point p2)
{
return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
}

int sink;
double di[2000],flow[2000][2000];
bool flag[2000];
void dijkstra()
{
     int i,j,v;
double min;
   
        memset(flag,true,sizeof(flag));  
        flag[0]=false;
        for(i=0;i<=sink;i++)
            di[i]=flow[0][i];
        for(i=0;i<sink;i++)
        {
           min=99999;
           for(j=0;j<=sink;j++)
           {
               if(flag[j]==true&&min>di[j])
               {
                   min=di[j];
                   v=j;
               }
           }
           flag[v]=false;
          
           for(j=0;j<=sink;j++)
           {
               if(flag[j]==true&&di[j]>flow[v][j]+di[v])
               di[j]=flow[v][j]+di[v];
           }
        }
}
int main()
{
int m,n,x,i,j,k,h,flag1;
point s1,e1,s2,e2;
while(scanf("%d",&n),n!=-1)
{
for(i=1;i<=n;i++)
scanf("%lf%lf%lf%lf%lf",&p[i].x,&p[i].q[0],&p[i].q[1],&p[i].q[2],&p[i].q[3]);
    for(i=0;i<=4*n+1;i++)
    for(j=0;j<=4*n+1;j++)
    flow[i][j]=99999;
for(i=0;i<=n;i++)
for(k=0;k<4;k++)
{
if(i==0&&k>0)
break;
for(j=i+1;j<=n+1;j++)
{
for(h=0;h<4;h++)
{
if(j==n+1&&h>0)
break;
if(i==0)
{
s1.x=0;s1.y=5;
}
else
{
s1.x=p[i].x;
s1.y=p[i].q[k];
}
if(j==n+1)
{
e1.x=10;
e1.y=5;
}
else
{
e1.x=p[j].x;
e1.y=p[j].q[h];
}
flag1=1;
for(m=i+1;m<j;m++)
{
e2.x=p[m].x;e2.y=0;
s2.x=p[m].x;s2.y=p[m].q[0];
if(is(s1,e1,s2,e2))
flag1=0;
e2.y=p[m].q[1];
s2.y=p[m].q[2];
if(is(s1,e1,s2,e2))
flag1=0;                               
e2.y=10;
s2.y=p[m].q[3];
if(is(s1,e1,s2,e2))
flag1=0;
    if(flag1==0)
    break;
}
if(flag1)
{
if(i==0)
{
flow[4*(j-1)+h+1][0]=flow[0][4*(j-1)+h+1]=dis(s1,e1);
}
else
{
flow[4*(j-1)+h+1][4*(i-1)+k+1]=flow[4*(i-1)+k+1][4*(j-1)+h+1]=dis(s1,e1);
}
    }
}
}
}
sink=4*n+1;
dijkstra();
printf("%.2f\n",di[4*n+1]);
}
}

  评论这张
 
阅读(105)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018