題目大意：求線段與實心矩形是否相交。
解題關鍵：轉化為線段與線段相交的判斷。
#include<cstdio> #include<cstring> #include<algorithm> #include<cstdlib> #include<cmath> #include<iostream> #define eps 1e-8 using namespace std; typedef long long ll; struct Point{double x,y;Point(){}Point(double _x,double _y){x=_x;y=_y;}Point operator-(const Point &b)const{return Point(x - b.x,y - b.y);}double operator^(const Point &b)const{return x*b.y-y*b.x;}double operator*(const Point &b)const{return x*b.x+y*b.y;} }; struct Line{Point s,e;Line(){}Line(Point _s,Point _e){s=_s;e=_e;} }A[35]; int sgn(double x){if(fabs(x)<eps)return 0;else if(x<0) return -1;else return 1; } //判斷線段相交，模板 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((l2.s-l1.s)^(l1.e-l1.s))*sgn((l2.e-l1.s)^(l1.e-l1.s))<=0&&sgn((l1.s-l2.s)^(l2.e-l2.s))*sgn((l1.e-l2.s)^(l2.e-l2.s))<=0; } int main(){ int t,i; double xleft,ytop,xright,ybottom; double x1,y1,x2,y2; scanf("%d",&t); while(t--){ scanf("%lf%lf%lf%lf",&A[0].s.x,&A[0].s.y,&A[0].e.x,&A[0].e.y);//線段 scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2); xleft=min(x1,x2);xright=max(x1,x2); ybottom=min(y1,y2);ytop=max(y1,y2); A[1].s.x=xleft;A[1].s.y=ybottom;A[1].e.x=xleft;A[1].e.y=ytop; A[2].s.x=xleft;A[2].s.y=ytop;A[2].e.x=xright;A[2].e.y=ytop; A[3].s.x=xright;A[3].s.y=ytop;A[3].e.x=xright;A[3].e.y=ybottom; A[4].s.x=xright;A[4].s.y=ybottom;A[4].e.x=xleft;A[4].e.y=ybottom;//矩形的四條線段 for(i=1;i<=4;++i) if(inter(A[0],A[i]))break;bool flag=false;//矩形是實心的。 if(A[0].s.x<=xright&&A[0].s.x>=xleft&&A[0].s.y>=ybottom&&A[0].s.y<=ytop)flag=true; if(A[0].e.x<=xright&&A[0].e.x>=xleft&&A[0].e.y>=ybottom&&A[0].e.y<=ytop)flag=true; if(i>4&&flag==0) printf("F\n");else printf("T\n"); } return 0; }
?
