[BOJ] 2022번: Crossed ladders

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

건물 사이의 거리를 d라고 할 때 

입니다. 이는 두 직선의 접점을 계산함으로서 구해낼 수 있습니다.

문제는, 직관적으로는 f(d)가 감소함수이지만 이를 증명하는 것이 쉽지 않았습니다. 울프람알파로 f'(d)를 계산해보기도 했는데 굉장히 더러웠습니다. 이 부분은 어쩔 수 없이 눈으로 보기에 그러니 아마 감소함수일 것이라고 생각하고 넘어갔습니다.

아무든 f(d)가 감소함수이기만 하다면 0~min(x,y)에서 binary search를 하면 됩니다. 실수의 오차로 인해 st, en 차이가 어느 정도 이하로 떨어지면 값을 출력해야 하는데, 너무 작은 값을 주면 시간초과가 나고 너무 큰 값을 주면 답이 틀릴 수 있습니다.

https://github.com/blisstoner/BOJ/blob/master/2022.cpp