注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

zxj015

 
 
 

日志

 
 

poj 2074 Line of Sight  

2011-05-06 12:39:36|  分类: 计算几何 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
两条平行线段A,B,之间放有数条做为障碍物的线段,所有线段都平行,求B上能看到整个A的最长区间。
poj 2074 Line of Sight - 某年某月 - zxj015的博客
 求出各个障碍物所对应的不能看到整个A的区间,如上图所示区间[a,b]和区间[c,d],剩下的区间即为可看到整个A的区间,求出最长的就可以了。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<iostream>
#include<algorithm>
#define eps 1e-8
using namespace std;
int n;
struct point
{
double x,y;
}p[10000];
struct line
{
point a,b;
}h,pro,obs[10000];
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);
}
point inter(point u1,point u2,point v1,point v2)
{
  point ret=u1;
  double t=((u1.x-v1.x)*(v1.y-v2.y)-(u1.y-v1.y)*(v1.x-v2.x))
        /((u1.x-u2.x)*(v1.y-v2.y)-(u1.y-u2.y)*(v1.x-v2.x));
ret.x+=(u2.x-u1.x)*t;
  ret.y+=(u2.y-u1.y)*t;
  return ret;
}

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);
}
bool judge(point p1,point p2,point t1,point t2)
{
if(multi(p1,p2,t1)*multi(p1,p2,t2)<eps)
return true;
else
return false;
}
bool cmp(point a,point b)
{
return a.x<b.x;
}
void work()
{
int i,num,j=0;
point t;
double ans=-1,y;
if(n==0)
{
printf("%.2f\n",pro.b.x-pro.a.x);
return;
}
for(i=0;i<n;i++,j++)
{
if(judge(h.b,obs[i].a,pro.a,pro.b))
{
t=inter(h.b,obs[i].a,pro.a,pro.b);
p[j].x=t.x;
}
else
{
if(multi(obs[i].a,h.b,pro.b)>-eps)
p[j].x=pro.b.x;
else
p[j].x=pro.a.x;
}
if(judge(h.a,obs[i].b,pro.a,pro.b))
{
t=inter(h.a,obs[i].b,pro.a,pro.b);
p[j].y=t.x;
}
else
{
if(multi(obs[i].b,pro.a,h.a)>-eps)
p[j].y=pro.a.x;
else
p[j].y=pro.b.x;
}
if(fabs(p[j].x-pro.a.x)<eps&&fabs(p[j].y-pro.b.x)<eps)
{
printf("No View\n");
return;
}
if(fabs(p[j].x-p[j].y)<eps)
j--;
}
num=j;
sort(p,p+num,cmp);
y=pro.a.x;
for(i=0;i<num;i++)
{
if(p[i].x-y>eps)
{
if(p[i].x-y-ans>eps)
ans=p[i].x-y;
y=p[i].y;
}
else if(p[i].y-y>eps)
y=p[i].y;
}
if(pro.b.x-y>ans)
ans=pro.b.x-y;
if(ans<eps)
printf("No View\n");
else
printf("%.2f\n",ans);
}
int main()
{
int i,j;
while(scanf("%lf%lf%lf",&h.a.x,&h.b.x,&h.a.y),h.a.x+h.b.x+h.a.y)
{
h.b.y=h.a.y;
j=0;
scanf("%lf%lf%lf",&pro.a.x,&pro.b.x,&pro.a.y);
pro.b.y=pro.a.y;
scanf("%d",&n);
for(i=0;i<n;i++,j++)
{
scanf("%lf%lf%lf",&obs[j].a.x,&obs[j].b.x,&obs[j].a.y);
obs[j].b.y=obs[j].a.y;
if(obs[j].b.y-pro.a.y<-eps||obs[j].b.y-h.a.y>eps)
j--;
}
n=j;
work();
}
return 0;
}



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

历史上的今天

评论

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

页脚

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