AT_agc051_e.[AGC051E] Middle Point

平面上最初有 $N$ 个点 $(x_1, y_1),\ \ldots,\ (x_N, y_N)$。すぬけ君可以进行任意有限次如下操作：

• 选择已经被打上的两个点，打上它们的中点（仅当该点尚未被打上时）。中点不要求是格子点。

操作结束后，所有被打上的格子点（包括最初的 $N$ 个点）的数量即为すぬけ君的得分。请计算能够获得的最高得分。

输入从标准输入中以以下格式给出。

$N$ $x_1$ $y_1$ $x_2$ $y_2$ $\ldots$ $x_N$ $y_N$

请输出答案。

限制条件

• $3 \leq N \leq 100$
• $0 \leq x_i, y_i \leq 10^9$
• 任意三点不共线。
• 输入中的所有值均为整数。

样例解释 1

获得最高得分的一种方法如下：

• 最初，打上了 $4$ 个点 $(0, 0), (0, 2), (2, 0), (2, 2)$。
• 打上 $(0, 0)$ 和 $(0, 2)$ 的中点 $(0, 1)$。
• 打上 $(0, 0)$ 和 $(0, 1)$ 的中点 $(0, 0.5)$。
• 打上 $(0, 0)$ 和 $(2, 0)$ 的中点 $(1, 0)$。
• 打上 $(0, 0)$ 和 $(2, 2)$ 的中点 $(1, 1)$。
• 打上 $(0, 2)$ 和 $(2, 2)$ 的中点 $(1, 2)$。
• 打上 $(2, 0)$ 和 $(2, 2)$ 的中点 $(2, 1)$。
• 这样共打上了 $10$ 个点：$(0, 0), (0, 0.5), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2), (2, 0), (2, 1), (2, 2)$。其中 $9$ 个点是格子点，因此可以获得 $9$ 分。

样例解释 2

可以证明，除了最初的 $N$ 个点外，无法再打上其他格子点。

由 ChatGPT 4.1 翻译