题目描述

平面上に、はじめ $N$ 点 $(x_1,\ y_1),\ \ldots,\ (x_N,\ y_N)$ が打たれています。 すぬけ君は、以下の操作を任意の有限回行うことができます。

• すでに打たれている $2$ 点を選び、その中点を打つ (その点がまだ打たれていない場合に限る)。中点が格子点である必要はない。

操作を済ませたら、打たれている格子点の数 (はじめの $N$ 点を含む) がすぬけ君の得点となります。 獲得可能な最高得点を計算してください。

输入格式

入力は標準入力から以下の形式で与えられる。

$N$ $x_1$ $y_1$ $:$ $x_N$ $y_N$

输出格式

答えを出力せよ。

题目大意

题目描述

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

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

4
0 0
0 2
2 0
2 2

9

4
0 0
0 3
3 0
3 3

4

提示

制約

• $3\ \leq\ N\ \leq\ 100$
• $0\ \leq\ x_i,\ y_i\ \leq\ 10^9$
• どの $3$ 点も同一直線上にない。
• 入力中の全ての値は整数である。

Sample Explanation 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$ 点を得る。

Sample Explanation 2

はじめの $N$ 点の他に格子点を打てないことが証明できます。