인디아나 존스는 도착할 수 있을까?

인디아나 존스가 전쟁으로 폐허가 된 무인 도시에 있다. 모든 집의 지붕은 무너졌고 벽의 일부만 남아 있다. 땅에는 지뢰가 가득해서, 도시를 안전하게 이동하는 유일한 방법은 남아 있는 벽 위를 걷는 것뿐이다. 그의 임무는 도시에 갇힌 사람을 구하는 것이다.

서로 연결되어 있지 않은 두 벽 사이를 이동하기 위해, 인디아나 존스는 나무판자를 가지고 다니면서 두 벽 사이에 걸쳐 놓고 건너가기로 했다. 판자는 두 벽 사이의 가장 가까운 지점에 걸칠 수 있으므로, 한 벽에서 다른 벽으로 건너가려면 판자의 길이가 두 벽 조각 사이의 최소 거리 이상이어야 한다. 인디아나 존스는 판자를 하나만 가지고 다니므로, 그 길이는 이동 경로에서 만나는 가장 큰 틈을 건널 수 있을 만큼 길어야 한다.

그림 1: 인디아나 존스가 사용한 경로가 표시된 도시 지도

인디아나 존스와 갇힌 사람의 처음 위치는 모두 어떤 벽 조각 위에 있다. 또한 모든 벽은 남북(South-North) 방향 또는 동서(West-East) 방향이다.

도시에 남아 있는 벽들의 지도가 주어진다. 인디아나 존스가 갇힌 사람에게 도달하기 위해 가지고 다녀야 하는 나무판자의 최소 길이를 구하여라. 즉, 시작 벽에서 목표 벽까지 벽들을 건너가는 모든 경로 중에서, 그 경로에서 건너야 하는 틈의 최댓값이 가장 작아지는 경로를 찾고, 그때의 최댓값을 출력하면 된다.

입력은 여러 개의 테스트 케이스로 이루어진다.

각 테스트 케이스의 첫 줄에는 도시에 남아 있는 벽 조각의 수 $N$이 주어진다 ($2 \le N \le 1000$). 이어지는 $N$개의 줄에는 각 벽 조각의 정보가 주어진다. 처음 등장하는 벽 조각은 인디아나 존스가 서 있는 벽이고, 두 번째로 등장하는 벽 조각은 갇힌 사람이 서 있는 벽이다.

각 벽 조각은 세 정수 $X$, $Y$, $L$로 표현된다 ($-10000 \le X, Y, L \le 10000$). 점 $(X, Y)$는 남북 방향 벽의 경우 가장 남쪽 끝점, 동서 방향 벽의 경우 가장 서쪽 끝점이다. $L$은 벽의 길이와 방향을 결정한다.

• $L \ge 0$이면 동서 방향 벽이며 길이는 $L$이다. 즉 $(X, Y)$에서 $(X+L, Y)$까지이다.
• $L < 0$이면 남북 방향 벽이며 길이는 $|L|$이다. 즉 $(X, Y)$에서 $(X, Y+|L|)$까지이다.

$N = 0$이면 입력이 끝난다.

각 테스트 케이스마다 인디아나 존스가 가지고 다녀야 하는 나무판자의 길이를 한 줄에 하나씩 출력한다.

길이는 소수점 아래 둘째 자리까지의 실수로 출력하며, 마지막 자리는 반올림한다. 입력에는 반올림 결과가 달라질 만큼 경계에 가까운 값이 주어지지 않는다.