백준 2022번:사다리

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

2022번: 사다리

 

 이 문제는 수학풀이를 썻는데 그림처럼 변수를 지정하고 식을 적으면 

h1=sqrt(x*x-d*d)

h2=sqrt(y*y-d*d)

h2/d=c/d1;

h1/d=c/d2;

d=d1+d2

1/h1+1/h2=1/c

c=h1*h2/(h1+h2)

라는 식이 나오고 d를 기준으로  c와 h를 비교하며 이분탐색을 진행하면 된다.

이 때 내가 여태껏 했던 이분탐색은 다 left=mid+1 ,right=mid-1 이어서 실수는 어떻게 해야 할까 고민이 많았는데

간단하게 그냥 left=mid,right=mid로 오차범위 까지 엄청 많이 돌리면 된다.

그게 가능한 이유는 시간복잡도log의 힘이다 

코드를 보자

#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
int main(){
    double x,y,c;
    scanf("%lf %lf %lf",&x,&y,&c);
    double left=0;
    double right=min(x,y);
    while (abs(right-left)>1e-6)
    {
        double mid=(left+right)/2.0;
        double d=mid;                       //건물 사이 거리
        double h1=sqrt(x*x-d*d);           //x사다리의 높이
        double h2=sqrt(y*y-d*d);          //y사다리 높이
        double h=(h1*h2)/(h1+h2);          //구해야하는 높이
        if(h>c){
            left=mid;
        }
        else{
            right=mid;
        }
    }
    printf("%.3lf",left);
    return 0;
    
}