BOJ 12011 : Splitting the Field

알고리즘

sorting, segtree

시간복잡도

$O(NlogN)$

풀이

한 가로선 또는 세로선 기준으로 두 직사각형이 구분됨이 보장됨.
WLOG 자르는 선을 세로선이라 하면, 각 직사각형당
가로 길이: 미리 sort 해놓은 배열에서의 차, $O(1)$
세로 길이: 구간에서의 $max-min$, segment tree로 $O(logN)$
(구간이 시작 또는 끝을 포함하므로 prefix/suffix max/min으로도 가능)

코드

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

int N;  
pair<ll, ll> a[50005];  
ll x[50005], y[50005], befans, ans = 1e18;  
struct z  
{  
    ll mx, mn;  
};  
z xtree[200005], ytree[200005];  

bool compx(const pair<ll, ll> &l, const pair<ll, ll> &r)  
{  
    return l.first < r.first;  
}  

bool compy(const pair<ll, ll> &l, const pair<ll, ll> &r)  
{  
    return l.second < r.second;  
}  

void mtx(int now, int s, int e)  
{  
    if (s > e) return;  
    if (s == e) {xtree[now] = {a[s].first, a[s].first}; return;}  
    int mid = s+e >> 1;  
    mtx(now*2, s, mid); mtx(now*2+1, mid+1, e);  
    xtree[now] = {max(xtree[now*2].mx, xtree[now*2+1].mx), min(xtree[now*2].mn, xtree[now*2+1].mn)};  
}  

void mty(int now, int s, int e)  
{  
    if (s > e) return;  
    if (s == e) {ytree[now] = {a[s].second, a[s].second}; return;}  
    int mid = s+e >> 1;  
    mty(now*2, s, mid); mty(now*2+1, mid+1, e);  
    ytree[now] = {max(ytree[now*2].mx, ytree[now*2+1].mx), min(ytree[now*2].mn, ytree[now*2+1].mn)};  
}  

z xcha(int now, int s, int e, int l, int r)  
{  
    if (s > e || r < s || e < l) return {-1, 1000000001LL};  
    if (l <= s && e <= r) return xtree[now];  
    int mid = s+e >> 1;  
    z A = xcha(now*2, s, mid, l, r);  
    z B = xcha(now*2+1, mid+1, e, l, r);  
    return {max(A.mx, B.mx), min(A.mn, B.mn)};  
}  

z ycha(int now, int s, int e, int l, int r)  
{  
    if (s > e || r < s || e < l) return {-1, 1000000001LL};  
    if (l <= s && e <= r) return ytree[now];  
    int mid = s+e >> 1;  
    z A = ycha(now*2, s, mid, l, r);  
    z B = ycha(now*2+1, mid+1, e, l, r);  
    return {max(A.mx, B.mx), min(A.mn, B.mn)};  
}  

ll cha(z k)  
{  
    return k.mx - k.mn;  
}  

int main()  
{  
    cin>>N;  
    for (int i = 1; i <= N; i++) {  
        cin>>a[i].first>>a[i].second;  
    }    sort(a+1, a+N+1, compx);  
    for (int i = 1; i <= N; i++) x[i] = a[i].first;  
    mty(1, 1, N);  
    sort(a+1, a+N+1, compy);  
    for (int i = 1; i <= N; i++) y[i] = a[i].second;  
    mtx(1, 1, N);  
    befans = (x[N] - x[1]) * (y[N] - y[1]);  
    for (int i = 1; i < N; i++) {  
        if (x[i] == x[i+1]) continue;  
        ll now = (x[i] - x[1]) * cha(ycha(1, 1, N, 1, i));  
        now += (x[N] - x[i+1]) * cha(ycha(1, 1, N, i+1, N));  
        ans = min(ans, now);  
    }    for (int i = 1; i < N; i++) {  
        if (y[i] == y[i+1]) continue;  
        ll now = (y[i] - y[1]) * cha(xcha(1, 1, N, 1, i));  
        now += (y[N] - y[i+1]) * cha(xcha(1, 1, N, i+1, N));  
        ans = min(ans, now);  
    }    cout<<befans - ans; return 0;  
}