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.

# | User | Rating |
---|---|---|

1 | MiFaFaOvO | 3681 |

2 | Um_nik | 3567 |

3 | tourist | 3520 |

4 | maroonrk | 3421 |

5 | apiadu | 3397 |

6 | 300iq | 3317 |

7 | ecnerwala | 3309 |

8 | Benq | 3283 |

9 | LHiC | 3229 |

10 | TLE | 3223 |

# | User | Contrib. |
---|---|---|

1 | Errichto | 194 |

2 | antontrygubO_o | 192 |

3 | vovuh | 178 |

4 | pikmike | 177 |

5 | Radewoosh | 167 |

6 | tourist | 166 |

7 | Um_nik | 165 |

8 | ko_osaga | 163 |

8 | McDic | 163 |

10 | Geothermal | 158 |

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.

↑

↓

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/05/2020 18:48:48 (g1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

sort by polar angle?

And then the minimum has to be between 2 consecutive vectors ?

Yes. If you want to practice implementing: https://codeforces.com/contest/598/problem/C

Thanks

Those 2 problems are completely different...

How so? I didn't download the OPs problemset, but it does "minimum angle between all pairs of vectors is what they're looking for.

In the problemset the vectors in question are 3d...

http://neerc.ifmo.ru/trains/zurich/analysis/20170426.pdf

Google is your friend!

Thank you

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)