首页 > 代码库 > POJ 1410

POJ 1410

内部也是相交

#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>using namespace std;struct point{	int x,y;};struct edge{	point start,end;}line[4],the;void swaped(int &x,int &y){	int tmp=x;	x=y;	y=tmp;}int multi(point p1,point p2, point p0){	return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);}bool cross(edge v1, edge v2){	if(max(v1.start.x,v1.end.x)>=min(v2.start.x,v2.end.x)&&	max(v2.start.x,v2.end.x)>=min(v1.start.x,v1.end.x)&&	max(v1.start.y,v1.end.y)>=min(v2.start.y,v2.end.y)&&	max(v2.start.y,v2.end.y)>=min(v1.start.y,v1.end.y)&&	multi(v2.start,v1.end,v1.start)*multi(v1.end,v2.end,v1.start)>=0&&	multi(v1.start,v2.end,v2.start)*multi(v2.end,v1.end,v2.start)>=0)	return true;	return false;}/*bool cross(point &a, point &b, point &c, point &d){    if (min(a.x, b.x) > max(c.x, d.x) || min(a.y, b.y) > max(c.y, d.y) || min(            c.x, d.x) > max(a.x, b.x) || min(c.y, d.y) > max(a.y, b.y))        return 0;    double h, i, j, k;    h = (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);    i = (b.x - a.x) * (d.y - a.y) - (b.y - a.y) * (d.x - a.x);    j = (d.x - c.x) * (a.y - c.y) - (d.y - c.y) * (a.x - c.x);    k = (d.x - c.x) * (b.y - c.y) - (d.y - c.y) * (b.x - c.x);    return h * i <= 0 && j * k <= 0;}*/int main(){	int T; int xleft,ytop,xright,ybottom; int xstart,ystart,xend,yend;	scanf("%d",&T);	while(T--){		scanf("%d%d%d%d%d%d%d%d",&xstart,&ystart,&xend,&yend,&xleft,&ytop,&xright,&ybottom);		the.start.x=xstart; the.start.y=ystart;		the.end.x=xend; the.end.y=yend;		if(xleft>xright)		swaped(xleft,xright);		if(ytop<ybottom)		swaped(ytop,ybottom);		line[0].start.x=xleft; line[0].start.y=ytop;		line[0].end.x=xright; line[0].end.y=ytop;		line[1].start.x=xleft; line[1].start.y=ybottom;		line[1].end.x=xright; line[1].end.y=ybottom;		line[2].start.x=xleft; line[2].start.y=ybottom;		line[2].end.x=xleft; line[2].end.y=ytop;		line[3].start.x=xright; line[3].start.y=ybottom;		line[3].end.x=xright; line[3].end.y=ytop;		bool flag=true;		for(int i=0;i<4;i++){			if(cross(the,line[i])){				flag=false;				break;			}		}		if(flag){			if(xstart>=min(xleft,xright)&&xstart<=max(xleft,xright)&&			   ystart>=min(ytop,ybottom)&&ystart<=max(ytop,ybottom)){			   	flag=false;			   }   			else if(xend>=min(xleft,xright)&&xend<=max(xleft,xright)&&			   yend>=min(ytop,ybottom)&&yend<=max(ytop,ybottom))			   flag=false;		}				if(flag){			printf("F\n");		}		else printf("T\n");			}	return 0;}