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
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
/*************************************************************************
 *                                                                       *
 *                   Potyczki Algorytmiczne 2014                         *
 *                                                                       *
 *                  Zadanie:           Plemiona [B]                      *
 *                  Autor:             Jakub Sroka                       *
 *                                                                       *
 *************************************************************************/

#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

class area {
public:
    int x1, x2, y1, y2;
    int nr;
};

void myMerge(area *area1, area *area2);
int binarySearch(int max, vector<area> *areas, int begin, int end);
bool areIntersecting(area *area1, area *area2);
bool mySort(area a, area b) { return a.x1 < b.x1; }
bool mySort2(area a, area b) { return a.x2 < b.x2; }
bool mySort3(area a, area b) { return a.y1 < b.y1; }
bool mySort4(area a, area b) { return a.y2 < b.y2; }

int main(int argc, const char * argv[])
{
    int n;
    scanf("%d", &n);
    
    vector<area> areas(n+1);
    for (int i=1; i<=n; i++) {
        scanf("%d %d %d %d", &areas[i].x1, &areas[i].x2, &areas[i].y1, &areas[i].y2);
        areas[i].nr = i;
    }
    
    sort(areas.begin(), areas.end(), mySort);
    
    vector<int> indexes;
    bool didMerge;
    int lastPossible;
    
    for (int i=1; i<=n; i++) {
        didMerge = false;
        lastPossible = binarySearch(areas[i].x2, &areas, 1, areas.size());
        if (lastPossible <= i) continue;
        for (int j=i+1; j<=lastPossible; j++) {
            if (areIntersecting(&areas[i], &areas[j])) {
                myMerge(&areas[i], &areas[j]);
                didMerge = true;
            }
        }
        if (didMerge) i=0;
    }
    
    vector<area> countries;
    vector<bool> table(n+1);
    
    for (int i=1; i<=n; i++) {
        if (!table[areas[i].nr]) {
            countries.push_back(areas[i]);
            table[areas[i].nr] = true;
        }
    }
    
    sort(countries.begin(), countries.end(), mySort4);
    stable_sort(countries.begin(), countries.end(), mySort3);
    stable_sort(countries.begin(), countries.end(), mySort2);
    stable_sort(countries.begin(), countries.end(), mySort);
    
    printf("%d\n", countries.size());
    for (int i=0; i<countries.size(); i++) {
        printf("%d %d %d %d\n", countries[i].x1, countries[i].x2, countries[i].y1, countries[i].y2);
    }
    
    return 0;

}

bool areIntersecting(area *area1, area *area2)
{
    if (area2->y2 > area1->y1 && area2->y1 < area1->y2 && area2->nr != area1->nr) {
        return true;
    }
    
    return false;
}

int binarySearch(int max, vector<area> *areas, int begin, int end)
{
    int index = (begin+end)/2;
    if (begin == end) {
        return index;
    }
    if (index == begin && areas->at(index+1).x1 >= max) {
        return index;
    }
    if (areas->at(index).x1 < max && ((index < areas->size()-1 && areas->at(index+1).x1 >= max) || index == areas->size()-1)) {
        return index;
    }
    if (areas->at(index).x1 < max) {
        return binarySearch(max, areas, index, end);
    }
    
    return binarySearch(max, areas, begin, index);
}

void myMerge(area *area1, area *area2)
{
    if (area1->x1 < area2->x1) {
        area2->x1 = area1->x1;
    }
    else area1->x1 = area2->x1;
    
    if (area1->x2 > area2->x2) {
        area2->x2 = area1->x2;
    }
    else area1->x2 = area2->x2;
    
    if (area1->y1 < area2->y1) {
        area2->y1 = area1->y1;
    }
    else area1->y1 = area2->y1;
    
    if (area1->y2 > area2->y2) {
        area2->y2 = area1->y2;
    }
    else area1->y2 = area2->y2;
    
    area2->nr = area1->nr;
}