zeyad_khattab's blog

By zeyad_khattab, history, 10 days ago, In English,

Can anyone explain the solution for this problem 102014F - Directional Resemblance ?

The problem basically says:

We are given N vectors in 3D and we want to find 2 vectors such that the angle between them is minimum.

 
 
 
 
  • Vote: I like it
  • +12
  • Vote: I do not like it

»
10 days ago, # |
  Vote: I like it -10 Vote: I do not like it

sort by polar angle?

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it
»
9 days ago, # |
Rev. 2   Vote: I like it +5 Vote: I do not like it

I solved that problem with a KD tree. Normalize the vectors, the distance will be proportional to the angle between them so you can use a KD tree to answer closest point.

Or you can use the same thing normalizing vectors in the sphere of same radius and solve it with the general idea for closest pairs (the idea in the editorial)