ABC130 F問題：Minimum Bounding Box

問題. Minimum Bounding Box

平面上に $n$ 個の点がある．時刻 0 のときの $i$ 番目の点の座標を $(x_i, y_i)$ とする．各点は時刻 0 から秒速 1 で決まった方向に同時に動き出す．ただし，動く方向は軸並行に左右上下のいずれか一方向のみである（または動かない）．ある時刻での各点の $x$ 座標と $y$ 座標の最小値と最大値をそれぞれ $x_{\min}, x_{\max}, y_{\min}, y_{\max}$ としたとき，そのときの値を $(x_{\max} - x_{\min}) \times (y_{\max} - y_{\min})$ とする．この値としてとりうる最小値を求めよ．

制約： $1 \le N \le 10^5$ ，　 $-10^8 \le x_i, y_i \le 10^8$

解法．三分探索

三分探索で解く．

関数 $f_{x, i} (t)$ を時刻 $t$ での $i$ 番目の点の $x$ 座標とする． $f_{x, i}$ は傾きが -1, 0, 1 のいずれかで，切片が $x_i$ の直線となる．したがって，これらの最大値 $x_{\max} (t) = \max_{1 \le i \le n} f_{x, i} (t)$ は凸関数となり，これらの最小値 $x_{\min} (t) = \min_{1 \le i \le n} f_{x, i} (t)$ は凹関数となる．よって， $x_{\max} - x_{\min}$ は凸関数同士の和となり凸関数である（凹関数 $x_{\min}$ の $- x_{\min}$ は凸関数）．また，この関数の値は非負である．したがって， $x_{\max} - x_{\min}$ は非負の値をとる区分線形凸関数となる．同様に， $y$ 軸についても考えると $y_{\max} - y_{\min}$ は非負の値をとる区分線形凸関数となる．

ここで，非負の値をとる2つの区分線形凸関数を $g_x = x_{\max} - x_{\min}, g_y = y_{\max} - y_{\min}$ とする．あとは， $g_x \times g_y$ の最小値を求めればよい． $g_x$ と $g_y$ は区分線形関数なので， $g_x \times g_y$ の各区間は二次関数となる（∵ $(a_1 x + b_1) \times (a_2 x + b_2)$ は2点 $- \frac{b_1}{a_1}, -\frac{b_2}{a_2}$ を通る二次関数）．
具体的に調べるべき区間は，与えられた点を移動方向で3つに分類したときに座標の最小値と最大値を与える点だけが重要で，それらの点が交差する時刻を昇順に並べたときの隣り合う時刻のすべての区間に対して三分探索で二次関数の最小値を求めればよい．各座標で移動方向は 3 パターンあり，それぞれの最小値と最大値を与える点の数は高々 2 個なので，調べるべき区間は高々 $2 \binom{6}{2} = 30$ 通りしかない．

正しいアルゴリズムのソースコードを表示

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

int main() {
    cin.tie(0); ios::sync_with_stdio(false);
    cout << setprecision(10) << setiosflags(ios::fixed);

    int n;
    cin >> n;

    // xy[0] = -, xy[1] = 0, xy[2] = +
    // xy[i][0] は最小値，xy[i][1] は最大値
    vector<vector<double>> x(3), y(3);
    for (int i = 0; i < n; ++i) {
        double xx, yy;
        char d;
        cin >> xx >> yy >> d;

        int idx_x = 1, idx_y = 1;
        if (d == 'R') idx_x = 2;
        else if (d == 'L') idx_x = 0;
        else if (d == 'U') idx_y = 2;
        else if (d == 'D') idx_y = 0;

        if (x[idx_x].size() == 0) { x[idx_x].push_back(xx); x[idx_x].push_back(xx); }
        else { x[idx_x][0] = min(x[idx_x][0], xx); x[idx_x][1] = max(x[idx_x][1], xx); }

        if (y[idx_y].size() == 0) { y[idx_y].push_back(yy); y[idx_y].push_back(yy); }
        else { y[idx_y][0] = min(y[idx_y][0], yy); y[idx_y][1] = max(y[idx_y][1], yy); }
    }

    vector<double> times = {0};
    for (auto x_i : x[0]) for (auto x_j : x[1]) if (x_j < x_i) times.push_back(x_i - x_j); // x_i - t = x_j
    for (auto x_i : x[0]) for (auto x_j : x[2]) if (x_j < x_i) times.push_back(0.5 * (x_i - x_j)); // x_i - t = x_j + t
    for (auto x_i : x[1]) for (auto x_j : x[2]) if (x_j < x_i) times.push_back(x_i - x_j); // x_i = x_j + t

    for (auto y_i : y[0]) for (auto y_j : y[1]) if (y_j < y_i) times.push_back(y_i - y_j);
    for (auto y_i : y[0]) for (auto y_j : y[2]) if (y_j < y_i) times.push_back(0.5 * (y_i - y_j));
    for (auto y_i : y[1]) for (auto y_j : y[2]) if (y_j < y_i) times.push_back(y_i - y_j);

    sort(times.begin(), times.end());


    const double INF = numeric_limits<double>::max();
    const double NINF = numeric_limits<double>::lowest();

    // 区間内では f は二次関数（または一次関数）
    auto f = [&](const double t) {
        pair<double, double> seg_x(INF, NINF), seg_y(INF, NINF);

        for (int i = 0; i < 3; ++i) {
            for (auto x_i : x[i]) {
                seg_x.first = min(seg_x.first, x_i + (i - 1) * t);
                seg_x.second = max(seg_x.second, x_i + (i - 1) * t);
            }
            for (auto y_i : y[i]) {
                seg_y.first = min(seg_y.first, y_i + (i - 1) * t);
                seg_y.second = max(seg_y.second, y_i + (i - 1) * t);
            }
        }
        return (seg_x.second - seg_x.first) * (seg_y.second - seg_y.first);
    };

    // 定義域の区間 [times[i], times[i + 1]] ごとに f の最小値を三分探索で求める
    double min_v = f(0);
    for (size_t i = 0; i + 1 < times.size(); ++i) {
        double lb = times[i], ub = times[i + 1];

        for (int i = 0; i < 200; ++i) {
            const double t1 = (2.0 * lb + ub) / 3.0;
            const double t2 = (lb + 2.0 * ub) / 3.0;

            if (f(t1) > f(t2)) lb = t1;
            else ub = t2;
        }
        min_v = min(min_v, f(lb));
    }

    cout << min_v << endl;

    return 0;
}

　
==========================================================================
下の説明は未証明（本当か嘘か分からない）
$g_x \times g_y$ は単峰関数（unimodal function）だと思うので，定義域を各区間ごとに分割して三分探索をせずに，十分大きな1つの区間として三分探索を行えば最小値が求まるはずなので，下の実装ではこの方針で AC した（たぶん反例がありそう）．

嘘っぽいソースコードを表示

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;

int main() {
    cin.tie(0); ios::sync_with_stdio(false);
    cout << setprecision(10) << setiosflags(ios::fixed);

    int n;
    cin >> n;

    vector<double> x(n), y(n), dx(n), dy(n);
    for (int i = 0; i < n; ++i) {
        char d;
        cin >> x[i] >> y[i] >> d;

        if (d == 'R') dx[i] = 1;
        else if (d == 'L') dx[i] = -1;
        else if (d == 'U') dy[i] = 1;
        else if (d == 'D') dy[i] = -1;
    }

    const double INF = numeric_limits<double>::max();
    const double NINF = numeric_limits<double>::lowest();

    auto f = [&](const ld t) {
        pair<double, double> seg_x(INF, NINF), seg_y(INF, NINF);

        for (int i = 0; i < n; ++i) {
            double vx = x[i] + t * dx[i], vy = y[i] + t * dy[i];

            seg_x.first = min(seg_x.first, vx);
            seg_x.second = max(seg_x.second, vx);
            seg_y.first = min(seg_y.first, vy);
            seg_y.second = max(seg_y.second, vy);
        }
        return (seg_x.second - seg_x.first) * (seg_y.second - seg_y.first);
    };

    double min_v = f(0), lb = 0, ub = 1e9;
    for (int i = 0; i < 200; ++i) {
        const double t1 = (2.0 * lb + ub) / 3.0;
        const double t2 = (lb + 2.0 * ub) / 3.0;

        min_v = min(min_v, f(t1));
        min_v = min(min_v, f(t2));

        if (f(t1) > f(t2)) lb = t1;
        else ub = t2;
    }

    cout << min_v << endl;

    return 0;
}