2022번: 사다리

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


$O(t\lg L)$ // L: 탐색구간 크기

떨어진 거리 d라 할 때 f(d)를 교점의 높이라 하자.
왼쪽 빌딩 교점의 높이: a
오른쪽 빌딩 교점의 높이: b
a=sqrt(x*x-d*d)
b=sqrt(y*y-d*d)
f(d)=a*b/(a+b)
y=f(x)는 감소함수 이므로 파라매트릭 서치를 통해 본 문제를 해결할 수 있다.

#include<cstdio>
#include<algorithm>
using namespace std;
double x, y, c;
int main() {
    while (~scanf("%lf%lf%lf", &x, &y, &c)) {
        double low = 0, up = min(x, y), m;
        for (int i = 0; i < 100; i++) {
            m = (low + up) / 2;
            1 / c < 1 / sqrt(x*x - m*m) + 1 / sqrt(y*y - m*m) ? up = m : low = m;
        }
        printf("%.3lf\n", m);
    }
    return 0;
}