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

zxj015

 
 
 

日志

 
 

poj 1039 Pipe 直线线段相交判断+枚举  

2011-05-05 16:18:01|  分类: 计算几何 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

http://poj.org/problem?id=1039
黑书P359例题
题目要我们求出光线在Pipe里能射到的最远处的x坐标。我们只要找出其中一条最优光线。
一条最优光线必须满足的一个必要条件是:它必定过Pipe的一个上顶点和一个下顶点。否则,我们总可以通过平移或是旋转使光线走更远的距离。有了这个条件,就可以通过枚举所有的上下顶点对(i,j),找出最优的。
过上下顶点的光线共有n*n条,要求的就是
Max{X(i,j) | 过上下顶点对(i,j)能达到的最远距离的横坐标} (i=0..n-1,j=0..n-1;)
poj 1039 Pipe 直线线段相交判断+枚举 - 某年某月 - zxj015的博客
 
 
光线(i,j)要能进入了k-1到k这一节,则它比与(0,0)..(k-1,k-1)都相交。并且当(i,j)与(0,0)..(k-1,k-1)都相交,而与(k,k)不交时,他必与上边或下边(k-1,k)相交。显然当k<=MAX(i,j)时,我们便不用处理(i,j),因为它或者不是最优光线,或者会在其他的(i’,j’)求出。对k>Max(i,j),求出(i,j)与上/下边(k-1,k)的交点的x坐标,并与当前最大值比较,决定取舍。

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<iostream>
#include<algorithm>
#define eps 1e-8
using namespace std;
int n;
struct point
{
 double x,y;
};
struct it
{
 point a,b;
}p[25];
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 judge(point p1,point p2,point p3,point p4)
{
 if(multi(p1,p2,p4)*multi(p1,p2,p3)>eps)
  return false;
 else
 return true;
}
double work(int i,int j)
{
 int k;
 point t1,t2;
 double m=p[0].a.x;
 for(k=0;k<n;k++)
 {
  if(!judge(p[i].a,p[j].b,p[k].a,p[k].b))
  {
   if(k==0)
   return p[1].a.x;
   t1=inter(p[i].a,p[j].b,p[k].a,p[k-1].a);
   t2=inter(p[i].a,p[j].b,p[k].b,p[k-1].b);
   return max(t1.x,t2.x);
  }
 }
 return p[n-1].a.x;
}
int main()
{
 int i,j;
 double x,ans;
 while(scanf("%d",&n),n)
 {
  for(i=0;i<n;i++)
  {
   scanf("%lf%lf",&p[i].a.x,&p[i].a.y);
   p[i].b.x=p[i].a.x;
   p[i].b.y=p[i].a.y-1;
  }
  ans=p[1].a.x;
  for(i=0;i<n;i++)
  for(j=0;j<n;j++)
  {
   if(i==j)
   continue;
   x=work(i,j);
   if(x-ans>eps)
   ans=x;
  }
  if(fabs(ans-p[n-1].a.x)<eps)
  printf("Through all the pipe.\n");
     else
     printf("%.2f\n",ans);
 }
    return  0;
}
    
    
   
  
   
   
   
  
  

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

历史上的今天

评论

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

页脚

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