题目描述

PUBG is a multiplayer online battle royale video game. In the game, up to one hundred players parachute onto an island and scavenge for weapons and equipment to kill others while avoiding getting killed themselves. Airdrop in this game is a key element, as airdrops often carry with them strong weapons or numerous supplies, helping players to survive.

textit{Airdrop in the game(?)

Consider the battle field of the game to be a two-dimensional plane. An airdrop has just landed at point $(x_0, y_0)$ (both $x_0$ and $y_0$ are integers), and all the $n$ players on the battle field, where $(x_i, y_i)$ (both $x_i$ and $y_i$ are integers) indicates the initial position of the $i$-th player, start moving towards the airdrop with the following pattern:

• If the position of a living player at the beginning of this time unit is not equal to $(x_0, y_0)$, he will begin his next move.
• • Let's say he is currently at point $(x, y)$. For his next move, he will consider four points $(x, y - 1)$, $(x, y + 1)$, $(x - 1, y)$ and $(x + 1, y)$.
• • He will select one of the four points whose Manhattan distance to the airdrop $(x_0, y_0)$ is the smallest to be the destination of his next move. Recall that the Manhattan distance between two points $(x_a, y_a)$ and $(x_b, y_b)$ is defined as $|x_a - x_b| + |y_a - y_b|$.
• • If two or more points whose Manhattan distance to the airdrop is the same, he will use the following priority rule to break the tie: $(x, y - 1)$ has the highest priority to be selected, $(x, y + 1)$ has the second highest priority, $(x - 1, y)$ has the third highest priority, and $(x + 1, y)$ has the lowest priority.
• • At the end of this time unit, he arrives at his destination.
• If the position of a living player at the beginning of this time unit is equal to $(x_0, y_0)$, he will continue to fatten his backpack with the supplies in the airdrop and stays at $(x_0, y_0)$.

But the battle is tough and it's almost impossible for all the players to arrive at the airdrop safely. If two or more players meet at point $(x', y')$ other than $(x_0, y_0)$, where both $x'$ and $y'$ are integers, they will fight and kill each other and none of them survive.

BaoBao is a big fan of the game and is interested in the number of players successfully arriving at the position of the airdrop, but he doesn't know the value of $x_0$. Given the value of $y_0$ and the initial position of each player, please help BaoBao calculate the minimum and maximum possible number of players successfully arriving at the position of the airdrop for all $x_0 \in \mathbb{Z}$, where $\mathbb{Z}$ is the set of all integers (note that $x_0$ can be positive, zero or negative).

输入格式

There are multiple test cases. The first line of the input contains an integer $T$, indicating the number of test cases. For each test case:

The first line contains two integers $n$ and $y_0$ ($1 \le n \le 10^5$, $1 \le y_0 \le 10^5$), indicating the number of players and the $y$ value of the airdrop.

For the following $n$ lines, the $i$-th line contains two integers $x_i$ and $y_i$ ($1 \le x_i, y_i \le 10^5$), indicating the initial position of the $i$-th player.

It's guaranteed that the sum of $n$ in all test cases will not exceed $10^6$, and in each test case no two players share the same initial position.

输出格式

For each test case output one line containing two integers $p_\text{min}$ and $p_\text{max}$ separated by one space. $p_\text{min}$ indicates the minimum possible number of players successfully arriving at the position of the airdrop, while $p_\text{max}$ indicates the maximum possible number.

题目大意

题目描述

有 $n$ 个玩家在一个平面直角坐标系中打 PUBG. 此时一个空投落在了 $(x_0, y_0)$ 处.

现在场上还剩 $n$ 个「存活」的玩家. 从空投落地的时刻起, 每一个时刻执行如下操作 :

1. 移动阶段

对于每个「存活」的玩家 :

• 如果其不在 $(x_0, y_0)$ :
  • 向空投方向沿 $x$ 轴或 $y$ 轴方向移动 $1$ 个单位距离, 使得移动后位置与 $(x_0, y_0)$ 的曼哈顿距离尽可能小.
  • 在上一条规则的基础上, 如果有多种符合要求的移动方式, 则优先沿 $y$ 轴移动.
• 如果其在 $(x_0, y_0)$, 则不进行操作.

2. 战斗阶段

移动阶段结束后, 如果除 $(x_0, y_0)$ 外任意一点存在超过 $1$ 名玩家, 则将这一点所有玩家判定为「死亡」并移出游戏.

---

可以证明, 经过足够多次操作后, 所有仍「存活」的玩家都会处在 $(x_0, y_0)$ 位置.

给定 $y_0$, 求 $x_0$ 取任意整数值时, 最终「存活」玩家数的最大值与最小值.

输入输出格式与数据范围

首先给出一个整数 $T$, 表示数据组数. 接下来对于每组数据 :

第一行给出两个正整数 $n, y_0$, 意义如题所述.

接下来 $n$ 行, 每行两个正整数 $x, y$, 表示 $n$ 个玩家的坐标.

$n$ 和所有点的坐标值都不超过 $10^5$, 且保证不存在两名玩家初始处在同一位置. 单个测试点的 $\sum n \le 10^6$.

注意 : $x_0$ 可以取 $0$ 或负值, 且不受坐标值不超过 $10^5$ 的限制.

对于每组数据, 输出一行 2 个空格分开的整数, 分别表示最终「存活」玩家数的最大值和最小值.

Translated by

3
3 2
1 2
2 1
3 5
3 3
2 1
2 5
4 3
2 3
1 3
4 3

1 3
0 3
2 2

提示

We now explain the first sample test case.

To obtain the answer of $p_\text{min} = 1$, one should consider $x_0 = 3$. The following table shows the position of each player at the end of each time unit when $x_0 = 3$.

To obtain the answer of $p_\text{max} = 3$, one should consider $x_0 = 2$. The following table shows the position of each player at the end of each time unit when $x_0 = 2$.