D – Come a Little Closer DIV3

题目分析

地图上面有很多怪兽，你可以用一个矩形将他们全部包围，然后删掉 花费单位矩形面积和的金币。
然后你有最多一次操作 ，把一个怪兽移动到任何一个没有怪兽的地方。

思路

• 这题我一开始以为是二分矩形边界，贪心矩形一个方向，但是发现不行，而且特别麻烦。（因为题目是可以跑nlogn 算法的所以比较容易想）

那怎么办？

我们先不要想什么算法，最起码知道可以跑一个n*logn 算法，先不要想移动一个的情况。

显然，在不移动任何一个怪兽的情况，矩形最优解就是 宽度 = 最右边的 – 最左边的 。 高度同理。
那么很简单了。

先排序把最左边的求出来最右边的求出来，最上面的求出来，最下面的求出来，看看删掉这些点后，最有解是啥。

但是很麻烦 ，不难发现删掉的点可能是 最左边加最上面，这样最上面也得改变。 那我们就得考虑八个情况去进行模拟。

注意这题是可以跑n*logn 算法的
我们上面的操作无非就是删掉一个点重新计算最左边和最右边或者最上面或者最下面，来实时更新矩形。 –> 这样我们不难联想到这是一个动态的排序。
那么我们就可以直接用mutiset 。 删掉一个点。 直接用mutiset求最左最右和最下 等。 直接把全部点单独删掉一遍 。 也就是 n*log 的复杂度（set 删掉一个点 和 增加一个点都是logn）
那就直接暴力一遍所有点，直接利用mutiset 自动的排序，O1的复杂度获取 各个方向的极值即可。

如果你不知道怎么用他获取最大值最小值，这里告诉你方法 *st.begin() (st是变量名，最小值) *st.rbegin() (最大值) （非常有用的方法）

AC 代码：

#include <bits/stdc++.h>
#define int long long

using namespace std;

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

  int t[n + 10][2];

  for (int i = 1; i <= n; i++)
  {
    cin >> t[i][0] >> t[i][1];
  }
  if (n == 1)
  {
    cout << 1 << endl;
    return;
  }

  multiset<int> sx, sy;

  for (int i = 1; i <= n; i++)
  {
    sx.insert(t[i][0]);
    sy.insert(t[i][1]);
  }

  int res = 1e18;

  res = min(res, (*sx.rbegin() - *sx.begin() + 1) * (*sy.rbegin() - *sy.begin() + 1));

  for (int i = 1; i <= n; i++)
  {
    sx.erase(sx.find(t[i][0]));
    sy.erase(sy.find(t[i][1]));
    int tp = (*sx.rbegin() - *sx.begin() + 1) * (*sy.rbegin() - *sy.begin() + 1);
    if (tp == n - 1)
    {
      tp += min((*sx.rbegin() - *sx.begin() + 1), (*sy.rbegin() - *sy.begin() + 1));
    }
    res = min(res, tp);
    sx.insert(t[i][0]);
    sy.insert(t[i][1]);
  }

  cout << res << endl;
}

signed main()
{

  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  int t;
  cin >> t;
  while (t--)
  {
    slove();
  }
}