Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

주어진 점을 포함하는 최적의 직사각형을 찾는 C++ 프로그램

개요

이 글에서는 주어진 점을 포함하는 가장 적합한(best fit) 직사각형을 찾는 프로그램을 C++로 구현하는 방법을 살펴보겠습니다.

문제 정의

점의 좌표 (x, y)와 가로세로 비율 l/b가 주어졌을 때, 다음 조건을 모두 만족하는 직사각형의 좌표를 구해야 합니다.

  • 주어진 점 (x, y)를 반드시 포함해야 합니다.
  • 직사각형의 가로와 세로 길이가 주어진 비율 l : b를 따라야 합니다.
  • 조건을 만족하는 직사각형이 여러 개 존재한다면, 직사각형의 중심과 주어진 점 사이의 유클리드 거리가 가장 짧은 것을 선택합니다.

접근 방법

이 문제는 다음 단계를 통해 해결할 수 있습니다.

  1. 비율 약분: 최대공약수(GCD)를 이용해 비율 l/b를 기약분수 형태로 줄여 불필요하게 큰 수 연산을 방지합니다.
  2. 크기 결정: 허용된 2차원 공간 (n, m) 안에 직사각형이 들어가도록 min(n/l, m/b) 값을 계산합니다.
  3. 중심 가정: 우선 (x, y)가 직사각형의 중심이라고 가정하고, 길이와 너비의 절반 값을 각각 빼고 더하며 네 꼭짓점의 좌표를 구합니다.
  4. 범위 보정: 계산된 좌표가 공간 범위를 벗어나면, 직사각형 전체를 평행 이동시켜 (n, m) 영역 안으로 맞춥니다.

C++ 구현 예제

#include <cmath>
#include <iostream>
#include <algorithm>
using namespace std;

// 주어진 비율을 기약분수로 만들기 위한 최대공약수 함수
int greatest_div(int l, int b) {
    if (l == 0)
        return b;
    else
        return greatest_div(b % l, l);
}

// 직사각형의 좌표를 계산하는 함수
void calc_coordinates(int n, int m, int x, int y, int l, int b) {
    int k, div1;
    int x1, y1, x2, y2;
    div1 = greatest_div(l, b);
    l /= div1;
    b /= div1;
    k = min(n / l, m / b);
    // 주어진 점을 중심으로 하는 직사각형의 범위 계산
    x1 = x - (k * l - k * l / 2);
    x2 = x + k * l / 2;
    y1 = y - (k * b - k * b / 2);
    y2 = y + k * b / 2;
    // 좌표가 공간 범위를 벗어나는 경우 보정
    if (x1 < 0){
        x2 -= x1;
        x1 = 0;
    }
    if (x2 > n){
        x1 -= x2 - n;
        x2 = n;
    }
    if (y1 < 0){
        y2 -= y1;
        y1 = 0;
    }
    if (y2 > m) {
        y1 -= y2 - m;
        y2 = m;
    }
    cout << "Coordinates : " << x1 << " " << y1 << " " << x2 << " " << y2 << endl;
}

int main() {
    int n = 50, m = 20, x = 10, y = 6, l = 4, b = 7;
    calc_coordinates(n, m, x, y, l, b);
    return 0;
}

실행 결과

Coordinates : 6 0 14 14

코드 동작 과정 분석

예제 입력(n=50, m=20, 점 (10, 6), 비율 4:7)을 기준으로 코드의 흐름을 단계별로 살펴보겠습니다.

  1. GCD 계산: gcd(4, 7) = 1이므로 비율은 이미 기약분수 상태입니다.
  2. k 값 결정: k = min(50/4, 20/7) = min(12, 2) = 2가 됩니다. 세로 방향이 공간 높이(m=20)에 의해 제한됩니다.
  3. 초기 좌표 계산: 직사각형의 크기는 가로 8(=2×4), 세로 14(=2×7)이며, 초기 좌표는 x1=6, x2=14, y1=-1, y2=13으로 계산됩니다.
  4. 범위 보정: y1이 음수(-1)이므로 직사각형을 위로 1만큼 이동시켜 y1=0, y2=14로 조정합니다.

최종 결과인 (6, 0)부터 (14, 14)까지의 직사각형은 크기가 8×14로 비율 4:7을 정확히 유지하면서 점 (10, 6)을 포함합니다.

시간 복잡도

최대공약수 계산에 유클리드 호제법을 사용하므로 시간 복잡도는 O(log(min(l, b)))이며, 나머지 좌표 계산과 보정 과정은 모두 상수 시간 O(1)에 처리됩니다. 따라서 전체적으로 매우 효율적인 알고리즘입니다.

마무리

이처럼 GCD를 활용한 비율 약분과 범위 보정 기법을 조합하면, 주어진 점을 포함하면서 지정된 비율을 만족하는 최적의 직사각형을 간단하고 빠르게 구할 수 있습니다. 그래픽스 영역 선택, 이미지 크롭 영역 계산 등 다양한 실무 문제에 응용할 수 있는 유용한 알고리즘이니 참고하시기 바랍니다.