[BOJ 9022] Stains

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

 

랜덤 icpc 플래 dp 뿌시기 하면서 나온 문제. 정렬에서 잘못해 몇번 틀리다가 맞았다. 이후 시간복잡도를 줄여보았다.

[2022.06.16 추가] IOI 2016의 Alien에서 Alien Trick을 제외한 것과 거의 동일한 문제이다.

 

문제

평면에 여러 정수좌표 점들이 주어진다. x축 위의 여러 점을 중심으로 각 변이 x축과 45도 기울어진 정사각형들을 그려 모든 점들이 적어도 하나의 정사각형의 경계나 내부에 있게 할 것이다. 정사각형 면적 합의 최소는?

 

풀이

우선 $y_i<0$인 점들에 대해 $y_i=-y_i$로 바꾸어도 문제는 동일하다.

 

이제 이 상황에서 $(x_i-y_i, x_i+y_i)$로 점을 찍어보자. 그러면 $x=y$인 선을 기준으로 위쪽에 점들이 있을 것이다. 여기서 $(x_i+y_i, x_i-y_i)$의 pair을 기준으로 점들을 정렬한다면 $i$번째 점까지 정사각형에 넣는 최소 면적의 2배를 $dp_i$라고 할 때 $\displaystyle dp_0=0, dp_i = \min_{0 \leq j < i} dp_j + ((x_i+y_i) - (\min_{j < k \leq i} x_k-y_k))^2$이 성립한다. 우선 점들 집합을 모두 포함하도록 하려면 $x-y=c_1$꼴 직선과 $x+y=c_2$꼴 직선 두 개 사이에 있어야 하기 때문에 $c_1 \leq c_2$라 하면 정사각형의 왼쪽 끝은 $(c_1, 0)$, 오른쪽 끝은 $(c_2, 0)$임을 쉽게 알 수 있을 것이다. 이 사실과 $x_i+y_i$값이 단조증가함, 그리고 모든 $0 \leq j < i$에 대해 검사하면 최적인 배치가 적어도 하나 있다는 사실을 관찰한다면 위 식이 성립함을 알 수 있다. 간단한 정렬과 $dp$채우기를 하면 풀 수 있다. 정답은 $dp_n$을 2로 나눈 값이다.

 

사실 점을 찍어봤다면 $(x_i-y_i, x_i+y_i)$에서 같은 $x_i-y_i$값을 가진 점들에 대해서는 $x_i+y_i$가 가장 점만 골라도 충분하고, 같은 $x_i+y_i$를 가진 점들에 대해서는 $x_i-y_i$가 가장 작은 점만 골라도 충분함을 알 수 있을 것이다. 이러한 점들만 남기자. 그러면 $x_i-y_i, x_i+y_i$가 모두 증가하도록 점들이 남을 것이다. 이 상태에서 위 $dp$를 채워도 동일하다. 다만 여기서는 항상 $x_i-y_i, x_i+y_i$가 증가하기 때문에, $\displaystyle dp_0=0, dp_i = \min_{0 \leq j < i} dp_j + ((x_i+y_i) - (x_{j+1}-y_{j+1}))^2$이 성립한다. 여기서 $x'_i=x_i-y_i, y'_i=x_i+y_i$라 한다면 $\displaystyle dp_i = \min_{0 \leq j < i} dp_j + (y'_i - x'_{j+1})^2$로 쓸 수 있다. 그리고 이 이차식의 최솟값을 구하는 것은 결국은 $y'_i$에서의 기울기가 $-2x'_{j+1}$이고 상수항이 $dp_j+{x'_{j+1}}^2$인 일차함수의 최솟값을 찾으면 된다는, 아주 유명한 CHT 풀이가 나온다.(대표적으로 APIO 특공대) 심지어 기울기에 단조성이 있기 때문에 이 문제를 $O(n)$에 풀 수 있게 된다. 다만 나는 multiset을 이용한 Line Container를 연습하기 위해 $O(n\log{n})$ 구현을 하였다. Special Thanks to Simon Lindholm.

 

코드

#include <bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
#define em emplace
#define all(v) v.begin(), v.end()
#define reset(x) memset(x, 0, sizeof(x))

using namespace std;
typedef long long ll;
typedef long double ld;
typedef complex <double> cpx;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

const int MAX = 101010;
const int INF = 1e9;
const ll LINF = 1e18;

/**
 * Author: Simon Lindholm
 * Date: 2017-04-20
 * License: CC0
 * Source: own work
 * Description: Container where you can add lines of the form kx+m, and query maximum values at points x.
 *  Useful for dynamic programming (``convex hull trick'').
 * Time: O(\log N)
 * Status: stress-tested
 */

struct Line {
    mutable ll k, m, p;
    bool operator<(const Line& o) const { return k > o.k; }
    bool operator<(ll x) const { return p < x; }
};

struct LineContainer : multiset<Line, less<>> {
    static const ll inf = LLONG_MAX;
    ll div(ll a, ll b) { 
        return a / b - ((a ^ b) < 0 && a % b); }
    bool isect(iterator x, iterator y) {
        if (y == end()) return x->p = inf, 0;
        if (x->k == y->k) x->p = x->m < y->m ? inf : -inf; 
        else x->p = div(y->m - x->m, x->k - y->k);
        return x->p >= y->p;
    }
    void add(ll k, ll m) {
        auto z = insert({k, m, 0}), y = z++, x = y;
        while (isect(y, z)) z = erase(z);
        if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
        while ((y = x) != begin() && (--x)->p >= y->p)
            isect(x, erase(y));
    }
    ll query(ll x) {
        assert(!empty());
        auto l = *lower_bound(x);
        return l.k * x + l.m;
    }
};

void solve() {
    int n;
    cin >> n;
    vector <pll> a(n), v;
    vector <ll> dp(n+1);
    for(int i = 0; i < n; i++) {
        ll x, y;
        cin >> x >> y;
        y = abs(y);
        a[i] = {x-y, x+y};
    }
    sort(all(a), [](pll x, pll y) {
        if(x.fi == y.fi) return x.se > y.se;
        return x.fi < y.fi;
    });
    v.eb(0, -LINF);
    for(int i = 0; i < n; i++) {
        if(v.back().se < a[i].se) v.eb(a[i]);
    }
    n = v.size()- 1;
    LineContainer CHT;
    for(int i = 1; i <= n; i++) {
        CHT.add(-2 * v[i].fi, v[i].fi * v[i].fi + dp[i-1]);
        dp[i] = CHT.query(v[i].se) + v[i].se * v[i].se;
    }
    cout << (double)dp[n] / 2 << '\n';
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    cout << fixed; cout.precision(1);

    int q;
    cin >> q;
    while(q--) {
        solve();
    }
}