poj 1410 计算几何

  1 /**
  2 注意： 千万得小心。。就因为一个分号，调了一个晚上。。。
  3 **/
  4 #include <iostream>
  5 #include <algorithm>
  6 using namespace std;
  7 struct point {
  8     int x,y;
  9 };
 10 
 11 struct line{
 12     point a;
 13     point b;
 14 };
 15 line l,lt;//l 直线 lt 矩形的边
 16 int x1,x2,y1,y2;
 17 
 18 int mmax(double a,double b){
 19     return a>b?a:b;
 20 }
 21 
 22 int mmin(double a,double b){
 23     return a<b?a:b;
 24 }
 25 
 26 double dir(point o,point p,point   q){
 27     return (p.x-o.x)*(q.y-o.y)-(p.y-o.y)*(q.x-o.x);
 28 }
 29 
 30 int on_border(point o,point p,point q){
 31     if(mmin(o.x,p.x)<=q.x&&q.x<=mmax(o.x,p.x)&&mmin(o.y,p.y)<=q.y&&q.y<=mmax(o.y,p.y))
 32         return 1;
 33     else
 34         return 0;
 35 }
 36 
 37 int cross(line v,line t){
 38     double a,b,c,d;
 39     a = dir(t.a,t.b,v.a);
 40     b = dir(t.a,t.b,v.b);
 41     c = dir(v.a,v.b,t.a);
 42     d = dir(v.a,v.b,t.b);
 43     if(a*b<0&&c*d<0)
 44         return 1;
 45     if(!a&&on_border(t.a,t.b,v.a))
 46         return 1;
 47     if(!b&&on_border(t.a,t.b,v.b))
 48         return 1;
 49     if(!c&&on_border(v.a,v.b,t.a))
 50         return 1;
 51     if(!d&&on_border(v.a,v.b,t.b))
 52         return 1;
 53     return 0;
 54 }
 55 
 56 int main()
 57 {
 58     int n;
 59     cin>>n;
 60     while(n--){
 61         cin>>l.a.x>>l.a.y>>l.b.x>>l.b.y;
 62         cin>>x1>>y1>>x2>>y2;
 63         if(x1>x2)
 64             swap(x1,x2);
 65         if(y1<y2)
 66             swap(y1,y2);
 67         int flag =0;
 68         lt.a.x = x1;
 69         lt.a.y=y1;
 70         lt.b.x = x2;
 71         lt.b.y =y1;
 72         if(cross(l,lt))
 73             flag =1;
 74         else{
 75             lt.a.x=x2;
 76             lt.a.y=y1;
 77             lt.b.x=x2;
 78             lt.b.y=y2;
 79             if(cross(l,lt))
 80                 flag =1;
 81             else{
 82                 lt.a.x=x1;
 83                 lt.a.y=y2;
 84                 lt.b.x=x2;
 85                 lt.b.y=y2;
 86                 if(cross(l,lt))
 87                     flag =1;
 88                 else{
 89                     lt.a.x = x1;
 90                     lt.a.y=y1;
 91                     lt.b.x=x1;
 92                     lt.b.y=y2;
 93                     if(cross(l,lt))
 94                         flag =1;
 95                 }
 96             }
 97         }
 98         if(flag)
 99             cout<<"T"<<endl;
100         else{
101             if((x1<mmin(l.a.x,l.b.x))&&(mmax(l.a.x,l.b.x)<x2)&&(y2<mmin(l.a.y,l.b.y))&&(mmax(l.a.y,l.b.y)<y1))
102                 cout<<"T"<<endl;
103             else
104                 cout<<"F"<<endl;
105         }
106     }
107     return 0;
108 }