[백준] 2022 사다리

April 07, 2021 ( last updated : April 07, 2021 )
수학 이분 탐색 기하학 선형대수학 피타고라스 정리 알고리즘

https://github.com/sneakstarberry/

Abstract

[백준] 2022번 사다리

[백준] 2022번 사다리

백준 2022번

알고리즘 유형

문제 이해

x, y 그리고 이 둘이 교차하는 높이 c 이 세개의 값을 통해서 건물 사이의 길이(w)를 구한다.

풀이방법

x, y 직각 삼각형의 대각선으로 피타고라스의 정리를 통해서 나머지 높이와 밑변의 길이를 추측할 수 있습니다.
그리고 나머지는 c로 인해서 x,y의 직각삼각형 내부에 작은 삼각형이 나오는데 해당 삼각형의 높이과 밑변의 비는 각각 x와 y 삼각형의 높이와 밑변의 비와 대응 됩니다.
이를 통해서 우리가 구해야하는 답 건물 사이의 길이(w)를 구할 수 있게 됩니다.

h1^2 = x^2 + w^2 h2^2 = y^2 + w^2 c = (h1 * h2) / (h1 + h2)

위의 식을 통해 우리는 w를 추측하고 실제 가지고 있는 값인 c 와 비교함으로서 값을 구할 수 있다. 이때 이분탐색 알고리즘을 이용합니다. 일반적으로 왼쪽 값을 +1 그리고 오른쪽 값을 -1 해주는데 해당 값은 정수가 아닌 실수 값이므로 0.00001씩 변화를 주어가며 w 값을 구해줍니다.

#include <cmath>
#include <iostream>

using namespace std;

double X, Y, C;

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin.precision(7);
  cin >> X >> Y >> C;
  double answer;
  double h, l, m;
  h = min(X,Y);
  l = 0;
  m = (h + l) / 2;
  while (l + 0.00001 < h) {
    m = (h + l) / 2;

    double high1 = pow(X, 2) - pow(m, 2);
    double high2 = pow(Y, 2) - pow(m, 2);

    double assume_c = (sqrt(high1) * sqrt(high2)) / (sqrt(high1) + sqrt(high2));

    if (assume_c <= C) {
      answer = m;
      h = m;
    } else {
      l = m;
    }
  }
  cout << fixed;
  cout.precision(3);
  cout << answer;
}

Originally published April 07, 2021
Latest update April 07, 2021

Related posts :

{# #}