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
| #include <iostream>
#include <cstring>
#include <list>
using namespace std;
int N, point[1001][4], classes[1001], classCount;
bool check[1000];
list<int> q;
void classify();
void countClass();
int main() {
memset(classes, -1, sizeof(classes));
cin >> N;
for (int i = 0; i < N; i++)
cin >> point[i][0] >> point[i][1] >> point[i][2] >> point[i][3];
classify();
countClass();
for (int i = 0; i < N + 1; i++) {
cout << classes[i] << " ";
}
cout << endl;
if (classes[N] == -1)
cout << classCount;
else
cout << classCount - 1;
}
void classify() {
int nextClass = 0;
for (int i = 0; i < N; i++)
q.push_back(i);
while(!q.empty()) {
int i = q.front();
q.pop_front();
if (classes[i] == -1)
classes[i] = nextClass++;
int x1 = point[i][0], x2 = point[i][2], y1 = point[i][1], y2 = point[i][3];
int iline[4][4] = { {x1, y2, x2, y2}, {x2, y1, x2, y2},{x1, y1, x2, y1},{x1, y1, x1, y2} }; // 위 오 아 왼
for (int j = 0; j < N + 1; j++) {
if (classes[j] != -1)
continue;
bool same = false;
x1 = point[j][0], x2 = point[j][2], y1 = point[j][1], y2 = point[j][3];
int jline[4][4] = { {x1, y2, x2, y2}, {x2, y1, x2, y2},{x1, y1, x2, y1},{x1, y1, x1, y2} };
for (int k = 0; k < 4; k++) {
for (int p = 0; p < 4; p++) {
if (k % 2 == 0 && p % 2 == 0 && iline[k][1] == jline[p][1] && !(iline[k][0] > jline[p][2] || iline[k][2] < jline[p][0]))
same = true;
else if (k % 2 == 1 && p % 2 == 1 && iline[k][0] == jline[p][0] && (!(iline[k][1] > jline[p][3] || iline[k][3] < jline[p][1])))
same = true;
else if (k % 2 == 0 && !(iline[k][0] > jline[p][0] || iline[k][2] < jline[p][0] || iline[k][1] > jline[p][3] || iline[k][1] < jline[p][1]))
same = true;
else if (!(iline[k][0] > jline[p][2] || iline[k][0] < jline[p][0] || iline[k][1] > jline[p][3] || iline[k][3] < jline[p][1]))
same = true;
}
}
if (same) {
classes[j] = classes[i];
q.push_front(j);
}
}
}
}
void countClass() {
for (int i = 0; i < N; i++) {
if (!check[classes[i]]) {
check[classes[i]] = true;
classCount++;
}
}
}
|
