#P18623. Airdrop

Airdrop

Airdrop

将战场看成二维平面。一个空投落在 (x0,y0)(x_0,y_0),其中两个坐标都是整数。战场上有 nn 名玩家,第 ii 名玩家的初始位置为 (xi,yi)(x_i,y_i),所有初始位置互不相同。

所有仍然存活的玩家同时行动。每个时间单位:

  • 若一名玩家在这个时间单位开始时已位于空投位置,他原地停留。
  • 否则,设他当前位于 (x,y)(x,y)。他从 (x,y−1)(x,y-1)、(x,y+1)(x,y+1)、(x−1,y)(x-1,y)、(x+1,y)(x+1,y) 中,选择到空投的曼哈顿距离最小的点,并在这个时间单位结束时到达该点。
  • 若有多个候选点的距离相同,依次优先选择下、上、左、右,即优先级为 (x,y−1)(x,y-1)、(x,y+1)(x,y+1)、(x−1,y)(x-1,y)、(x+1,y)(x+1,y)。

两点 (xa,ya)(x_a,y_a)、(xb,yb)(x_b,y_b) 的曼哈顿距离为 ∣xa−xb∣+∣ya−yb∣|x_a-x_b|+|y_a-y_b|。因此,玩家会先沿竖直方向到达直线 y=y0y=y_0,再沿水平方向到达空投。

如果至少两名仍然存活的玩家,在空投位置以外的同一整数坐标 (x′,y′)(x',y') 相遇,他们会互相战斗,所有在该处相遇的玩家全部被淘汰,没有人幸存。在空投位置相遇的玩家不会因此被淘汰。

已知 y0y_0 和所有玩家的初始位置,但不知道 x0x_0。请在所有 x0∈Zx_0\in\mathbb Z 中,分别求出最终成功到达空投的玩家人数的最小值与最大值。注意,x0x_0 可以为正数、零或负数。

输入格式

第一行包含整数 TT,表示测试用例数。

每个测试用例的第一行包含两个整数 n,y0n,y_0。

接下来 nn 行,第 ii 行包含两个整数 xi,yix_i,y_i。

数据范围

  • 1≤n≤1051\le n\le10^5;
  • 1≤y0,xi,yi≤1051\le y_0,x_i,y_i\le10^5;
  • 每个测试用例中,所有初始位置 (xi,yi)(x_i,y_i) 互不相同;
  • 一个输入文件中,所有测试用例的 nn 之和不超过 10610^6。

输出格式

每个测试用例输出一行,包含两个整数 pmin⁡,pmax⁡p_{\min},p_{\max},依次表示成功到达空投的玩家人数的最小可能值和最大可能值。

样例输入 1

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

样例输出 1

1 3
0 3
2 2

样例解释

第一个测试用例中,取 x0=3x_0=3 可以使幸存人数为1。各时间单位结束时的位置如下。时间1中玩家1、2在非空投位置 (2,2)(2,2) 相遇,因此在该次移动后同时被淘汰。

时间 玩家1 玩家2 玩家3
0 (1,2) (2,1) (3,5)
1 (2,2) (3,4)
2 已淘汰 (3,3)
3 (3,2)

取 x0=2x_0=2 可以使幸存人数为3。此时玩家1、2在空投位置 (2,2)(2,2) 相遇,不会被淘汰。

时间 玩家1 玩家2 玩家3
0 (1,2) (2,1) (3,5)
1 (2,2) (3,4)
2 (3,3)
3 (3,2)
4 (2,2)