题目描述

John 和 Ada 坐在一个小山丘的草地上。此刻是午夜，天空中满是星星。从遥远的地方看，天空就像一个二维平面，星星就像是平面上的点。Ada 非常喜欢蓝色的星星，她突然注意到一颗蓝色的星星，而天空中其余所有的星星都是白色的。她非常喜欢这颗蓝色的星星，以至于想要将它困住。于是她向 John 求助。

Ada 会告诉 John 蓝色星星的位置，而 John 必须将它困住。要困住它，John 需要用他的巨剑在天空中画出一个多边形，使得蓝色星星严格位于多边形内部（不在多边形边界上），并且该多边形的周长尽可能小。多边形的顶点必须是白色的星星。

尽管 John 非常厉害，他还是需要你的帮助。给定白星和蓝星的位置，你需要判断 John 能否困住蓝星，如果能，则找出他所用多边形的最小周长。

输入格式

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。

对于每个测试用例，第一行包含一个整数 $N$，表示天空中白星的数量。

接下来的 $N$ 行，每行包含两个整数 $X_i$ 和 $Y_i$。第 $i$ 对整数表示第 $i$ 颗白星的 $x$ 和 $y$ 坐标。

在这 $N$ 行之后，还有一行，包含两个整数 $X_s$ 和 $Y_s$，表示蓝星的 $x$ 和 $y$ 坐标。

输出格式

对于每个测试用例，输出一行，格式为 Case #x: y，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是困住蓝星所用多边形的最小周长。如果 John 无法画出困住蓝星的多边形，则 $y$ 应为 IMPOSSIBLE。

如果 $y$ 与正确答案的绝对误差或相对误差在 $10^{-6}$ 以内，则认为正确。

2
2
0 0
5 0
2 2
3
0 0
5 0
0 5
1 1

Case #1: IMPOSSIBLE
Case #2: 17.071068

提示

在第一个测试用例中，只有两颗白星，因此无法画出任何多边形。

在第二个测试用例中，有三颗白星，因此只能画出一个多边形（一个三角形），如下图所示。结果发现，该三角形能够困住蓝星。该三角形的周长为 $5 + 5 + 5\sqrt{2} \approx 17.071068$。

:::align{center} :::

限制条件

内存限制：$1$ GB。

$1 \le T \le 100$。

对于所有 $i$，$0 \le X_i, Y_i \le 10^6$。

$0 \le X_s, Y_s \le 10^6$。

没有两颗星星（包括蓝星）位置相同。

测试集 1

$1 \le N \le 10$。

测试集 2

$1 \le N \le 45$。

测试集 3

最多 $10$ 个测试用例满足：

$1 \le N \le 300$。

其余测试用例满足：

$1 \le N \le 60$。

翻译由 DeepSeek V4 Pro 完成