分数: 1300 点
问题陈述
有一个尺寸方形网格 10^9 \times 10^9。 单元格已编号 (1, 1) 通过 (10^9, 10^9)。 细胞 (i, j) 位于 i从顶部开始的第行,以及 j左起第 列。 最初, N 细胞 (x_1, y_1), \ldots, (x_N, y_N) 为黑色,所有其他单元格为白色。
Snuke 可以执行任意次数的以下操作:
- 选择一个整数 x (1 \leq x \leq 10^9 - 1) 和一个整数 y (1 \leq y \leq 10^9 - 2),然后翻转(黑到白,白到黑)以下六个单元格的颜色: (x, y), (x, y+1), (x, y+2), (x+1, y), (x+1, y+1), (x+1, y+2)
计算运算后黑色单元格的最小可能数量。
约束
- 1 \leq N \leq 10^5
- 1 \leq x_i, y_i \leq 10^9
- (x_i, y_i) 成对不同。
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N x_1 \ y_1 : x_N \ y_N
输出
打印答案。
示例输入 1
9 1 2 1 3 2 1 2 3 2 4 3 2 3 3 3 4 4 2
示例输出 1
3
在下图中, j第一个字母 i从顶部开始的第一个字符串代表单元格 (i, j).
# 是黑色, . 是白色的。
.##. #.## .### .#.. -> #... .#.# .### .#.. -> #... ..#. .... .#..