注册 登录  
 加关注

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

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

zxj015

 
 
 

日志

 
 

poj 1066 Treasure Hunt 线段相交判断  

2011-05-03 11:53:11|  分类: 计算几何 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
     宝藏在一个矩形的内部,矩形内有纵横交错的墙形成多个房间,求最少炸掉多少道墙可到达宝藏所在的房间,宝藏不会在墙上,炸点必须在墙的中间点上,不会超过两个的墙相交以一点。
    若起点和宝藏点连线的线段和某直线相交,那么无论你怎么绕你都要穿过这条直线才能到达宝藏点。所以我们可以这样做:枚举矩形边上的所有点做为起点,(不需要求中点做为起点)。连接起点、宝藏点,求出这条线段会和多少条其它的直线相交。然后加1(因为也要炸掉矩形边),即为所求答案。

#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
using namespace std;
struct point
{
double x,y;
}p[100];
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);
}
int main()
{
int i,j,n,min,num;
while(scanf("%d",&n)!=EOF)
{
n*=2;
for(i=0;i<n+1;i++)
scanf("%lf%lf",&p[i].x,&p[i].y);
min=0x7fffffff;
for(i=0;i<n;i++)
{
num=0;
for(j=0;j<n;j+=2)
{
if(i==j||i==j+1)  //起点要不在这条线段上
continue;
if(is(p[i],p[n],p[j],p[j+1]))
num++;
}
if(num<min)
min=num;
}
if(n==0) //要注意墙数为零的情况
min=0;
printf("Number of doors = %d\n",min+1);
}
return 0;
}
        

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

历史上的今天

评论

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

页脚

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