문제 7

가장 큰 삼각형 만들기

내 상태: 미제출
난이도: 7번 문제 난이도 보기

Silver I
출제자: pizzaroot
시간 제한: 1000 ms
메모리 제한: 1024 MB

태그 보기

기하학수학애드 혹

정환이는 길이가 각각 $a$, $b$, $c$인 세 개의 막대를 가지고 있고, 각 막대의 길이를 원하는 만큼 줄일 수 있다.

정환이가 이 막대들을 변으로 하는 삼각형을 만들 때, 넓이의 최댓값을 구하라.

입력

첫 번째 줄에 세 정수 $a$, $b$, $c$가 공백으로 구분되어 주어진다. $(1 \le a, b, c \le 10^8)$

출력

첫 번째 줄에 만들 수 있는 가장 큰 삼각형의 넓이를 출력한다. 절대/상대 오차는 $10^{-6}$까지 허용한다.

예제 입력 1

4 3 5

예제 출력 1

공식 해설 풀이 스포일러 보기 접기

가장 긴 막대만 줄이면 된다

막대의 길이를 $a\le b\le c$로 정렬하자. 앞의 두 막대를 줄인 길이를 $x\le a$, $y\le b$라 하면, 두 변 사이의 각 $\theta$에 따른 넓이는
\[ K=\frac{xy\sin\theta}{2}\le\frac{ab}{2} \]
이다. 따라서 어떤 삼각형을 만들더라도 $ab/2$보다 넓을 수 없다.

$c^2\ge a^2+b^2$이면 마지막 막대를 $\sqrt{a^2+b^2}$로 줄여 두 짧은 막대를 직각으로 놓을 수 있다. 이때 넓이는 $ab/2$이므로 최적이다.

직각삼각형이 되기 전에 막대가 끝나는 경우

$c^2<a^2+b^2$이면 세 막대를 그대로 사용한다. 짧은 막대들을 줄여도 더 넓어질 수 없는 이유를 확인하자.

$x$, $y$를 고정했을 때 넓이는 끼인각이 직각이 될 때까지 증가한다. 따라서 세 번째 변의 최적 길이는
\[ z=\min(c,\sqrt{x^2+y^2}) \]
이다. 직각을 만들 수 있으면 최대 넓이는 $xy/2$이므로 $x$, $y$가 커질수록 증가한다.

직각을 만들 수 없어 $z=c$인 범위에서도 마찬가지이다. $X=x^2$, $Y=y^2$, $C=c^2$라 두면 헤론 공식으로
\[ 16K^2=2XY+2YC+2CX-X^2-Y^2-C^2 \]
를 얻는다. $Y$를 고정하고 $X_1<X_2\le C$로 늘릴 때 오른쪽의 증가량은
\[ (X_2-X_1)(2Y+2C-X_1-X_2)>0 \]
이다. $Y$를 늘리는 경우도 같고, 직각이 되는 경계에서는 두 넓이 식이 일치한다. 따라서 $x=a$, $y=b$로 두는 것이 최적이며, 현재 조건에서는 $z=c$이다.

결국 $c^2\ge a^2+b^2$이면 $ab/2$, 아니라면
\[ \frac{\sqrt{(a+b+c)(-a+b+c)(a-b+c)(a+b-c)}}4 \]
를 출력한다. 제곱의 대소관계는 정확히 판정하고, 넓이는 주어진 허용 오차를 만족하는 정밀도로 구한다.

시간복잡도와 추가 공간복잡도는 $O(1)$이다.

구현 · 언어별 풀이

C++ 구현

길이를 long long으로 저장하면 제곱의 비교가 안전하다. 넓이 계산은 곱셈 전부터 long double로 바꾸고 sqrtl을 사용한다. 최종값은 fixed와 충분한 setprecision으로 출력한다. 정수로 네 인수를 먼저 곱한 뒤 변환하면 중간 곱이 넘칠 수 있다.

C 구현

세 변을 정렬하고 제곱 비교는 long long으로 계산한다. 제곱은 최대 $10^{16}$이지만 헤론 공식의 네 인수 곱은 64비트를 넘을 수 있으므로 곱하기 전에 long double로 바꾸고 sqrtl을 사용한다.

정렬된 정수 변 a, b, c에서 넓이는 다음처럼 계산한다. 첫 곱부터 실수 자료형을 사용한다.

long double area;
if (1LL * c * c >= 1LL * a * a + 1LL * b * b) {
    area = (long double)a * b / 2;
} else {
    area = sqrtl((long double)(a + b + c) *
                 (-a + b + c) * (a - b + c) * (a + b - c)) / 4;
}

Python 구현

정수로 제곱을 비교하여 분기를 결정한 뒤 넓이에만 math.sqrt를 쓴다. Python int는 헤론 공식의 곱도 정확하게 계산한다. 넓이는 충분한 소수 자릿수로 출력한다.

정렬된 정수 변 a, b, c에서는 곱을 정수로 계산한 뒤 제곱근을 취해도 된다.

import math

if c * c >= a * a + b * b:
    area = a * b / 2
else:
    area = math.sqrt((a + b + c) * (-a + b + c) *
                     (a - b + c) * (a + b - c)) / 4

Java 구현

세 변의 제곱 비교는 long으로 하고, 헤론 공식에서는 첫 인수부터 double로 바꾼다. long으로 네 인수를 먼저 곱한 뒤 변환하면 이미 오버플로가 난다. Math.sqrt로 넓이를 구한다.

정렬된 정수 변 a, b, c에서 정수 비교와 실수 넓이 계산을 분리한다.

double area;
if (1L * c * c >= 1L * a * a + 1L * b * b) {
    area = (double) a * b / 2;
} else {
    area = Math.sqrt((double) (a + b + c) *
        (-a + b + c) * (a - b + c) * (a + b - c)) / 4;
}

Rust 구현

제곱 비교에는 i64, 넓이 계산에는 f64를 사용한다. 네 인수를 f64로 변환한 뒤 곱하고 sqrt()를 호출한다. 정수 곱을 만든 뒤 변환하지 않는다.

정렬된 i64 변 a, b, c에서 넓이는 다음과 같이 계산한다.

let area = if c * c >= a * a + b * b {
    a as f64 * b as f64 / 2.0
} else {
    let product = (a + b + c) as f64 * (-a + b + c) as f64
        * (a - b + c) as f64 * (a + b - c) as f64;
    product.sqrt() / 4.0
};

JavaScript 구현

세 길이는 Number로 정확히 읽을 수 있지만, 제곱은 $10^{16}$까지 커져 안전 정수 범위를 넘는다. 분기 조건은 정수로 변환한 BigInt의 제곱으로 비교하고 넓이를 계산할 때만 Number와 Math.sqrt를 사용한다.

const [a, b, c] = lengths.sort((x, y) => x - y);
const [x, y, z] = [a, b, c].map(BigInt);
const area = z * z >= x * x + y * y
    ? a * b / 2
    : Math.sqrt((a + b + c) * (-a + b + c) *
                (a - b + c) * (a + b - c)) / 4;
console.log(area.toFixed(10));

lengths는 세 막대 길이를 읽은 배열이다. 헤론 식의 곱을 부동소수로 계산하는 것은 허용 오차가 있는 넓이 계산이고, 삼각형을 고르는 정수 비교와 구분한다. 삼각형 부등식이 성립하지 않는 긴 막대도 첫 분기에서 직각삼각형으로 줄이므로 별도 실패 처리하지 않는다.

제출

언어