
ZOJ Problem Set  3139
A mountainous region had many forest fires in the dry season of the last year. Prior to the dry season of this year, to watch the forest fire, you are planning to construct a fire tower which enables us to watch all mountain slopes. To minimize the construction cost, you want to minimize the height of the fire tower. A polyhedral terrain can be thought of as the surface of a mountain range with flat faces and with no curves or overhangs. In this problem, we consider only the 2dimensional case, which simplifies the polyhedral terrain into a 2dimensional polygonal chain in the plane. This polygonal chain is represented by n consecutive vertices v_{1}, v_{2}, ..., v_{n} that are given by increasing order of xcoordinate of the vertices and n  1 edges which connect two adjacent vertices v_{i} and v_{i + 1} for 1 <= i <= n  1. Following figure shows the minimum height fire tower of a polygonal chain. Your task is to compute the minimum height of the fire tower on a polygonal chain such that every point on the polygonal chain is visible from the top of the fire tower. Note that the fire tower can be placed on a vertex or an edge of the polygonal chain. You can assume that there are no cases where the minimum height of the fire tower is zero. Input Your program is to read from standard input. The input consists of Ttest cases. The number of test cases T is given in the first line of the input. Each test case starts with a line containing an integer n, the number of input points, 4 <= n <= 1,000. In the next n lines, the coordinates of a polygonal chain's vertices are given in increasing order of xcoordinate. Each line contains two positive integers x and y that represent the coordinates of the vertex, 0 <= x, y<= 100,000. Output Your program is to write to standard output. Print exactly one line for each test case. For each test case, print the minimum height of the fire tower that watches the given polygonal chain with rounded one fractional digit. If the height of the fire tower is greater than 1,000 then print IMPOSSIBLE. Sample Input 3 12 1 8 3 11 5 1 7 4 9 3 10 1 12 7 14 4 16 3 19 2 20 13 22 12 11 11 9 16 215 21 9 26 215 31 9 36 1 41 9 46 215 51 9 56 215 61 9 8 7 8 12 18 17 8 27 23 37 23 47 8 52 18 57 8Sample Output 10.5 IMPOSSIBLE 35.0 Source: Asia Regional Contest Seoul 2006 