题解：CF2114D Come a Little Closer

· · 题解

模拟题，根据题目意思来即可，对于读入的数据，我们可以分别用两个数组来维护，用 q[i] 维护以 x 为准的单调递增点，用 p[i] 维护以 y 为准的单调递增点，然后分别对四个顶点角进行判断求最小值即可，需要注意的是，可能会存在最小值小于 n 的情况，此时需要进行判断，代码如下。

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
#define int long long
#define MAXN 1000010
#define x first
#define y second
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
typedef pair<int,int> PII;
PII q[MAXN],p[MAXN];
void solve(){
    int n;
    cin>>n;
    int x1=1e14,x2=0,y1=1e14,y2=0;
    int mi=1e18;
    for(int i=1;i<=n;i++){
        int a,b;
        cin>>a>>b;
        x1=min(x1,a);
        x2=max(x2,a);
        y1=min(y1,b);
        y2=max(y2,b);
        q[i]={a,b};
        p[i]={b,a};
    }
    if(n==1){
        cout<<1<<endl;
        return ;
    }
    sort(q+1,q+1+n);//x轴 
    sort(p+1,p+1+n);//y轴 
    if(q[n].x==p[n].y)mi=min(mi,(q[n-1].x-x1+1)*(p[n-1].x-y1+1));
    else {
        mi=min(mi,(q[n-1].x-x1+1)*(y2-y1+1));
        mi=min(mi,(x2-x1+1)*(p[n-1].x-y1+1));
    }
    if(q[n].x==p[1].y)mi=min(mi,(q[n-1].x-x1+1)*(y2-p[2].x+1));
    else {
        mi=min(mi,(q[n-1].x-x1+1)*(y2-y1+1));
        mi=min(mi,(x2-x1+1)*(y2-p[2].x+1));
    }
    if(q[1].x==p[1].y)mi=min(mi,(x2-q[2].x+1)*(y2-p[2].x+1));
    else {
        mi=min(mi,(x2-q[2].x+1)*(y2-y1+1));
        mi=min(mi,(x2-x1+1)*(y2-p[2].x+1));
    } 
    if(q[1].x==p[n].y)mi=min(mi,(x2-q[2].x+1)*(p[n-1].x-y1+1));
    else {
        mi=min(mi,(x2-q[2].x+1)*(y2-y1+1));
        mi=min(mi,(x2-x1+1)*(p[n-1].x-y1+1));
    } 
    if(mi<n){
        mi=1e18;
            if(q[n].x==p[n].y)mi=min(mi,min((q[n-1].x-x1+2)*(p[n-1].x-y1+1),(q[n-1].x-x1+1)*(p[n-1].x-y1+2)));
        else {
            mi=min(mi,(q[n-1].x-x1+2)*(y2-y1+1));
            mi=min(mi,(q[n-1].x-x1+1)*(y2-y1+2));
            mi=min(mi,(x2-x1+1)*(p[n-1].x-y1+2));
            mi=min(mi,(x2-x1+2)*(p[n-1].x-y1+1));
        }
            if(q[n].x==p[1].y)mi=min(mi,min((q[n-1].x-x1+1)*(y2-p[2].x+2),(q[n-1].x-x1+2)*(y2-p[2].x+1)));
        else {
            mi=min(mi,(q[n-1].x-x1+2)*(y2-y1+1));
            mi=min(mi,(q[n-1].x-x1+1)*(y2-y1+2));
            mi=min(mi,(x2-x1+2)*(y2-p[2].x+1));
            mi=min(mi,(x2-x1+1)*(y2-p[2].x+2));
        }
        if(q[1].x==p[1].y)mi=min(mi,min((x2-q[2].x+1)*(y2-p[2].x+2),(x2-q[2].x+2)*(y2-p[2].x+1)));
        else {
            mi=min(mi,(x2-q[2].x+2)*(y2-y1+1));
            mi=min(mi,(x2-q[2].x+1)*(y2-y1+2));
            mi=min(mi,(x2-x1+2)*(y2-p[2].x+1));
            mi=min(mi,(x2-x1+1)*(y2-p[2].x+2));
        } 
            if(q[1].x==p[n].y)mi=min(mi,min((x2-q[2].x+2)*(p[n-1].x-y1+1),(x2-q[2].x+1)*(p[n-1].x-y1+2)));
        else {
            mi=min(mi,(x2-q[2].x+2)*(y2-y1+1));
            mi=min(mi,(x2-q[2].x+1)*(y2-y1+2));
            mi=min(mi,(x2-x1+2)*(p[n-1].x-y1+1));
            mi=min(mi,(x2-x1+1)*(p[n-1].x-y1+2));
        } 
    }
    cout<<mi<<endl;
}
signed main(){
    ios;
    int t;
    cin>>t;
    while(t--)
    solve();
    return 0;
}