P17358 [ECNA 2024] Fences Make Good Neighbors

Gletrian 国王拥有一大片庄园，希望把它划分成若干三角形地块，再赏赐给有功——也就是有钱——的追随者。庄园是一个凸多边形，边界已经修有围栏，因此现在的成本只有为划分土地而新建的围栏。每段围栏都沿庄园现有两个顶点之间的直线修建，任意两段围栏不能相交。国王十分注重财政——也就是吝啬——所以希望新建围栏的总长度最小。 但问题总会出现。国王的两个儿子已经在庄园内各有一座住宅。一个是讨人喜欢的小伙子，另一个则有些“钝”，而且二人相处得很不好。因此，让他们的地块只隔一段围栏绝不可行，否则会争吵不断，最坏还可能动手。 不过，国王仍希望两个儿子最终能够学会欣赏彼此，并认为只需一位优秀的调解人充当联络者。为此，他要求两个兄弟的地块之间恰好隔着两段围栏，使二人的土地之间正好有一块地，供某位“自愿”——也就是被征召——的人居住并居中调解。 在这些限制下，国王仍希望项目成本最低，即使用的围栏总长度最小。此外，为避免穿过兄弟的住宅，三角剖分中不能使用任何直接经过兄弟位置的候选围栏。 图 1 展示了对应样例一的情况，两个加号表示兄弟的位置。右侧划分虽然围栏更短，却不是合法方案，因为兄弟位置之间隔着超过两段围栏；左侧则是正确的三角剖分。 :::align{center}  :::

第一行包含一个整数 $n$（$6\le n\le 500$），表示庄园的顶点数量。 接下来给出 $n$ 对整数 $x_i,y_i$（$|x_i|,|y_i|\le 3000$），按顺时针顺序表示各顶点坐标。任意两个顶点位置不同，连接这些顶点形成的多边形为凸多边形，任意连续三个顶点不共线。 最后两行各包含一对坐标。第一行包含 $bx_1,by_1$（$|bx_1|,|by_1|\le 3000$），表示第一个兄弟的位置；第二行包含 $bx_2,by_2$（$|bx_2|,|by_2|\le 3000$），表示第二个兄弟的位置。两个位置互不相同，且都严格位于多边形内部。所有坐标的单位为千米。

输出满足全部条件所需围栏的最小总长度，单位为千米。若答案与标准答案的绝对误差不超过 $10^{-3}$，则认为正确。如果无法满足条件，输出 `IMPOSSIBLE`。