New Year Contest 2015 L - 机のしみ

複素数は奥深いなぁ

問題文

$N$ 個の点が与えられる． $i (1 \le i \le N)$ 番目の座標は $(x_i, y_i)$ である．
これらの点の集合にいくつか点を追加して， $K \times K$ の正方格子を構成したい．
追加すべき点の個数の最小値は?

解法

$N = 1$ なら，すでに正方格子なので答えは $0$ です．
以下， $N \ge 2$ とします．
与えられた点が正方格子状に並んでいることが重要なので，与えられたある点を基準とした相対座標 $(x^{\prime}_i, y^{\prime}_i)$ を考えます．
ここでは， $1$ 番目の点を基準として， $(x^{\prime}_i, y^{\prime}_i) = (x_i - x_1, y_i - y_1)$ とします．
ここで，複素平面を考えると，正方格子の基底を $g$ とすると，相対座標は次のように表すことができる．
$z^{\prime}_i = x^{\prime}_i + y^{\prime}_ii = c_ig$ とかける．ここで， $c_i = u_i + v_ii$ は複素数である．
正方格子であることを考えると， $c_i$ の実部と虚部は整数である必要があるので， $c_i$ はガウス整数である．
また，入力の制約から $z^{\prime}_i$ もガウス整数である．
求めたい正方格子の1辺の長さは大きい方が良いため，条件を満たす $g$ の中でノルム最大のものを見つけたい．
つまり，求めたい $g$ は $z^{\prime}_i (1 \le i le N)$ の最大公約数である．
ガウス整数上での最大公約数は定義できるのか?
最大をノルム最大ということにすれば定義できて，同伴による違いを無視すると素因数分解の一意性から一意に定まる．
ということで，ガウス整数に対するユークリッドの互除法を計算すると， $g$ が求まる．
剰余を求める際には，商が有理数になるので実部と虚部をそれぞれ最も近い整数に丸めれば良い．
その上で，剰余のノルムが除数のノルムより小さい剰余を選択する．
あとは， $g$ から $c_i$ を求めると， $K = \max(\max(u_i) - \min(u_i) + 1, \max(v_i) - \min(v_i) + 1)$ である．
答えは， $K^2 - N$ となる．