P16859 [GKS 2021 #F] Star Trappers
题目描述
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}$ 以内，则认为正确。
说明/提示
在第一个测试用例中，只有两颗白星，因此无法画出任何多边形。
在第二个测试用例中，有三颗白星，因此只能画出一个多边形（一个三角形），如下图所示。结果发现，该三角形能够困住蓝星。该三角形的周长为 $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 完成