题目描述

平面上有 $N$ 个点 $(x_1,\ y_1),\ \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$ 个点为整点。

样例解释 2

可以证明除了初始点，无法作出其他整点。