题目链接：https://vjudge.net/problem/POJ-1410
题意：判断线段和矩形是否相交。
思路：注意这里的相交包括线段在矩形内，因此先判断线段与矩形的边是否相交，再判断线段的两端点是否在矩形内（因为是矩形，即凸多边形，直接用叉积判断即可，如果是一般的多边形，需要用射线法判断。）
AC code:
#include<cstdio> #include<algorithm> #include<cmath> #include<cstdlib> using namespace std; const double eps=1e-8; const double inf=1e20; int T,flag; int sgn(double x){ if(abs(x)<eps) return 0; if(x<0) return -1; return 1; } 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)) == 0) { if(sgn((s-b.e)^(b.s-b.e)) == 0) return make_pair(0,res);//重合 else return make_pair(1,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(2,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))<=0&& sgn((l2.s-l1.s)^(l1.e-l1.s))*sgn((l2.e-l1.s)^(l1.e-l1.s))<=0; } 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))==0&& sgn((P.x-L.s.x)*(P.x-L.e.x))<=0&& sgn((P.y-L.s.y)*(P.y-L.e.y))<=0; } //判断点在凸多边形内，复杂度O(n) //点形成一个凸包，而且按逆时针排序（如果是顺时针把里面的<0改为>0） //点的编号:0~n-1 //返回值： //-1:点在凸多边形外 //0:点在凸多边形边界上 //1:点在凸多边形内 int inConvexPoly(Point a,Point p[],int n){ for(int i=0;i<n;++i) if(sgn((p[i]-a)^(p[(i+1)%n]-a))<0) return -1; else if(OnSeg(a,Line(p[i],p[(i+1)%n]))) return 0; return 1; } //判断点在任意多边形内,复杂度O(n) //射线法，poly[]的顶点数要大于等于3,点的编号0~n-1 //返回值 //-1:点在凸多边形外 //0:点在凸多边形边界上 //1:点在凸多边形内 int inPoly(Point a,Point p[],int n){ int cnt=0; Line ray,side; ray.s=a; ray.e.y=a.y; ray.e.x=-inf; for(int i=0;i<n;++i){ side.s=p[i]; side.e=p[(i+1)%n]; if(OnSeg(a,side)) return 0; if(sgn(side.s.y-side.e.y)==0) continue; if(OnSeg(side.s,ray)){ if(sgn(side.s.y-side.e.y)>0) ++cnt; } else if(OnSeg(side.e,ray)){ if(sgn(side.e.y-side.s.y)>0) ++cnt; } else if(inter(ray,side)) ++cnt; } if(cnt%2==1) return 1; else return -1; } int main(){ scanf("%d",&T); double x1,yy1,x2,yy2; while(T--){ flag=0; 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[10]; p[0]=Point(x1,yy1); p[1]=Point(x2,yy1); p[2]=Point(x2,yy2); p[3]=Point(x1,yy2); for(int i=0;i<4;++i) if(inter(line,Line(p[i],p[(i+1)%4]))){ flag=1; break; } if(inConvexPoly(line.s,p,4)>0&&inConvexPoly(line.e,p,4)>0) flag=1; if(flag) printf("T "); else printf("F "); } return 0; }