[Python] BOJ 2022 사다리

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

 

[English Translation available through pressing 한국어 button and checking English]

 

해당 문제는 Binary Search를 이용하여 오차 범위 이내에서 두 빌딩 사이의 거리를 구하는 문제이다.

먼저, 해당 문제를 diagram으로 나타내보겠다.

문제 정의

x,y,c의 값은 문제와 같게 고정된 값으로 정해진다.

x_h란 x를 빗변으로 갖는 삼각형의 높이, y_h는 y를 빗변으로 갖는 삼각형의 높이로 정의하였다.

mid는 두 삼각형의 공통 밑변으로 정의하였다.

mid의 값이 커지면 빗변의 길이가 고정되어 있기 때문에, x_h와 y_h의 값이 작아진다.

mid의 값이 작아지면, x_h와 y_h의 값이 커질 것이다.

따라서, 우리는 삼각형의 높이들와 c의 비율관계를 이용하여 계산을 진행해볼 것이다.

해당 그림을 보면, x_h와 c의 비율, y_h와 c의 비율을 이용하여 mid의 두 길이를 나타낼 수 있다.

각각 x_h, y_h를 높이로 갖는 삼각형과 c를 높이로 갖는 삼각형의 닮음 관계를 가지고 있기 때문이다.

따라서 높이가 c일때 교점을 갖기 위해서는, c/x_h 와 c/y_h를 더했을 때 1이 나오면 된다.

 

만약 값이 c/x_h와 c/y_h의 합이 1보다 크다면, x_h와 y_h의 값이 너무 작게 정의된 것이기 때문에, mid의 값을 키우는 식으로 유도한다. 이와 반대로 x_h와 y_h의 합이 1보다 작다면, x_h와 y_h의 값이 너무 큰 것이므로, mid의 값을 줄인다.

 

x,y,c=map(float,input().split())
left=0
right=(min(x,y)**2-c**2)**0.5
while left<=right:
    mid=(left+right)/2
    xheight=(x**2-mid**2)**0.5
    yheight=(y**2-mid**2)**0.5
    val=c/xheight+c/yheight
    if 0.999<val<1.001:
        print(mid)
        break
    if val>1:
        right=mid
    else:
        left=mid

그러나 이 문제는 스페셜 저지로, 10^-3의 오차를 허용한다. 그러므로 우리가 구한 공식을 통해서 구한 mid의 값이 10^-3의  범위 내에 들어오면 정답으로 설정하고 break한다.