[BOJ/Gold 5] 백준 9001 Rectangle Coloring(C++)

문제 링크

https://www.acmicpc.net/problem/9001

9001번: Rectangle Coloring

 

문제

You are given n axis-parallel rectangles on a plane. Here, an axis -parallel rectangle is a rectangle whose edges are parallel to either x -axis or y -axis. You are to find the number of colors to paint the given n rectangles according to the following rules:

1. 1. Each rectangle has to be painted with one color.
2. 2. A pair of intersecting rectangles must have the same color. Two rectangles are intersecting if their intersection is not empty when we regard a rectangle as a set of points including the boundary.
3. 3. A rectangle Ra must have the same color as Rb if there is a sequence of rectangles Ra = Ri1, Ri2, …,Rik = Rb such that Rij and Rij+1 are intersecting for all 1≤ j < k ; otherwise, they must have different colors. For instance, rectangle R9 in the following figure must have the same color as R4, R5, R8, and have a different color from R1, R2, R3, R6, R7.

 

입력

The input consists of T test cases. The number of test cases (T) is given in the first line of the input file. Each test case begins with a line containing an integer N , 1≤ N ≤ 200 , that represents the number of rectangles in the test case. Each of the following N lines contains four positive integers x1 , y1 , x2 , and y2, 1 ≤ x1,y1,x2,y2 ≤ 10000 , representing a rectangle. (x1 ,y1) and (x2 , y2) are the (x, y) -coordinates of the lower - left and upper -right corners of the rectangle, respectively. The four integers are delimited by one or more spaces. From the N +3 -th line, the remaining test cases are listed in the same manner as above.

 

출력

The output should contain the number of colors, one per line.

 

예제 입력 1

2
9
3 8 6 12
1 2 4 9
5 6 8 10
11 9 13 11
12 4 14 7
6 2 7 7
3 1 7 3
10 4 12 7
9 6 11 9
4 
11 9 13 11
12 4 14 7
10 4 12 7
9 6 11 9

예제 출력 1

1

 

알고리즘 분류

• 유니온 파인드

 

풀이

두 직사각형이 겹치는지를 확인하는 방법은 다음과 같다.

• (RectA.Left <= RectB.Right) && (RectA.Right >= RectB.Left) && (RectA.Top >= RectB.Bottom) && (RectA.Bottom <= RectB.Top)
• 교차점이 1개 이상 존재하면 겹치는 직사각형으로 판단한다.

 

직사각형은 최대 200개까지 존재할 수 있기 때문에 O(n^2)의 시간복잡도를 가지고 모든 직사각형이 겹치는지를 비교해도 오랜 시간이 걸리지 않는다.

 

코드

#include <iostream>
#include <vector>
#include <string>
#include <set>
#include <algorithm>
#define MAX 201
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
struct RECTANGLE {
    int X1, Y1, X2, Y2;
};

int T, N, X1, Y1, X2, Y2;
vector<RECTANGLE> Rectangles;
int Parent[MAX];
set<int> Answer;

void init() {
    Rectangles.clear();
    for (int i = 0; i < MAX; i++) {
        Parent[i] = i;
    }
    Answer.clear();
}

int find_Parent(int X) {
    if (Parent[X] == X) {
        return X;
    }

    return Parent[X] = find_Parent(Parent[X]);
}

void union_Group(int X, int Y) {
    int ParentX = find_Parent(X);
    int ParentY = find_Parent(Y);
    if (ParentX < ParentY) {
        Parent[ParentY] = ParentX;
    }
    else {
        Parent[ParentX] = ParentY;
    }
}

bool intersect_Rectangles(RECTANGLE A, RECTANGLE B) {
    if ((A.X1 <= B.X2) && (A.X2 >= B.X1) && (A.Y2 >= B.Y1) && (A.Y1 <= B.Y2)) {
        return true;
    }

    return false;
}

void settings() {
    for (int i = 0; i < N; i++) {
        for (int j = (i + 1); j < N; j++) {
            if ((find_Parent(i) != find_Parent(j)) && (intersect_Rectangles(Rectangles[i], Rectangles[j]))) {
                union_Group(i, j);
            }
        }
    }
    for (int i = 0; i < N; i++) {
        Answer.insert(find_Parent(i));
    }
}

void find_Answer() {
    cout << (int)Answer.size() << "\n";
}

void input() {
    cin >> T;
    while (T--) {
        init();
        cin >> N;
        for (int i = 0; i < N; i++) {
            cin >> X1 >> Y1 >> X2 >> Y2;
            Rectangles.push_back({ X1,Y1,X2,Y2 });
        }
        settings();
        find_Answer();
    };
}

int main() {
    FASTIO
    input();

    return 0;
}