結果

問題 No.3759 Watch Fireworks
コンテスト
ユーザー D M
提出日時 2026-10-28 15:35:31
言語 C++23
(gcc 15.3.0 + boost 1.92.0 + ACL)
コンパイル:
g++-15 -O2 -fplugin=/usr/lib/yukicoder/noavx512-gcc15.so -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 128 ms / 2,000 ms
+ 392µs
コード長 2,079 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,590 ms
コンパイル使用メモリ 334,412 KB
実行使用メモリ 8,064 KB
最終ジャッジ日時 2026-10-28 15:35:53
合計ジャッジ時間 6,166 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge5_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 46
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<pair<ll,ll>> P(n);

    ll minU = LLONG_MAX, maxU = LLONG_MIN;
    ll minV = LLONG_MAX, maxV = LLONG_MIN;

    for (int i = 0; i < n; i++) {
        ll x, y;
        cin >> x >> y;

        ll u = x + y;
        ll v = x - y;

        P[i] = {u, v};

        minU = min(minU, u);
        maxU = max(maxU, u);
        minV = min(minV, v);
        maxV = max(maxV, v);
    }

    // 一辺 m の正方形2個で覆えるか
    auto check = [&](ll m) -> bool {

        // 1人目の正方形を四隅に配置
        for (int a = 0; a < 2; a++) {
            for (int b = 0; b < 2; b++) {

                ll leftU = (a == 0 ? minU : maxU - m);
                ll leftV = (b == 0 ? minV : maxV - m);

                // 1人目が担当できない点の範囲
                ll loU = LLONG_MAX, hiU = LLONG_MIN;
                ll loV = LLONG_MAX, hiV = LLONG_MIN;

                for (auto [u, v] : P) {

                    // 1人目が担当できる
                    if (leftU <= u && u <= leftU + m &&
                        leftV <= v && v <= leftV + m) {
                        continue;
                    }

                    // 2人目が担当する点
                    loU = min(loU, u);
                    hiU = max(hiU, u);
                    loV = min(loV, v);
                    hiV = max(hiV, v);
                }

                // 残りが0点
                if (loU == LLONG_MAX) return true;

                // 残りが一辺 m の正方形に収まる
                if (hiU - loU <= m &&
                    hiV - loV <= m) {
                    return true;
                }
            }
        }

        return false;
    };

    // 答えの二分探索
    ll l = -1;
    ll r = max(maxU - minU, maxV - minV);

    while (r - l > 1) {
        ll m = l + (r - l) / 2;

        if (check(m)) r = m;
        else l = m;
    }

    cout << r << '\n';
}
0