Problems
BOJ 23274 Joint Jog Jam

BOJ 23274 Joint Jog Jam

문제 링크:

문제 내용

Kari와 Ola가 각각 2차원 평면 위의 직선 경로 위를 일정한 속도로 달립니다. 두 사람이 같은 시각에 달리기를 시작해서 같은 시각에 달리기를 마쳤다고 할 때, 두 사람 사이의 거리의 최댓값을 구하세요.

입력

Kari의 시작 지점, Ola의 시작 지점, Kari의 도착 지점, Ola의 도착 지점이 한 줄에 순서대로 주어집니다. 각 지점은 xx좌표와 yy좌표의 쌍으로 주어지며, 각각의 값은 0 이상 10410^4 이하의 정수입니다.

출력

문제의 정답을 출력합니다. 정답과 절대 또는 상대 오차가 10−610^{-6} 이하이면 정답으로 인정됩니다.

문제 풀이

스포일러

시간이 지남에 따라 두 사람 사이의 거리가 멀어지다가 가까워지는 것은 불가능합니다. 따라서 양 끝점의 거리 중 큰 것을 출력하면 됩니다.

이를 엄밀히 증명하려면 다음과 같이 할 수 있습니다.

  • 두 사람의 거리의 제곱은 xx좌표 간의 거리의 제곱과 yy좌표 간의 거리의 제곱을 더한 값입니다. xx좌표와 yy좌표의 차이는 모두 선형으로 변화하므로, (a+bt)2+(c+dt)2(a+bt)^2 + (c+dt)^2의 꼴로 쓸 수 있습니다.
  • 이 함수의 이계도함수는 2(b2+d2)2(b^2+d^2)이므로, 주어진 식은 아래로 볼록하거나, b=d=0b = d = 0일 경우 상수함수임을 알 수 있습니다.
  • 따라서 극대는 존재하지 않고, 주어진 범위에서 최대는 양 끝에서의 값 중에서 결정됩니다.
Last updated on
BOJ 23091 Calculate! 3BOJ 23507 Marbles