Hide

Problem E
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 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.

\includegraphics[width=.7\textwidth ]{fpfenc4.png}
Figure 1: Sample Input 1. (a) Correct solution. (b) Incorrect solution.

Input

Input starts with a single integer $n$ ($6 \leq n \leq 500$), indicating the number of corners of the estate. Following this are $n$ pairs of integers $x_i$ $y_i$ ($|x_i|,|y_i|\leq 3\, 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 $bx_1$ $by_1$ ($|bx_1|,|by_1|\leq 3\, 000$), indicating the location of the first brother, and the second contains $bx_2$ $by_2$ ($|bx_2|,|by_2|\leq 3\, 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

Output the minimum length of fencing in kilometers needed to satisfy all the constraints specified above. Answers within an absolute error of $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.

Sample Input 1 Sample Output 1
6
0 -50
-40 10
0 50
80 50
120 0
80 -50
-10 0
100 0
354.553591
Sample Input 2 Sample Output 2
6
0 -50
-30 0
0 50
90 50
120 0
90 -50
0 5
90 -5
IMPOSSIBLE
Sample Input 3 Sample Output 3
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

Please log in to submit a solution to this problem

Log in