(雑です。後でしっかりしたものになるかもしれません。)

答えで二分探索して、「答えを \(a\) 以下にできるか？」を解きます。

また、x座標とy座標は独立に考えて何ら支障がないので、分離します。

そうすると、以下の問題を解くことになります。

長さ \(N\) の数列 \(A\) がある。\(f(x)=\sum_{i \in A} \max(0,i-x)+\max(0,x-(i+a))\) の最小値を求めよ。

これは、Slope Trickというデータ構造(テクニック？)を使用して高速に解くことが可能です。

(追記: \(2N\) 個の座標の中央値を求める方が賢いです。)