[Jungol] 정올 1264 마법색종이

출처: http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=547&sca=99

Approach

- 사각형을 시작점(sx, sy), 끝점(ex, ey), 색(color)로 정의

- 현재 사각형 내부에 또 다른 사각형이 없는 사각형을 '단말 사각형'

   그렇지 않은 경우 '일반 사각형'으로 정의

- 새로운 점이 단말 노드 사각형에 포함되는 경우

  단말 사각형은 두 개의 단말 사각형을 만들면서 사각형의 색이 바뀐다.

  그리고 자신은 일반 사각형이 된다. → 이진 트리 생성 및 탐색

※ 편향 이진 트리가 형성되는 경우 최악의 시간 복잡도를 가질 수 있다.

     높이는 N이므로, 시간복잡도 O(N × N)

 

 

또한 완성된 트리에서 단말 노드 중 사각형 면적의 최대값 최소값을 구할 수 있습니다.

 

시뮬레이션

- 초기 색종이는 흰색

- 흰색일 때 가로로 나뉘고, 검은색 일때 세로로 나뉜다.

 

결과

 

 

(2, 3) 기준으로 slice

 

 

 

(6, 2) 기준으로 slice

 

---

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
 
const int LM = 60050;
int W, H, N, ansMax, ansMin = (int)21e8;
struct Node {
    int sr, sc, er, ec, color;
    Node *left, *right;
    Node*alloc(int a, int b, int c, int d, int cl = 0) {
        sr = a; sc = b;
        er = c; ec = d;
        color = cl;
        left = right = NULL;
        return this;
    }
    bool isIn(int r, int c) {
        return sr < r && sc < c && r < er && c < ec;
    }
    void slice(int r, int c);
    void getAns() {
        if (left == NULL) { // 자식 노드가 없는 경우(=단말 노드인 경우)
            int area = (er - sr) * (ec - sc);
            if (ansMax < area) ansMax = area;
            if (ansMin > area) ansMin = area;
            return;
        }
        left->getAns();
        right->getAns();
    }
}buf[LM];
int bcnt;
void Node::slice(int r, int c) {
    if (left == NULL) {
        if (color == 0) {
            left = buf[bcnt++].alloc(sr, sc, er, c, 1);
            right = buf[bcnt++].alloc(sr, c, er, ec, 1);
        }
        else {
            left = buf[bcnt++].alloc(sr, sc, r, ec);
            right = buf[bcnt++].alloc(r, sc, er, ec);
        }
        return;
    }
    if (left->isIn(r, c)) left->slice(r, c);
    else right->slice(r, c);
}
 
struct Tree {
    Node* root;
    void init(int sr, int sc, int er, int ec) {
        root = buf[bcnt++].alloc(sr, sc, er, ec);
    }
    void push(int r, int c) {
        root->slice(r, c);
    }
    void getAns() {
        root->getAns();
    }
};
 
int main() {
    scanf("%d %d %d", &W, &H, &N);
    int r, c;
    Tree*tree = new Tree();
    tree->init(0, 0, W, H);
 
    for (int i = 0; i < N; ++i) {
        scanf("%d %d", &r, &c);
        tree->push(r, c);
    }
    tree->getAns();
    printf("%d %d", ansMax, ansMin);
}