分数: 2000 点
问题陈述
最初, N 点 (x_1, y_1), \ldots, (x_N, y_N) 绘制在平面上。 Snuke 可以执行任意有限次数的以下操作:
- 选择已绘制的两个点,并绘制两个所选点的中间点(如果尚未绘制中间点)。中点的坐标不一定必须是整数。
当他完成操作后,他的分数是具有整数坐标的绘制点的数量(包括初始点)。 计算他可以获得的最高分数。
约束
- 3 \leq N \leq 100
- 0 \leq x_i, y_i \leq 10^9
- 没有三个点在同一条线上。
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N x_1 y_1 : x_N y_N
输出
打印答案。
示例输入 1
4 0 0 0 2 2 0 2 2
示例输出 1
9
获得最高分数的一种可能方法如下:
- 最初,四点 绘制了 (0, 0), (0, 2), (2, 0), (2, 2) 。
- 情节 (0, 1): 的中点 (0, 0) 和 (0, 2).
- 情节 (0, 0.5): 的中点 (0, 0) 和 (0, 1).
- 情节 (1, 0): 的中点 (0, 0) 和 (2, 0).
- 情节 (1, 1): 的中点 (0, 0) 和 (2, 2).
- 情节 (1, 2): 的中点 (0, 2) 和 (2, 2).
- 情节 (2, 1): 的中点 (2, 0) 和 (2, 2).
- 现在我们有 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
我们可以证明,除了初始点之外,他无法绘制任何具有整数坐标的点。