poj 1410 矩形与线段相交判断
2012-07-31 07:39:00

[cpp]
#include <iostream>
#include <cstring>
#include<cmath>
#include<algorithm>
using namespace std;
struct point

int x,y;
};
int xj(point x1,point x2,point x3,point x4)//相交为1,不交为0

if(min(x1.x,x2.x)>max(x3.x,x4.x)||min(x1.y,x2.y)>max(x3.y,x4.y)
||min(x3.x,x4.x)>max(x1.x,x2.x)||min(x3.y,x4.y)>max(x1.y,x2.y)
)
return 0;//不交：矩形排斥实验 ，最小的>最大的 肯定不交
int a,b,c,d;
a=(x1.x-x2.x)*(x3.y-x1.y)-(x1.y-x2.y)*(x3.x-x1.x);//跨立实验
b=(x1.x-x2.x)*(x4.y-x1.y)-(x1.y-x2.y)*(x4.x-x1.x);
c=(x3.x-x4.x)*(x1.y-x3.y)-(x3.y-x4.y)*(x1.x-x3.x);
d=(x3.x-x4.x)*(x2.y-x3.y)-(x3.y-x4.y)*(x2.x-x3.x);
return a*b<=0&&c*d<=0;

int main(void)

int t;
point x1,x2,j1,j2,j3,j4;
cin>>t;
while(t--)
{
cin>>x1.x>>x1.y>>x2.x>>x2.y>>j1.x>>j1.y>>j3.x>>j3.y;
j2.x=j1.x; j2.y=j3.y;
j4.x=j3.x; j4.y=j1.y;
if(  min(x1.x,x2.x)>min(j1.x,j3.x)&&max(x1.x,x2.x)<max(j1.x,j3.x)&&
min(x1.y,x2.y)>min(j1.y,j3.y)&&max(x1.y,x2.y)<max(j1.y,j3.y)  )
{cout<<"T"<<endl;continue;}//判断是否在内部
if(xj(x1,x2,j1,j2)||xj(x1,x2,j2,j3)||xj(x1,x2,j3,j4)||xj(x1,x2,j4,j1))
cout<<"T"<<endl; //只要有一条边相交，就是相交
else cout<<"F"<<endl;
}