CF2114D Come a Little Closer

考虑枚举是哪一个被移动。每次计算出所需的面积，取最小值即可。

注意特殊情况：如果这个矩形的面积小于 $n$，则说明这个矩形不够大，也就是说一开始的移动就不成立，此时需要添一条较短的边来补足。

直接枚举（中间还有搜索）的复杂度过大，考虑使用 multiset 进行维护。

这里浅记录一下 multiset 的一些用法：

• 同其它 STL 模板，可使用 multiset<typename> name 进行声明。
• .begin() 返回排序后的第一个元素。
• .end() 返回排序后的最后一个元素。
• .rbegin() 返回排序后的最后一个元素（反向迭代器）。
• .rend() 返回排序后的第一个元素（反向迭代器）。
• .find(value) 以 $O(\log n)$ 的速度查询某个值的位置。
• .insert(value) 以 $O(\log n)$ 的速度插入某个值并排序。
• .erase(position) 以 $O(\log n)$ 的速度删除某个位置上的值。
• .empty() 同其它 STL，返回是否为空。
• .size() 返回该 multiset 的大小。
• .clear() 清空该 multiset。

#include <bits/stdc++.h>
#define MAXN 200005
using namespace std;
long long x[MAXN],y[MAXN];
multiset<long long> px,py;
int main()
{
    int T,n;
    scanf("%d",&T);
    while (T)
    {
        px.clear();
        py.clear();
        scanf("%d",&n);
        for (int i=1;i<=n;i++)
        {
            scanf("%lld %lld",&x[i],&y[i]);
            px.insert(x[i]);
            py.insert(y[i]);
        }
        long long ans=1e18;
        for (int i=1;i<=n;i++)
        {
            long long tx=x[i],ty=y[i];
            px.erase(px.find(tx));
            py.erase(py.find(ty));
            if (px.empty()||py.empty())
            {
                px.insert(tx);
                py.insert(ty);
                ans=1;
                continue;
            }
            long long dx=*px.rbegin()-*px.begin()+1,dy=*py.rbegin()-*py.begin()+1;
            ans=min(ans,dx*dy);
            if (ans==n-1)
            {
                ans+=min(dx,dy);
            }
            px.insert(tx);
            py.insert(ty);
        }
        printf("%lld\n",ans);
        T--;
    }
    return 0;
}