[Algorithm] C++ 백준 9063번 : Bounding Rectangle Area

문제 요약

N개의 점이 주어질 때, 이 점들을 모두 포함하는 축에 평행한 최소 직사각형의 넓이를 구하라.
N ≤ 1이면 넓이는 0이다.

접근 방법

x좌표의 최솟값/최댓값, y좌표의 최솟값/최댓값을 한 번의 순회로 갱신한다.
넓이 = (max_x - min_x) × (max_y - min_y). 단, N ≤ 1이면 0을 출력.
시간복잡도 O(N), 추가 메모리 O(1).

Python 풀이

 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
# 더 많은 정보는 https://42jerrykim.github.io 에서 확인하세요.
import sys

def main():
    input = sys.stdin.readline
    n_line = input().strip()
    if not n_line:
        print(0)
        return
    n = int(n_line)

    min_x = 10**18
    max_x = -10**18
    min_y = 10**18
    max_y = -10**18

    for _ in range(n):
        parts = input().split()
        if not parts:
            continue
        x, y = map(int, parts)
        if x < min_x:
            min_x = x
        if x > max_x:
            max_x = x
        if y < min_y:
            min_y = y
        if y > max_y:
            max_y = y

    if n <= 1:
        print(0)
    else:
        print((max_x - min_x) * (max_y - min_y))

if __name__ == "__main__":
    main()

C++ 풀이

 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
// 더 많은 정보는 https://42jerrykim.github.io 에서 확인하세요.
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    long long n;
    if (!(cin >> n)) {
        cout << 0 << '\n';
        return 0;
    }

    long long min_x = LLONG_MAX, max_x = LLONG_MIN;
    long long min_y = LLONG_MAX, max_y = LLONG_MIN;

    for (long long i = 0; i < n; ++i) {
        long long x, y;
        cin >> x >> y;
        min_x = min(min_x, x);
        max_x = max(max_x, x);
        min_y = min(min_y, y);
        max_y = max(max_y, y);
    }

    if (n <= 1) {
        cout << 0 << '\n';
    } else {
        cout << (max_x - min_x) * (max_y - min_y) << '\n';
    }
    return 0;
}