結果

問題 No.960 マンハッタン距離3
ユーザー PachicobuePachicobue
提出日時 2019-12-23 17:32:14
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,288 ms / 2,000 ms
コード長 4,004 bytes
コンパイル時間 2,270 ms
コンパイル使用メモリ 211,864 KB
最終ジャッジ日時 2025-01-08 14:18:03
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 216
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using ll = long long;
int main()
{
    using pll = std::pair<ll, ll>;
    ll W, H;
    std::cin >> W >> H;
    auto enc   = [&](ll x, ll y) -> pll { return pll{x + y, y - x}; };
    auto dec   = [&](ll x, ll y) -> pll { return std::abs(x + y) % 2 == 1 ? pll{-1, -1} : pll{(x - y) / 2, (x + y) / 2}; };
    auto L1    = [&](ll x1, ll y1, ll x2, ll y2) { return std::abs(x1 - x2) + std::abs(y1 - y2); };
    auto is_in = [&](ll x, ll y) { return 1 <= y and y <= H and 1 <= x and x <= W; };
    int N;
    std::cin >> N;
    std::vector<ll> rxs(N), rys(N);
    for (int i = 0; i < N; i++) { std::cin >> rxs[i] >> rys[i]; }
    {
        std::set<ll> parity;
        for (int i = 0; i < N; i++) { parity.insert(std::abs(rxs[i] + rys[i]) % 2); }
        if (parity.size() == 2) { return std::cout << 0 << std::endl, 0; }
    }
    std::vector<ll> xs(N), ys(N);
    for (int i = 0; i < N; i++) { std::tie(xs[i], ys[i]) = enc(rxs[i], rys[i]); }
    auto is_ok = [&](ll x, ll y) {
        if (not is_in(x, y)) { return false; }
        std::set<ll> ds;
        for (int i = 0; i < N; i++) { ds.insert(L1(rxs[i], rys[i], x, y)); }
        return ds.size() == 1;
    };
    const ll ym = *std::min_element(ys.begin(), ys.end());
    const ll xm = *std::min_element(xs.begin(), xs.end());
    const ll yM = *std::max_element(ys.begin(), ys.end());
    const ll xM = *std::max_element(xs.begin(), xs.end());
    ll ps[]     = {xm + (yM - ym) / 2, xM - (yM - ym) / 2, (xm + xM) / 2, (xm + xM) / 2};
    ll qs[]     = {(ym + yM) / 2, (ym + yM) / 2, yM - (xM - xm) / 2, ym + (xM - xm) / 2};
    for (int i = 0; i < 4; i++) { std::tie(ps[i], qs[i]) = dec(ps[i], qs[i]); }
    if (xm == xM) {
        if (not is_ok(ps[0], qs[0]) or not is_ok(ps[1], qs[1])) { return std::cout << 0 << std::endl, 0; }
        ll ans = (W - ps[0] + 1) * (H - qs[0] + 1) + ps[1] * qs[1];
        if (N == 2) { ans += (ps[0] - ps[1] - 1); }
        return std::cout << ans << std::endl, 0;
    }
    if (ym == yM) {
        if (not is_ok(ps[2], qs[2]) or not is_ok(ps[3], qs[3])) { return std::cout << 0 << std::endl, 0; }
        ll ans = (W - ps[2] + 1) * qs[2] + ps[3] * (H - qs[3] + 1);
        if (N == 2) { ans += (ps[2] - ps[3] - 1); }
        return std::cout << ans << std::endl, 0;
    }
    std::set<pll> start;
    for (int i = 0; i < 4; i++) {
        if (is_ok(ps[i], qs[i])) { start.insert({ps[i], qs[i]}); }
    }
    ll ans = start.size();
    if (start.size() == 1) {
        const auto [p, q] = *start.begin();
        constexpr ll dx[] = {-1, -1, -1, 0, 0, 1, 1, 1};
        constexpr ll dy[] = {-1, 0, 1, -1, 1, -1, 0, 1};
        for (int i = 0; i < 8; i++) {
            ll inf = 0, sup = H + W;
            while (sup - inf > 1) {
                const ll mid = (inf + sup) / 2;
                const ll np = p + mid * dx[i], nq = q + mid * dy[i];
                (is_ok(np, nq) ? inf : sup) = mid;
            }
            ans += inf;
        }
    } else if (start.size() == 2) {
        const auto [p0, q0] = *start.begin();
        const auto [p1, q1] = *start.rbegin();
        constexpr ll dx[]   = {-1, -1, -1, 0, 0, 1, 1, 1};
        constexpr ll dy[]   = {-1, 0, 1, -1, 1, -1, 0, 1};
        for (int i = 0; i < 8; i++) {
            ll inf = 0, sup = H + W;
            while (sup - inf > 1) {
                const ll mid = (inf + sup) / 2;
                const ll np = p0 + mid * dx[i], nq = q0 + mid * dy[i];
                (is_ok(np, nq) and (np != p1 or nq != q1) ? inf : sup) = mid;
            }
            ans += inf;
        }
        for (int i = 0; i < 8; i++) {
            if (dx[i] != 0 and dy[i] != 0) { continue; }
            ll inf = 0, sup = H + W;
            while (sup - inf > 1) {
                const ll mid = (inf + sup) / 2;
                const ll np = p1 + mid * dx[i], nq = q1 + mid * dy[i];
                (is_ok(np, nq) ? inf : sup) = mid;
            }
            ans += inf;
        }
    }
    std::cout << ans << std::endl;
    return 0;
}
0