[問題案] Euclidean MST

[sakikuroe]

Problem name: Euclidean MST
Problem ID: euclideanmst

問題文

2次元平面上に $N$ 個の点が与えられる. $i$ 個目の頂点の座標は $(x_i,~y_i)$ である.

2点間の距離をユークリッド距離, つまり $\sqrt{(x_i - x_j)^{2} + (y_i - y_j)^{2}}$ で定義するときの, MSTを求めよ.

制約

• $1 \leq N \leq 200,000$
• $0 \leq x_{i},~y_{i} \leq 1,000$

解法

• ドロネーグラフの最小全域木を求める
• $O(N\log{N})$

参考

• [Tutorial] Voronoi Diagram and Delaunay Triangulation in O(n log n) with Fortune's Algorithm - Codeforces https://codeforces.com/blog/entry/85638
• ユークリッド最小全域木 https://www.slideshare.net/maroonrk/ss-65378126
• Euclidean minimum spanning tree - Wikipedia https://en.wikipedia.org/wiki/Euclidean_minimum_spanning_tree

入力

$N$
$x_0$ $y_0$
$x_1$ $y_1$
:
$x_{N - 1}$ $y_{N - 1}$

出力

$u_0$ $v_0$
$u_1$ $v_1$
:
$u_{N - 2}$ $v_{N - 2}$

解が複数存在する場合, どれを返しても構わない.

Note

• $0 \leq x_{i},~y_{i} \leq 1,000$ より $0 \leq x_{i},~y_{i} \leq 10^{9}$ の方が良い？

[SSRS-cp]

1000 とした理由は何かありますか？特に理由がなければ 10^9 のほうが良いと思います

[sakikuroe]

平面の座標で√付きの有理数が出てくる気がしていて、うまく大小比較できるのか分からなかったためです。
Static Convex Hull (3 dimensional) が $10^9$ とかで実装できるみたいなので大きい制約で良さそうです。

[maspypy]

√付きの有理数が出てくる気がしていて、うまく大小比較できるのか分からなかったためです

これは $10^9$ を $10^3$ にしたところで同様の問題は残ってしまう気がしまうのですが、どうでしょうか。

実数ジャッジについては、少なくとも現状は導入できる見込みがないので、問い方を考えるか、気長に待っていただくかになると思います。

[noshi91]

出力は整数なので良くて、内部で実数を使う時の精度を気にしているのだと思います。アルゴリズムを真面目に検討していないですが、整数範囲だけで書けるならそれでも良さそうです。

[maspypy]

整数で誤差なしで解く想定であれば、一番微妙なのは、三角形の外心に相当する計算ですか？
であれば有理数だけで、sqrt{} は出てこないような気がしています。
座標 10^9 だと分子分母が 10^{18} くらいで、128bit あれば比較できるかな。

[NachiaVivias]

必要な演算について、

• Fortune の方法で √ 付きの有理数の大小比較（程度のヤバい比較）を避ける方法は分かりません（見つかりません）でした。そういう比較があるという言及があるスライド（最後のページ）はありました。

• 分割統治のほうは「点 D は △ABC の外接円の内部にあるか？」が一番難しくて、 Wikipedia に載っている行列式で計算できるようです。（ $0 \leq x _ i,y _ i \leq X$ なら絶対値 $6 X^4$ 以下の 2 整数の大小比較で判定できる）

[NachiaVivias]

Problem ID: euclideanmst

docs/style.md によると euclidean_mst です。

[maspypy]

以下の制約にしようと考えています。準備で不都合があれば相談してください。

• $1\leq N\leq 200000$
• $-10^4\leq x_i,y_i\leq 10^4$

テストケース作りは、oupc2023 運営に頼めば、出題時に使った生成器をもらうことができるかもしれません。
ただし、あれ小数ジャッジだったから、誤差に厳しいケースとかは作られていない可能性があります。

[NachiaVivias]

作ります