백준 2022번 사다리

문제 링크입니다: https://www.acmicpc.net/problem/2022

코드에 앞서 func 함수를 유도하는 수식을 소개하겠습니다.

$$w=w_1+w_2$$

$$h_1/w=c/w_2$$

$$h_2/w=c/w_1$$

$$w=w*c/h_2+w*c/h_1$$

$$1=c/h_2+c/h_1$$

$$1=c(h_1+h_2)/(h_1*h_2)$$

$$c=(h_1*h_2)/(h_1+h_2)$$

그리고 실수 이분탐색의 경우 정수 이분탐색과 달리 엡실론을 더해주고 빼줘야하는데 이게 참 까다롭습니다.

앱실론을 너무 큰 값으로 잡으면 WA가 뜨고 너무 작게 잡으면 TLE가 발생합니다.

따라서, kks227님 이분탐색을 참고하여 기존에 제가 작성하던 이분탐색 코드와는 다르게 접근했습니다.

#include <iostream>

#include <algorithm>

#include <cmath>

using namespace std;

 

double x, y, c;

 

double func(double mid)

{

        double h1 = sqrt(x*x - mid * mid);

        double h2 = sqrt(y*y - mid * mid);

 

        return (h1*h2) / (h1 + h2);

}

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        cin >> x >> y >> c;

 

        double low = 0, high = min(x, y);

        double result = 0;

        while (high - low > 0.000001)

        {

                 double mid = (high + low) / 2.0;

 

                 if (func(mid) >= c)

                 {

                         result = mid;

                         low = mid;

                 }

                 else

                         high = mid;

        }

        printf("%.3lf\n", result);

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~