Gletrian 国王拥有一大片地产,他希望将其划分为三角形地块,然后分给那些值得(即富有)的追随者。这片地产是一个凸多边形,其边界已经围好了栅栏,因此现在的唯一成本就是修建新的栅栏来划分土地。所有栅栏都将位于地产现有顶点之间的直线上,且任意两条栅栏不得交叉。出于财政考虑(即为了省钱),他希望使用的栅栏总长度最小。
但这里有一个问题(总会有问题的!)。他有两个儿子,他们已经在地产上有了住所。一个儿子是个可爱的年轻人,另一个则有点迟钝,但问题在于他们相处得并不融洽。正因如此,在他们两人的地块之间直接修建一道栅栏是不可能的——这会导致他们之间不断的争吵,甚至可能引发某种肢体冲突。然而,国王希望他的两个儿子最终能学会欣赏对方,他觉得只需要一位优秀的仲裁者作为他们之间的联络人即可。为了实现这一点,国王希望在兄弟俩的地块之间修建恰好两道栅栏,通过一个中间地块将兄弟俩的土地隔开,他将在该地块安置一名志愿者(即被征召者)作为中间人。在这些约束条件下,国王仍然希望最小化工程成本,这意味着要最小化所用栅栏的总长度。此外,为了避开兄弟俩的住所,任何直接穿过兄弟俩所在位置的潜在栅栏都不得用于三角剖分。
图 E.1 展示了一个示例(对应样例输入 1),其中兄弟俩的位置用两个加号表示。右侧的划分虽然使用的栅栏较少,但不是一个合法的解,因为兄弟俩位置之间的栅栏超过了两道。左侧展示了一个正确的三角剖分。
图 E.1:样例输入 1。(a) 正确解。(b) 错误解。
输入格式
输入的第一行包含一个整数 $n$ ($6 \le n \le 500$),表示地产的顶点数。接下来是 $n$ 对整数 $x_i, y_i$ ($|x_i|, |y_i| \le 3\,000$),按顺时针顺序给出每个顶点的位置。任意两个顶点位置不重合,且由这些顶点连接而成的多边形是凸的。没有三个连续的顶点共线。最后两行各包含一对坐标:第一行包含 $bx_1, by_1$ ($|bx_1|, |by_1| \le 3\,000$),表示第一个兄弟的位置;第二行包含 $bx_2, by_2$ ($|bx_2|, |by_2| \le 3\,000$),表示第二个兄弟的位置。兄弟俩的位置互不相同,且位于多边形内部。所有坐标单位均为千米。
输出格式
输出满足上述所有约束条件所需的最小栅栏长度(单位为千米)。如果答案与裁判答案的绝对误差在 $10^{-3}$ 以内,则视为正确。如果无法满足上述条件,输出 IMPOSSIBLE。
样例
样例输入 1
6 0 -50 -40 10 0 50 80 50 120 0 80 -50 -10 0 100 0
样例输出 1
354.553591
样例输入 2
6 0 -50 -30 0 0 50 90 50 120 0 90 -50 0 5 90 -5
样例输出 2
IMPOSSIBLE
样例输入 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
样例输出 3
1113.370332