题目大意

在一个无限大的二维网格上，每个整点 $(x, y)$ 有一个灯泡。初始时，所有灯泡都熄灭，除了一个灯泡（宝藏位置 $(s, t)$）是亮着的。

可以执行任意多次（包括零次）如下操作：选择两个整数 $x, y$，切换以下四个灯泡的状态（开→关，关→开）：

• $(x, y)$
• $(x, y+1)$
• $(x+1, y-1)$
• $(x+1, y)$

最终给定 $n$ 个亮着的灯泡坐标（互不相同）。保证存在某个宝藏位置能够通过一系列操作得到该配置。要求输出任意一个可能的宝藏位置 $(s, t)$。

数据范围：$t \le 10^4$，$\sum n \le 2\cdot 10^5$，坐标绝对值 $\le 10^8$，宝藏坐标可 $\le 10^9$。

核心观察：奇偶性不变量

1. 总亮灯数的奇偶性

初始只有 $1$ 个灯泡亮着（奇数）。每次操作恰好改变 $4$ 个灯泡的状态，$4$ 是偶数，因此无论操作多少次，亮着的灯泡总数必定是奇数。

这样看来，如果输入端 $n$ 是偶数，则不可能有合法宝藏——但题目保证了输入是合法的，我们只需利用这个性质。

2. 固定某一垂直线 $x = c$ 上的亮灯数

考察一条垂直线 $x = c$。初始宝藏位于 $(s, t)$：

• 若 $c = s$，则该线上恰好有 $1$ 个灯泡亮（奇数）。
• 若 $c \neq s$，则该线上有 $0$ 个灯泡亮（偶数）。

现在，每执行一次操作 $(u, v)$，会切换四个灯泡：

• 两个在垂直线 $x = u$ 上：$(u, v)$ 和 $(u, v+1)$。
• 两个在垂直线 $x = u+1$ 上：$(u+1, v-1)$ 和 $(u+1, v)$。

因此，对于任意垂直线 $x = c$，操作只可能影响当 $c = u$ 或 $c = u+1$ 时的灯泡数。效应是：这两条线上的灯泡数都恰好改变 $2$（增加或减少 $2$），于是 每条垂直线上的亮灯数量的奇偶性在整个过程中保持不变。

结合初始状态可知：

• 垂直线 $x = s$ 上的亮灯数始终为奇数。
• 任何其他垂直线 $x \neq s$ 上的亮灯数始终为偶数。

因此，从最终亮着的灯泡中统计每条垂直线上的数量，找到唯一出现奇数的那条线，即可确定 $s$。

3. 固定某条对角线 $x + y = c$ 上的亮灯数

再考察对角线 $x + y = c$。初始宝藏 $(s, t)$ 所在对角线为 $x + y = s + t$，上面有 $1$ 个亮灯（奇数），其他对角线上有 $0$ 个（偶数）。

一次操作 $(u, v)$ 切换的四个点：

• $(u, v)$ 和 $(u+1, v-1)$ 在对角线 $x+y = u+v$ 上（因为 $u+v = (u+1)+(v-1)$）。
• $(u, v+1)$ 和 $(u+1, v)$ 在对角线 $x+y = u+v+1$ 上（因为 $u+(v+1) = (u+1)+v = u+v+1$）。

所以一次操作只会改变对角线 $c = u+v$ 和对角线 $c = u+v+1$ 上的灯泡数，且每条线上的改变量都是 $2$（增加或减少 $2$）。因此，每条对角线上的亮灯数的奇偶性也保持不变。

从而：

• 对角线 $x + y = s + t$ 上的亮灯数始终为奇数。
• 其他对角线上的亮灯数始终为偶数。

于是，从最终配置中找到唯一出现奇数的对角线 $x + y = C$，则 $s + t = C$，结合第一步求出的 $s$，即得 $t = C - s$。

4. 结论

我们只需统计所有最终亮灯坐标在垂直线和对角线上的频次，找出频次为奇数的那条线，直接解出 $(s, t)$。

算法步骤

对于每组测试数据：

1. 读入 $n$，以及 $n$ 个点 $(x_i, y_i)$。
2. 使用 map（或哈希表）分别统计：
   • cntVer[x]：垂直线 $x$ 上的点数。
   • cntDiag[x + y]：对角线 $x+y$ 上的点数。
3. 遍历 cntVer，找到值为奇数的 $x$，即为 $s$。
4. 遍历 cntDiag，找到值为奇数的对角线值 $c$，则 $t = c - s$。
5. 输出 $s$ 和 $t$。

由于题目保证有解，奇数值的键一定存在且唯一。

时间复杂度

• 统计 $n$ 个点需要 $O(n \log n)$ 或 $O(n)$（使用 unordered_map）。
• 总复杂度 $O(\sum n \log \sum n)$，足以通过 $2\times 10^5$。

参考代码

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

void test() {
    int n;
    cin >> n;

    map<int, int> cntVer, cntDiag;
    for (int i = 0; i < n; ++i) {
        int x, y;
        cin >> x >> y;
        cntVer[x]++;
        cntDiag[x + y]++;
    }

    int s = 0;
    for (auto [c, cnt] : cntVer) {
        if (cnt % 2 == 1) {
            s = c;
            break;
        }
    }

    int t = 0;
    for (auto [c, cnt] : cntDiag) {
        if (cnt % 2 == 1) {
            t = c - s;
            break;
        }
    }

    cout << s << " " << t << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        test();
    }

    return 0;
}