21953_TrackSmoothing

Bob has the task to plan a racing track of a specific length. He thought it is a great idea to just form a convex polygon that has exactly the required length. Then he was told that racing cars cannot drive such sharp corners like in his plan.

He has to ensure some minimal radius for all curves in his track. Bobs loves the shape of his track, so he don't want to change it too much. His plan is to scale the track down around the balance point of the polygon that specifies his track. Then, he wants to draw the new track with a line that has a constant distance to the scaled track. The chosen distance should be minimal distance that fulfills the given minimum radius constraint. He asks you to write a program to calculate the scale factor for a given track and minimum radius so that the resulting track has the same length as the one of his original plan. Bob made some drawings of the first test case:

The input starts with the number of test cases t (0 < t ≤ 100). Every test case starts with a line consisting of two integers: the minimal required radius r and the number of points n of the original track polygon (0 ≤ r ≤ 1000 , 3 ≤ n ≤ 10000). Then n lines follow, where each line specifies 2D-coordinates as two integers x_i and y_i (-10000 ≤ x_i, y_i ≤ 10000). (0, 0) is the lower left corner. These are the coordinates of the original track in counterclockwise direction. You may safely assume that the area of the given polygon is non-empty.

For each test case print out one line. If it is possible to construct a course according to the above description, output the scaling factor, "Not possible" otherwise. The factor must have a relative or absolute error smaller than 10^-5.

2
20 5
10 0
110 0
130 20
0 150
0 10
1 5
0 0
1 0
2 0
2 1
0 1

0.730494
Not possible