지붕

새 집을 지으려고 한다. 지붕의 최소 건축 비용을 어림잡으려면 먼저 지붕의 높이를 알아야 한다. 가진 정보는 집의 외곽선뿐이므로, 이 외곽선으로부터 지붕의 높이를 계산해야 한다.

정확한 정의는 다음과 같다. 집의 외곽선은 모든 변이 좌표축에 평행한(수평 또는 수직) 직교 다각형이다. 이 다각형을 $P$라 하고, 꼭짓점의 개수를 $n$이라 하자.

직선 골격 $SK(P)$는 $P$가 줄어들 때 꼭짓점들이 남기는 자취다. 이때 각 변은 방향은 그대로 유지한 채 모두 같은 속도로 안쪽을 향해 움직인다. 그림 1의 (a)와 (b)는 각각 $P$가 줄어드는 과정과 그렇게 얻어지는 $SK(P)$를 보여 준다.

그림 1

이제 $P$를 $XY$ 평면 위에 놓고, 단위 속도로 줄이는 동시에 단위 속도로 위쪽($+Z$ 방향)으로 들어 올린다. 그러면 $P$는 삼차원 다면체 곡면을 쓸고 지나가며, 이 곡면을 지형(terrain)이라 부른다. $SK(P)$는 바로 이 지형의 모서리를 $XY$ 평면에 정사영한 것이다. 정의에 의해 이 지형의 각 면은 $XY$ 평면과 이면각 $45^\circ$를 이루는 평면 안에 놓이며, 각 면은 $P$의 변을 적어도 하나 경계로 가진다. 이 지형을 $P$의 지붕이라 하며, 그림 1의 (c)가 그 예다.

지붕 위의 한 점 $q$의 높이는 그 고도, 즉 $q$와 $q$를 $XY$ 평면에 정사영한 점 사이의 거리다. 지붕의 높이는 지붕 위 모든 점의 높이 중 최댓값이다. 주어진 직교 다각형 $P$의 지붕 높이를 구하여라.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다.

각 테스트 케이스의 첫째 줄에는 다각형 $P$의 꼭짓점 개수 $n$이 주어지며, $4 \le n \le 1000$이다. 다음 줄에는 $P$의 꼭짓점 $n$개의 $(x, y)$ 좌표가 반시계 방향 순서로 주어진다. 먼저 첫 번째 꼭짓점의 $x$와 $y$, 그다음 두 번째 꼭짓점의 $x$와 $y$ 순서이며, 이런 식으로 이어진다. 모든 값은 하나의 공백으로 구분되고, 각 좌표는 $1$ 이상 $100000$ 이하의 정수다.

각 테스트 케이스마다 $P$의 지붕 높이를 정확히 한 줄에 출력한다. 소수점 아래 정확히 한 자리까지 출력한다.