두 번째 부분

우리가 사랑하는 가이드는 첫 번째 부분에서 벌어진 실수 때문에 우승 기회를 날렸다는 것을 깨달았다. 패배하고, 부끄럽고, 먼지투성이가 된 가이드는 복수 계획을 세웠다. 이번에는 홈 어드밴티지가 그의 편이고, 말나르 씨는 아무 희망이 없어 보인다. 바로 경주다! 100미터 달리기나 시시한 마라톤이 아니라, 불의 나라에 있는 두 도시 사이의 장대한 경주다. 유일한 규칙은 규칙이 없다는 것이고, 중요한 것은 출발 도시에서 도착 도시까지 상대보다 먼저 도착하는 것뿐이다.

가이드는 자전거로 경주하기로 했다. 현재 모든 도시 간 자동차 도로가 폐쇄되어 있다는 것을 알고 있기 때문이다. 말나르 씨가 이 사실을 모르고 자신이 신체적으로 더 우월하다고 생각한다는 것을 알기에, 어느 두 도시 사이에서 경주할지 직접 고르게 해 주겠다고 한다.

하지만 가이드는 말나르 씨가 도시 반대편에서 볼일을 볼 때를 대비해 이미 개인 헬리콥터를 빌려 두었다는 사실을 모른다. 물론 말나르 씨는 도전을 받아들였지만, 불쌍한 가이드를 조금 측은히 여겨 가능한 한 가장 작은 차이로 이길 경로를 고르기로 했다.

아제르바이잔의 도시들은 좌표평면 위의 점으로 나타낼 수 있다. 도시 간 자전거 도로는 직사각형 격자 모양이라 가이드는 좌표축에 평행하게만 움직일 수 있다. 반면 말나르 씨는 도시 사이를 두 점을 잇는 선분을 따라 이동한다. 정확히 말해, 출발 도시가 점 (x1, y1)에 있고 도착 도시가 점 (x2, y2)에 있다면 가이드는 거리 dv = |x1 − x2| + |y1 − y2|를 이동하고, 말나르 씨는 거리 dm = √((x1 − x2)2 + (y1 − y2)2)를 이동한다. 말나르 씨는 비 dv/dm이 가장 작아지는 도시 쌍을 고른다. 그 비를 구하시오!

첫째 줄에 자연수 n (2 ≤ n ≤ 300 000)이 주어진다.

다음 n개 줄의 i번째 줄에는 i번째 도시의 좌표를 나타내는 정수 xi, yi (0 ≤ |xi|, |yi| ≤ 109)가 주어진다. 두 도시가 같은 좌표에 있는 경우는 없다.

첫째 줄에 문제에서 요구한 비를 출력한다.

공식 해와의 절대 오차 또는 상대 오차가 10−10 이하이면 정답으로 인정된다.