#P18623. Airdrop
Airdrop
Airdrop
将战场看成二维平面。一个空投落在 ,其中两个坐标都是整数。战场上有 名玩家,第 名玩家的初始位置为 ,所有初始位置互不相同。
所有仍然存活的玩家同时行动。每个时间单位:
- 若一名玩家在这个时间单位开始时已位于空投位置,他原地停留。
- 否则,设他当前位于 。他从 、、、 中,选择到空投的曼哈顿距离最小的点,并在这个时间单位结束时到达该点。
- 若有多个候选点的距离相同,依次优先选择下、上、左、右,即优先级为 、、、。
两点 、 的曼哈顿距离为 。因此,玩家会先沿竖直方向到达直线 ,再沿水平方向到达空投。
如果至少两名仍然存活的玩家,在空投位置以外的同一整数坐标 相遇,他们会互相战斗,所有在该处相遇的玩家全部被淘汰,没有人幸存。在空投位置相遇的玩家不会因此被淘汰。
已知 和所有玩家的初始位置,但不知道 。请在所有 中,分别求出最终成功到达空投的玩家人数的最小值与最大值。注意, 可以为正数、零或负数。
输入格式
第一行包含整数 ,表示测试用例数。
每个测试用例的第一行包含两个整数 。
接下来 行,第 行包含两个整数 。
数据范围
- ;
- ;
- 每个测试用例中,所有初始位置 互不相同;
- 一个输入文件中,所有测试用例的 之和不超过 。
输出格式
每个测试用例输出一行,包含两个整数 ,依次表示成功到达空投的玩家人数的最小可能值和最大可能值。
样例输入 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
样例解释
第一个测试用例中,取 可以使幸存人数为1。各时间单位结束时的位置如下。时间1中玩家1、2在非空投位置 相遇,因此在该次移动后同时被淘汰。
| 时间 | 玩家1 | 玩家2 | 玩家3 |
|---|---|---|---|
| 0 | (1,2) | (2,1) | (3,5) |
| 1 | (2,2) | (3,4) | |
| 2 | 已淘汰 | (3,3) | |
| 3 | (3,2) | ||
取 可以使幸存人数为3。此时玩家1、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) | ||