← 返回题目列表

Codeforces · 930/D

D. 代币游戏

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

考虑以下两个玩家的游戏。有一个白色令牌和一些黑色令牌。每个标记都放置在平面上具有整数坐标 x 和 y 的点上。

玩家轮流下棋,白色开始。每回合,玩家将其颜色的所有标记向上、向下、向左或向右移动 1。黑棋者可以独立选择每个棋子的方向。

白色玩家回合后,白色标记不能位于黑色标记所在的点。对标记的位置没有其他限制:黑色标记的位置可以在黑色玩家转动之后重合,并且最初白色标记可以与一些黑点处于同一点。如果在某个时刻白人玩家无法采取行动,他就输了。如果白人玩家走了 10100500 步,他就赢了。

您需要解决以下问题。您将获得所有黑色标记的初始位置。可以保证最初所有这些位置都是不同的。白色标记最初可以位于多少个位置,以便如果两个玩家都发挥最佳,则黑色玩家获胜?

输入

第一行包含一个整数 n (1 ≤ n ≤ 105) — 黑点的数量。

第 (i + 1) 行包含两个整数 xi, yi ( - 105 ≤ xi, yi, ≤ 105) — 第 i 个黑色标记最初所在点的坐标。

保证黑色标记的初始位置不同。

输出

打印白色标记最初可以位于的点数,这样如果两个玩家都发挥最佳,则黑色玩家获胜。

示例

输入 #1

4
-2 -1
0 1
0 -3
2 -1

输出 #1

4

输入 #2

4
-2 0
-1 1
0 -2
1 -1

输出 #2

2

输入 #3

16
2 1
1 2
-1 1
0 1
0 0
1 1
2 -1
2 0
1 0
-1 -1
1 -1
2 2
0 -1
-1 0
0 2
-1 2

输出 #3

4

注意

在第一和第二示例中,黑色令牌的初始位置用黑点示出,白色令牌的可能位置(使得黑色玩家获胜)用白点示出。

第一个例子:

第二个例子:

在第三个示例中,白色标记应位于内部方格 2 × 2 中,以使黑色玩家获胜。