P13585 [NWRRC 2023] Every Queen

在一个无限大的棋盘上有 $n$ 个国际象棋皇后。它们分别放置在坐标为 $(x_1, y_1), (x_2, y_2), \ldots, (x_n, y_n)$ 的格子上。你的任务是找出一个被所有皇后攻击到的格子，或者报告不存在这样的格子。 如果皇后位于 $(x_i, y_i)$，那么它攻击 $(x, y)$ 当且仅当以下任意一个条件成立： - $x_i = x$； - $y_i = y$； - $|x_i - x| = |y_i - y|$。 注意，在本题中，皇后之间不会互相阻挡。例如，如果有皇后在 $(1, 1)$ 和 $(2, 2)$，它们都能攻击到 $(3, 3)$。此外，你可以选择一个已经有皇后的格子作为答案。例如，在上述例子中，$(1, 1)$ 也是一个合法答案。

每个测试点包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^5$），表示测试用例的数量。接下来是每个测试用例的描述。 每个测试用例的第一行包含一个整数 $n$，表示皇后的数量（$1 \le n \le 10^5$）。 接下来的 $n$ 行中，第 $i$ 行包含两个整数 $x_i$ 和 $y_i$，表示第 $i$ 个皇后所在格子的坐标（$-10^8 \le x_i, y_i \le 10^8$）。保证没有两个皇后在同一个格子上。 保证所有测试用例中 $n$ 的总和不超过 $10^5$。

对于每个测试用例，如果存在答案，第一行输出 $\tt{YES}$。第二行输出两个整数 $x$ 和 $y$，表示一个被所有皇后攻击到的格子的坐标（$-10^9 \le x, y \le 10^9$）。 如果不存在这样的格子，输出一行 $\tt{NO}$。 可以证明，如果存在答案，则一定存在满足 $-10^9 \le x, y \le 10^9$ 的答案。如果有多个答案，输出任意一个即可。

由 ChatGPT 4.1 翻译