POJ 1410 Intersection(判断线段与矩形是否相交)

POJ 1410 Intersection(判断线段与矩形是否相交)

http://poj.org/problem?id=1410

题意:

给你一个矩形的对角坐标(x1,y1)与(x2,y2),然后再给你一条线段的两个端点坐标,问你该线段是否与矩形相交?(如果线段仅在矩形内部也算线段与矩形相交)

分析:

首先判断线段是否在矩形内部. 一条线段在矩形内部,充要条件 线段的x与y坐标范围是 矩形的x与y坐标范围的子集(子集即可,不需要真子集).

如果线段不在矩形内部,那么就判断线段是否与矩形的4条边相交(在端点相交也算). 判断线段相交用刘汝佳的模板.

AC代码:

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const double eps=1e-10;
int dcmp(double x)
{
    if(fabs(x)<eps) return 0;
    return x<0?-1:1;
}
struct Point
{
    double x,y;
    Point(){}
    Point(double x,double y):x(x),y(y){}
};
typedef Point Vector;
Vector operator-(Point A,Point B)
{
    return Vector(A.x-B.x,A.y-B.y);
}
double Dot(Vector A,Vector B)
{
    return A.x*B.x+A.y*B.y;
}
double Cross(Vector A,Vector B)
{
    return A.x*B.y-A.y*B.x;
}
bool InSegment(Point P,Point A,Point B)
{
    return dcmp(Cross(A-P,B-P))==0 && dcmp(Dot(A-P,B-P))<=0;
}
bool SegmentIntersection(Point a1,Point a2,Point b1,Point b2)
{
    double c1=Cross(a2-a1,b1-a1),c2=Cross(a2-a1,b2-a1);
    double c3=Cross(b2-b1,a1-b1),c4=Cross(b2-b1,a2-b1);
    if(dcmp(c1)*dcmp(c2)<0 && dcmp(c3)*dcmp(c4)<0) return true;
    if(dcmp(c1)==0 && InSegment(b1,a1,a2)) return true;
    if(dcmp(c2)==0 && InSegment(b2,a1,a2)) return true;
    if(dcmp(c3)==0 && InSegment(a1,b1,b2)) return true;
    if(dcmp(c4)==0 && InSegment(a2,b1,b2)) return true;
    return false;
}
/***以上为刘汝佳模板***/
struct Rectangle
{
    double x1,y1,x2,y2;//矩形的最小最大 x y 坐标
    bool Intersection(Point a1,Point a2)//判断线段a1a2是否和矩形相交
    {
        double min_x=min(a1.x,a2.x),max_x=max(a1.x,a2.x);
        double min_y=min(a1.y,a2.y),max_y=max(a1.y,a2.y);
        if(min_x>=x1 && max_x<=x2 && min_y>=y1 && max_y<=y2)
            return true;//线段在矩形内
        else
        {
            Point p[4];
            p[0]=Point(x1,y1),p[1]=Point(x2,y1),p[2]=Point(x2,y2),p[3]=Point(x1,y2);
            for(int i=0;i<4;++i)
                if(SegmentIntersection(a1,a2,p[i],p[(i+1)%4])) return true;
        }
        return false;
    }
};

int main()
{
    int T; scanf("%d",&T);
    while(T--)
    {
        Point a1,a2;
        Rectangle r;
        scanf("%lf%lf%lf%lf%lf%lf%lf%lf",&a1.x,&a1.y,&a2.x,&a2.y,&r.x1,&r.y1,&r.x2,&r.y2);
        if(r.x1>r.x2) swap(r.x1,r.x2);
        if(r.y1>r.y2) swap(r.y1,r.y2);
        printf("%c\n",r.Intersection(a1,a2)?'T':'F');
    }
    return 0;
}