P13721 [GCPC 2024] Fair Fruitcake Fragmenting

Frida 的生日快到了，作为她最好的朋友，你当然为她烤了一个蛋糕。 你知道 Frida 喜欢旋转对称，所以你打算烤一个从上方看起来在旋转 $180^\circ$ 后依然相同的蛋糕。 当然，你本可以简单地烤一个普通的圆形蛋糕，但没有一个完美的圆形蛋糕模具，这听起来比做起来要容易。 因此，你决定烤一个可以用直线段描述形状的蛋糕。  :::align{center} 图 F.1：样例输入 2 的可视化。像 S 形的蛋糕可以用一刀分成红色和蓝色两部分。 ::: 然而，在你完成蛋糕后，你发现你还想把蛋糕切成两等份，一份给 Frida，一份给你自己。 更准确地说，你想知道是否可以沿着一条无限长的直线将蛋糕精确地分成两部分，每部分的重量相等。 你可以假设蛋糕的密度和高度都是均匀的。

输入包括： - 一行包含一个*偶数*整数 $n$（$4 \leq n \leq 10^5$），表示描述蛋糕形状所需的点的数量。 - 接下来的 $n$ 行，每行包含两个整数 $x$、$y$（$0 \leq x, y \leq 10^6$），表示蛋糕边界上一点的 $x$ 和 $y$ 坐标。 关于蛋糕形状，给出以下额外保证： - 蛋糕具有 $180^\circ$ 旋转对称性。 - 点按逆时针顺序给出。 - 任意三个连续的点不共线。 - 形状是简单多边形（没有线段相交，只有相邻线段在端点处相接）。

输出所需直线上的两个不同点，格式为 $x_1/c_1$ $y_1/d_1$ $x_2/c_2$ $y_2/d_2$，其中 $|x_i|$、$|y_i|$、$|c_i|$ 和 $|d_i|$ 均为整数且不超过 $10^9$，$x_i/c_i$ 表示第 $i$ 个点的第一个坐标，$y_i/d_i$ 表示第二个坐标（$1 \leq i \leq 2$）。如果某个分数的分母为 $1$，你可以只输出分子。分数不需要约分。如果不存在这样的直线，输出“impossible”。 可以证明，如果存在所需的直线，则一定可以用上述格式表示。

由 ChatGPT 4.1 翻译