산불 감시탑

어느 산악 지역에서 지난해 건기에 산불이 여러 번 발생했다. 올해 건기가 시작되기 전에, 산맥의 모든 비탈을 감시할 수 있는 산불 감시탑 하나를 세우려고 한다. 건설 비용을 최대한 줄이기 위해, 감시탑의 높이를 가능한 한 낮게 만들고 싶다.

다면체 지형(polyhedral terrain)은 평평한 면들로만 이루어지고 곡면이나 처마처럼 튀어나온 부분이 없는 산맥의 표면이라고 생각할 수 있다. 이 문제에서는 2차원 경우만 다루며, 이때 지형은 평면 위의 다각형 사슬(polygonal chain) 하나로 단순화된다. 이 사슬은 $x$좌표가 증가하는 순서로 주어진 $n$개의 꼭짓점 $v_1, v_2, \dots, v_n$과, 인접한 두 꼭짓점 $v_i$와 $v_{i+1}$ ($1 \le i \le n-1$)을 잇는 $n-1$개의 변으로 이루어진다.

아래 그림은 어떤 다각형 사슬에 대해 높이가 가장 낮은 산불 감시탑을 보여 준다.

감시탑은 지형 위에 수직으로 세우며, 그 밑면은 사슬의 어떤 꼭짓점 위에도, 어떤 변 위에도 놓을 수 있다. 탑 꼭대기에서 사슬 위의 모든 점을 볼 수 있도록 하면서, 탑의 높이를 가장 작게 하는 값을 구하여라. 지형의 한 점 $q$가 탑 꼭대기 $p$에서 보인다는 것은 선분 $pq$가 지형 아래로 내려가지 않는다는 뜻이다. 감시탑의 최소 높이가 $0$인 경우는 없다고 가정해도 된다.

입력은 표준 입력으로 주어진다. 첫째 줄에 테스트 케이스의 수 $T$가 주어진다. 각 테스트 케이스의 첫째 줄에는 꼭짓점의 개수 $n$이 주어지며, $4 \le n \le 1000$이다. 이어지는 $n$개의 줄에는 각 꼭짓점의 좌표를 나타내는 두 정수 $x$와 $y$가 주어지며, $0 \le x, y \le 100000$이다. 꼭짓점은 $x$좌표가 서로 다르며 증가하는 순서로 주어진다.

각 테스트 케이스마다 한 줄에, 주어진 다각형 사슬 전체를 감시할 수 있는 산불 감시탑의 최소 높이를 소수점 아래 한 자리까지 반올림하여 출력한다. 이 최소 높이가 $1000$보다 크면 대신 IMPOSSIBLE을 출력한다.