柱を頂点，ビームを辺と見なすと，結果として得られるのは単純平面 \(2\) 部グラフである． このグラフ \(G\) の頂点数を \(N\)，辺数を \(M\)，面数を \(F\) とすると，オイラーの多面体定理

\[N - M + F = 2\]

から，\(M \le 2N - 4\) が従う． 何故なら，\(G\) の各面の境界は \(4\) 本以上の辺からなり，各辺は高々 \(2\) 個の面の境界にしかなれないため，\(4F \le 2M\) が成り立つからである．

一方で，四隅を結んでできる四角形から始めて，「四角形の内点を任意に選んで四角形の対角ペアの一方からその内点に \(2\) 本の線分を伸ばす」という操作を，領域を線分で区切って再帰的に繰り返すことができる． ここで，一方の対角ペアから内点に線分を伸ばしたときに四角形の辺と交わってしまう場合は，必ず他方の対角ペアから線分を伸ばせることに注意する． この操作により，内点 \(1\) つにつき \(2\) 本の辺を追加で張ることができ，初期状態が \(N = 4, M = 4\) であることから，\(M = 2N - 4\) を達成できる． したがってこれが最適である．

次に選ぶ内点を毎回乱択すれば，クイックソートの要領で期待 \(\mathrm{O}(N \log N)\) 時間の分割統治アルゴリズムが得られると期待され，実際の挙動も概ねその通りであるが，正当性は不明である．（証明できたよ！って人は教えてくださると嬉しいです．）

実装は多少重くなるかもしれないが，たとえば以下のような決定性アルゴリズムを考えれば，計算量の理論保証が得られる． 最初の四角形を左上隅から右下隅に向かう対角線で区切って，これを跨ぐ辺を張らないことにし，それぞれの三角形領域の内部ではこの対角線からの距離の昇順に格子点を処理することにする． このようにすれば，処理される内点は常に右上隅（あるいは左下隅）の格子点を含む四角形領域内に存在することが保証できる． そのような四角形全体を平衡二分探索木などで管理しておけば，それらのうちのどれに属するかを \(\mathrm{O}(\log N)\) 時間で見つけることができ，更新も併せて全体で \(\mathrm{O}(N \log N)\) 時間で計算できる．

余談

ジャッジも \(\mathrm{O}(N \log N)\) 時間である． ABC-G(Ex) にちょうどよいぐらい？