QOJ.ac

QOJ

実行時間制限: 4 s メモリ制限: 2048 MB 満点: 100

#9758. 篱笆造就好邻居

統計

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

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.