配点 : $2000$ 点

問題文

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

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

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

制約

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

入力

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

$N$

$x_1$ $y_1$

$:$

$x_N$ $y_N$

出力

答えを出力せよ。

4
0 0
0 2
2 0
2 2

9

最高得点を得る方法の一例は以下の通りです。

• はじめ、$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$ 点を得る。

4
0 0
0 3
3 0
3 3

4

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