🔗 링크

https://www.acmicpc.net/problem/2022

✏️ 문제

주어진 조건 하에서 높이 c를 구하는 문제입니다.

🧠 접근

삼각형의 닮음 관계를 이용하여 해결할 수 있는 문제입니다.

문제의 그림을 도식화하면 아래와 같습니다.

높이를 구하는 지점 C를 기준으로 내린 수선의 발을 F라 하면 두 삼각형에서 닮음 관계를 찾을 수 있습니다.

• 삼각형 ABC와 AFE
• 삼각형 BAD와 BFE

이 때, 닮음 관계를 이용하여 아래 두 식을 도출할 수 있습니다.

$a_1=\frac{c(a_1+a_2)}{h_2}$, $a_2=\frac{c(a_1+a_2)}{h_1}$

선분 AB의 길이를 $a=a_1+a_2$라고 하면

$a=$$\frac{c(a_1+a_2)}{h_2}+\frac{c(a_1+a_2)}{h_1}=\frac{c(h_1+h_2)(a_1+a_2)}{h_1h_2}$

수식을 정리하면 $c(h_1+h_2)=h_1h_2$, 즉 $c=\frac{h_1h_2}{h_1+h_2}$이 됩니다.

마지막으로 피타고라스 정리에 의해 $h_1^2=x^2-a^2, h_2^2=y^2-a^2$이므로 두 값을 이용해 구하는 값 $c$의 오차 범위가 $10^{-3}$ 이내가 되도록 이분 탐색하면 됩니다.

while (right - left >= 0.001) {
	double width = (left + right) / 2;
    double h1 = Math.sqrt(Math.pow(x, 2) - Math.pow(width, 2));
	double h2 = Math.sqrt(Math.pow(y, 2) - Math.pow(width, 2));
    double res = (h1 * h2) / (h1 + h2);
  
    if (res >= c) left = width;
    else right = width;
}

위 과정을 수행한 뒤 오차 범위 안으로 들어온 이분 탐색의 두 피벗 값 중 하나를 출력하면 문제가 해결됩니다.

📄 전체 소스 코드

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String[] input = reader.readLine().split(" ");
        double x = Double.parseDouble(input[0]);
        double y = Double.parseDouble(input[1]);
        double c = Double.parseDouble(input[2]);


        double left = 0, right = Math.min(x, y);

        while (right - left >= 0.001) {
            double width = (left + right) / 2;
            double h1 = Math.sqrt(Math.pow(x, 2) - Math.pow(width, 2));
            double h2 = Math.sqrt(Math.pow(y, 2) - Math.pow(width, 2));
            double res = (h1 * h2) / (h1 + h2);
  
            if (res >= c) left = width;
            else right = width;
        }
        System.out.println(String.format("%.3f", right));
    }
}