Reconnaissance

• 여러 개의 점들이 직선을 따라 이동할 때, 가장 멀리 떨어진 두 점 사이의 거리 D가 최소가 될 때를 찾는 문제는 삼분탐색의 대표적인 활용 문제 중 하나이다.
• 보통 이런 문제에서는 시간에 따른 D의 함수가 유니모달 함수이기 때문에 삼분탐색을 바로 적용해서 풀 수 있다. 이 문제의 경우도 다음의 이유로 유니모달 함수가 된다.
  • t시간 뒤의 i번째 점의 위치를 x_i(t) 라고 두면, t시간 후, 가장 멀리 떨어진 점 사이의 거리 D(t) = max(x_i(t)) - min(x_i(t))가 된다
  • x_i(t) = x_i(0) + v_i*t 로 주어져 있고, 이는 선형함수이고 볼록함수이자 오목함수이다
  • max(x_i(t)) 는 볼록함수들의 최댓값이므로 역시 볼록함수이고, 같은 원리로 min(x_i(t))는 오목함수이다
  • -min(x_i(t)) 는 볼록함수이다
  • max(x_i(t)) + (-min(x_i(t))) 는 볼록함수들의 합이므로 역시 볼록함수이고, 그러므로 최솟값을 갖는 유니모달 함수이다.
• 이제 삼분탐색을 통해 최솟값을 구하기만 하면 된다.
  • 탐색해야할 최대 범위는, 처음에 가장 멀리 떨어져 있던 두 점이 가장 가까워질 때까지 걸리는 시간이다. 상대속도가 최소 1이상이기 때문에, 모든 점들은 [0, max(X) - min(X)] 시간 안에 가장 가까워진다.
    • 그러므로 시간복잡도는 O(nlogm), n은 점의 갯수, m은 초기 좌표 범위의 최댓값
  • f(t)는 t*10^5 스케일이다. f(t)의 값이 소수 2자리까지 정확하게 되려면, t의 값은 소수 7자리까지 정확해야 한다. eps=1e-8로 주자.

"""Solution code for "BOJ 10247. Reconnaissance".

- Problem link: https://www.acmicpc.net/problem/10247
- Solution link: http://www.teferi.net/ps/problems/boj/10247

Tags: [ternary search]
"""

import sys
from teflib import ternsearch


END_OF_INPUT = '0'


def main():
    while (line := sys.stdin.readline().rstrip()) != END_OF_INPUT:
        n = int(line)
        x_and_v = [
            [int(x) for x in sys.stdin.readline().split()] for _ in range(n)
        ]

        def compute_max_dist(t):
            poses = [(x_i + t * v_i) for x_i, v_i in x_and_v]
            return max(poses) - min(poses)

        min_x, max_x = min(x_and_v)[0], max(x_and_v)[0]
        answer = ternsearch.min_of_unimodal_real_func(
            0, max_x - min_x, compute_max_dist, eps=1e-8
        )

        print(f'{answer:.02f}')


if __name__ == '__main__':
    main()

• Dependency: teflib.ternsearch.min_of_unimodal_real_func