けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 130 F - Minimum Bounding Box (600 点)

時刻  t に対する面積関数  f(t) の最小化問題。
全体で三分探索をするのは嘘。

問題へのリンク

問題概要

二次元平面上に  N 個の点がある。各点は初期位置から出発して秒速 1 の速度で上下左右のいずれかに動いている。

このとき、 N 点の  (x_{\max} - x_{\min}) \times (y_{\max} - y_{\min}) の値の最小値を求めよ。

制約

  •  1 \le N \le 10^{5}

考えたこと

シンプルな設定で面白い。二次元平面の問題だと割と x 軸方向と y 軸方向とが独立に考察できるケースが多いけど、今回ばかりは難しそう。でもそれでも個別に考えるとよいことがある。

  •  x_{\max} - x_{\min} の変化の仕方が変わる瞬間は、実はそう多くはなく、その間は「2 ずつ減少」「1 ずつ減少」「変化なし」「1 ずつ増加」「2 ずつ増加」のいずれかになる。
  • y についても同じ

ということがわかる。これらのことから、求める面積は

  • たかだか有限個の「二次関数」または「線分」を区分的につないだもの

であることがわかる。そして僕は慎重になって、二次関数の場合は極値をちゃんと求めてそれも解候補に入れたりしていたのだが、その必要はなかった

  • len(x) も len(y) も単調非減少なら区間の始点で最小
  • len(x) も len(y) も単調非増加なら区間の終点で最小
  • len(x) が単調減少、len(y) が単調増加なら、上に凸なので区間の始点終点のどちらかが最小

というわけで、区間の両端点でしか最小とはなりえないのだ。よって問題は、「いかにしてイベントを列挙するか」に帰着された。

イベント列挙

 x_{\max} にとりあえず焦点を当ててみる。

  • 'U' か 'D' な頂点の最右値
  • 'L' な頂点の最右値
  • 'R' な頂点の最右値

しか  x_{max} にはなりえないことを思うと、これらの順位が入れ替わる地点がイベント地点だということになる。同様のことは  x_{\min} y_{\max},  y_{\min} にも言える。こうしてイベント変化点を列挙したら、それらについて面積を計算すれば OK。

#include <iostream>
#include <vector>
#include <iomanip>
#include <cmath>
#include <algorithm>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

const long long INF = 1LL<<60;
int N;
vector<double> x, y;
vector<char> d;

double area(double t) {
    double xmi = INF, xma = -INF, ymi = INF, yma = -INF;
    for (int i = 0; i < N; ++i) {
        double cx, cy;
        if (d[i] == 'L') cx = x[i] - t, cy = y[i];
        else if (d[i] == 'R') cx = x[i] + t, cy = y[i];
        else if (d[i] == 'U') cx = x[i], cy = y[i] + t;
        else cx = x[i], cy = y[i] - t;
        chmin(xmi, cx);
        chmax(xma, cx);
        chmin(ymi, cy);
        chmax(yma, cy);
    }
    return (xma - xmi) * (yma - ymi);
}

double solve() {
    vector<double> alt;
    alt.push_back(0);

    // 左
    {
        double mi1 = INF; // L
        double mi2 = INF; // R
        double mi3 = INF; // UD
        for (int i = 0; i < N; ++i) {
            if (d[i] == 'L') chmin(mi1, x[i]);
            else if (d[i] == 'R') chmin(mi2, x[i]);
            else chmin(mi3, x[i]);
        }
        if (mi1 < INF && mi2 < INF) alt.push_back( abs(mi1 - mi2) / 2 );
        if (mi1 < INF && mi3 < INF) alt.push_back( abs(mi1 - mi3) );
        if (mi2 < INF && mi3 < INF) alt.push_back( abs(mi2 - mi3) );
    }
    
    // 右
    {
        double ma1 = -INF; // L
        double ma2 = -INF; // R
        double ma3 = -INF; // UD
        for (int i = 0; i < N; ++i) {
            if (d[i] == 'L') chmax(ma1, x[i]);
            else if (d[i] == 'R') chmax(ma2, x[i]);
            else chmax(ma3, x[i]);
        }
        if (ma1 > -INF && ma2 > -INF) alt.push_back( abs(ma1 - ma2) / 2 );
        if (ma1 > -INF && ma3 > -INF) alt.push_back( abs(ma1 - ma3) );
        if (ma2 > -INF && ma3 > -INF) alt.push_back( abs(ma2 - ma3) );
    }
    
    // 下
    {
        double mi1 = INF; // D
        double mi2 = INF; // U
        double mi3 = INF; // 
        for (int i = 0; i < N; ++i) {
            if (d[i] == 'D') chmin(mi1, y[i]);
            else if (d[i] == 'U') chmin(mi2, y[i]);
            else chmin(mi3, y[i]);
        }
        if (mi1 < INF && mi2 < INF) alt.push_back( abs(mi1 - mi2) / 2 );
        if (mi1 < INF && mi3 < INF) alt.push_back( abs(mi1 - mi3) );
        if (mi2 < INF && mi3 < INF) alt.push_back( abs(mi2 - mi3) );
    }
    // 上
    {
        double ma1 = -INF; // U
        double ma2 = -INF; // D
        double ma3 = -INF; // 
        for (int i = 0; i < N; ++i) {
            if (d[i] == 'D') chmax(ma1, y[i]);
            else if (d[i] == 'U') chmax(ma2, y[i]);
            else chmax(ma3, y[i]);
        }
        if (ma1 > -INF && ma2 > -INF) alt.push_back( abs(ma1 - ma2) / 2 );
        if (ma1 > -INF && ma3 > -INF) alt.push_back( abs(ma1 - ma3) );
        if (ma2 > -INF && ma3 > -INF) alt.push_back( abs(ma2 - ma3) );
    }

    sort(alt.begin(), alt.end());
    alt.erase(unique(alt.begin(), alt.end()), alt.end());
    double res = INF;
    for (int i = 0; i < alt.size(); ++i) {
        double tmp = area(alt[i]);
        chmin(res, tmp);
    }
    
    return res;
}

int main() {
    cin >> N;
    x.resize(N), y.resize(N), d.resize(N);
    for (int i = 0; i < N; ++i) cin >> x[i] >> y[i] >> d[i];
    double res = solve();
    cout << fixed << setprecision(10) << res << endl;
}