yukicoder No.325 マンハッタン距離2

問題

No.325 マンハッタン距離2 - yukicoder

解法

落ち着いて場合分けをします。

頂点の数え方としては,
(第一象限の点の数) + (第二象限の点の数) + (第三象限の点の数) + (第四象限の点の数) - (x 軸の点の数) - (y 軸の点の数) + (原点の点の数)
という数え方をします。

下のソースコードでは 象限の点の数は calc 関数で, 軸の点の数は calc2 関数でやっています。

calc 関数は, 原点 (0, 0) から頂点 (x, y) までの長方形で, マンハッタン距離が d 以下の頂点数がいくつあるかを調べます。
これは, d の値で適当に場合分けすればいけます。

calc 関数を使って第一象限の(x1, y1) から (x2, y2) の長方形内の頂点数を求めることを考えます。
まず, x2 >= 0, y2 >= 0 でないとダメですね。で, dx = max(0, x1), dy = max(0, y1) とすると, calc 関数で「原点(0, 0) から」と書かれているところで, 実際には左下の頂点が どの座標かがわかります。つまり (dx, dy) から (x2, y2) への頂点数を求めれば良いわけです。
左下の頂点が (dx, dy) になったので, 原点が左下として考えるときは, 距離 d を d-dx-dy にしないといけません。これに注意して, calc 関数を使います。

第二象限以降も同じです。

ull calc(ll x, ll y, ll d) {
    ull ret = 0;
    if (d <= y) {
        if (d <= x) {
            ret = (d+2)*(d+1)/2;
        } else {
            ret = (d+d-x+2)*(x+1)/2;
        }
    } else if (d-y <= x) {
        ret = (y+1)*(d-y+1);
        if (d >= x) {
            ret += (y + d-x+1) * (x-d+y) / 2;
        } else {
            ret += y*(y+1)/2;
        }
    } else {
        ret += (y+1)*(x+1);
    }
    return ret;
}

ull calc2(ll low, ll high, ll d) {
    ll mini = max(low, -d);
    ll maxi = min(d, high);
    return maxi-mini+1;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll x1, y1, x2, y2, d;
    cin >> x1 >> y1 >> x2 >> y2 >> d;
    ull ans = 0;
    if (y2 >= 0 && x2 >= 0) {
        ll dx = max<ll>(0, x1);
        ll dy = max<ll>(0, y1);
        if (d-dx-dy >= 0) ans += calc(x2-dx, y2-dy, d-dx-dy);
    }
    //cout << ans << endl;
    if (y2 >= 0 && x1 <= 0) {
        ll dx = max<ll>(0, -x2);
        ll dy = max<ll>(0, y1);
        if (d-dx-dy >= 0) ans += calc(-x1-dx, y2-dy, d-dx-dy);
    }
    //cout << ans << endl;
    if (y1 <= 0 && x1 <= 0) {
        ll dx = max<ll>(0, -x2);
        ll dy = max<ll>(0, -y2);
        if (d-dx-dy >= 0) ans += calc(-x1-dx, -y1-dy, d-dx-dy);
    }
    //cout << ans << endl;
    if (y1 <= 0 && x2 >= 0) {
        ll dx = max<ll>(0, x1);
        ll dy = max<ll>(0, -y2);
        if (d-dx-dy >= 0) ans += calc(x2-dx, -y1-dy, d-dx-dy);
    }
    //cout << ans << endl;
    if (x1 <= 0 && 0 <= x2) ans -= calc2(y1, y2, d);
    //cout << ans << endl;
    if (y1 <= 0 && 0 <= y2) ans -= calc2(x1, x2, d);
    //cout << ans << endl;
    if (x1 <= 0 && 0 <= x2 && y1 <= 0 && 0 <= y2) ans--;
    cout << ans << endl;
    return 0;
}