[問題案] Euclidean MST

sakikuroe commented 1 year ago

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 commented 1 year ago

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

sakikuroe commented 1 year ago

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

maspypy commented 1 year ago

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

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

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

noshi91 commented 1 year ago

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

maspypy commented 1 year ago

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

NachiaVivias commented 1 year ago

必要な演算について、

Fortune の方法で √ 付きの有理数の大小比較（程度のヤバい比較）を避ける方法は分かりません（見つかりません）でした。そういう比較があるという言及があるスライド（最後のページ）はありました。
分割統治のほうは「点 D は △ABC の外接円の内部にあるか？」が一番難しくて、 Wikipedia に載っている行列式で計算できるようです。（ $0 \leq x i,y i \leq X$ なら絶対値 $6 X^4$ 以下の 2 整数の大小比較で判定できる）

NachiaVivias commented 1 year ago

Problem ID: euclideanmst

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

maspypy commented 7 months ago

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

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

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

NachiaVivias commented 2 months ago

作ります

yosupo06 / library-checker-problems

[問題案] Euclidean MST #916

問題文

制約

解法

参考

入力

出力

Note