Public Judge

pjudge

Time Limit: 3 s Memory Limit: 1024 MB Total points: 100 Hackable ✓

# 21663. 【PR #7】杜杜和DUDU

统计

i5q8b9nc.png

DUDU是只可爱的小熊,喜欢乱吃农场主杜杜的蜂蜜,因此杜杜希望修一个长方形的篱笆,包裹住所有蜂蜜点,从而将DUDU隔离在外。

具体而言,杜杜有 $n$ 个养殖蜂蜜点,依次为 $(x_1,y_1),(x_2,y_2),\cdots,(x_n,y_n)$ 。任何时刻篱笆都是长方形的。假设有篱笆位于 $(X,Y)$ , $(x_i,y_i)$ 位于长方形里边当且仅当 $x_i\leq X$ 且 $y_i\leq Y$ 。由于修建过程不能被DUDU知晓,杜杜建造篱笆要满足特定的规律!

我们需要进行一轮轮的扩建,直到我们的篱笆包裹住了所有蜂蜜点。假设当前篱笆位于 $(X,Y)$ ,扩建的时候我们会选择一个 $(x_j,y_j)$ 满足其不在篱笆里边,然后我们会扩建至 $(\max(X,x_j),\max(Y,y_j))$ 。令 $A=\max(X,x_j),B=\max(Y,y_j)$ 。DUDU有个察觉值 $m$,所以这次扩建还需要满足 $(A,B)$ 的篱笆周长减去 $(A,B)$ 和 $(X,Y)$ 的公共部分不超过 $m$ 。详细解释如下:

  • 若 $X=A$ ,那么 $2(B-Y)+X\leq m$ 。
  • 若 $Y=B$ ,那么 $2(A-X)+Y\leq m$ 。
  • 其他情况, $2A+2B-X-Y\leq m$ 。

试问杜杜有没有扩建的方案,多组测试数据。

输入格式

第一行一个正整数 $T$ 。

接下来 $T$ 组测试数据,每组第一行两个整数 $n,m$ 。

接下来 $n$ 行,每行两个正整数 $(x,y)$ ,表示其中一个蜂蜜点。

输出格式

对于每组测试数据,输出一行一个 YesNo 表示是否有扩建方案。

样例一

input

3
3 6
1 1
4 1
2 2
4 9
1 4
2 3
3 2
4 1
10 14
10 8
1 6
2 5
4 2
5 5
8 9
2 7
6 8
6 5
7 4

output

Yes
No
Yes

样例二、三、四、五、六

见下发文件。

数据范围与提示

对于所有数据,$x,y\leq 10^9,m \leq 4\times 10^9,\sum n\leq 5\times 10^5$ 。记 $L$ 为 所有数据中 $n$ 的最大值,记 $S=\sum n^2$ ,$H=\sum n^3$

子任务编号 $L\leq$ $S\leq$ $H\leq$ 分值
$1$ $1000$ $1.25\times10^7$ $1.25\times 10^7$ $20$
$2$ $5\times 10^7$ $1.25\times 10^{17}$ $30$
$3$ $5\times10^5$ $2.5\times 10^{11}$ $50$

时间限制:$\texttt{3s}$

空间限制:$\texttt{1024MB}$