POJ 1410 Intersection-白红宇

POJ 1410 Intersection

阅读量：5212 次

发布时间：2019-06-14

本文共 2713 字，大约阅读时间需要 9 分钟。

题意：给出一条线段、一个矩形，判断两者是否相交。

注意两个问题：

1.这里的相交是指线段不在矩形的外面，也就是说线段与矩形有交点或者线段完全在矩形内部。

2.题目描述有问题，题目中说是按照 xstart ystart xend yend xleft ytop xright ybottom 的format （格式）给出，

按照题意，也就是说给出的坐标顺序是

起点，终点，左上角，右下角。

但是根据实际给出的数据看出来，应该是

起点，终点，对角顶点。

因此，后面两个数据就不一定是左上角，右下角了。

思路：先判断线段所在的直线是否与矩形相交，进一步判断线段是否与矩形相交两种情况：

1.斜率存在，

直线方程：y=k*x+b ,

令s =y-k*x-b ，由s符号可判断点与直线的位置

相交的两种可能：

(1).两个点位于线段所在直线的两侧的时候，则s[i]与s[j] 异号，乘积sum<0;

(2).其中一个点正好在线段上，即其中一个s为0，则 sum=s[i]*s[j] =0，这里斜率有误差，取0.00000001 近似为 0

如果直线与矩形相交，进一步判断线段是否与矩形相交

2.斜率不存在的时候，很好判断了

代码：

#include
    
     #include
     
      using namespace std;int main(){	float xstart,ystart ,xend,yend;	float xleft,ytop ,xright,ybottom;	float x1,y1 ,x2,y2;//矩形两个对角坐标	int n;	int i,j;	scanf("%d",&n);	while(n--){		scanf("%f%f%f%f",&xstart,&ystart,&xend,¥d);		scanf("%f%f%f%f",&x1,&y1,&x2,&y2);//这里的输入仅仅是两个对角的坐标，哪两个角并不确定		xleft=x1
      
       x2?x1:x2;		ytop=y1>y2?y1:y2;		ybottom=y1
       
        ytop&¥d>ytop||ystart
        
         
          xright&&xend>xright)//线段在矩形左或右，不想交 flag=false; if(flag) printf("T\n"); else printf("F\n"); } } else{//斜率不存在的时候 if(ystart>ytop&¥d>ytop||ystart
          
           
            xright)//线段在矩形左或右，不想交 printf("F\n"); else printf("T\n"); } } return 0;}