competitive-programming2021년 2월 20일1분 분량

[Codeforces] 1486B. Eastern Exhibition 풀이

수정일: 2021년 2월 20일

GeometryMathSortings

지원 언어:enko

#Problem

1486B. Eastern Exhibition

#Approach

관찰 1: 최소 거리는 ( $y-axis$ 와 $x-axis$ 를 각각) 분리해서 계산할 수 있습니다.

관찰 2: 1차원 직선에서 최소 거리가 되는 점은 항상 $left$ $median$ 과 $right$ $median$ 사이에 위치합니다.

최적의 전시 지점의 개수:

(x-axis 좌표의 개수) x (y-axis 좌표의 개수)

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