[백준] 2022 - 사다리

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

2022번: 사다리

 

기하학이 가미된 이분 탐색 문제였다.

그림이 좀 이상하지만, x와 y가 만나는 교점과 mid의 양 끝점을 세 점으로 하는 삼각형의 넓이를 살펴보자.

우리는 mid값을 구하기 위해 파라매트릭 서치로 이분 탐색을 사용할 것이고, 매 반복마다 mid 값으로 A, B값을 구할 수 있을 것이다(via 피타고라스 정리).

 

한 편 빨간색 삼각형의 넓이 S = c * mid / 2 이다.

이 삼각형의 넓이를 A, B, c로도 구할 수 있다.

바로 빨간색 삼각형의 오른쪽 부분과, A * mid / 2를 넓이로 하는 삼각형의 넓이의 비는

c * c : A * A이기 때문이다. 똑같이 오른쪽 삼각형도 적용해 주면,

빨간색 삼각형의 넓이 c * mid / 2 = (mid * B / 2) * (c * c) / (B * B) + (mid * A / 2) * (c * c) / (A * A)

각 항을 정리해 주면, 1 = (c / A) + (c / B)라는 식이 도출된다.

mid가 작아지면 A, B가 커지고, mid가 커지면 A, B가 작아지므로 mid 값 하나로 이분탐색을 수행해 답을 구할 수 있다.

 

#include <iostream>
#include <cmath>
using namespace std;

double x, y, c;

int main()
{
	cin >> x >> y >> c;
	double ans = 0;
	double left = 0, right = min(x, y);
	for (int i = 0; i < 10000; i++)
	{
		double mid = (left + right) / 2;
		double yy = sqrt(y * y - mid * mid);
		double xx = sqrt(x * x - mid * mid);
		if (c / yy + c / xx >= 1)
		{
			ans = mid;
			right = mid - 0.0000000001;
		}
		else
		{
			left = mid + 0.0000000001;
		}
	}
	printf("%0.3lf", ans);
}