POJ 1410 Intersection(判断线段与矩形位置关系)

题目链接

题目大意：判断一条线段与一个实心矩形（四条边以及中间包含的部分）是否相交。

分析：线段与矩形四条边的不规范相交（交于一条线段的端点或者重合），以及线段在矩形的内部，都算作相交。这题看似简单，其实有很多比较细节的地方，比较坑，调了好久。

#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<stack>
#include<cstdio>
#include<vector>
#include <iomanip>
#include<utility>
#include<cctype>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define inf 0x3f3f3f3f
#define Clear(x) memset(x,0,sizeof(x))
#define fup(i,a,b) for(int i=a;i<b;i++)
#define rfup(i,a,b) for(int i=a;i<=b;i++)
#define fdn(i,a,b) for(int i=a;i>b;i--)
#define rfdn(i,a,b) for(int i=a;i>=b;i--)
typedef long long ll;
using namespace std;
const double pi=acos(-1.0);
const int maxn = 1e2+7;
const double eps = 1e-8;
struct Point{
double x,y;
Point(){}
Point(double _x,double _y){x=_x;y=_y;}
};
struct Line{
Point s,e;
Line(){}
Line(Point _s,Point _e){s=_s;e=_e;}
}line[10];
int sgn(double x)
{
if(fabs(x)<eps) return 0;
else return x<0?-1:1;
}
double cross(Point a,Point b,Point c)
{
a.x-=c.x;a.y-=c.y;
b.x-=c.x;b.y-=c.y;
return a.x*b.y-b.x*a.y;
}
bool intersect(Line l1,Line l2){
return(sgn(max(l1.s.x,l1.e.x)-min(l2.s.x,l2.e.x))>=0&&
//排斥实验
sgn(max(l2.s.x,l2.e.x)-min(l1.s.x,l1.e.x))>=0&&
sgn(max(l1.s.y,l1.e.y)-min(l2.s.y,l2.e.y))>=0&&
sgn(max(l2.s.y,l2.e.y)-min(l1.s.y,l1.e.y))>=0&&
sgn(cross(l2.s,l1.e,l1.s)*cross(l2.e,l1.e,l1.s)<=0)&& //跨立实验
sgn(cross(l1.s,l2.e,l2.s)*cross(l1.e,l2.e,l2.s)<=0));
}
int main()
{
int T;
scanf("%d",&T);
double x1,y1,x2,y2,x3,y3,x4,y4;
while(T--)
{
Clear(line);
int flag=0;
double x1,y1,x2,y2;
scanf("%lf%lf%lf%lf%lf%lf%lf%lf",&x1,&y1,&x2,&y2,&x3,&y3,&x4,&y4);
if(x3>x4)
swap(x3,x4);
if(y3<y4)
swap(y3,y4);
line[0]=Line(Point(x1,y1),Point(x2,y2));
line[1]=Line(Point(x3,y3),Point(x3,y4));
line[2]=Line(Point(x3,y4),Point(x4,y4));
line[3]=Line(Point(x4,y3),Point(x4,y4));
line[4]=Line(Point(x3,y3),Point(x4,y3));
for(int i=1;i<=4;i++){
if(intersect(line[0],line[i]))
{
flag=1;
break;
}
}
if(flag){}
else if(min(x1,x2)>x3&&max(x1,x2)<x4&&min(y1,y2)>y4&&max(y1,y2)<y3)
flag=1;
if(flag) printf("Tn");
else printf("Fn");
}
return 0;
}

最后

以上就是贤惠超短裙为你收集整理的POJ 1410 Intersection(判断线段与矩形位置关系)的全部内容，希望文章能够帮你解决POJ 1410 Intersection(判断线段与矩形位置关系)所遇到的程序开发问题。

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