既见君子

poj 1410计算几何基础

因为在练习点与多边形的关系，所以选择射线法，我们在引射线的时候注意平行的是不算在内的，如果这个点刚好在边界上也可以判掉（因为我的射线法有点奇怪，是求完交点之后再判交点），所以还是有一些细节需要注意，感觉这次poj数据也不是很水，至少我拿着标程拍了10000+才拍出错。

//网上的标程写了整整180行，还是一个叫做kuangbin的人，之前做概率与期望好像看过他的博客呢。

//题意：给出一个矩形和一条线段，如果线段在矩形内部或者有交点就输出T否则F

code：

#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
#define eps 1e-7
int sgn(double v){
        if(fabs(v)<eps) return 0;
        return v<0?-1:1;
}
struct Point{
        double x,y;
        void read(){scanf("%lf%lf",&x,&y);}
        void print(){printf("%.6f %.6f\n",x,y);}
        Point(double a=0,double b=0){x=a,y=b;}
        Point operator +(const Point &c){return Point(x+c.x,y+c.y);}
        Point operator -(const Point &c){return Point(x-c.x,y-c.y);}
        Point operator *(const double &c){return Point(x*c,y*c);}
        Point operator /(const double &c){return Point(x/c,y/c);}
}p[4];
struct Segment{
        Point st,ed;
        void read(){st.read(),ed.read();}
        void print(){puts("st:");st.print();puts("ed");ed.print();}
}s[4],T;
typedef Point Vector;
double det(Vector a,Vector b){
        return a.x*b.y-a.y*b.x;
}
Point insect(Segment p,Segment q){
        double v=det(p.ed-p.st,q.st-p.st),u=det(q.ed-p.st,p.ed-p.st);
        return (q.ed*v+q.st*u)/(u+v);
}
bool in(Point a,Segment b){
        return sgn(a.x-max(b.st.x,b.ed.x))<=0&&sgn(a.x-min(b.st.x,b.ed.x))>=0&&sgn(a.y-max(b.st.y,b.ed.y))<=0&&sgn(a.y-min(b.st.y,b.ed.y))>=0;
}
Vector dir=Point(-1000000000,0);
bool judge(){
        for(int i=0;i<4;++i)
                if(in(insect(T,s[i]),T)&&in(insect(T,s[i]),s[i])) return true;
        Point op=T.st+dir;
        Segment tmp1;
        tmp1.st=T.st,tmp1.ed=op;
        int cnt=0;
        if(in(insect(tmp1,s[3]),tmp1)&&in(insect(tmp1,s[3]),s[3])) cnt++;
        if(in(insect(tmp1,s[1]),tmp1)&&in(insect(tmp1,s[1]),s[1])) cnt++;
        return cnt%2;
}
int main(){
    //    freopen("insect.in","r",stdin);
        int n;
        scanf("%d",&n);
        while(n--){
                T.read();
                p[0].read(),p[2].read();
                p[1]=Point(p[2].x,p[0].y);
                p[3]=Point(p[0].x,p[2].y);
                for(int i=0;i<4;++i){
                        s[i].st=p[i];
                        s[i].ed=p[(i+1)%4];
                }
            //    for(int i=0;i<4;++i) s[i].print();
                puts(judge()?"T":"F");
        }
        return 0;
}