POJ1410

注意：这个矩形是实心！

其余没什么说的。

判断线段与矩形的位置关系

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
using namespace std;
const double eps = 1e-8;

struct Point{
	double x,y;
};
struct Rect{
	Point p[4];
};
struct Line{
	Point a,b;
};

double xmult( Point sp,Point ep,Point op ){
	return (sp.x-op.x)*(ep.y-op.y)-(sp.y-op.y)*(ep.x-op.x);
}

bool Point_in_Rect( Point p,Rect s ){
	if( xmult( s.p[3],s.p[0],p )<-eps ) return false;
	if( xmult( s.p[0],s.p[1],p )<-eps ) return false;
	if( xmult( s.p[1],s.p[2],p )<-eps ) return false;
	if( xmult( s.p[2],s.p[3],p )<-eps ) return false;
	return true;
}

bool between_a_b( Point aim,int x1,int x2,int y1,int y2 ){
	if( aim.x>=x1&&aim.x<=x2&&aim.y>=y1&&aim.y<=y2 )
		return true;
	return false;
}

 bool inLine( Line now,Point p ){
     double minx,maxx,miny,maxy;
     minx=min( now.a.x,now.b.x );
     maxx=max( now.a.x,now.b.x );
     miny=min( now.a.y,now.b.y );
     maxy=max( now.a.y,now.b.y );
     if( p.x>=minx&&p.x<=maxx&&p.y>=miny&&p.y<=maxy )
         return true;
     else
         return false;
 }
 
 bool Intersect( Line one,Line two ){
     double d1,d2,d3,d4;
     d1=xmult( two.a,one.b,one.a );
     d2=xmult( two.b,one.b,one.a );
     d3=xmult( one.a,two.a,two.b );
     d4=xmult( one.b,two.a,two.b );
     if( d1*d2<0&&d3*d4<0 )
         return true;//相互跨过
     if( d1==0&&inLine( one,two.a )==true )
         return true;
     if( d2==0&&inLine( one,two.b )==true )
         return true;
     if( d3==0&&inLine( two,one.a )==true )
         return true;
     if( d4==0&&inLine( two,one.b )==true )
         return true;//分别表示某个点在一条直线上的情况
     return false;
 }

int main(){
	int ca;
	scanf("%d",&ca);
	while( ca-- ){
		Point s,t;
		Rect rect;
		scanf("%lf%lf%lf%lf%lf%lf%lf%lf",&s.x,&s.y,&t.x,&t.y,&rect.p[0].x,&rect.p[0].y,&rect.p[2].x,&rect.p[2].y);
		rect.p[1].x = rect.p[0].x;
		rect.p[1].y = rect.p[2].y;
		rect.p[3].x = rect.p[2].x;
		rect.p[3].y = rect.p[0].y;
		double min_x,max_x,min_y,max_y;
		min_x = min( rect.p[0].x,min( rect.p[1].x,min( rect.p[2].x,rect.p[3].x) ) );
		min_y = min( rect.p[0].y,min( rect.p[1].y,min( rect.p[2].y,rect.p[3].y) ) );
		max_x = max( rect.p[0].x,max( rect.p[1].x,max( rect.p[2].x,rect.p[3].x) ) );
		max_y = max( rect.p[0].y,max( rect.p[1].y,max( rect.p[2].y,rect.p[3].y) ) );
		if( Point_in_Rect( s,rect )==true||Point_in_Rect( t,rect )==true||between_a_b( s,min_x,max_x,min_y,max_y )==true||between_a_b( t,min_x,max_x,min_y,max_y )==true )
			printf("T\n");
		else{
			Line t1,t2;
			t1.a = s,t1.b = t;
			t2.a = rect.p[0],t2.b = rect.p[1];
			if( Intersect(t1,t2)==true ){
				printf("T\n");
				continue;
			}
			t2.a = rect.p[1],t2.b = rect.p[2];
			if( Intersect(t1,t2)==true ){
				printf("T\n");
				continue;
			}
			t2.a = rect.p[2],t2.b = rect.p[3];
			if( Intersect(t1,t2)==true ){
				printf("T\n");
				continue;
			}
			t2.a = rect.p[3],t2.b = rect.p[0];
			if( Intersect(t1,t2)==true ){
				printf("T\n");
				continue;
			}
			printf("F\n");
		}
	}
	return 0;
}