← 返回题目列表

AtCoder · agc051_c

C. 脚蹼

中文机器翻译题面 查看原题

分数: 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). # 是黑色, . 是白色的。

.##.
#.##
.###
.#..

->

#...
.#.#
.###
.#..

->

#...
..#.
....
.#..