POJ 1410 Intersection（計算幾何）

POJ 1410 Intersection（計算幾何）

題目鏈接：Intersection

判斷線段與矩形的關系，與矩形相交打印T，否則打印F；

坑題，精度。。。。

思路就是，先判斷 線段是否在矩形裡面，再判斷線段和兩條對角線的關系，利用叉積模板即可

測試數據有個坑，就是 左上角的坐標並不一定比右下角的小。。。這根本不符合題意嘛

#include 
#include 
#include 
#include 
#include 
#include 
#define init(a) memset(a,0,sizeof(a))
#define PI acos(-1,0)
using namespace std;
const int maxn = 110;
const int maxm = 10010;
#define lson left, m, id<<1
#define rson m+1, right, id<<1|1
#define min(a,b) (a>b)?b:a
#define max(a,b) (a>b)?a:b
void swap(int a,int b) {int t = a;a = b; b = t;}
struct node
{
    int x1,y1,x2,y2;
};
node g,h;
int judge(node p1,node p2)
{
    double h1,h2;
    h1 = p2.x1*(p1.y2-p1.y1) + p1.x2*p1.y1 - p1.x1 * p1.y2 - p2.y1*(p1.x2 - p1.x1);
    h2 = p2.x2*(p1.y2-p1.y1) + p1.x2*p1.y1 - p1.x1*p1.y2 - p2.y2*(p1.x2 - p1.x1);
    if(h1*h2<=0)
        return 1;
    else
        return 0;
}
bool OK(node g,node h)//判斷是否在矩形裡面
{
    if(g.x1>=h.x1 &&g.x1<=h.x2 && g.x2>=h.x1&&g.x2<=h.x2 &&
        g.y2>=h.y1&&g.y2<=h.y2 &&g.y1>=h.y1&&g.y1<=h.y2)
     {
         return 1;
     }
     return 0;
}
int main()
{
    int n;
    scanf("%d",&n);
    while(n--)
     {
      scanf("%d%d",&g.x1,&g.y1);
      scanf("%d%d",&g.x2,&g.y2);
      scanf("%d%d",&h.x1,&h.y1);
      scanf("%d%d",&h.x2,&h.y2);

    //  printf("%d %d %d %d\n",h.x1,h.y1,h.x2,h.y2);

     if(h.x1>h.x2)
         swap(h.x1,h.x2);
     if(h.y1>h.y2)
        swap(h.y1,h.y2);
        //printf("%d %d %d %d\n",h.x1,h.y1,h.x2,h.y2);
     if(OK(g,h))
     {
         puts("T");
         continue;
     }
      if(judge(g,h)==1 && judge(h,g)==1 )//判斷主對角線
          {
           puts("T");
           continue;
          }

        int flag = 0;
       // h.y1 = 12; h.y2 = 20;
          //swap(h.y1,h.y2);
          int t = h.y1; h.y1 = h.y2; h.y2 = t;
       // printf("%d %d %d %d\n",h.x1,h.y1,h.x2,h.y2);
         if(judge(g,h) && judge(h,g))//另一條對角線
            {
                flag=1;
            }
            (flag==1)?puts("T"):puts("F");
     }
        // printf("%d %d %d %d\n",h.x1,h.y1,h.x2,h.y2);
    return 0;
}