题目描述

平面上最初有 $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$

输出格式

请输出答案。

样例 1

输入

4
0 0
0 2
2 0
2 2

输出

9

样例 2

输入

4
0 0
0 3
3 0
3 3

输出

4

说明/提示

限制条件

• $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 翻译