|
Posted on 2009-10-02 03:13 Uriel 阅读(378) 评论(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; }
|