// CS algorithm

#include <stdio.h>

#define SET_BIT(x,y) x|=(1<<y)

struct rect
{
  int xleft,ytop;
  int xright,ybottom;
};

int __inline__ sign(int x)
{
  return x==0?0:(x<0?-1:1);
}

int get_code(int x,int y,struct rect r)
{
  int code=0;
  if (x<r.xleft) SET_BIT(code,0);
  else if (x>r.xright) SET_BIT(code,1);
  if (y>r.ytop) SET_BIT(code,3);
  else if (y<r.ybottom) SET_BIT(code,2);
  return code;
}

int main()
{
  int n;
  int i;
  int x1,y1,x2,y2;
  struct rect r;
  int code1,code2;
  int s1,s2,s3,s4;

  scanf("%d",&n);
  for (i=0;i<n;++i) {
    scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
    scanf("%d %d %d %d",&r.xleft,&r.ytop,&r.xright,&r.ybottom);
    if (x1==x2 && y1==y2) {
      printf("T\n");
      continue;
    }
    if (r.xleft>r.xright) {
      r.xleft^=r.xright;r.xright^=r.xleft;r.xleft^=r.xright;
    }
    if (r.ytop<r.ybottom) {
      r.ytop^=r.ybottom;r.ybottom^=r.ytop;r.ytop^=r.ybottom;
    }
    code1=get_code(x1,y1,r);
    code2=get_code(x2,y2,r);
    if (code1&code2)
      printf("F\n");
    else {
      x2-=x1;r.xleft-=x1;r.xright-=x1;
      y2-=y1;r.ytop-=y1;r.ybottom-=y1;
      x1=y1=0;
      s1=sign(r.ytop*x2-r.xleft*y2);
      s2=sign(r.ytop*x2-r.xright*y2);
      s3=sign(r.ybottom*x2-r.xleft*y2);
      s4=sign(r.ybottom*x2-r.xright*y2);
      if (s1==s2 && s2==s3 && s3==s4 && s1!=0)
	printf("F\n");
      else
	printf("T\n");
    }
  }

  return 0;
}
  

• Re:你的线段退化为点后，难道就不判断点是否在矩形内部。。 (1695) kevinew 2007-01-02 02:32:31
  • Re:你的线段退化为点后，难道就不判断点是否在矩形内部。。 (120) richardxx 2007-01-02 02:37:13