题目链接:https://vjudge.net/problem/POJ-1410

题意:判断线段和矩形是否相交。

思路:注意这里的相交包括线段在矩形内,因此先判断线段与矩形的边是否相交,再判断线段的两端点是否在矩形内(因为是矩形,即凸多边形,直接用叉积判断即可,如果是一般的多边形,需要用射线法判断。)

AC code:

#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstdlib>
using namespace std; const double eps=1e-;
const double inf=1e20;
int T,flag; int sgn(double x){
if(abs(x)<eps) return ;
if(x<) return -;
return ;
} struct Point{
double x,y;
Point(){}
Point(double xx,double yy):x(xx),y(yy){}
Point operator + (const Point& b)const{
return Point(x+b.x,y+b.y);
}
Point operator - (const Point& b)const{
return Point(x-b.x,y-b.y);
}
double operator * (const Point& b)const{
return x*b.x+y*b.y;
}
double operator ^ (const Point& b)const{
return x*b.y-b.x*y;
}
//绕原点旋转角度b(弧度值),后x、y的变化
void transXY(double b){
double tx=x,ty=y;
x=tx*cos(b)-ty*sin(b);
y=tx*sin(b)+ty*cos(b);
}
}; struct Line{
Point s,e;
Line(){}
Line(Point ss,Point ee){
s=ss,e=ee;
}
//两直线相交求交点
//第一个值为0表示直线重合,为1表示平行,为2表示相交
//只有第一个值为2时,交点才有意义
pair<int,Point> operator &(const Line &b)const{
Point res = s;
if(sgn((s-e)^(b.s-b.e)) == )
{
if(sgn((s-b.e)^(b.s-b.e)) == )
return make_pair(,res);//重合
else return make_pair(,res);//平行
}
double t = ((s-b.s)^(b.s-b.e))/((s-e)^(b.s-b.e));
res.x += (e.x-s.x)*t;
res.y += (e.y-s.y)*t;
return make_pair(,res);
}
};
//判断线段相交
bool inter(Line l1,Line l2){
return
max(l1.s.x,l1.e.x)>=min(l2.s.x,l2.e.x)&&
max(l2.s.x,l2.e.x)>=min(l1.s.x,l1.e.x)&&
max(l1.s.y,l1.e.y)>=min(l2.s.y,l2.e.y)&&
max(l2.s.y,l2.e.y)>=min(l1.s.y,l1.e.y)&&
sgn((l1.s-l2.s)^(l2.e-l2.s))*sgn((l1.e-l2.s)^(l2.e-l2.s))<=&&
sgn((l2.s-l1.s)^(l1.e-l1.s))*sgn((l2.e-l1.s)^(l1.e-l1.s))<=;
} double dis(Point a,Point b){
return sqrt((b-a)*(b-a));
}
//判断点在线段上
bool OnSeg(Point P,Line L){
return
sgn((L.s-P)^(L.e-P))==&&
sgn((P.x-L.s.x)*(P.x-L.e.x))<=&&
sgn((P.y-L.s.y)*(P.y-L.e.y))<=;
}
//判断点在凸多边形内,复杂度O(n)
//点形成一个凸包,而且按逆时针排序(如果是顺时针把里面的<0改为>0)
//点的编号:0~n-1
//返回值:
//-1:点在凸多边形外
//0:点在凸多边形边界上
//1:点在凸多边形内
int inConvexPoly(Point a,Point p[],int n){
for(int i=;i<n;++i)
if(sgn((p[i]-a)^(p[(i+)%n]-a))<) return -;
else if(OnSeg(a,Line(p[i],p[(i+)%n]))) return ;
return ;
}
//判断点在任意多边形内,复杂度O(n)
//射线法,poly[]的顶点数要大于等于3,点的编号0~n-1
//返回值
//-1:点在凸多边形外
//0:点在凸多边形边界上
//1:点在凸多边形内
int inPoly(Point a,Point p[],int n){
int cnt=;
Line ray,side;
ray.s=a;
ray.e.y=a.y;
ray.e.x=-inf;
for(int i=;i<n;++i){
side.s=p[i];
side.e=p[(i+)%n];
if(OnSeg(a,side)) return ;
if(sgn(side.s.y-side.e.y)==) continue;
if(OnSeg(side.s,ray)){
if(sgn(side.s.y-side.e.y)>) ++cnt;
}
else if(OnSeg(side.e,ray)){
if(sgn(side.e.y-side.s.y)>) ++cnt;
}
else if(inter(ray,side)) ++cnt;
}
if(cnt%==) return ;
else return -;
} int main(){
scanf("%d",&T);
double x1,yy1,x2,yy2;
while(T--){
flag=;
scanf("%lf%lf%lf%lf",&x1,&yy1,&x2,&yy2);
Line line=Line(Point(x1,yy1),Point(x2,yy2));
scanf("%lf%lf%lf%lf",&x1,&yy1,&x2,&yy2);
if(x1>x2) swap(x1,x2);
if(yy1>yy2) swap(yy1,yy2);
Point p[];
p[]=Point(x1,yy1);
p[]=Point(x2,yy1);
p[]=Point(x2,yy2);
p[]=Point(x1,yy2);
for(int i=;i<;++i)
if(inter(line,Line(p[i],p[(i+)%]))){
flag=;
break;
}
if(inConvexPoly(line.s,p,)>&&inConvexPoly(line.e,p,)>)
flag=;
if(flag) printf("T\n");
else printf("F\n");
}
return ;
}

最新文章

  1. 【转】[fix] Wireshark error: There are no interfaces on which a capture can be done. on Mac OS X
  2. Web API配置自定义路由
  3. Redis系列一之数据结构
  4. jQuery.validator 详解二
  5. 重温WCF之WCF抛出异常的处理SOAP Fault(十二)
  6. android基础开发之scrollview
  7. 用UNIX消息队列实现IPC(以ATM为例)
  8. PHP导出CSV文件
  9. Swift 注释
  10. sql server 2008 安装过程与创建建sql server登录用户
  11. 如何在tomcat安装部署php项目
  12. browserify.js 的模块加载
  13. CSS display 属性详解
  14. vijosP1413 Valentine’s Present
  15. 31.Spring-开发流程.md
  16. BZOJ 3233: [Ahoi2013]找硬币( dp )
  17. Day4:T1小技巧(类似于指针操作)T2搜索+小细节
  18. Sharepoint 2013搜索服务配置总结(实战)
  19. 记录一次go性能调试的过程
  20. k8s学习笔记之一:kubernetes简介

热门文章

  1. 评估类模型之优劣解距离法Topsis模型
  2. CF 940F - Machine Learning ( 带 修 )
  3. 安装包设计-------安装(QT)---------知识总结
  4. bit,byte,word,bps,Bps,比特,字节,字, 一图看懂
  5. win7虚拟机MAC系统
  6. shell 字符串分割cut
  7. CF1214D
  8. Mysql 原理以及常见mysql 索引等
  9. Angular4.x+Ionic3 踩坑之路之打包时出现JAVASCRIPT HEAP OUT OF MEMORY的几种解决办法
  10. git仓库与项目源码分离