[Codeforces] 1486B. Eastern Exhibition explained

Problem

1486B. Eastern Exhibition

Approach

Observation 1: minimum distance can be computed separately. (\(y-axis\) and \(x-axis\) each.)

Observation 2: in a 1-dimensional line, the minimal distance point always lies in between \(left\) \(median\) and \(right\) \(median\) .

The number of optimal exibition point:

(# of x-axis coordinates) x (# of y-axis coordinates)

\(\therefore ans = ( x{rightMedian} - x{leftMedian} + 1 ) \cdot ( x{rightMedian} - x{leftMedian} + 1) \)

Code

/**
 * author: jooncco
 * written: 2021. 2. 20. Sat. 17:09:30 [UTC+9]
 **/

#include <bits/stdc++.h>
using namespace std;

#define FAST_IO ios_base::sync_with_stdio(0),cin.tie(0)
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef deque<int> di;

int t,n;

ll howMany(vi &arr) {

    sort(arr.begin(),arr.end());

    // right median - left median + 1
    return arr[arr.size()/2] - arr[(arr.size()-1)/2] +1;
}

int main() {

    FAST_IO;
    cin >> t;
    while (t--) {
        cin >> n;
        vi x(n),y(n);
        for (int i=0; i < n; ++i) {
            cin >> x[i] >> y[i];
        }
        // ll: prevent integer overflow
        ll ans= howMany(x) * howMany(y);
        cout << ans << "\n";
    }
}

Complexity

• Time: \(O(n\cdot{\log}n)\)
• Space: \(O(n)\)