题意简述

你位于无限笛卡尔平面上的点 $(0,0)$。你有一个带有 $4$ 个按钮的控制器，每个按钮可以执行以下操作之一：

• $U$：从 $(x,y)$ 移动到 $(x,y+1)$；
• $R$：从 $(x,y)$ 移动到 $(x+1,y)$；
• $D$：从 $(x,y)$ 移动到 $(x,y-1)$；
• $L$：从 $(x,y)$ 移动到 $(x-1,y)$。

不幸的是，控制器坏了。如果你按下了全部 $4$ 个按钮（无论顺序如何），控制器就会停止工作。这意味着在整个行程中，你最多只能按 $3$ 个不同的按钮（每个按钮可以按任意次数，顺序任意）。

平面上有 $n$ 个特殊点，坐标为整数 $(x_i, y_i)$。你能否在不损坏控制器的情况下访问所有特殊点（顺序任意）？

解法分析

关键观察

• 如果只使用 $U,R,D$ 三个按钮，则 $x$ 坐标永远不会减少，因此只能到达 $x \ge 0$ 的区域。
• 如果只使用 $U,R,L$ 三个按钮，则 $y$ 坐标永远不会减少，因此只能到达 $y \ge 0$ 的区域。
• 如果只使用 $U,D,L$ 三个按钮，则 $x$ 坐标永远不会增加，因此只能到达 $x \le 0$ 的区域。
• 如果只使用 $R,D,L$ 三个按钮，则 $y$ 坐标永远不会增加，因此只能到达 $y \le 0$ 的区域。

更一般地，只要存在一个方向（上、下、左、右）我们完全不使用，那么所有点都必须位于该方向所允许的半平面内。

反过来，如果点集中同时存在：

• $x > 0$ 的点（需要 $R$ 按钮），
• $x < 0$ 的点（需要 $L$ 按钮），
• $y > 0$ 的点（需要 $U$ 按钮），
• $y < 0$ 的点（需要 $D$ 按钮），

那么四个按钮都必不可少，无法只用三个按钮，答案就是 "NO"。

算法步骤

对于每个测试用例：

1. 初始化四个布尔变量：

   • $posX$：是否存在 $x_i > 0$ 的点
   • $negX$：是否存在 $x_i < 0$ 的点
   • $posY$：是否存在 $y_i > 0$ 的点
   • $negY$：是否存在 $y_i < 0$ 的点

2. 遍历所有点，根据坐标更新这四个标志。

3. 如果 $posX$、$negX$、$posY$、$negY$ 四个标志 同时为真，则输出 "NO"，否则输出 "YES"。

正确性证明

充分性：若四个标志不全为真，则至少有一个方向（例如 $x>0$ 的方向）没有点。此时我们可以选择 不使用该方向对应的按钮，只使用其余三个按钮。由于所有点的坐标在该方向上的分量都不大于 $0$（或都不小于 $0$），我们可以通过逐层移动（类似“扫描线”方法）访问所有点。例如，若所有点满足 $x \ge 0$，则可以用 $U,D$ 在每一列上下移动，用 $R$ 向右推进。因此答案为 "YES"。

必要性：若四个标志全为真，则存在点需要 $R$、存在点需要 $L$、存在点需要 $U$、存在点需要 $D$。任何三个按钮都无法同时满足这四个方向的需求，因此答案为 "NO"。

复杂度分析

• 每个测试用例只需遍历 $n$ 个点，时间复杂度 $O(n)$。
• 空间复杂度 $O(1)$（不考虑输入存储）。

参考代码（C++）

#include <bits/stdc++.h>
using namespace std;

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        bool posX = false, negX = false, posY = false, negY = false;
        for (int i = 0; i < n; ++i) {
            int x, y;
            cin >> x >> y;
            if (x > 0) posX = true;
            if (x < 0) negX = true;
            if (y > 0) posY = true;
            if (y < 0) negY = true;
        }
        if (posX && negX && posY && negY) {
            cout << "NO\n";
        } else {
            cout << "YES\n";
        }
    }
    return 0;
}