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.
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | ecnerwala | 3649 |
| 2 | Benq | 3581 |
| 3 | orzdevinwang | 3570 |
| 4 | Geothermal | 3569 |
| 4 | cnnfls_csy | 3569 |
| 6 | tourist | 3565 |
| 7 | maroonrk | 3531 |
| 8 | Radewoosh | 3521 |
| 9 | Um_nik | 3482 |
| 10 | jiangly | 3468 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 164 |
| 3 | adamant | 163 |
| 4 | TheScrasse | 159 |
| 5 | nor | 158 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 151 |
| 8 | SecondThread | 147 |
| 9 | orz | 146 |
| 10 | pajenegod | 145 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 25.04.2024 18:28:37 (l2).
Десктопная версия, переключиться на мобильную.
При поддержке
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)