C++에서 사변형의 최대 면적 구하기

문제 설명

사변형의 네 변 a, b, c, d가 주어졌을 때, 이 변들을 이용해 만들 수 있는 사변형의 최대 면적을 구하는 것이 목표입니다.

알고리즘

이 문제는 고대 인도의 수학자 브라마굽타(Brahmagupta)가 제시한 공식을 활용해 해결할 수 있습니다.

브라마굽타 공식:

면적 = √((s-a)(s-b)(s-c)(s-d))

위 공식에서 s는 준둘레(semi-perimeter)를 의미하며, 다음과 같이 계산됩니다.

s = (a + b + c + d) / 2

왜 이 공식이 최대 면적을 보장할까?

네 변의 길이가 고정되어 있을 때, 모든 꼭짓점이 하나의 원 위에 놓이는 순환 사변형(cyclic quadrilateral)이 만들 수 있는 면적 중 가장 큰 값을 가집니다. 브라마굽타 공식은 바로 이 순환 사변형의 면적을 계산하는 공식이므로, 주어진 변으로 얻을 수 있는 최대 면적을 정확히 구할 수 있습니다.

C++ 구현 예제

이제 실제 코드로 살펴보겠습니다.

#include <bits/stdc++.h>
using namespace std;

double getMaxArea(double a, double b, double c, double d) {
    double s = (a + b + c + d) / 2;          // 준둘레 계산
    double area = (s - a) * (s - b) * (s - c) * (s - d);
    return sqrt(area);                        // 제곱근을 취해 면적 반환
}

int main() {
    double a = 1, b = 2.5, c = 1.8, d = 2;
    cout << "Maximum area = " << getMaxArea(a, b, c, d) << endl;
    return 0;
}

실행 결과

Maximum area = 3.05

정리

사변형의 최대 면적 문제는 브라마굽타 공식 하나로 간단히 해결됩니다. 핵심 단계를 요약하면 다음과 같습니다.

1. 네 변의 합을 2로 나누어 준둘레 s를 구합니다.
2. (s-a), (s-b), (s-c), (s-d) 네 값을 곱합니다.
3. 곱한 값의 제곱근을 계산하면 최대 면적이 됩니다.

시간 복잡도는 O(1)로 상수 시간 안에 결과를 얻을 수 있어 매우 효율적인 알고리즘입니다.