注册 登录  
 加关注

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

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

zxj015

 
 
 

日志

 
 

poj 1410 Intersection 线段相交判断  

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

  下载LOFTER 我的照片书  |

http://poj.org/problem?id=1410

     给定一个矩形和一条线段,求线段能否交矩形,线段与矩形的边或矩形内部有交点即为交。

    很简单的一道判断线段相交的题目,不过要正确理解题目意思:相交要包括矩形的内部,即线段在矩形内部也是True。(The rectangle consists of four straight lines and the area in between.)题目说的左上、右下并非座标中的位置,数据给的点也会是左下、右上!!!(The terms top left and bottom right do not imply any ordering of coordinates. )

#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
using namespace std;
struct point
{
 double x,y;
}p[10];
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 cas,i,flag;
 double maxx,maxy,minx,miny;
 scanf("%d",&cas);
 while(cas--)
 {
  for(i=0;i<4;i++)
  scanf("%lf%lf",&p[i].x,&p[i].y);
  p[4].x=p[3].x;
  p[4].y=p[2].y;
  p[5].x=p[2].x;
  p[5].y=p[3].y;
  flag=1;
  if(is(p[0],p[1],p[2],p[5])||is(p[0],p[1],p[5],p[3])||is(p[0],p[1],p[3],p[4])||is(p[0],p[1],p[4],p[2]))
  flag=0;
  maxx=max(p[2].x,p[3].x);
  maxy=max(p[2].y,p[3].y);
  minx=min(p[2].x,p[3].x);
  miny=min(p[2].y,p[3].y);
  if(p[0].x>=minx&&p[0].x<=maxx&&p[0].y>=miny&&p[0].y<=maxy)
  flag=0;
  if(flag)
  cout<<"F"<<endl;
  else
  cout<<"T"<<endl;
 } 
 return 0;
}
  测试数据:

   

68
4 9 11 2 1 1 7 5
11 2 4 9 1 1 7 5
12 12 24 24 19 5 25 17
4 6 15 9 1 1 11 11
19 5 25 17 12 12 24 24
0 18 8 12 1 1 11 11
2 4 4 2 1 1 11 11
-4 9 -11 2 -1 1 -7 5
-11 2 -4 9 -1 1 -7 5
-12 12 -24 24 -19 5 -25 17
-4 6 -15 9 -1 1 -11 11
-19 5 -25 17 -12 12 -24 24
0 18 -8 12 -1 1 -11 11
-2 4 -4 2 -1 1 -11 11
4 -9 11 -2 1 -1 7 -5
11 -2 4 -9 1 -1 7 -5
12 -12 24 -24 19 -5 25 -17
4 -6 15 -9 1 -1 11 -11
19 -5 25 -17 12 -12 24 -24
0 -18 8 -12 1 -1 11 -11
2 -4 4 -2 1 -1 11 -11
-4 -9 -11 -2 -1 -1 -7 -5
-11 -2 -4 -9 -1 -1 -7 -5
-12 -12 -24 -24 -19 -5 -25 -17
-4 -6 -15 -9 -1 -1 -11 -11
-19 -5 -25 -17 -12 -12 -24 -24
0 -18 -8 -12 -1 -1 -11 -11
-2 -4 -4 -2 -1 -1 -11 -11
9 1 9 2 4 3 9 6
9 2 9 1 4 3 9 6
10 3 13 3 4 3 9 6
13 3 10 3 4 3 9 6
10 6 14 6 4 3 9 6
14 6 10 6 4 3 9 6
9 7 9 10 4 3 9 6
9 10 9 7 4 3 9 6
4 7 4 10 4 3 9 6
4 10 4 7 4 3 9 6
0 6 3 6 4 3 9 6
3 6 0 6 4 3 9 6
1 3 3 3 4 3 9 6
3 3 1 3 4 3 9 6
4 0 4 2 4 3 9 6
4 2 4 0 4 3 9 6
5 3 8 5 4 3 9 6
8 5 5 3 4 3 9 6
5 3 8 3 4 3 9 6
8 3 5 3 4 3 9 6
6 4 6 5 4 3 9 6
6 5 6 4 4 3 9 6
4 3 9 6 4 3 9 6
9 6 4 3 4 3 9 6
4 3 5 4 4 3 9 6
5 4 4 3 4 3 9 6
5 3 8 3 4 3 9 6
8 3 5 3 4 3 9 6
5 3 9 3 4 3 9 6
9 3 5 3 4 3 9 6
4 4 4 5 4 3 9 6
4 5 4 4 4 3 9 6
4 3 4 5 4 3 9 6
4 5 4 3 4 3 9 6
4 3 4 6 4 3 9 6
4 6 4 3 4 3 9 6
9 2 9 5 4 3 9 6
9 5 9 2 4 3 9 6
9 2 9 7 4 3 9 6
9 7 9 2 4 3 9 6

out

F
F
F
T
T
F
T
F
F
F
T
T
F
T
F
F
F
T
T
F
T
F
F
F
T
T
F
T
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
T
T
T
T
T
T
T
T
T
T
T
T
T
T
T
T
T
T
T
T
T
T
T
T

   
   
  
  

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

历史上的今天

评论

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

页脚

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