問題概要

凸多角形 $P, Q$ と整数 $a, b, c, d$ があり、 $ac - bd = 1$ を満たしている。凸多角形 $R = aP + bQ, S = cP + dQ$ が与えられるので、条件を満たす $P, Q, a, b, c, d$ のうち、 $P, Q$ の面積の和の二倍の最小値を求めてください。ただし + はミンコフスキー和を表す。

解法

まず、ミンコフスキー和は、凸多角形をなす辺を順番に並べて偏角ソートしたものをマージソートすることで求まることが知られています。このことから、 $P + Q = R$ のうち、 $R, Q$ が分かっているとき $P$ を、つまり $R - Q$ を求めることができます。

ここで、 $R - S$ を考えてみましょう。線形性より、 $R - S$ が存在したとすると $R - S = (a - c)P + (b - d)Q$ が成り立ちます。このとき、引き算した部分が打ち消し合うことから、 $a' = a - c, b' = b - d$ としたとき、 $a'c - b'd = 1$ が引き続き成り立ちます。よって、 $R - S, S$ で問題を考えても答えは等しくなります。

引き算が出来る条件を考えましょう。これはそこまで難しくなく、単に $S$ の全ての辺に対して、同じ向きで長さが $S$ のそれ以上であるような辺が $R$ に存在していることです。引き算する向きは一意に定まります。

このユークリッドの互除法のような操作を繰り返すことで、最終的に引き算が行えなくなったとき、それらが $P, Q$ です。これは、引き算が行えないことと $a > c$ かつ $b \lt d$ (またはその逆) が同値であることと、それに加えて $a, b > 0$ が同時に成り立つことがないことから言えます。( $|ad - bc| > 1$ となってしまう)

よって、この操作が行えればこの問題が解けたことが分かりました。計算量については、ユークリッドの互除法と同様に座標が 2 回で半分以下になることから、 $O ( ( N + M ) \log X ) )$ です。(引き算をする際、一気に引ける限り引かないと計算量が $O((N+M)X)$ になりますが、テストケースが弱いので通ります。(一辺 1 の正方形と、その辺と平行な長さ 10 ^ 6 の辺を含んで頂点数 1000 の図形の組とかがたくさんあると死ぬ)

実装

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i, n) for(ll i = 0; i < (n); i++)
using P = vector<pair<ll, ll>>;

constexpr int type(ll x, ll y) {
    if(x == 0 and y == 0) return 0;
    if(y < 0 or (y == 0 and x > 0)) return -1;
    return 1;
}

bool arg_cmp(pair<ll, ll> x, pair<ll, ll> y) {
    int L = type(x.first, x.second), R = type(y.first, y.second);
    if(L != R) return L < R;
    ll X = x.first * y.second, Y = y.first * x.second;
    if(X != Y) return X > Y;
    return x.first < y.first;
}

long long solve(P &x, P &y, int second = 0) {
    bool flag = true;
    int j = 0;
    P ny;
    if(empty(x)) flag = false;
    for(auto &[a, b] : x) {
        while(j < y.size()) {
            auto &[c, d] = y[j];
            if(a * d == b * c and abs(a + b) <= abs(c + d)) { break; }
            ny.emplace_back(c, d);
            j++;
        }
        if(j == y.size()) {
            flag = false;
            break;
        }
        if(y[j].first - a or y[j].second - b) ny.emplace_back(y[j].first - a, y[j].second - b);
        j++;
    }
    while(j < y.size()) { ny.emplace_back(y[j++]); }
    if(flag)
        return solve(x, ny);
    else if(!second) { return solve(y, x, true); }

    ll res = 0;
    auto calc = [&](const P &x) {
        pair<ll, ll> p{};
        rep(i, x.size()) {
            pair<ll, ll> np(p.first + x[i].first, p.second + x[i].second);
            res += p.first * np.second - p.second * np.first;
            p = np;
        }
    };
    calc(x);
    calc(y);
    return res;
}

int main() {
    while(true) {
        int n, m;
        cin >> n >> m;
        if(!n) exit(0);
        auto get = [](int n) {
            P r(n);
            rep(i, n) cin >> r[i].first >> r[i].second;
            P res(n);
            rep(i, n) res[i] = pair(r[(i + 1) % n].first - r[i].first, r[(i + 1) % n].second - r[i].second);

            int k = min_element(begin(res), end(res), arg_cmp) - begin(res);
            rotate(begin(res), begin(res) + k, end(res));
            return pair(r, res);
        };
        auto [r, x] = get(n);
        auto [s, y] = get(m);

        ll res = solve(x, y);
        cout << res << endl;
    }
}

のいみのいみのいみのいみ

凸多角形の加法 (AOJ 1639)

問題概要

解法

実装