No.325

象限ごとに考える.

以下は第1象限の場合であり, 他の象限については適宜 $x, y$ 軸に対して対称移動させておく.

$(x, y)$ のマンハッタン距離を $M(x, y)$ とする.

$M(x_1, y_1) \gt d$ のときは求める点はない. 以下 $M(x, y) \leq d$ とする.

$M(x_2, y_2) \leq d$ のときは長方形の内部のすべての点が求める点である. この数は $(x_2 - x_1 + 1)(y_2 - y_1 + 1)$ である. 以下 $M(x_2, y_2) \gt d$ とする.

$M(x_1, y_2) \gt d$ のときは $y \gt d - x_1$ に求める点はない. 以下 $y_2 = d - x_1$ とする.

$M(x_1, y_2) \lt d$ のときは $x \lt d - y_2$ の長方形の内部のすべての点が求める点である. この数は $(d - y_2 - x_1)(y_2 - y_1 + 1)$ である. 以下 $x_1 = d - y_2$ とする.

$M(x_2, y_1) \gt d$ のときは $x \gt d - y_1$ に求める点はない. 以下 $x_2 = d - y_1$ とする.

$M(x_1, y_2) \lt d$ のときは $y \lt d - x_2$ の長方形の内部のすべての点が求める点である. この数は $(d - x_2 - y_1)(x_2 - x_1 + 1)$ である. 以下 $y_1 = d - x_2$ とする.

以上の操作を行った後は残った長方形は正方形となり, $M(x, y) = d$ の直線は正方形の対角線となる. この中にある求める点の数は, $(x_2 - x_1 + 1)(x_2 - x_1 + 2) / 2$ となる.

すべての象限について上記の計算で求めた数を合計する.

ただし, 長方形が2つの象限にまたがっている場合は軸上の点を2回足しているのでこれを引く. また, 長方形が4つの象限にまたがっている場合は軸上の点を2回, 原点を4回足しているのでこれを引く.