[이분탐색] 백준 11662. 민호와강호 (거리계산, 수학, 삼분탐색)

 

문제링크

참고링크

https://goodsosbva.tistory.com/m/37?category=454008
https://m.blog.naver.com/PostView.nhn?blogId=kks227&logNo=221432986308&proxyReferer=https:%2F%2Fwww.google.com%2F
https://velog.io/@chang626/11662-%EB%AF%BC%ED%98%B8%EC%99%80-%EA%B0%95%ED%98%B8

백준 11662번 - 민호와 강호

 

https://velog.io/@bobsiunn/Search-11662%EB%B2%88-%EB%AF%BC%ED%98%B8%EC%99%80-%EA%B0%95%ED%98%B8-24%EC%9D%BC%EC%B0%A8

 

 

도함수랑 3분할 하는 게 핵심인 거 같은데 아직 잘 이해가 안간다.
거리 구하는 공식을 민호랑 강호좌표로 구해야 하는 건 알겠는데, dist에 들어가는 t 기울기에 대한 게 어색하다. ㅍㅅㅍ..

 

전체 거리를 100% 느낌으로 탐색하는 게 새로웠다.

def threeSearch(l,r):
    while abs(r-l) > 1e-9:
        left3 = (2*l + r)/3
        right3 = (l + r*2)/3
        if dist(left3) > dist(right3):
            l = left3
        else:
            r = right3
    return dist(l)

def dist(t):
    mx = ax*t + bx*(1-t)
    my = ay*t + by*(1-t)
    kx = cx*t + dx*(1-t)
    ky = cy*t + dy*(1-t)
    return ((kx-mx)**2 + (ky-my)**2)**0.5
    # route = ((ax-bx)**2+(ay-by)**2)**(1/2)


ax, ay, bx, by, cx, cy, dx, dy = map(int, input().split())
print("%.16f" % threeSearch(0, 1))      # 비율은 1을 기준으로