heno239’s blog

まとめたいことをまとめる

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

 

  • おわりに

なにかあれば↓にお願いします。

twitter.com