33OJ
登录 注册

#P17524. [ECUSTPC 2026 Fall] 净化行动 3

    ID: 20252 远端评测题 2000ms 1024MiB 尝试: 0 已通过: 0 显示难度普及+/提高− 上传者: 标签>模拟Special Judge拓扑排序2026高校校赛

[ECUSTPC 2026 Fall] 净化行动 3

背景

除恶务尽——何为「恶」,我们自有裁定。

题目描述

Maddy 仍在清剿 Baddy 的邪恶军团……(这已经是第三次了!)

游戏在一个无限大的平面直角坐标系(可以看作无限大的棋盘)上进行。Baddy 操控了 nn 个炮棋子。这些炮分别部署在 (x1,y1),(x2,y2),…,(xn,yn)(x_1, y_1), (x_2, y_2), \ldots, (x_n, y_n) 上,且固定不会移动。

在象棋规则中,炮的攻击规则是"隔山打牛"。如果两个炮 AA 和 BB 处于同一行或同一列,且它们之间有且仅有一个其他炮 CC,那么我们称 AA 攻击了 BB(同时 BB 也攻击了 AA),而 CC 就是它们攻击的"炮架"。

每一次,Maddy 可以选择一个当前没有受到任何其他炮攻击的炮,并将其摧毁。被摧毁的炮会被立即移出棋盘,它将不再能攻击其他炮,也不能再作为其他炮的"炮架"。

Maddy 的目标是摧毁所有的 nn 个炮。是否存在一种摧毁顺序,使得 Maddy 可以最终清空棋盘?

输入格式

第一行输入一个整数 TT (1≤T≤1051 \le T \le 10^5),表示测试数据的数量。

每组测试数据第一行输入一个整数 nn (1≤n≤2×1051 \le n \le 2 \times 10^5),表示炮的数量。

随后 nn 行,每行输入两个整数 xi,yix_i, y_i (−109≤xi,yi≤109-10^9 \le x_i, y_i \le 10^9),表示第 ii 个炮的位置。

保证所有测试数据的 ∑n≤2×105\sum n \le 2 \times 10^5,且单组测试数据中所有炮的位置两两不同。

输出格式

对于每组测试数据,若存在一种合法的摧毁顺序能够清空棋盘,则输出一行 YES,否则输出一行 NO。

注意评测时不会区分 YES 和 NO 的大小写,换言之,当答案是肯定的时候输出 yes、YES、Yes、YeS 等都会被认为是正确的。

3
3
0 0
0 1
0 2
4
0 0
1 0
2 0
3 0
8
2 0
0 1
1 1
2 1
1 2
2 2
3 2
1 3
YES
NO
NO

提示

样例 1 解释

对于第 11 组测试数据,三个炮在同一列上。初始时,(0,0)(0, 0) 和 (0,2)(0, 2) 互相攻击(以 (0,1)(0, 1) 为炮架),而 (0,1)(0, 1) 没有受到攻击。因此可以先摧毁 (0,1)(0, 1),然后 (0,0)(0, 0) 和 (0,2)(0, 2) 都不再受到攻击,可以按任意顺序摧毁。

对于第 22 组测试数据,四个炮在同一行上。初始时,(0,0)(0, 0) 和 (2,0)(2, 0) 互相攻击(以 (1,0)(1, 0) 为炮架),(1,0)(1, 0) 和 (3,0)(3, 0) 互相攻击(以 (2,0)(2, 0) 为炮架)。因此 (0,0)(0, 0)、(1,0)(1, 0)、(2,0)(2, 0)、(3,0)(3, 0) 都受到攻击,无法摧毁任何一个,因此无解。