Codeforces #1486B Eastern Exhibition

문제

https://codeforces.com/problemset/problem/1486/B

걸린 시간

- 실패

풀이

C++

#include <bits/stdc++.h>
#define INF 1e9
#define all(c) c.begin(), c.end()
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int tc;
    cin >> tc;
    while(tc--){
        int n;
        cin >> n;
        vector<ll> x(n), y(n);
        for(int i = 0; i < n; i++)
            cin >> x[i] >> y[i];
        sort(all(x));
        sort(all(y));
        cout << (x[n/2]-x[(n-1)/2]+1)*(y[n/2]-y[(n-1)/2]+1) << "\n";
    }
    return 0;
}

동부 지역에 있는 n 개의 집 좌표가 주어진다. 모든 집으로부터의 거리가 최소가 되도록 하는 지점에 전시회를 개최하려고 할 때, 전시회를 개최할 수 있는 지점의 개수를 출력하여야 한다.

2차원 좌표는 맨해튼 거리(Manhattan Distance)로 두 x, y 좌표 각각의 차를 절대값으로 바꾼 후 합한 값이 두 지점 사이의 거리이다.

종만북 32 페이지에 나온 예제와 똑같은 문제로 2차원 좌표를 1차원으로 단순화하여 풀 수 있다.

y 축이 모두 0 인 좌표만이 존재한다고 생각했을 때 전시회를 개최할 수 있는 지점의 개수는 집이 짝수개 일 경우 가장 가운데에 있는 두 좌표 와 그 사이 지점 모두가 되고, 홀수개 일 경우는 가운데에 있는 집 하나만이 될 수 있다.

문제의 거리가 맨해튼 거리임을 생각했을 때 이 문제는 x, y 축을 분리하여 두개의 1차원 문제로 생각할 수 있다.

x, y 축 좌표를 분리한 후 정렬하여 각각 전시회를 개최할 수 있는 지점의 개수를 구한다. 구한 두개의 곱이 정답이다.