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
#include <stdio.h>
#include <stdlib.h>

#define min(x,y)    ((x) < (y) ? (x) : (y))
#define max(x,y)    ((x) < (y) ? (y) : (x))

#define MAKS_N  100000

struct pole
{
    int x1;
    int x2;
    int y1;
    int y2;
    int lacz;
};
typedef struct pole t_pole;

t_pole pole[2][MAKS_N];

int porownaj(const void *e1, const void *e2)
{
    t_pole *p1 = (t_pole *) e1;
    t_pole *p2 = (t_pole *) e2;
    int por = p1->x1 - p2->x1;
    if (por == 0)
        por = p1->x2 - p2->x2;
    if (por == 0)
        por = p1->y1 - p2->y1;
    if (por == 0)
        por = p1->y2 - p2->y2;
    return por;
}

int lacz_pola(int a, int b, int i, int j, int n2)
{
    if (pole[a][i].x2 > pole[a][j].x1 && pole[a][i].y1 < pole[a][j].y2 && pole[a][i].y2 > pole[a][j].y1)
    {
        pole[b][n2].x1 = /*pole[a][i].x1 = */min(pole[a][i].x1, pole[a][j].x1);
        pole[b][n2].x2 = /*pole[a][i].x2 = */max(pole[a][i].x2, pole[a][j].x2);
        pole[b][n2].y1 = /*pole[a][i].y1 = */min(pole[a][i].y1, pole[a][j].y1);
        pole[b][n2].y2 = /*pole[a][i].y2 = */max(pole[a][i].y2, pole[a][j].y2);
        pole[b][n2].lacz = 0;
        pole[a][i].lacz = 1;
        pole[a][j].lacz = 1;
//        printf("\t%d\t%d\t%d\t%d\n", pole[b][n2].x1, pole[b][n2].x2, pole[b][n2].y1, pole[b][n2].y2);
        return 1;
    }
    else
        return 0;
}

int main()
{
    int n, i, j, a, b, n2;
    scanf("%d", &n);
    for (i = 0; i < n; i++)
    {
        scanf("%d%d%d%d", &pole[0][i].x1, &pole[0][i].x2, &pole[0][i].y1, &pole[0][i].y2);
        pole[0][i].lacz = 0;
    }
    a = 0;
    b = 1;
    do
    {
        qsort(pole[a], n, sizeof(t_pole), porownaj);
        n2 = 0;
        for (i = 0; i < n - 1; i++)
        {
            for (j = i + 1; j < n && pole[a][i].x2 > pole[a][j].x1 && n2 < MAKS_N; j++)
                if (lacz_pola(a, b, i, j, n2))
                    n2++;
        }
        if (n2 > 0)
        {
            for (i = 0; i < n; i++)
            {
                if (!pole[a][i].lacz)
                {
                    pole[b][n2].x1 = pole[a][i].x1;
                    pole[b][n2].x2 = pole[a][i].x2;
                    pole[b][n2].y1 = pole[a][i].y1;
                    pole[b][n2].y2 = pole[a][i].y2;
                    pole[b][n2].lacz = 0;
                    n2++;
                }
            }
            n = n2;
        }
        a = 1 - a;
        b = 1 - b;
    } while (n2 > 0);
    printf("%d\n", n);
    for (i = 0; i < n; i++)
        printf("%d %d %d %d\n", pole[b][i].x1, pole[b][i].x2, pole[b][i].y1, pole[b][i].y2);
    return 0;
}