题目描述

难度分:$1400$

输入$T(\leq 10^4)$表示$T$组数据。所有数据的$n$之和$\leq 2 \times 10^5$。

每组数据输入$n(1 \leq n \leq 2 \times 10^5)$和$n$个点$(x_i,y_i)$，范围$[1,10^9]$。保证$n$个点互不相同。

有一个$10^9 \times 10^9$的矩阵，矩阵中有$n$个怪物，第$i$个怪物在$(x_i,y_i)$单元格中。

你最多可以把一个怪物移动到另一个没有怪物的单元格中。输出包含所有怪物的最小子矩形的面积（即子矩形中的单元格个数）。

输入样例

7
3
1 1
1 2
2 1
5
1 1
2 6
6 4
3 3
8 2
4
1 1
1 1000000000
1000000000 1
1000000000 1000000000
1
1 1
5
1 2
4 2
4 3
3 1
3 2
3
1 1
2 5
2 2
4
4 3
3 1
4 4
1 2

输出样例

3
32
1000000000000000000
1
6
4
8

算法

枚举+贪心

比较容易发现贪心策略，用有序表$xcnt$和$ycnt$构建两个映射，分别表示指定横坐标对应的点数、指定纵坐标对应的点数。分为以下两种情况：

1. 如果给定的$n$个点已经紧密堆积成一个矩形了（面积为$n$），说明$n$个点之间严丝合缝，已经是最优解了，答案就是$n$。
2. 否则将最外侧的一个点移动到中间的空位，假设$n$个点中横纵左边的最小值和最大值分别为$xmin$、$xmax$、$ymin$、$ymax$。这里面又有$4$种情况：如果$xmin$对应的点只有一个，就可以把它往内部移动，假设这个点是$(x,y)$（其中$x=xmin$），将这个点从$xcnt$和$ycnt$中删除，就可以得到剩下$n-1$个点的$xmin$、$xmax$、$ymin$、$ymax$，只要$(xmax-xmin+1) \times (ymax-ymin+1) \gt n-1$，说明剩下的$n-1$个点中间有空位，把$(x,y)$移进去就可以了，答案为$(xmax-xmin+1) \times (ymax-ymin+1)$。否则$(x,y)$就只能贴在最外层，答案是$(xmax-xmin+1) \times (ymax-ymin+2)$和$(xmax-xmin+2) \times (ymax-ymin+1)$的较小值。同理分析$xmax$只有一个，$ymax$、$ymin$只有一个的情况，它们对应答案的最小值就是最终答案。

复杂度分析

时间复杂度

遍历$O(n)$个点预处理出$xcnt$和$ycnt$两个有序表，时间复杂度为$O(nlog_2n)$。为了快速从$xmin$、$xmax$、$ymin$、$ymax$定位出点对应的纵坐标或横坐标，还需要$x2y$、$y2x$两个哈希表。之后分情况讨论只需要对有序表$xcnt$和$ycnt$操作，时间复杂度为$O(log_2n)$。因此，整个算法的时间复杂度为$O(nlog_2n)$。

空间复杂度

空间消耗主要在于两个有序表$xcnt$和$ycnt$，两个哈希表$x2y$和$y2x$，它们之中都有$O(n)$级别的键值对数量。因此，整个算法的额外空间复杂度为$O(n)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

int main() {
    int T;
    scanf("%d", &T);
    while(T--) {
        int n;
        scanf("%d", &n);
        map<int, int> xcnt, ycnt;
        unordered_map<int, int, custom_hash> x2y, y2x;
        int xmax = -1e9, xmin = 1e9, ymax = -1e9, ymin = 1e9;
        for(int i = 0; i < n; i++) {
            int x, y;
            scanf("%d%d", &x, &y);
            xcnt[x]++;
            ycnt[y]++;
            x2y[x] = y;
            y2x[y] = x;
            xmax = max(xmax, x);
            xmin = min(xmin, x);
            ymax = max(ymax, y);
            ymin = min(ymin, y);
        }
        LL lx = xmax - xmin + 1, ly = ymax - ymin + 1;
        if(ly * lx == n) {
            printf("%d\n", n);
        }else {
            LL ans = lx * ly;
            if(xcnt.begin()->second == 1 || xcnt.rbegin()->second == 1) {
                if(xcnt.begin()->second == 1) {
                    int x = xcnt.begin()->first, y = x2y[x];
                    xcnt[x]--, ycnt[y]--;
                    if(xcnt[x] == 0) xcnt.erase(x);
                    if(ycnt[y] == 0) ycnt.erase(y);
                    xmin = xcnt.begin()->first, xmax = xcnt.rbegin()->first;
                    ymin = ycnt.begin()->first, ymax = ycnt.rbegin()->first;
                    if((xmax - xmin + 1LL) * (ymax - ymin + 1) > n - 1) {
                        ans = min(ans, (xmax - xmin + 1LL) * (ymax - ymin + 1));
                    }
                    if((xmax - xmin + 1LL) * (ymax - ymin + 1) == n - 1) {
                        ans = min(ans, min((xmax - xmin + 2LL) * (ymax - ymin + 1), (xmax - xmin + 1LL) * (ymax - ymin + 2)));
                    }
                    xcnt[x]++, ycnt[y]++;
                }
                if(xcnt.rbegin()->second == 1) {
                    int x = xcnt.rbegin()->first, y = x2y[x];
                    xcnt[x]--, ycnt[y]--;
                    if(xcnt[x] == 0) xcnt.erase(x);
                    if(ycnt[y] == 0) ycnt.erase(y);
                    xmin = xcnt.begin()->first, xmax = xcnt.rbegin()->first;
                    ymin = ycnt.begin()->first, ymax = ycnt.rbegin()->first;
                    if((xmax - xmin + 1LL) * (ymax - ymin + 1) > n - 1) {
                        ans = min(ans, (xmax - xmin + 1LL) * (ymax - ymin + 1));
                    }
                    if((xmax - xmin + 1LL) * (ymax - ymin + 1) == n - 1) {
                        ans = min(ans, min((xmax - xmin + 2LL) * (ymax - ymin + 1), (xmax - xmin + 1LL) * (ymax - ymin + 2)));
                    }
                    xcnt[x]++, ycnt[y]++;
                }
            }
            if(ycnt.begin()->second == 1 || ycnt.rbegin()->second == 1) {
                if(ycnt.begin()->second == 1) {
                    int y = ycnt.begin()->first, x = y2x[y];
                    xcnt[x]--, ycnt[y]--;
                    if(xcnt[x] == 0) xcnt.erase(x);
                    if(ycnt[y] == 0) ycnt.erase(y);
                    xmin = xcnt.begin()->first, xmax = xcnt.rbegin()->first;
                    ymin = ycnt.begin()->first, ymax = ycnt.rbegin()->first;
                    if((xmax - xmin + 1LL) * (ymax - ymin + 1) > n - 1) {
                        ans = min(ans, (xmax - xmin + 1LL) * (ymax - ymin + 1));
                    }
                    if((xmax - xmin + 1LL) * (ymax - ymin + 1) == n - 1) {
                        ans = min(ans, min((xmax - xmin + 2LL) * (ymax - ymin + 1), (xmax - xmin + 1LL) * (ymax - ymin + 2)));
                    }
                    xcnt[x]++, ycnt[y]++;
                }
                if(ycnt.rbegin()->second == 1) {
                    int y = ycnt.rbegin()->first, x = y2x[y];
                    xcnt[x]--, ycnt[y]--;
                    if(xcnt[x] == 0) xcnt.erase(x);
                    if(ycnt[y] == 0) ycnt.erase(y);
                    xmin = xcnt.begin()->first, xmax = xcnt.rbegin()->first;
                    ymin = ycnt.begin()->first, ymax = ycnt.rbegin()->first;
                    if((xmax - xmin + 1LL) * (ymax - ymin + 1) > n - 1) {
                        ans = min(ans, (xmax - xmin + 1LL) * (ymax - ymin + 1));
                    }
                    if((xmax - xmin + 1LL) * (ymax - ymin + 1) == n - 1) {
                        ans = min(ans, min((xmax - xmin + 2LL) * (ymax - ymin + 1), (xmax - xmin + 1LL) * (ymax - ymin + 2)));
                    }
                    xcnt[x]++, ycnt[y]++;
                }
            }
            printf("%lld\n", ans);
        }
    }
    return 0;
}