/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 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
出力
答えを出力せよ。
入力例 1
4 0 0 0 2 2 0 2 2
出力例 1
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 点を得る。
入力例 2
4 0 0 0 3 3 0 3 3
出力例 2
4
はじめの N 点の他に格子点を打てないことが証明できます。
Score : 2000 points
Problem Statement
Initially, N points (x_1, y_1), \ldots, (x_N, y_N) are plotted on a plane. Snuke is allowed to perform the following operation an arbitrary finite number of times:
- Choose two points that are already plotted, and plot the middle point of the two chosen points (if the middle point hasn't been plotted yet). The coordinates of the middle point don't necessarily have to be integers.
After he finish performing operations, his score is the number of plotted points with integer coordinates (including the initial points). Compute the maximum score he can get.
Constraints
- 3 \leq N \leq 100
- 0 \leq x_i, y_i \leq 10^9
- No three points are on the same line.
- All values in the input are integers.
Input
Input is given from Standard Input in the following format:
N x_1 y_1 : x_N y_N
Output
Print the answer.
Sample Input 1
4 0 0 0 2 2 0 2 2
Sample Output 1
9
One possible way to achieve the maximum score is as follows:
- Initially, four points (0, 0), (0, 2), (2, 0), (2, 2) are plotted.
- Plot (0, 1): the middle point of (0, 0) and (0, 2).
- Plot (0, 0.5): the middle point of (0, 0) and (0, 1).
- Plot (1, 0): the middle point of (0, 0) and (2, 0).
- Plot (1, 1): the middle point of (0, 0) and (2, 2).
- Plot (1, 2): the middle point of (0, 2) and (2, 2).
- Plot (2, 1): the middle point of (2, 0) and (2, 2).
- Now we have 10 points: (0, 0), (0, 0.5), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2), (2, 0), (2, 1), (2, 2). 9 of them have integer coordinates, so the score is 9.
Sample Input 2
4 0 0 0 3 3 0 3 3
Sample Output 2
4
We can prove that, besides the initial points, he can't plot any points with integer coordinates.