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

int liczba_plemion;
int* maxi;
int* mini;
typedef struct {
	int x1; int x2; int y1; int y2; int* x_list; int* y_list; short used;
} full;

full* plemiona;

int sortx(const void* a,const void* b) {
	int a1 = *((int*) a);
	int a2 = *((int*) b);
	if (plemiona[a1].x1 > plemiona[a2].x1) { return(1); }
	if (plemiona[a1].x1 < plemiona[a2].x1) { return(-1); }
	if (plemiona[a1].y1 > plemiona[a2].y1) { return(1); }
	return (-1);
}
int sorty(const void* a,const void* b) {
	int a1 = *((int*) a);
	int a2 = *((int*) b);
	if (plemiona[a1].x2 > plemiona[a2].x2) { return(-1); }
	if (plemiona[a1].x2 < plemiona[a2].x2) { return(1); }
	if (plemiona[a1].y2 > plemiona[a2].y2) { return(-1); }
	return (1);
}

void wczytaj() {
	int i; int x1; int x2; int y1; int y2;
	scanf("%d",&liczba_plemion);
	plemiona = (full*) malloc (sizeof(full)*liczba_plemion);
	maxi = (int*) malloc(sizeof(int)*liczba_plemion);
	mini = (int*) malloc(sizeof(int)*liczba_plemion);
	for (i=0; i<liczba_plemion;i++) {
		scanf("%d %d %d %d",&x1,&x2,&y1,&y2);
		plemiona[i].x1 = x1; plemiona[i].x2 = x2; plemiona[i].y1 = y1; plemiona[i].y2 = y2; plemiona[i].used = 0; plemiona[i].x_list = 0; plemiona[i].y_list = 0;
		maxi[i] = i; mini[i] = i;
	}
	qsort((void*)maxi,liczba_plemion,sizeof(int),sorty);
	qsort((void*)mini,liczba_plemion,sizeof(int),sortx);
	for (i=0; i<liczba_plemion;i++) {
		plemiona[maxi[i]].x_list = maxi + i;
		plemiona[mini[i]].y_list = mini + i;
	}
}

int main() {
	int* iterator; int* poszukiwania; short znaleziono = 1;
	int i;int suma = 0;
	wczytaj();
	iterator = mini;
	while(znaleziono) {
	znaleziono = 0;
	while (iterator < mini + liczba_plemion) {
		if (plemiona[*iterator].used) { iterator += 1; continue; }
		poszukiwania = iterator + 1;
		while (poszukiwania < mini + liczba_plemion) {
			if (plemiona[*iterator].x2 <= plemiona[*poszukiwania].x1) {
				break;
			}
			if (plemiona[*iterator].x2 > plemiona[*poszukiwania].x1 && (plemiona[*iterator].y2 > plemiona[*poszukiwania].y1 || plemiona[*iterator].y1 < plemiona[*poszukiwania].y2)) {
				znaleziono = 1;
				plemiona[*poszukiwania].used = 1;
				if (plemiona[*iterator].x2 < plemiona[*poszukiwania].x2) {
					plemiona[*iterator].x2 = plemiona[*poszukiwania].x2;
				}
				if (plemiona[*iterator].y1 > plemiona[*poszukiwania].y1) {
					plemiona[*iterator].y1 = plemiona[*poszukiwania].y1;
				}
				if (plemiona[*iterator].y2 < plemiona[*poszukiwania].y2) {
					plemiona[*iterator].y2 = plemiona[*poszukiwania].y2;
				}
			}
			poszukiwania++;
		}
		iterator += 1;
	}
	}
	for (i=0; i < liczba_plemion; i++) {
		if (plemiona[i].used == 0) { suma++; }
	}
	printf("%d\n",suma);
	for (i=0; i < liczba_plemion; i++) {
		if (plemiona[i].used) {continue;}
		printf("%d %d %d %d\n",plemiona[mini[i]].x1,plemiona[mini[i]].x2,plemiona[mini[i]].y1,plemiona[mini[i]].y2);
	}
	return(0);
}