AOJ 1340 Directional Resemblance
-
まえがき
初見でかなり混乱したので書きました
そんなに厳密な説明じゃないです(覚え書き程度です)
-
問題内容
N個の3次元ベクトルが与えられる。
これらのベクトルは全てx軸方向、y軸方向、z軸方向に正である。
ベクトルのうち2つをとったとき、なす角の最小値と、最小値になるようなindexのpairを求めよ。
-
解法
問題を言い換えます。
まず、各ベクトルを、「原点を中心とする半径1の球の表面」に射影します。
(前述でベクトルv_iを点p_iに射影したとします。)
そうすると、2つのベクトルv_i,v_jのなす角の大きさは、点p_i,点p_jを最短距離で結ぶ球の弧の長さと比例します。さらにこの値は、点p_iと点p_jのユークリッド距離に比例します(最重要)。
結局、「球面上にN個の点が与えられるので、ユークリッド距離が最短の2点を求める」問題に言い換えられました。
あとは、最近点対(参照: https://compro.tsutaj.com//archive/190207_divcon.pdf )と同様にやります。具体的には、(z軸のことを忘れて)上のスライドのp37のように各点についてスリットを考え、この点とスリット内にある点それぞれについて、(z軸のことを思い出して)3次元空間上の距離を求めます。
「x,yの値が近いがzの値が違う点がめちゃくちゃある」みたいなときに計算量が崩壊しそうですが、「点が球面上にある」という条件が効いて(?)十分高速に動きました。
-
実装
https://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=6148187#1
-
おわりに
なにかあれば↓にお願いします。