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

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

题意：判断线段和矩形是否相交。

思路：注意这里的相交包括线段在矩形内，因此先判断线段与矩形的边是否相交，再判断线段的两端点是否在矩形内（因为是矩形，即凸多边形，直接用叉积判断即可，如果是一般的多边形，需要用射线法判断。）

AC code:

#include<cstdio>

#include<algorithm>

#include<cmath>

#include<cstdlib>

using namespace std;

const double eps=1e-;

const double inf=1e20;

int T,flag;

int sgn(double x){

    if(abs(x)<eps) return ;

    if(x<) return -;

    return ;

}

struct Point{

    double x,y;

    Point(){}

    Point(double xx,double yy):x(xx),y(yy){}

    Point operator + (const Point& b)const{

        return Point(x+b.x,y+b.y);

    }

    Point operator - (const Point& b)const{

        return Point(x-b.x,y-b.y);

    }

    double operator * (const Point& b)const{

        return x*b.x+y*b.y;

    }

    double operator ^ (const Point& b)const{

        return x*b.y-b.x*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 ss,Point ee){

        s=ss,e=ee;

    }

    //两直线相交求交点

    //第一个值为0表示直线重合，为1表示平行，为2表示相交

    //只有第一个值为2时，交点才有意义

    pair<int,Point> operator &(const Line &b)const{

        Point res = s;

        if(sgn((s-e)^(b.s-b.e)) == )

        {

            if(sgn((s-b.e)^(b.s-b.e)) == )

                return make_pair(,res);//重合

            else return make_pair(,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(,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((l1.s-l2.s)^(l2.e-l2.s))*sgn((l1.e-l2.s)^(l2.e-l2.s))<=&&

        sgn((l2.s-l1.s)^(l1.e-l1.s))*sgn((l2.e-l1.s)^(l1.e-l1.s))<=;

}

double dis(Point a,Point b){

    return sqrt((b-a)*(b-a));

}

//判断点在线段上

bool OnSeg(Point P,Line L){

    return

        sgn((L.s-P)^(L.e-P))==&&

        sgn((P.x-L.s.x)*(P.x-L.e.x))<=&&

        sgn((P.y-L.s.y)*(P.y-L.e.y))<=;

}

//判断点在凸多边形内，复杂度O(n)

//点形成一个凸包，而且按逆时针排序（如果是顺时针把里面的<0改为>0）

//点的编号:0~n-1

//返回值：

//-1:点在凸多边形外

//0:点在凸多边形边界上

//1:点在凸多边形内

int inConvexPoly(Point a,Point p[],int n){

    for(int i=;i<n;++i)

        if(sgn((p[i]-a)^(p[(i+)%n]-a))<) return -;

        else if(OnSeg(a,Line(p[i],p[(i+)%n]))) return ;

    return ;

}

//判断点在任意多边形内,复杂度O(n)

//射线法，poly[]的顶点数要大于等于3,点的编号0~n-1

//返回值

//-1:点在凸多边形外

//0:点在凸多边形边界上

//1:点在凸多边形内

int inPoly(Point a,Point p[],int n){

    int cnt=;

    Line ray,side;

    ray.s=a;

    ray.e.y=a.y;

    ray.e.x=-inf;

    for(int i=;i<n;++i){

        side.s=p[i];

        side.e=p[(i+)%n];

        if(OnSeg(a,side)) return ;

        if(sgn(side.s.y-side.e.y)==) continue;

        if(OnSeg(side.s,ray)){

            if(sgn(side.s.y-side.e.y)>) ++cnt;

        }

        else if(OnSeg(side.e,ray)){

            if(sgn(side.e.y-side.s.y)>) ++cnt;

        }

        else if(inter(ray,side)) ++cnt;

    }

    if(cnt%==) return ;

    else return -;

}

int main(){

    scanf("%d",&T);

    double x1,yy1,x2,yy2;

    while(T--){

        flag=;

        scanf("%lf%lf%lf%lf",&x1,&yy1,&x2,&yy2);

        Line line=Line(Point(x1,yy1),Point(x2,yy2));

        scanf("%lf%lf%lf%lf",&x1,&yy1,&x2,&yy2);

        if(x1>x2) swap(x1,x2);

        if(yy1>yy2) swap(yy1,yy2);

        Point p[];

        p[]=Point(x1,yy1);

        p[]=Point(x2,yy1);

        p[]=Point(x2,yy2);

        p[]=Point(x1,yy2);

        for(int i=;i<;++i)

            if(inter(line,Line(p[i],p[(i+)%]))){

                flag=;

                break;

            }

        if(inConvexPoly(line.s,p,)>&&inConvexPoly(line.e,p,)>)

            flag=;

        if(flag) printf("T\n");

        else printf("F\n");

    }

    return ;

}

poj1410(判断线段和矩形是否相交)的相关教程结束。