Fences Make Good Neighbors

문제

The King of Gletrian has a large estate that he wishes to divide up into triangular parcels which he then plans to give to deserving (that is, wealthy) followers. The estate is a convex polygon and already has fences around its borders, so the only cost now will be putting in new fences to perform the partitioning of the land. All fences will lie on straight lines between existing corners of the estate and no two fences will cross each other. Being fiscally minded (that is, cheap) he wants to put in the minimum amount of fencing possible.

But there is a problem (there always seems to be, doesn’t there!). He has two sons who already have homes on the estate. One is a cute young lad and the other is a bit obtuse, but the problem lies in that they don't really get along with each other. Because of this, placing a single fence between their two parcels of land is out of the question --- there will be constant bickering between them and at worst some type of physical altercation. However, the King has hope that his two sons might eventually learn to appreciate one another and he feels that all is needed is one good arbiter to serve as a liaison between them. To accomplish this the King wants to place exactly two fences between the brother's parcels, separating the brothers' lands by a single parcel where he'll place some voluntary (that is, conscripted) person to serve as go-between. Given these constraints, the King still wants to minimize the cost of the project, which means minimizing the length of fencing used. In addition, to avoid the brothers' houses, no potential fence which passes directly through a brother's location may be used in the triangulation.

An example (corresponding to Sample Input 1) is shown in Figure E.1, where the brother's locations are indicated by the two plus signs. The partitioning to the right, while using less fencing, is not a solution since there are more than two fences between the brothers' locations. A correct triangulation is shown on the left.

Figure E.1: Sample Input 1. (a) Correct solution. (b) Incorrect solution.

입력

Input starts with a single integer $nn$ ($6\le n\le 5006\; \backslash leq\; n\; \backslash leq\; 500$), indicating the number of corners of the estate. Following this are $nn$ pairs of integers $x_{i}x\_i$ $y_{i}y\_i$ ($\mathrm{\mid }{x}_i\mathrm{\mid },\mathrm{\mid }{y}_i\mathrm{\mid }\le 3000|x\_i|,|y\_i|\backslash leq\; 3\backslash ,000$) specifying the location of each corner, given in clockwise order. No two corner locations are the same and the polygon formed by connecting these corners is convex. No three consecutive corner locations are collinear. The last two lines each contain a pair of coordinates: the first of these lines contains $b{x}_{1}bx\_1$ $b{y}_{1}by\_1$ ($\mathrm{\mid }b{x}_1\mathrm{\mid },\mathrm{\mid }b{y}_1\mathrm{\mid }\le 3000|bx\_1|,|by\_1|\backslash leq\; 3\backslash ,000$), indicating the location of the first brother, and the second contains $b{x}_{2}bx\_2$ $b{y}_{2}by\_2$ ($\mathrm{\mid }b{x}_2\mathrm{\mid },\mathrm{\mid }b{y}_2\mathrm{\mid }\le 3000|bx\_2|,|by\_2|\backslash leq\; 3\backslash ,000$), indicating the location of the second brother. The two brother's locations are distinct and lie within the interior of the polygon. All coordinates are in kilometers.

출력

Output the minimum length of fencing in kilometers needed to satisfy all the constraints specified above. Answers within an absolute error of ${10}^{-3}10^\{-3\}$ of the judges' answer will be deemed correct. If it is not possible to satisfy the conditions stated above, output the word IMPOSSIBLE.

6
0 -50
-40 10
0 50
80 50
120 0
80 -50
-10 0
100 0

354.553591

6
0 -50
-30 0
0 50
90 50
120 0
90 -50
0 5
90 -5

IMPOSSIBLE

12
0 100
50 86
86 50
100 0
86 -50
50 -86
0 -100
-50 -86
-86 -50
-100 0
-86 50
-50 85
60 60
-60 -60

1113.370332