|
|
Posted on 2009-10-02 03:13 Uriel 閱讀(413) 評論(0) 編輯 收藏 引用 所屬分類: POJ 、 計算幾何
判斷矩形與一線段是否相交，注意線段在矩形內部的情況
其他都是模板。。沒什么了。。
  /**//*Problem: 1410 User: Uriel
 Memory: 172K Time: 0MS
 Language: C++ Result: Accepted*/
#include<stdio.h>
#include<stdlib.h>
#include <math.h>
#define eps 1e-8
#define zero(x) (((x)>0?(x):-(x))<eps)
struct point
 {
double x,y;
};
struct line
{
point a,b;
};
double xmult(point p1,point p2,point p0)
{
return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}
int dot_online_in(point p,point l1,point l2)
{
return zero(xmult(p,l1,l2))&&(l1.x-p.x)*(l2.x-p.x)<eps&&(l1.y-p.y)*(l2.y-p.y)<eps;
}
int dots_inline(point p1,point p2,point p3)
{
return zero(xmult(p1,p2,p3));
}
int same_side(point p1,point p2,point l1,point l2)
{
return xmult(l1,p1,l2)*xmult(l1,p2,l2)>eps;
}
int intersect_in(point u1,point u2,point v1,point v2)
{
if (!dots_inline(u1,u2,v1)||!dots_inline(u1,u2,v2))
  {
return !same_side(u1,u2,v1,v2)&&!same_side(v1,v2,u1,u2);
 }
return dot_online_in(u1,v1,v2)||dot_online_in(u2,v1,v2)||dot_online_in(v1,u1,u2)||dot_online_in(v2,u1,u2);
}
point P1,P2,S1,S2,S3,S4;
int main()
{
int t,flag;
double temp;
scanf("%d",&t);
while(t--)
{
scanf("%lf %lf %lf %lf %lf %lf %lf %lf",&P1.x,&P1.y,&P2.x,&P2.y,&S1.x,&S1.y,&S2.x,&S2.y);
if(S1.x>S2.x)
{
temp=S1.x;
S1.x=S2.x;
S2.x=temp;
}
if(S1.y<S2.y)
{
temp=S1.y;
S1.y=S2.y;
S2.y=temp;
}
S3.x=S1.x;
S3.y=S2.y;
S4.x=S2.x;
S4.y=S1.y;
flag=0;
if(intersect_in(P1,P2,S1,S3) || intersect_in(P1,P2,S1,S4) || intersect_in(P1,P2,S2,S3) || intersect_in(P1,P2,S2,S4))
{
flag=1;
}
if(P1.x>=S1.x && P1.x<=S2.x && P2.x>=S1.x && P2.x<=S2.x && P1.y<=S1.y && P1.y>=S2.y && P2.y<=S1.y && P2.y>=S2.y)
{
flag=1;
}
if(!flag)
{
printf("F\n");
}
else
{
printf("T\n");
}
}
// system("PAUSE");
return 0;
}
|