POJ - 1410 Intersection （线段是否与矩形相交 或 被覆盖 模板）

链接：https://cn.vjudge.net/problem/POJ-1410

题意：判断一条线段是否与矩形相交或被覆盖。

思路：直接判断线段是否与矩形相交，再特判线段是否在矩形内即可。（坑点，说是给左上和右下的坐标，但要你自己确定。）外加kuangbin大神的模板

#include <cstdio>
#include <iostream>
#include <cmath>
#define ll long long
using namespace std;
const double eps = 1e-8;
const int N = 10;
int sgn(double x)
{
if(fabs(x)<eps) return 0;
else if(x<0) return -1;
else return 1;
}
struct Point
{
double x,y;
Point(){}
Point(double x,double y):x(x),y(y){}
Point operator -(const Point& b)const//相减
{
return Point(x-b.x,y-b.y);
}
double operator ^(const Point& b)const//叉乘
{
return x*b.y-y*b.x;
}
double operator *(const Point& b)const//点乘
{
return x*b.x+y*b.y;
}
}s,e;
struct Line
{
Point s,e;
Line(){}
Line(Point ss,Point ee){ s=ss,e=ee;}
}ls[N],l;
int n;
double x1,y1,x2,y2;
double xle,yle,xt,yt;
double dist(Point a,Point b)
{
return sqrt((a-b)*(a-b));
}
//判断线段相交
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((l2.s-l1.s)^(l1.e-l1.s))*sgn((l2.e-l1.s)^(l1.e-l1.s))<=0
&& sgn((l1.s-l2.s)^(l2.e-l2.s))*sgn((l1.e-l2.s)^(l2.e-l2.s))<=0;
}
int main(void)
{
bool flag;
int t;
scanf("%d",&t);
while(t--)
{
flag=0;
scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
l=Line(Point(x1,y1),Point(x2,y2));
scanf("%lf%lf%lf%lf",&xle,&yle,&xt,&yt);
if(xle>xt) swap(xle,xt);
if(yt>yle) swap(yle,yt);
ls[1]=Line(Point(xle,yle),Point(xle,yt));
ls[2]=Line(Point(xle,yle),Point(xt,yle));
ls[3]=Line(Point(xle,yt),Point(xt,yt));
ls[4]=Line(Point(xt,yle),Point(xt,yt));
for(int i=1;i<=4;i++)
if(inter(l,ls[i]))
flag=1;
if((xle<=x1&&x1<=xt)&&(yt<=y1&&y1<=yle)
&& (xle<=x2&&x2<=xt)&&(yt<=y2&&y2<=yle))
flag=1;
flag?puts("T"):puts("F");
}
return 0;
}

/************************************************************
* Author
: kuangbin
* Email
: kuangbin2009@126.com
* Last modified : 2013-07-15 10:14
* Filename
: POJ1410Intersection.cpp
* Description
:
* *********************************************************/
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>
#include <map>
#include <vector>
#include <set>
#include <string>
#include <math.h>
using namespace std;
const double eps = 1e-6;
int sgn(double x)
{
if(fabs(x) < eps)return 0;
if(x < 0)return -1;
else return 1;
}
struct Point
{
double x,y;
Point(){}
Point(double _x,double _y)
{
x = _x;y = _y;
}
Point operator -(const Point &b)const
{
return Point(x - b.x,y - b.y);
}
//叉积
double operator ^(const Point &b)const
{
return x*b.y - y*b.x;
}
//点积
double operator *(const Point &b)const
{
return x*b.x + y*b.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 _s,Point _e)
{
s = _s;e = _e;
}
//两直线相交求交点
//第一个值为0表示直线重合，为1表示平行，为0表示相交,为2是相交
//只有第一个值为2时，交点才有意义
pair<int,Point> operator &(const Line &b)const
{
Point res = s;
if(sgn((s-e)^(b.s-b.e)) == 0)
{
if(sgn((s-b.e)^(b.s-b.e)) == 0)
return make_pair(0,res);//重合
else return make_pair(1,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(2,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((l2.s-l1.e)^(l1.s-l1.e))*sgn((l2.e-l1.e)^(l1.s-l1.e)) <= 0 &&
sgn((l1.s-l2.e)^(l2.s-l2.e))*sgn((l1.e-l2.e)^(l2.s-l2.e)) <= 0;
}
//判断点在线段上
//判断点在线段上
bool OnSeg(Point P,Line L)
{
return
sgn((L.s-P)^(L.e-P)) == 0 &&
sgn((P.x - L.s.x) * (P.x - L.e.x)) <= 0 &&
sgn((P.y - L.s.y) * (P.y - L.e.y)) <= 0;
}
//判断点在凸多边形内
//点形成一个凸包，而且按逆时针排序（如果是顺时针把里面的<0改为>0）
//点的编号:0~n-1
//返回值：
//-1:点在凸多边形外
//0:点在凸多边形边界上
//1:点在凸多边形内
int inConvexPoly(Point a,Point p[],int n)
{
for(int i = 0;i < n;i++)
{
if(sgn((p[i]-a)^(p[(i+1)%n]-a)) < 0)return -1;
else if(OnSeg(a,Line(p[i],p[(i+1)%n])))return 0;
}
return 1;
}
//判断点在任意多边形内
//射线法，poly[]的顶点数要大于等于3,点的编号0~n-1
//返回值
//-1:点在凸多边形外
//0:点在凸多边形边界上
//1:点在凸多边形内
int inPoly(Point p,Point poly[],int n)
{
int cnt;
Line ray,side;
cnt = 0;
ray.s = p;
ray.e.y = p.y;
ray.e.x = -100000000000.0;//-INF,注意取值防止越界
for(int i = 0;i < n;i++)
{
side.s = poly[i];
side.e = poly[(i+1)%n];
if(OnSeg(p,side))return 0;
//如果平行轴则不考虑
if(sgn(side.s.y - side.e.y) == 0)
continue;
if(OnSeg(side.s,ray))
{
if(sgn(side.s.y - side.e.y) > 0)cnt++;
}
else if(OnSeg(side.e,ray))
{
if(sgn(side.e.y - side.s.y) > 0)cnt++;
}
else if(inter(ray,side))
cnt++;
}
if(cnt % 2 == 1)return 1;
else return -1;
}
int main()
{
int T;
double x1,y1,x2,y2;
scanf("%d",&T);
while(T--)
{
scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
Line line = Line(Point(x1,y1),Point(x2,y2));
scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
if(x1 > x2)swap(x1,x2);
if(y1 > y2)swap(y1,y2);
Point p[10];
p[0] = Point(x1,y1);
p[1] = Point(x2,y1);
p[2] = Point(x2,y2);
p[3] = Point(x1,y2);
if(inter(line,Line(p[0],p[1])))
{
printf("Tn");
continue;
}
if(inter(line,Line(p[1],p[2])))
{
printf("Tn");
continue;
}
if(inter(line,Line(p[2],p[3])))
{
printf("Tn");
continue;
}
if(inter(line,Line(p[3],p[0])))
{
printf("Tn");
continue;
}
if(inConvexPoly(line.s,p,4) >= 0 || inConvexPoly(line.e,p,4) >= 0)
{
printf("Tn");
continue;
}
printf("Fn");
}
return 0;
}

最后

以上就是外向小土豆为你收集整理的POJ - 1410 Intersection （线段是否与矩形相交 或 被覆盖 模板）的全部内容，希望文章能够帮你解决POJ - 1410 Intersection （线段是否与矩形相交 或 被覆盖 模板）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。