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
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <ctime>
#include <cmath>

using namespace std;

struct rect {
  int x1,x2,y1,y2;
  
  bool operator < (const rect &r) const {
    if(x1 != r.x1) return x1 < r.x1;
    if(x2 != r.x2) return x2 < r.x2;
    if(y1 != r.y1) return y1 < r.y1;
    return y2 < r.y2;
  };
};

long long intersect(rect &r1, rect &r2) {
  long long x = min(r1.x2,r2.x2) - max(r1.x1,r2.x1);
  long long y = min(r1.y2,r2.y2) - max(r1.y1,r2.y1);
  if(x<=0 || y<=0) return 0;
  return x*y;
}

int main(int argc, char *argv[]) {  
  int n;
  
  srand(time(NULL));
  
  scanf("%d", &n);
  vector<rect> v;
  rect r;
  
  for(int i=0; i<n; i++) {
    scanf("%d%d%d%d", &r.x1, &r.x2, &r.y1, &r.y2);
    v.push_back(r);
  }
  
  long long hi=2000000;long long low=1;
  while(low<hi) {
    long long s=(hi+low)/2;
    if(s*n>50000000) hi=s;
    else low=s+1;
  }
  
  int iter=low;
  while(iter--) {
    int rnd = rand()%(v.size());
    int i=0;
    int c=0;
    while(i<v.size()) { 
      if(i!=rnd && intersect(v[i], v[rnd])>0) {
        r.x1=min(v[i].x1, v[rnd].x1);
        r.x2=max(v[i].x2, v[rnd].x2);
        r.y1=min(v[i].y1, v[rnd].y1);
        r.y2=max(v[i].y2, v[rnd].y2);
  
        v.erase(v.begin()+i);
        int a = 0; if(i<rnd) a=1;
        rnd-=a;
        
        v.push_back(r);
        ++c;
      }
      ++i;
    }
    if(c) v.erase(v.begin()+rnd);
  }
  
  sort(v.begin(), v.end());
  printf("%d\n", (int)v.size());
  for(int i=0; i<v.size(); i++)
    printf("%d %d %d %d\n", v[i].x1, v[i].x2, v[i].y1, v[i].y2);
  
  return 0;
}