[질문] 백준 11662번 민호와 강호 힌트좀 주세욥ㅠ

[Clichy(nabiz12)]

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

점과 점사이의 거리는 구하는 방식은 A~B, C~D 의 거리는 구하는 법을 아직 기억하는데;

 민호와 강호는 출발지(A,C)에서 같이 출발하여  도착지(B,D)에 같이 도착하는데 그 부분을 어떤식으로 해야할지 모르겠고, 공식도 모르겠고,

 점과 점을 잇는 선분에는 많은 점들이 있잖아요. 하나하나 어떻게 점들을 구할지도 모르겠습니다.

 아시는 분있으면 힌트 주시면 정말 감사하겠습니다!

[하루룽(ailedear)]

시간에 대한 볼록함수니까 삼분탐색?

[Clichy(nabiz12)]

모르겠어요.. 일단 삼분탐색에 대해서 알아보겠습니다

[미쿡취준생(nsh3389)]

민호에 대한 강호의 상대 속도를 구하고 민호는 고정된 상태에서 강호만 움직인다고 보면 쉽게 풀릴 것 같은데

[신동원(110.15)]

삼분탐색 하면 쉬울 것 같고 점과 직선 사이 거리 식으로도 풀 수 있겠네요 - dc App

[0xrgb(0xrgb)]

시간에 따른 두 점의 좌표를 식으로 구하고, 거리의 제곱을 구하면 시간에 대한 이차함수가 나옴. 따라서 (1) 이차함수가 최소가 될 때의 답을 구하거나 (2) 삼분탐색을 이용하면 된다는 사실을 알 수 있음

[0xrgb(0xrgb)]

여기서 알고리즘 하나를 더 넣으면 KOI'16 먼 별 같은 문제가 나옴.
https://www.acmicpc.net/problem/13310

[Clichy(nabiz12)]

고수님덜..감사영.. - dc App