## Problem

## Key Idea

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) \)

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

## Implementation

```
/**
* 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";
}
}
```

## Leave a comment