English · Original
Chinese · Translation
Formal · Original
Consider the following game for two players. There is one white token and some number of black tokens. Each token is placed on a plane in a point with integer coordinates _x_ and _y_.
The players take turn making moves, white starts. On each turn, a player moves **all** tokens of their color by 1 to up, down, left or right. Black player can choose directions for each token independently.
After a turn of the white player the white token can not be in a point where a black token is located. There are no other constraints on locations of the tokens: positions of black tokens can coincide, after a turn of the black player and initially the white token can be in the same point with some black point. If at some moment the white player can't make a move, he loses. If the white player makes 10100500 moves, he wins.
You are to solve the following problem. You are given initial positions of all black tokens. It is guaranteed that initially all these positions are distinct. In how many places can the white token be located initially so that if both players play optimally, the black player wins?
## Input
The first line contains a single integer _n_ (1 ≤ _n_ ≤ 105) — the number of black points.
The (_i_ + 1)-th line contains two integers _x__i_, _y__i_ ( - 105 ≤ _x__i_, _y__i_, ≤ 105) — the coordinates of the point where the _i_\-th black token is initially located.
It is guaranteed that initial positions of black tokens are distinct.
## Output
Print the number of points where the white token can be located initially, such that if both players play optimally, the black player wins.
[samples]
## Note
In the first and second examples initial positions of black tokens are shown with black points, possible positions of the white token (such that the black player wins) are shown with white points.
The first example: 
The second example: 
In the third example the white tokens should be located in the inner square 2 × 2, to make the black player win. 
考虑一个双人游戏。游戏中有一个白子和若干个黑子。每个棋子都位于一个整数坐标点 $(x, y)$ 上。
两名玩家轮流行动，白方先手。每回合，玩家移动自己颜色的所有棋子，每个棋子可向上、下、左或右移动 $1$ 格。黑方可以为每个黑子独立选择移动方向。
在白方行动后，白子不能位于任何黑子所在的位置。除此之外，对棋子位置无其他限制：黑子的位置可以重合；在黑方行动后或初始时，白子可以与某个黑子位于同一位置。若某时刻白方无法行动，则白方输；若白方成功进行了 $10100500$ 次移动，则白方赢。
你需要解决以下问题：给定所有黑子的初始位置，保证这些位置互不相同。问有多少个初始位置可以放置白子，使得在双方均采取最优策略时，黑方获胜？
第一行包含一个整数 $n$ ($1 ≤ n ≤ 10^5$) —— 黑子的数量。
第 $i+1$ 行包含两个整数 $x_i, y_i$ ($-10^5 ≤ x_i, y_i ≤ 10^5$) —— 第 $i$ 个黑子的初始坐标。
保证所有黑子的初始位置互不相同。
输出满足条件的白子初始位置数量，即在双方均采取最优策略时，黑方获胜的位置数。
在第一和第二个例子中，黑子的初始位置用黑点表示，能使黑方获胜的白子可能位置用白点表示。
第一个例子：
第二个例子：
在第三个例子中，白子必须位于一个 $2 × 2$ 的内部正方形中，才能使黑方获胜。
## Input
第一行包含一个整数 $n$ ($1 ≤ n ≤ 10^5$) —— 黑子的数量。第 $i+1$ 行包含两个整数 $x_i, y_i$ ($-10^5 ≤ x_i, y_i ≤ 10^5$) —— 第 $i$ 个黑子的初始坐标。保证所有黑子的初始位置互不相同。
## Output
输出满足条件的白子初始位置数量，即在双方均采取最优策略时，黑方获胜的位置数。
[samples]
## Note
在第一和第二个例子中，黑子的初始位置用黑点表示，能使黑方获胜的白子可能位置用白点表示。第一个例子： 第二个例子： 在第三个例子中，白子必须位于一个 $2 × 2$ 的内部正方形中，才能使黑方获胜。
**Definitions**
Let $ n \in \mathbb{Z}^+ $ be the number of black tokens.
Let $ B = \{ (x_i, y_i) \in \mathbb{Z}^2 \mid i \in \{1, \dots, n\} \} $ be the set of initial positions of black tokens, with all points distinct.
Let $ W = (x_w, y_w) \in \mathbb{Z}^2 $ be the initial position of the white token.
**Constraints**
1. $ 1 \leq n \leq 10^5 $
2. $ -10^5 \leq x_i, y_i \leq 10^5 $ for all $ i \in \{1, \dots, n\} $
3. All points in $ B $ are distinct.
**Objective**
Determine the number of integer coordinate positions $ W \in \mathbb{Z}^2 $ such that, under optimal play:
- White moves first; on each turn, white moves *all* white tokens (one) by 1 unit in one of the four cardinal directions.
- Black moves second; on each turn, black may move *each* black token independently by 1 unit in any of the four cardinal directions.
- After white’s move, the white token must not coincide with any black token.
- White loses if it cannot move; white wins if it makes $ 10^{100500} $ moves.
- **Black wins** if and only if white is eventually unable to move.
This occurs if and only if the white token is initially contained within the **axis-aligned bounding box** defined by the extreme black token positions, **strictly inside** the region where every adjacent move leads to a position occupied or soon blockable by black tokens under optimal play.
**Key Insight**:
Black can win iff the white token starts in the **interior** of the minimal axis-aligned rectangle that contains all black tokens — i.e., the region:
$$
\left( \min_{b \in B} x_b + 1,\ \max_{b \in B} x_b - 1 \right) \times \left( \min_{b \in B} y_b + 1,\ \max_{b \in B} y_b - 1 \right)
$$
because only then can black, by mirroring or surrounding, eventually trap white in finite moves.
Thus, the number of winning initial positions for black is:
$$
\max\left(0,\ \left( \max_{b \in B} x_b - \min_{b \in B} x_b - 1 \right)\right) \cdot \max\left(0,\ \left( \max_{b \in B} y_b - \min_{b \in B} y_b - 1 \right)\right)
$$
API Response (JSON)
{
"problem": {
"name": "D. Game with Tokens",
"description": {
"content": "Consider the following game for two players. There is one white token and some number of black tokens. Each token is placed on a plane in a point with integer coordinates _x_ and _y_. The players tak",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF930D"
},
"statements": [
{
"statement_type": "Markdown",
"content": "Consider the following game for two players. There is one white token and some number of black tokens. Each token is placed on a plane in a point with integer coordinates _x_ and _y_.\n\nThe players tak...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "考虑一个双人游戏。游戏中有一个白子和若干个黑子。每个棋子都位于一个整数坐标点 $(x, y)$ 上。\n\n两名玩家轮流行动，白方先手。每回合，玩家移动自己颜色的所有棋子，每个棋子可向上、下、左或右移动 $1$ 格。黑方可以为每个黑子独立选择移动方向。\n\n在白方行动后，白子不能位于任何黑子所在的位置。除此之外，对棋子位置无其他限制：黑子的位置可以重合；在黑方行动后或初始时，白子可以与某个黑子位于同一位...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n \\in \\mathbb{Z}^+ $ be the number of black tokens. \nLet $ B = \\{ (x_i, y_i) \\in \\mathbb{Z}^2 \\mid i \\in \\{1, \\dots, n\\} \\} $ be the set of initial positions of black tokens, ...",
"is_translate": false,
"language": "Formal"
}
]
}