条件 \(|x-i| = |y-j|\) は 「\(x-i = y-j\) または \(x-i = -(y-j)\)」、すなわち

\[ y-x = i-j ~ または ~ x+y = i+j \]

に整理されます。\(y-x = i-j\) は右下方向、 \(x+y = i+j\) は右上方向の直線です。

そこで、「右下方向の直線によって塗られるマスの合計個数」と「右上方向の直線によって塗られるマスの合計個数」を求めてから、「右下方向の直線と右上方向の直線との交点になるマスの合計個数」を引くことでこの問題に答えることができます。

右下方向の直線によって塗られるマスの合計個数

\(-(L-1) \le d \le L-1\) について、\(y_i-x_i = d\) となる \((x_i, y_i)\) があれば、 \(L - |d|\) 個が塗られます。

これは、 \(k = 0\) でちょうど \(L\) 個塗られ、 \(d=-1, 1\) でちょうど \(L-1\) 個塗られ、 …、\(d=L-1\) では \(1\) 個しか塗られない、ということから導けます。

\(y_i-x_i = d\) となる \((x_i, y_i)\) が複数個あっても \(1\) 回しか数えないことに注意してください。

右上方向の直線によって塗られるマスの合計個数

\(0 \le s \le 2(L-1)\) について、 \(x_i+y_i = s\) となる \((x_i, y_i)\) があれば、 \(L - |s - (L-1)|\) 個が塗られます。

これは、 \(s = 0\) でちょうど \(1\) 個塗られ、 \(s=1\) でちょうど \(2\) 個塗られ、 \(s=L-1\) でちょうど \(L\) 個塗られてから今度は減少し、 \(s=L\) でちょうど \(L-1\) 個塗られ、… \(s=2L-2\) でちょうど \(1\) 個塗られる、ということから導けます。

交点のマスの合計個数

注意すべきは、交点の個数は最大で \(N^2\) 個オーダーになる点です。交点をすべて求めると実行時間に間に合わないため、工夫して交点の個数をすべて数え上げる必要があります。

右下方向に \(i-j = d\)、右上方向に \(i+j = s\) の直線があるとき、その交点の候補は

\[ i = \frac{s+d}{2}, j = \frac{s-d}{2} \]

です。これが \(0 \le i, j < L\) かつ \(i, j\) が整数であるとき、そのときだけ交点があります。

\(d\) を固定してみて、交点を持つような \(s\) の条件を求めます。

まず、 \(s+d\) は偶数でなくてはなりません。これは、 \(d\) と \(s\) の偶奇が一致することと同値です。

次に \(0 \le s+d, s-d < 2L\) を整理します。 \(d\) が負の場合・非負の場合をそれぞれ考えることによって、これは \(0 \le s-|d| \le s+|d| < 2L\) と同値です。よって、これは

\[ |d| \le s < 2L - |d| \]

と同値です。

以上から、次の結論が得られます：

\(y_i - x_i = d\) を満たす \((x_i, y_i)\) があるとする。 この \(d\) に対して交点を持つような \(s\) の個数は、 \(x_j + y_j = s\) を満たす \((x_j, y_j)\) が存在するような \(s\) のうち、 \(d\) と偶奇が同じ、かつ、 \(|d| \le s < 2L - |d|\) を満たすものの個数に等しい。

これは、まず前もって \(s\) の値を偶奇で分裂した配列を用意してそれぞれソートし、各 \(d\) に対しては \(d\) の偶奇に対応する配列を二分探索することによって求められます。ただし、配列内の \(s\) の要素はすべて相異なるようにすることに注意してください。

いま数えた交点たちはどれも相異なる点であることが分かるので、そのまま交点のマスの合計個数が求められます。時間計算量は \(O(N \log N)\) です。

実装例(C++)