算法

(几何、最短路径和排序) $O(n\log n)$

首先横坐标和纵坐标是相互独立的，所以可以分开来考虑。其次注意到在一个单调序列中，在以中位数为端点的闭区间上的点到原序列上任意一点的距离可以做到最小。

C++ 代码

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; ++i)

using std::cin;
using std::cout;
using std::vector;
using ll = long long;

int main() {
    int t;
    cin >> t;

    while (t--) {
        int n;
        cin >> n;
        vector<int> x(n), y(n);
        rep(i, n) cin >> x[i] >> y[i];
        auto f = [&](vector<int> x) {
            std::sort(x.begin(), x.end());
            return 1ll * x[x.size() >> 1] - x[x.size() - 1 >> 1] + 1;
        };
        cout << f(x) * f(y) << '\n';
    }

    return 0;
}