{"trustable":true,"prependHtml":"\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\(\u0027, right: \u0027\\\\)\u0027, display: false},\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003ePUBG是一款多人在线大逃杀游戏。在游戏中,最多一百名玩家将降落到一个岛上,搜寻武器和装备,互相残杀,同时避免被杀。游戏中的空投是一个关键元素,因为空投通常携带着强力武器或大量补给,帮助玩家生存。\u003c/p\u003e\n\n\u003ccenter\u003e\u003cimg src\u003d\"CDN_BASE_URL/1805df5768875b9ab32fba7555a949ea?v\u003d1702875690\" width\u003d\"300px\"\u003e\u003cbr\u003e\u003ci\u003e游戏中的空投\u003c/i\u003e\u003c/center\u003e\n\n\u003cp\u003e将游戏的战场视为二维平面。一个空投刚刚降落在点$(x_0, y_0)$($x_0$和$y_0$都是整数)处,所有$n$名玩家在战场上开始向空投移动,其中$(x_i, y_i)$($x_i$和$y_i$都是整数)表示第$i$名玩家的初始位置,移动规则如下:\u003c/p\u003e\n\n\u003cul\u003e\n \u003cli\u003e如果某个玩家在本时间单位开始时的位置不等于$(x_0, y_0)$,他将开始下一步移动。\n \u003cul\u003e\n \u003cli\u003e假设他当前在点$(x, y)$。对于他的下一步移动,他将考虑四个点$(x, y - 1)$、$(x, y + 1)$、$(x - 1, y)$和$(x + 1, y)$。\u003c/li\u003e\n \u003cli\u003e他将选择四个点中曼哈顿距离空投$(x_0, y_0)$最小的一个作为他下一步移动的目的地。这里提醒一下,两点$(x_a, y_a)$和$(x_b, y_b)$之间的曼哈顿距离定义为$|x_a - x_b| + |y_a - y_b|$。\u003c/li\u003e\n \u003cli\u003e如果有两个或更多的点到空投的曼哈顿距离相同,他将使用以下优先级规则来打破平局:点$(x, y - 1)$具有最高优先级被选中,$(x, y + 1)$具有第二高优先级,$(x - 1, y)$具有第三高优先级,$(x + 1, y)$具有最低优先级。\u003c/li\u003e\n \u003cli\u003e在本时间单位结束时,他到达目的地。\u003c/li\u003e\n \u003c/ul\u003e\n \u003c/li\u003e\n \u003cli\u003e如果某个玩家在本时间单位开始时的位置等于$(x_0, y_0)$,他将继续从空投中获取补给并留在$(x_0, y_0)$。\u003c/li\u003e\n\u003c/ul\u003e\n\n\u003cp\u003e但战斗是激烈的,几乎不可能所有玩家都安全到达空投位置。如果两个或更多玩家在点$(x\u0027, y\u0027)$($(x_0, y_0)$以外的点)相遇,他们将战斗并互相残杀,没有人能幸存。\u003c/p\u003e\n\n\u003cp\u003eBaoBao是这款游戏的忠实粉丝,他对成功到达空投位置的玩家数量感兴趣,但他不知道$x_0$的值。给定$y_0$的值和每个玩家的初始位置,请帮助BaoBao计算在所有$x_0 \\in \\mathbb{Z}$的情况下,成功到达空投位置的玩家数量的最小和最大可能值,其中$\\mathbb{Z}$是所有整数的集合(注意$x_0$可以是正数、零或负数)。\u003c/p\u003e\n\n\u003ch4\u003e输入\u003c/h4\u003e\n\u003cp\u003e包含多个测试用例。输入的第一行包含一个整数$T$,表示测试用例的数量。对于每个测试用例:\u003c/p\u003e\n\n\u003cp\u003e第一行包含两个整数$n$和$y_0$($1 \\le n \\le 10^5$,$1 \\le y_0 \\le 10^5$),表示玩家数量和空投的$y$值。\u003c/p\u003e\n\n\u003cp\u003e接下来的$n$行,第$i$行包含两个整数$x_i$和$y_i$($1 \\le x_i, y_i \\le 10^5$),表示第$i$名玩家的初始位置。\u003c/p\u003e\n\n\u003cp\u003e保证所有测试用例中$n$的总和不超过$10^6$,并且在每个测试用例中没有两个玩家共享相同的初始位置。\u003c/p\u003e\n\n\u003ch4\u003e输出\u003c/h4\u003e\n\u003cp\u003e对于每个测试用例,输出一行,包含两个整数$p_\\text{min}$和$p_\\text{max}$,用一个空格分隔。其中$p_\\text{min}$表示成功到达空投位置的玩家数量的最小可能值,$p_\\text{max}$表示最大可能值。\u003c/p\u003e\n\n\u003ch4\u003e示例\u003c/h4\u003e\n\u003ctable class\u003d\"vjudge_sample\"\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3\n3 2\n1 2\n2 1\n3 5\n3 3\n2 1\n2 5\n4 3\n2 3\n1 3\n4 3\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1 3\n0 3\n2 2\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\n\n\u003ch4\u003e提示\u003c/h4\u003e\n\u003cp\u003e我们现在解释第一个示例测试用例。\u003c/p\u003e\n\n\u003cp\u003e要获得$p_\\text{min} \u003d 1$的答案,应该考虑$x_0 \u003d 3$。以下表格显示了$x_0 \u003d 3$时每个玩家在每个时间单位结束时的位置。\u003c/p\u003e\n\n\u003ctable id\u003d\"problem-table\" style\u003d\"border-collapse: collapse; text-align: center;\" align\u003d\"center\"\u003e\n \u003cthead\u003e\n \u003ctr\u003e\u003cth\u003e时间\u003c/th\u003e\u003cth\u003e玩家1\u003c/th\u003e\u003cth\u003e玩家2\u003c/th\u003e\u003cth\u003e玩家3\u003c/th\u003e\u003c/tr\u003e\n \u003c/thead\u003e\n \u003ctbody\u003e\n \u003ctr\u003e\u003ctd\u003e0\u003c/td\u003e\u003ctd\u003e(1, 2)\u003c/td\u003e\u003ctd\u003e(2, 1)\u003c/td\u003e\u003ctd\u003e(3, 5)\u003c/td\u003e\u003c/tr\u003e\n \u003ctr\u003e\u003ctd\u003e1\u003c/td\u003e\u003ctd\u003e(2, 2)\u003c/td\u003e\u003ctd\u003e(2, 2)\u003c/td\u003e\u003ctd\u003e(3, 4)\u003c/td\u003e\u003c/tr\u003e\n \u003ctr\u003e\u003ctd\u003e2\u003c/td\u003e\u003ctd\u003e被淘汰\u003c/td\u003e\u003ctd\u003e被淘汰\u003c/td\u003e\u003ctd\u003e(3, 3)\u003c/td\u003e\u003c/tr\u003e\n \u003ctr\u003e\u003ctd\u003e3\u003c/td\u003e\u003ctd\u003e被淘汰\u003c/td\u003e\u003ctd\u003e被淘汰\u003c/td\u003e\u003ctd\u003e(3, 2)\u003c/td\u003e\u003c/tr\u003e\n \u003c/tbody\u003e\n\u003c/table\u003e\n\n\u003cp\u003e要获得$p_\\text{max} \u003d 3$的答案,应该考虑$x_0 \u003d 2$。以下表格显示了$x_0 \u003d 2$时每个玩家在每个时间单位结束时的位置。\u003c/p\u003e\n\n\u003ctable id\u003d\"problem-table\" style\u003d\"border-collapse: collapse; text-align: center;\" align\u003d\"center\"\u003e\n \u003cthead\u003e\n \u003ctr\u003e\u003cth\u003e时间\u003c/th\u003e\u003cth\u003e玩家1\u003c/th\u003e\u003cth\u003e玩家2\u003c/th\u003e\u003cth\u003e玩家3\u003c/th\u003e\u003c/tr\u003e\n \u003c/thead\u003e\n \u003ctbody\u003e\n \u003ctr\u003e\u003ctd\u003e0\u003c/td\u003e\u003ctd\u003e(1, 2)\u003c/td\u003e\u003ctd\u003e(2, 1)\u003c/td\u003e\u003ctd\u003e(3, 5)\u003c/td\u003e\u003c/tr\u003e\n \u003ctr\u003e\u003ctd\u003e1\u003c/td\u003e\u003ctd\u003e(2, 2)\u003c/td\u003e\u003ctd\u003e(2, 2)\u003c/td\u003e\u003ctd\u003e(3, 4)\u003c/td\u003e\u003c/tr\u003e\n \u003ctr\u003e\u003ctd\u003e2\u003c/td\u003e\u003ctd\u003e(2, 2)\u003c/td\u003e\u003ctd\u003e(2, 2)\u003c/td\u003e\u003ctd\u003e(3, 3)\u003c/td\u003e\u003c/tr\u003e\n \u003ctr\u003e\u003ctd\u003e3\u003c/td\u003e\u003ctd\u003e(2, 2)\u003c/td\u003e\u003ctd\u003e(2, 2)\u003c/td\u003e\u003ctd\u003e(3, 2)\u003c/td\u003e\u003c/tr\u003e\n \u003ctr\u003e\u003ctd\u003e4\u003c/td\u003e\u003ctd\u003e(2, 2)\u003c/td\u003e\u003ctd\u003e(2, 2)\u003c/td\u003e\u003ctd\u003e(2, 2)\u003c/td\u003e\u003c/tr\u003e\n \u003c/tbody\u003e\n\u003c/table\u003e\n\n\u003cstyle type\u003d\"text/css\"\u003e\n#problem-table \u003e thead \u003e tr \u003e th, #problem-table \u003e tbody \u003e tr \u003e td\n{\n padding: 3px 5px;\n border: 1px solid black;\n}\n\u003c/style\u003e"}}]}