BOJ 12011 Splitting the Field

  점들을 두 사각형으로 재분할하는 문제이다. 

 

  사각형을 이루는 선은 항상 x축이나 y축과 평행하다는 조건이 있다. 이 조건으로부터 만들어지는 두 직사각형은 두 축 중 하나와 평행하는 임의의 직선을 기준으로 항상 양쪽에 위치한다는 것을 알 수 있다. 양쪽부터 분할선까지의 점들을 순차적으로 탐색하면서 분할선이 y축과 평행할 경우에는 y좌표의 최대, 최소를, x축과 평행할 경우에는 x좌표의 최대 최소를 저장해주면 분할된 두 직사각형의 넓이를 쉽게 알아낼 수 있다.

 

  각각의 최대 최소를 세그먼트 트리로 저장하는 방법으로 해결할 수도 있다.

#include <cstdio>
#include <algorithm>
#include <vector>
#include <utility>
using namespace std;
 
typedef long long ll;
typedef pair<ll, ll> p;
 
const ll MAX = 1e18 + 10;
 
// maxd1,mind1 = 분할선을 기준으로 왼쪽(아래)부터 분할선까지의 좌표 최대최소값을 저장
// maxd2,mind2 = 오른(위)쪽부터 분할선까지의 최대최소값을 저장
ll n, maxd1[50005], mind1[50005], maxd2[50005], mind2[50005];
vector<p> vt;
 
bool comp(p& a, p& b) {
    if (a.second == b.second)
        return a.first < b.first;
    return a.second < b.second;
}
 
int main() {
 
    scanf("%lld", &n);
 
    ll a, b, t1 = MAX, t2 = -100;
    for (ll i = 0; i < n; i++) {
 
        scanf("%lld %lld", &a, &b);
        vt.push_back({ a,b });
 
        t1 = min(t1, b);
        t2 = max(t2, b);
    }
    
    // x를 기준으로 정렬
    sort(vt.begin(), vt.end());
    
    // 하나의 울타리만 있을 경우
    ll origin = (vt.back().first - vt[0].first) * (t2 - t1);
    ll res = 0;
 
    for (ll i = 0; i < vt.size(); i++) {
        if (i == 0) {
            maxd1[i] = vt[i].second;
            mind1[i] = vt[i].second;
        }
        else {
            maxd1[i] = max(maxd1[i - 1], vt[i].second);
            mind1[i] = min(mind1[i - 1], vt[i].second);
        }
    }
 
    for (ll i = vt.size() - 1; i >= 0; i--) {
        if (i == vt.size() - 1) {
            maxd2[i] = vt[i].second;
            mind2[i] = vt[i].second;
        }
        else {
            maxd2[i] = max(maxd2[i + 1], vt[i].second);
            mind2[i] = min(mind2[i + 1], vt[i].second);
        }
    }
 
    // temp1 = x좌표값의 차
    // temp2 = 현재까지의 y좌표값의 최대와 최소의 차
    ll temp1, temp2;
    for (ll i = 0; i < n - 1; i++) 
        temp1 = maxd1[i] - mind1[i];
        temp2 = maxd2[i + 1] - mind2[i + 1];
        res = max(res, origin - temp1 * (vt[i].first - vt[0].first) - temp2 * (vt.back().first - vt[i + 1].first));
    }
 
    // y를 기준으로 정렬
    sort(vt.begin(), vt.end(), comp);
 
    for (ll i = 0; i < vt.size(); i++) {
        if (i == 0) {
            maxd1[i] = vt[i].first;
            mind1[i] = vt[i].first;
        }
        else {
            maxd1[i] = max(maxd1[i - 1], vt[i].first);
            mind1[i] = min(mind1[i - 1], vt[i].first);
        }
    }
 
    for (ll i = vt.size() - 1; i >= 0; i--) {
        if (i == vt.size() - 1) {
            maxd2[i] = vt[i].first;
            mind2[i] = vt[i].first;
        }
        else {
            maxd2[i] = max(maxd2[i + 1], vt[i].first);
            mind2[i] = min(mind2[i + 1], vt[i].first);
        }
    }
 
    // temp1 = y좌표값의 차
    // temp2 = 현재까지의 x좌표값의 최대와 최소의 차
    for (ll i = 0; i < n - 1; i++) {
        temp1 = maxd1[i] - mind1[i];
        temp2 = maxd2[i + 1] - mind2[i + 1];
        res = max(res, origin - temp1 * (vt[i].second - vt[0].second) - temp2 * (vt.back().second - vt[i + 1].second));
    }
 
    printf("%lld\n", res);
}