JAG 夏合宿 Day3 G - Share the Ruins Preservation

問題

jag2016autumn.contest.atcoder.jp

二次元平面上に点が N 個与えられる。ある X 座標を境に二つの頂点を分割し, それぞれで凸包を作る。この二つの凸包の面積の和を最小化せよ。

解法

蟻本に載っている凸包は, 凸包の下側と上側に分けて凸包を構成します。上側の凸包を構成するのは, y 座標の上下を逆転させて下側の凸包を構成するのと同じようにできます。よって, 下側凸包を構成しながらそれぞれの凸包の面積を更新していく, というように計算すれば, O(N log N) で

• X 座標の左から見ていった下側凸包
• X 座標の左から見ていった上側凸包(Y 座標を -1 倍すれば良い)
• X 座標の右から見ていった下側凸包(X 座標を -1 倍すれば良い)
• X 座標の右から見ていった上側凸包(X, Y 座標を -1 倍すれば良い)

の面積をそれぞれ計算できます。これを適当に組み合わせて最小値を求めましょう。

すこし注意なのは, 点をソートすべきタイミングです。X 座標の左側から凸包を考えている際, Y 座標を -1 倍した後にソートしてしまうと, 点の位置関係がずれる可能性があるのでソートしてはいけません。

typedef long long Real;

struct P {
    Real x, y;
    P() {}
    P(Real x, Real y) : x(x), y(y) {}
    P operator-(P p) const {return P(x-p.x, y-p.y);}
    Real det(P p) const {return x*p.y-y*p.x;} // 外積
    bool operator<(const P& rhs) const {
        if (x != rhs.x) return x < rhs.x;
        return y < rhs.y;
    }
};

ll triArea(const P& x, const P& y, const P& z) {
    return abs((y-x).det(z-x));
}

// 下側凸包の面積を求める
vector<ll> convex_hull(vector<P> ps) {
    int n = ps.size();
    int k = 0;         // 凸包の頂点数
    vector<P> qs(n); // 構築中の凸包
    vector<ll> area(n+1);
    // 下側凸包の作成
    for (int i = 0; i < n; i++) {
        area[i+1] = area[i];
        while (k > 1 && (qs[k-1]-qs[k-2]).det(ps[i]-qs[k-1]) < 0) {
            if (k >= 3) area[i+1] -= triArea(qs[0], qs[k-2], qs[k-1]);
            k--;
        }
        if (k >= 2) area[i+1] += triArea(qs[0], qs[k-1], ps[i]);
        qs[k++] = ps[i];
    }
    return area;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    vector<P> ps(N);
    for (int i = 0; i < N; i++) {
        cin >> ps[i].x >> ps[i].y;
    }
    sort(ps.begin(), ps.end());
    auto lb = convex_hull(ps);
    for (int i = 0; i < N; i++)
        ps[i].y *= -1;
    auto lu = convex_hull(ps);
    for (int i = 0; i < N; i++) 
        ps[i].x *= -1;
    sort(ps.begin(), ps.end());
    auto ru = convex_hull(ps);
    for (int i = 0; i < N; i++)
        ps[i].y *= -1;
    auto rb = convex_hull(ps);
    for (int i = 0; i < N; i++)
        ps[i].x *= -1;
    sort(ps.begin(), ps.end());
    ll ans = lb[N] + lu[N] + ru[0] + rb[0];
    for (int i = 1; i < N; i++) {
        if (ps[i-1].x == ps[i].x) continue;
        // cout << i << endl;
        // cout << lb[i] << " " << lu[i] << " " << rb[N-i] << " " << ru[N-i] << endl;
        ll tmp = lb[i] + lu[i] + ru[N-i] + rb[N-i];
        ans = min(ans, tmp);
    }
    cout << (ans+1)/2 << endl;
    return 0;
}