Hello World

Eastern Exhibition

The question

Input & Output

Solve

The very first thing we should know is we are using Manhattan distance to represent the distance of to points, which means we can handle Xs and Ys separately.

for(int i=0; i<n; i++) cin>>x[i]>>y[i];
sort(x.begin(), x.end());
sort(y.begin(), y.end());

If the number of points is odd, there will be only 1 point to make sum of absolute difference of Xs minimum, so does Ys.

Otherwise, any X between two mid Xs has the same sum, so does Ys.

ll cx, cy;
if(x.size()&1) cx=1;
else {
    int mid=x.size()>>1;
    cx=x[mid]-x[mid-1]+1;
}
if(y.size()&1) cy=1;
else {
    int mid=y.size()>>1;
    cy=y[mid]-y[mid-1]+1;
}
cout<<cx*cy<<endl;

Code

#include<bits/stdc++.h>

using namespace std;

const int maxn = 2e5 + 5;
const int inf = INT_MAX;
const int mod = 1e9 + 7;

typedef long long ll;

vector<int> x, y;

int main() {
    ios::sync_with_stdio(false);
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        x.resize(n);
        y.resize(n);
        for(int i=0; i<n; i++) cin>>x[i]>>y[i];
        sort(x.begin(), x.end());
        sort(y.begin(), y.end());
        ll cx, cy;
        if(x.size()&1) cx=1;
        else {
            int mid=x.size()>>1;
            cx=x[mid]-x[mid-1]+1;
        }
        if(y.size()&1) cy=1;
        else {
            int mid=y.size()>>1;
            cy=y[mid]-y[mid-1]+1;
        }
        cout<<cx*cy<<endl;
    }

    return 0;
}