[백준] 2022번 사다리 Java

문제 링크

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

문제

아래의 그림과 같이 높은 빌딩 사이를 따라 좁은 길이 나있다. 두 개의 사다리가 있는데 길이가 x인 사다리는 오른쪽 빌딩의 아래를 받침대로 하여 왼쪽 빌딩에 기대져 있고 길이가 y인 사다리는 왼쪽 빌딩의 아래를 받침대로 하여 오른쪽 빌딩에 기대져 있다. 그리고 두 사다리는 땅에서부터 정확하게 c인 지점에서 서로 교차한다. 그렇다면 두 빌딩은 얼마나 떨어져 있는 걸까?!

입력

첫째 줄에 차례대로 x, y, c에 해당하는 양의 실수 세 개가 입력된다. 수는 소수점 여섯째 자리까지 주어질 수 있으며, 3,000,000,000보다 작거나 같다.

출력

두 빌딩사이에 너비가 되는 수치를 출력한다. 절대/상대 오차는 10-3까지 허용한다.

알고리즘: 이분 탐색

풀이

? 값은 이분 탐색으로 찾아낼 수 있다.
min_width = 0, max_width은 x,y중 작은 값으로 설정해준다.
여기서 mid_width값으로 왼쪽 삼각형의 밑변, 오른쪽 삼각형의 밑변을 구할 수 있다.
그러면 비례식으로 왼쪽 삼각형의 높이, 왼쪽 삼각형의 오른쪽 변을 구할 수 있고, 높이와 오른쪽 변으로 n_c값을 구할 수 있다.
c보다 n_c가 더 크다면 min_width을 mid_width로 업데이트해 준다.
-> (n_c를 줄이기 위해서 mid_width가 커지는 방향으로 업데이트 x,y선 교차 지점이 내려가기 때문에)
n_c보다 c가 더 크다면 max_width을 mid_width로 업데이트해 준다.
-> (n_c를 늘리기 위해서 mid_width가 작아지는 방향으로 업데이트 x,y선 교차 지점이 올라가기 때문에)

위 방식을 c - 0.001 <= n_c <= c + 0.001 범위에 들어올 때까지 반복해준다.

소스 코드

import java.io.*;
import java.util.*;

public class Main {
    static double x, y, c;
    static double ans;
    public static void main(String args[]) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(br.readLine());
      x = Double.parseDouble(st.nextToken());
      y = Double.parseDouble(st.nextToken());
      c = Double.parseDouble(st.nextToken());
      double min_width = 0;
      double max_width = Math.min(x,y);
      //이분 탐색
      while(true) {
          double mid_width = (min_width + max_width)/2;
          double l = Math.sqrt((Math.pow(x, 2) - Math.pow(mid_width, 2)));
          double r = Math.sqrt((Math.pow(y, 2) - Math.pow(mid_width, 2)));
          double a = (l/r * y)/(1 + l/r); //가운데 삼각형 왼쪽 변
          double h = (l/r * mid_width)/(1 + l/r); //왼쪽 삼각형 높이
          double n_c = Math.sqrt((Math.pow(a, 2) - Math.pow(h, 2)));
          if( ((c-0.001)<= n_c) && ((c+0.001)>=n_c) ) {
              ans = mid_width;
              break;
          } else {
              if(n_c < c) {
                  max_width = mid_width;
              } else if(n_c > c) {
                  min_width = mid_width;
              }
          }
      }
      System.out.println(Math.round(ans*1000)/1000.0); 
    }
}