백준 2022 - 사다리

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

사전 지식

본인은 이 문제를 삼분 탐색으로 풀었다.

 

그 외에도 풀이를 이해하기 위해선 중학교 수준의 기하 지식과 비례식에 대한 이해가 필요하다.

풀이

구하려는 밑변의 길이를 $z = a + b$라고 두자. 그리고 x와 y는 다음과 같이 정리가 가능하다.

하지만 z의 길이를 모르는데 a, b를 구할 수 없다. 우리는 z를 구하는 대신 건물 벽에 접촉한 지점의 높이에 해당하는 옆변의 길이 $w_{x}$, $w_{y}$를 구할 것이다.

이렇게 $w_{x}$와 $w_{y}$를 꺼내면 $w_{x}$와 c, 그리고 $w_{y}$와 c는 각각 $a:a+b = c:w_{y} \; (b:a+b = c:w_{x})$의 비례식으로 표현이 가능함을 발견할 수 있다. 그리고 $w_{x}$, $w_{y}$를 알아내면 피타고라스 정리를 통해 다음과 같은 수식을 전개할 수 있다.

 

$x^{2} = w_{x}^{2} + z^{2}$

$y^{2} = w_{y}^{2} + z^{2}$

$->$

$z^{2} = x^{2} - w^{2}_{x}$

$z^{2} = y^{2} - w^{2}_{y}$

$-> z = \sqrt{x^{2} - w^{2}_{x}} = \sqrt{y^{2} - w^{2}_{y}}$

$-> \sqrt{x^{2} - w^{2}_{x}} = \sqrt{y^{2} - w^{2}_{y}}$

$-> (\sqrt{x^{2} - w^{2}_{x}}) - (\sqrt{y^{2} - w^{2}_{y}}) = 0$

 

그러면 이 문제는 $w_{x}$와 $w_{y}$를 구하는 문제로 바뀐다. 그러면 $w_{x}$와 $w_{y}$를 어떻게 구할 수 있을까? 이를 구하기 위해 우리는 위에 언급한 비례식에서 비율을 "임의로" 부여할 것이다. 임의로 비율을 부여하면 다음 관찰을 할 수 있다. 다음 설명은 c와 $w_{y}$의 비율을 기준으로 한다.

c의 비율이 a일때 a보다 큰 비율을 부여하는 경우

a보다 과대평가된 상황이다. 과대평가한 비율로 계산한 $w_{y}$를 $w_{y}'$이라고 하고 $w_{y}$와 크기 관계를 따져보면 $w_{y}' < w_{y}$, 즉 원래 값보다 작게 측정된다. 반대로 $w_{x}$를 기준으로 보면 비율이 과소평가되므로 $w_{x}' > w_{x}$가 된다.

 

따라서 $(x^{2} - w^{2}_{x}) - (y^{2} - w^{2}_{y}) > 0$이다.

c의 비율이 a일때 a보다 작은 비율을 부여하는 경우

위의 경우의 완전히 반대다. $w_{y}' > w_{y}$이고 $w_{x}' < w_{x}$이므로 $(x^{2} - w^{2}_{x}) - (y^{2} - w^{2}_{y}) < 0$이다.

 

두 경우를 잘 생각하면 이 문제는 $(x^{2} - w^{2}_{x}) - (y^{2} - w^{2}_{y}) = 0$를 만족하는 비율 ratio를 구하는 문제가 된다.

 

함수 $f_{ratio} = (x^{2} - w^{2}_{x}) - (y^{2} - w^{2}_{y})$를 정의하고 개형을 보도록 하자.

정확하지 않은 개형이므로 참고에 유의한다.

여기서 0이 되는 지점을 어떻게 찾아야 할까? 함수를 $f_{ratio} = |(x^{2} - w^{2}_{x}) - (y^{2} - w^{2}_{y})|$로 재정의하고 개형을 보도록 하자.

 

정확하지 않은 개형이므로 참고에 유의한다.

그러면 극값이 0인 함수가 나오고 이런 유니모달 함수는 삼분 탐색으로 log 시간 복잡도에 극값을 찾을 수 있음이 알려져 있다.

 

따라서 우리는 삼분 탐색을 통해 $f_{ratio} = 0$이 되는 ratio를 찾으면 된다. 0과 1 사이의 범위에서 함숫값이 0이 되도록 하는 ratio를 찾아 위에서 전개한 수식으로 z를 구하도록 하자.

유의 사항

삼분 탐색 과정에서 $x^{2} - w^{2}_{x}$와 $y^{2} - w^{2}_{y}$가 음수가 되는 경우가 있는데 sqrt() 함수에 음수를 넣으면 허수가 되어 값이 제대로 계산되지 않으니 0보다 작으면 0으로 바꿔줘야 한다.

전체 코드

#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2,fma")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
 
#include "bits/stdc++.h"
#include "ext/rope"
 
using namespace std;
using namespace __gnu_cxx;
 
using pii = pair<int, int>;
using ll = long long;
 
double x, y, c;
 
double func(double ratio)
{
  double ywall = c / ratio;
  double xwall = c / (1 - ratio);
  double y_pred = sqrt(max(0., y * y - ywall * ywall));
  double x_pred = sqrt(max(0., x * x - xwall * xwall));
  return abs(y_pred - x_pred);
}
 
double guess(double ratio)
{
  double ywall = c / ratio;
  return sqrt(y * y - ywall * ywall);
}
 
void solve()
{
  cout.precision(10);
  cout << fixed;
 
  cin >> x >> y >> c;
 
  double l = 0., r = 1;
 
  for (int _ = 0; _ < 100; _++)
  {
    double diff = r - l;
    double p1 = l + diff / 3;
    double p2 = l + diff / 3 * 2;
 
    if (func(p1) > func(p2))
    {
      l = p1;
    }
    else
    {
      r = p2;
    }
  }
 
  cout << guess((l + r) / 2);
}
 
int main()
{
#ifdef LOCAL
  freopen("input.txt", "r", stdin);
#endif
 
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
 
  solve();
}

제출 기록