1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
#include <stdio.h>

#define MIN(a,b) (((a)<(b))?(a):(b))
#define MAX(a,b) (((a)>(b))?(a):(b))

#define MAXPLE	100000

//****** zmienne ****
struct plemie {
  long int x1;
  long int x2;
  long int y1;
  long int y2;
  int flag;	//0 - istniejący, 1 - stopiony z innym plemieniem
}	plemiona[MAXPLE];


//******* proto ************
int cmp_fun(const void* p1, const void* p2);

//***** main ********************
int main(void)
{
	long int n; /* 1-100.000 liczba plemion */
//	long int x1, x2, y1, y2; /* 0-1000.000 terytorium plemienne x1<x2, y1<y2 */
	long int i,j;
	long int licznik;
	int stopienie, stopienie_zew;

	scanf("%ld\n", &n);
		
	for(i=0; i<n; i++) // wczytaj pozycje wejściowe
	  scanf("%ld %ld %ld %ld\n", &plemiona[i].x1, &plemiona[i].x2, &plemiona[i].y1, &plemiona[i].y2 );
		
	//sortowanie wg kolejności leksykograficznej 
	qsort(plemiona, n, sizeof(struct plemie), cmp_fun);

//********* test ******	
//	for(i=0;i<n;i++)
//	  printf("ind_we: %ld, %ld %ld %ld %ld, flag: %d\n", i, plemiona[i].x1, plemiona[i].x2, plemiona[i].y1, plemiona[i].y2, plemiona[i].flag);
//*****************		
	

	  //sprawdzanko
	do{
	  stopienie_zew = 0;
	  for(i=0;i<n;i++)
	  {
	    do 
	    {
	      stopienie = 0;
	      for(j = i+1; j<n; j++)
		if( ! plemiona[j].flag )
		{
//printf("%ld %ld %ld\n",i,j,plemiona[j].flag);		  
		  if(plemiona[j].x1 >= plemiona[i].x2)
		    break;
		  if(plemiona[j].y1 < plemiona[i].y2 && plemiona[j].y2 > plemiona[i].y1)
		  {
		    plemiona[i].x1 = MIN(plemiona[i].x1,plemiona[j].x1);
		    plemiona[i].x2 = MAX(plemiona[i].x2,plemiona[j].x2);
		    plemiona[i].y1 = MIN(plemiona[i].y1,plemiona[j].y1);
		    plemiona[i].y2 = MAX(plemiona[i].y2,plemiona[j].y2);
		    plemiona[j].flag = 1;
		    stopienie = 1;
		    stopienie_zew = 1;
		  }
		}
	    } while(stopienie);
	  }
	} while (stopienie_zew);


	//policz ilość państw i wyprowadź
	licznik = 0;
	for(i=0;i<n;i++)  
	  if( ! plemiona[i].flag )
	    licznik++;
	printf("%ld\n", licznik);
	for(i=0;i<n;i++)  
	  if( ! plemiona[i].flag )
	    printf("%ld %ld %ld %ld\n", plemiona[i].x1, plemiona[i].x2, plemiona[i].y1, plemiona[i].y2 );
	  
	
	
	return 0;
}

//************** functions *************************
int cmp_fun(const void* p1, const void* p2)
{
  struct plemie *a = (struct plemie *)p1, *b = (struct plemie*)p2;
  
  if( ( a->x1 > b->x1 ) || 
      ( ( a->x1 == b->x1 ) && ( a->x2 > b->x2 ) ) ||
      ( ( a->x1 == b->x1 ) && ( a->x2 == b->x2 ) && (a->y1 > b->y1) ) ||
      ( ( a->x1 == b->x1 ) && ( a->x2 == b->x2 ) && (a->y1 == b->y1) && (a->y2 > b->y2) )
    )
    return 1;
  else 
    if( ( a->x1 < b->x1 ) || 
      ( ( a->x1 == b->x1 ) && ( a->x2 < b->x2 ) ) ||
      ( ( a->x1 == b->x1 ) && ( a->x2 == b->x2 ) && (a->y1 < b->y1) ) ||
      ( ( a->x1 == b->x1 ) && ( a->x2 == b->x2 ) && (a->y1 == b->y1) && (a->y2 < b->y2) )
    )
    return -1;
  else
    return 0;
}
//-------------