[BOJ]2022번: 사다리 (c++)

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

2022번: 사다리

 

 

실수 이분탐색

#include <iostream>
#include <cmath>
#include <algorithm>

using namespace std;

// 계산시 오차 범위
const double EPS = 1e-6;
double x, y, c;

bool check(double w)
{
	// 피타고라스 법칙
	double h_L = sqrt(x * x - w * w);
	double h_R = sqrt(y * y - w * w);

	// 닮음비 이용하여 tmp_c 계산
	double tmp_c = (h_L * h_R) / (h_L + h_R);

	// tmp_c가 주어진 c값보다 같거나 크다면 true
	return tmp_c >= c;
}

double binary_search(double left, double right)
{
	// left < right 인 동안 이분탐색으로 두 빌딩의 떨어진 거리 찾기
	while (abs(right - left) > EPS)
	{
		double mid = (left + right) / 2.0;

		if (check(mid))
		{
			left = mid;
		}
		else
		{
			right = mid;
		}
	}
	return left;
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> x >> y >> c;

	// 이분탐색으로 두 빌딩의 떨어진 거리를 찾고, 소수점 3째 자리까지 출력
	printf("%.3lf\n", binary_search(0, min(x, y)));

	return 0;
}

 

 

이분탐색을 실수로 진행하는 문제는 처음 풀어보았다.

입력조건
첫째 줄에 차례대로 x, y, c에 해당하는 양의 실수 세 개가 입력된다. 수는 소수점 여섯째 자리까지 주어질 수 있다.

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

 

실수로 이분탐색을 진행하려면 오차범위를 신경써주어야 한다.

알다시피 실수의 표현 방식과 관련하여 오차가 발생하기 때문이다.

 

친절하게도 문제에서는 계산시 / 출력시 2가지의 오차범위를 알려주었다. 

즉, 계산시에는 1e-6까지의 오차범위가 허용되고

출력시에는 소수점 3째 자리까지 출력하면 된다.

double binary_search(double left, double right)
{
    // left, right 차이가 오차범위 1e-6 이하가 되면 탐색 종료
    while (abs(right - left) > 1e-6)
    {
        ...
    }
}

...

// 소수점 3째 자리까지 출력
printf("%.3lf\n", binary_search(0, min(x, y)));

 

 

오차범위 처리를 참고한 글

부동소숫점 오류