BOJ 12011 Splitting the Field

https://www.acmicpc.net/problem/12011

12011번: Splitting the Field

모든 점 들을 2개의 직사각형 안에 가두어 놨을 때, 1개의 직사각형 안에 가두었을 때 보다 직사각형들의 넓이가 얼마나 더 작아질 수 있는 지 구하는 문제이다.

나는 스위핑 + segment tree를 썼다. 그 이유는 아래와 같다. 
1. 직사각형 안에 가두어놔야 하기 때문에 특정 축 기준으로 정렬하여 순차적으로 봐야할 필요가 있다. -> 스위핑
2. 이때, 직사각형의 넓이를 구하기 위해서 특정 축 구간 [n, m] 에서의 점들의 y최소값, y 최대값 을 알 필요가 있다 -> 세그먼트 트리

따라서 아래와 같은 코드가 나왔다.

#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

typedef unsigned long long ull;

ull answer = 0;
int n;
pair<int, int> arr[200000];
vector<pair<int, int>> info;

void update(int now, int s, int e, int v, int i){
    if(s == e && s == i) arr[now].first = arr[now].second = v;
    else if(i < s || e < i) return;
    else{
        int mid = (s+e)/2;
        update(now*2, s, mid, v, i); update(now*2+1, mid+1, e, v, i);;
        arr[now].first = max(arr[now*2].first, arr[now*2+1].first);
        arr[now].second = min(arr[now*2].second, arr[now*2+1].second);
    }
}

void search(int now, int s, int e){
	printf("%d : %d %d\n",now, arr[now].first, arr[now].second);
	if(s == e) return;
	else{
		int mid = (s + e) / 2;
		search(now*2, s, mid);
		search(now*2+1, mid+1, e);
	}
}
pair<int, int> get(int now, int s, int e, int f, int l){

    if( l < s || e < f) return {-1, 2000000000};
    else if( f <= s && e <= l) return arr[now];
    int mid = (s+e)/2;
    auto left  = get(now*2, s, mid, f, l);
    auto right = get(now*2+1, mid+1, e, f, l);
    pair<int, int> ret;

    ret.first  = max(left.first, right.first);
    ret.second = min(left.second, right.second);
    return ret;
}


int main(){
    int xl = 2000000000, xh=0, yl=2000000000, yh=0;
    ull area = 0;
    scanf("%d", &n);
    for(int i=0;i<n;i++){
        int x, y; scanf("%d%d",&x,&y);
        info.push_back({x,y});
        if(x < xl) xl = x;
        if(x > xh) xh = x;
        if(y < yl) yl = y;
        if(y > yh) yh = y;
    }
    area = (ull)(xh - xl) * (ull)(yh - yl);

    //x 기준 정렬
    sort(info.begin(), info.end());
    for(int i=0;i<n;i++) {
    	update(1,1,n,info[i].second, i+1);
    }
    
    for(int i=1;i<n;i++){
        if(info[i-1].first == info[i].first) continue;
        auto a = get(1,1,n, 1,  i);
        auto b = get(1,1,n, i+1,n);
        
        ull aa, ab;
        aa = (ull)(a.first - a.second) * (ull)(info[i-1].first - info[0].first);
        ab = (ull)(b.first - b.second) * (ull)(info[n-1].first - info[i].first);
        if(area - (aa+ab) > answer) answer = area - (aa+ab);
    }
    
    
    //y기준 정렬
    sort(info.begin(), info.end(), [](auto &left, auto &right) {
        return left.second < right.second;
    });
    for(int i=0;i<n;i++) update(1,1,n,info[i].first, i+1);

    for(int i=1;i<n;i++){
        if(info[i-1].second == info[i].second) continue;
        auto a = get(1,1,n, 1,  i);
        auto b = get(1,1,n, i+1,n);

        ull aa, ab;
        aa = (ull)(a.first - a.second) * (ull)(info[i-1].second - info[0].second);
        ab = (ull)(b.first - b.second) * (ull)(info[n-1].second - info[i].second);
        if(area - (aa+ab) > answer) answer = area - (aa+ab);
    }
    
    
    printf("%llu\n",answer);

    return 0;
}

 

PS. 1등 코드는 더 간단하게 풀었다. 닭 잡는데 소 잡는 칼을 쓴 것 같다.