[Round#403 Div.2] B. The Meeting Place Cannot Be Changed

http://codeforces.com/contest/782/problem/B

N명의 사람들이 각각 이동할 수 있는 최대속도가 주어지고, 남/북 방향중 한쪽으로 일정한 속도로 이동할 수 있을 때 최소 몇시간(단위시간)만에 모두 만날 수 있는지를 묻는 문제이다.

속도와 거리의 범위가 1~1e9이므로 만나는 시간을 기준으로 parametric search를 시도한다. 

다시말해 처음엔 k 시간동안 N명의 사람들이 이동할 수 있는 거리범위를 모두 구했을 때 만날 수 있는 장소가 있다면(교집합이 존재한다면) N명의 사람들은 늦어도 k시간 안에는 만날 수 있다는 뜻이므로 최소 시간의 범위는 1~k사이에 있게 된다. 

문제에서 오차범위를 1e-6이하로 줄이라고 했기 때문에 시간의 low, hi범위의 차가 1e-7정도 안쪽으로 들어왔을 떄 search를 종료하고 시간을 출력하면 답을 구할 수 있다.

다른 풀이방법으로는 만나는 위치를 기준으로 ternary search나 binary search를 하는 방법도 있다.