C++로 주어진 점들을 모두 포함하는 최소 사각형의 좌표 구하기

이 튜토리얼에서는 주어진 좌표 점들이 모두 내부에 포함되는 사각형의 좌표를 구하는 프로그램을 다룹니다.

여러 개의 좌표 점이 주어졌을 때, 우리가 해야 할 일은 모든 점을 내부에 포함하면서 변이 좌표축(X축, Y축)에 평행한 가장 작은 사각형을 찾는 것입니다.

접근 방법

핵심 아이디어는 매우 간단합니다. 사각형의 변이 좌표축에 평행해야 하므로, 다음 네 가지 값만 구하면 됩니다.

• X 좌표들 중 최솟값(Xmin)
• X 좌표들 중 최댓값(Xmax)
• Y 좌표들 중 최솟값(Ymin)
• Y 좌표들 중 최댓값(Ymax)

이 네 값을 조합하면 사각형의 네 꼭짓점 좌표를 순서대로 얻을 수 있습니다. 즉, 왼쪽 아래 → 왼쪽 위 → 오른쪽 위 → 오른쪽 아래 순으로 출력하면 됩니다.

예제 코드

#include <bits/stdc++.h>
using namespace std;
// 가장 작은 사각형의 좌표 계산
void print_rectangle(int X[], int Y[], int n){
    // 최솟값과 최댓값 찾기
    int Xmax = *max_element(X, X + n);
    int Xmin = *min_element(X, X + n);
    int Ymax = *max_element(Y, Y + n);
    int Ymin = *min_element(Y, Y + n);
    cout << "{" << Xmin << ", " << Ymin << "}" << endl;
    cout << "{" << Xmin << ", " << Ymax << "}" << endl;
    cout << "{" << Xmax << ", " << Ymax << "}" << endl;
    cout << "{" << Xmax << ", " << Ymin << "}" << endl;
}
int main(){
    int X[] = { 4, 3, 6, 1, -1, 12 };
    int Y[] = { 4, 1, 10, 3, 7, -1 };
    int n = sizeof(X) / sizeof(X[0]);
    print_rectangle(X, Y, n);
    return 0;
}

실행 결과

{-1, -1}
{-1, 10}
{12, 10}
{12, -1}

결과 해석

입력된 점들의 X 좌표 범위는 -1부터 12, Y 좌표 범위는 -1부터 10입니다. 따라서 모든 점을 포함하는 가장 작은 축 평행 사각형의 네 꼭짓점은 (-1, -1), (-1, 10), (12, 10), (12, -1)이 됩니다.

C++ STL에서 제공하는 max_element()와 min_element() 함수를 사용하면 배열 전체를 직접 반복하지 않고도 최댓값과 최솟값을 손쉽게 구할 수 있습니다. 이 알고리즘의 시간 복잡도는 O(n)이며, n은 입력 점의 개수입니다.