poj1410判断线段与矩形是否相交(判断线段相交)

Description

You are to write a program that has to decide whether a given line segment intersects a given rectangle. 

An example: 
line: start point: (4,9) 
end point: (11,2) 
rectangle: left-top: (1,5) 
right-bottom: (7,1) 

 
Figure 1: Line segment does not intersect rectangle 

The line is said to intersect the rectangle if the line and the rectangle have at least one point in common. The rectangle consists of four straight lines and the area in between. Although all input values are integer numbers, valid intersection points do not have to lay on the integer grid. 

Input

Output

Sample Input

1
4 9 11 2 1 5 7 1

Sample Output

F

(线段在矩形里面属于相交)
题意：给出的矩形的坐标不一定左上右下，需要自己判断

（1）判断线段与线段之间是否相交

1、两线段不在同一直线上

将其中一条线段看成直线，然后就是判断直线与线段之间的关系，

将另一条线段看成直线，当两种情况的叉积都为负时说明两线段相交

2、两线段在同一直线上（相交和不相交两种情况）

当其中一条线段端点的 较大横坐标（较大纵坐标） 小于 另一条线段端点的 较小横坐标（较小纵坐标）说明两线段不相交，否则相交

#include<stdio.h>
#include<algorithm>
using namespace std;
struct point{
    double x,y;
}L1,L2;
struct line{
    point A,B;
}L[5];
double cal(point A,point B,point C)
{
    return (C.x-A.x)*(B.y-A.y)-(B.x-A.x)*(C.y-A.y);
}
int cross(point C,point D)
{
    double d1,d2,d3,d4;
    d1=cal(L1,L2,C);
    d2=cal(L1,L2,D);
    d3=cal(C,D,L1);
    d4=cal(C,D,L2);
    if(d1==0 && d2==0 && d3==0 && d4==0)    //两线段在同一直线上
    {
        if(max(L1.x,L2.x)<min(C.x,D.x)||max(C.x,D.x)<min(L1.x,L2.x))
            return 0;
        else if(max(L1.y,L2.y)<min(C.y,D.y)||max(C.y,D.y)<min(L1.y,L2.y))
            return 0;
        else return 1;
    }
    if(d1*d2<0 && d3*d4<0)
    {
        return 1;
    }
     return 0;
}
int fun1(double x1,double y1,double x2,double y2)
{
    double xmin=x1<x2?x1:x2;
    double xmax=x1>x2?x1:x2;
    double ymin=y1<y2?y1:y2;
    double ymax=y1>y2?y1:y2;
    double Lxmin=L1.x<L2.x?L1.x:L2.x;
    double Lxmax=L1.x>L2.x?L1.x:L2.x;
    double Lymin=L1.y<L2.y?L1.y:L2.y;
    double Lymax=L1.y>L2.y?L1.y:L2.y;
    if(Lxmin>=xmin&&Lxmax<=xmax&&Lymin>=ymin&&Lymax<=ymax)
        return 1;
    else return 0;
}
void fun(double x1,double y1,double x2,double y2)
{
    for(int i=0; i < 4; i++)
    {
        if(cross(L[i].A,L[i].B)==1)
        {
            printf("Tn");
            return ;
        }
    }
    if(fun1(x1,y1,x2,y2)==1)
    {
        printf("Tn");
        return ;
    }
    printf("Fn");
}

int main()
{
    int n;
    double x1,y1,x2,y2;
    scanf("%d",&n);
    while(n--)
    {
        scanf("%lf%lf%lf%lf",&L1.x,&L1.y,&L2.x,&L2.y);
        scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
        L[0].A.x=x1; L[0].A.y=y1;
        L[0].B.x=x2; L[0].B.y=y1;
        L[1].A.x=x2; L[1].A.y=y1;
        L[1].B.x=x2; L[1].B.y=y2;
        L[2].A.x=x1; L[2].A.y=y2;
        L[2].B.x=x2; L[2].B.y=y2;
        L[3].A.x=x1; L[3].A.y=y1;
        L[3].B.x=x1; L[3].B.y=y2;
        fun(x1,y1,x2,y2);
    }
    return 0;
}

最后

以上就是俊秀盼望为你收集整理的poj1410判断线段与矩形是否相交(判断线段相交)的全部内容，希望文章能够帮你解决poj1410判断线段与矩形是否相交(判断线段相交)所遇到的程序开发问题。

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