1901648_re.c

北大大牛代码 1240道题的原代码 超级权威

# include <stdio.h>
# include <stdlib.h>
# define maxsize 250

struct node
{
  long ldx, ldy;
  long rux, ruy;
  int flag;
} barn[maxsize];

struct Node
{
  long x, y;
};

struct NODE
{
	long no;
	struct Node c;
}xx[maxsize*4],yy[maxsize*4],tmpu, tmpd;

int cmpx(const void *a, const void *b)
{
   struct NODE *aa = (struct NODE *)a;
   struct NODE *bb = (struct NODE *)b;
   if(aa->c.x == bb->c.x)
     return aa->c.y - bb->c.y;
   else
     return aa->c.x - bb->c.x;
}
int cmpy(const void *a, const void *b)
{
  struct NODE *aa = (struct NODE *)a;
  struct NODE *bb = (struct NODE *)b;
  if(aa->c.y == bb->c.y)
    return aa->c.x - bb->c.x;
  else
    return aa->c.y - bb->c.y;
}
int main()
{
  int i, n, no;
  struct NODE *p, *q, *r;

  scanf("%d",&n);
  for(i = 0; i < n; i++)
   {
     scanf("%ld%ld%ld%ld",&barn[i].ldx,&barn[i].ldy,&barn[i].rux,&barn[i].ruy);
     barn[i].flag = 0;
     xx[i*4+0].c.x = yy[i*4+0].c.x = barn[i].ldx;xx[i*4+0].no = i;yy[i*4+0].no = i;
     xx[i*4+0].c.y = yy[i*4+0].c.y = barn[i].ldy;xx[i*4+1].no = i;yy[i*4+1].no = i;
     xx[i*4+1].c.x = yy[i*4+1].c.x = barn[i].rux;xx[i*4+2].no = i;yy[i*4+2].no = i;
     xx[i*4+1].c.y = yy[i*4+1].c.y = barn[i].ruy;xx[i*4+3].no = i;yy[i*4+3].no = i;
     xx[i*4+2].c.x = yy[i*4+2].c.x = barn[i].rux;
     xx[i*4+2].c.y = yy[i*4+2].c.y = barn[i].ldy;
     xx[i*4+3].c.x = yy[i*4+3].c.x = barn[i].ldx;
     xx[i*4+3].c.y = yy[i*4+3].c.y = barn[i].ruy;
   }
   qsort(xx,n*4,sizeof(xx[0]),cmpx);
   qsort(yy,n*4,sizeof(yy[0]),cmpy);
   for(i = 0; i < n; i++)
    {
      tmpd.no = i;
      tmpu.no = i;
      tmpd.c.x = barn[i].ldx; tmpd.c.y = barn[i].ldy;
      tmpu.c.x = barn[i].ldx; tmpu.c.y = barn[i].ruy;
      p = (struct NODE *)bsearch(&tmpd,xx,n*4,sizeof(xx[0]),cmpx);
      q = (struct NODE *)bsearch(&tmpu,xx,n*4,sizeof(xx[0]),cmpx);
      if(p!=&xx[0])
		  if(p->c.x==(p-1)->c.x&&p->c.y==(p-1)->c.y)
		  {
			  barn[p->no].flag = 1;
		      barn[(p-1)->no].flag = 1;
		  }
	  if(q!=&xx[n*4-1])
		  if(q->c.x==(q+1)->c.x&&q->c.y==(q+1)->c.y)
		  {
			  barn[q->no].flag = 1;
			  barn[(q+1)->no].flag = 1;
		  }
      if(q > p + 1)	   
	   for(r = p + 1; r < q; r++)
	     barn[r->no].flag = 1;
	  tmpd.c.x = barn[i].rux;
      tmpu.c.x = barn[i].rux;
	  p = (struct NODE *)bsearch(&tmpd,xx,n*4,sizeof(xx[0]),cmpx);
      q = (struct NODE *)bsearch(&tmpu,xx,n*4,sizeof(xx[0]),cmpx);
      if(p!=&xx[0])
		  if(p->c.x==(p-1)->c.x&&p->c.y==(p-1)->c.y)
		  {
			  barn[p->no].flag = 1;
		      barn[(p-1)->no].flag = 1;
		  }
	  if(q!=&xx[n*4-1])
		  if(q->c.x==(q+1)->c.x&&q->c.y==(q+1)->c.y)
		  {
			  barn[q->no].flag = 1;
			  barn[(q+1)->no].flag = 1;
		  }
      if(q > p + 1)
	   for(r = p ; r < q; r++)
	     barn[r->no].flag = 1;
	   tmpd.c.y = barn[i].ldy; tmpd.c.x = barn[i].ldx;
      tmpu.c.y = barn[i].ldy; tmpu.c.x = barn[i].rux;
      p = (struct NODE *)bsearch(&tmpd,yy,n*4,sizeof(yy[0]),cmpy);
      q = (struct NODE *)bsearch(&tmpu,yy,n*4,sizeof(yy[0]),cmpy);
      if(p!=&yy[0])
		  if(p->c.x==(p-1)->c.x&&p->c.y==(p-1)->c.y)
		  {
			  barn[p->no].flag = 1;
		      barn[(p-1)->no].flag = 1;
		  }
	  if(q!=&yy[n*4-1])
		  if(q->c.x==(q+1)->c.x&&q->c.y==(q+1)->c.y)
		  {
			  barn[q->no].flag = 1;
			  barn[(q+1)->no].flag = 1;
		  }
      if(q > p + 1)
	   for(r = p; r < q; r++)
	    barn[r->no].flag = 1;
	  tmpd.c.y = barn[i].ruy;
      tmpu.c.y = barn[i].ruy;
	  p = (struct NODE *)bsearch(&tmpd,yy,n*4,sizeof(yy[0]),cmpy);
      q = (struct NODE *)bsearch(&tmpu,yy,n*4,sizeof(yy[0]),cmpy);
      if(p!=&yy[0])
		  if(p->c.x==(p-1)->c.x&&p->c.y==(p-1)->c.y)
		  {
			  barn[p->no].flag = 1;
		      barn[(p-1)->no].flag = 1;
		  }
	  if(q!=&yy[n*4-1])
		  if(q->c.x==(q+1)->c.x&&q->c.y==(q+1)->c.y)
		  {
			  barn[q->no].flag = 1;
			  barn[(q+1)->no].flag = 1;
		  }
      if(q > p + 1)
	   for(r = p; r < q; r++)
	     barn[r->no].flag = 1;
    }
   no = 0;
   for(i = 0; i < n; i++)
	   if(barn[i].flag==0)
		   no++;
	   printf("%d\n",no);
   return 1;
}