Вот такой http://users.livejournal.com/_darkus_/655190.html конкурс проводится автором русских книг по Haskell.
Задача:
«Демиург задумал поместить новую разумную расу на планету во Вселенной так, чтобы она как можно быстрее освоила весь доступный космос. Для этих целей он собрал перечень всех планет, находящихся в поясе Златовласки, после чего решил найти среди них две, наиболее близко расположенные друг к другу. Разумная раса должна быть расположена на одной из таких планет. Это, по замыслу Демиурга, позволит максимально быстро обеспечить освоение космоса. Помогите Демиургу найти две планеты, находящиеся на наименьшем расстоянии друг от друга.»
Суть — решить как можно более общно. Зачастую в конкурсе побеждают хаскеллисты, дабы разбавить эту статистику, мы решили разместить этот пост на цф :)
kd tree за O(n5 / 3), на рандоме за
.
http://en.wikipedia.org/wiki/K-d_tree
Должно отработать за пару минут.
Писать пока лень...
dist^2 = 11558
977464 250360 504213
977446 250385 504316
all done in 63078 ms
надеюсь нигде не напортачил в реализации))
upd. да, написание кода — где то час с вспоминанием как kd-tree вообще работает...
upd2. а я ведь напортачил. версия вроде без глюков теперь находит
dist^2 = 7393
637957 813791 458265
637999 813818 458335
all done in 32205 ms
но я пока еще погоняю на рандоме, запущу стресс тест)
upd3. http://pastie.org/4055843
Теперь сходится =) . Но у меня нет КД-дерева, просто сортировка по X и один проход с отсечением по расстоянию по X.
значит тест слабенький.
стресстест не нашел контртеста на 1000 рандомных тестов по 1000 вершин, значит мое kd-дерево без глюков) доволен там, что написал его, пишу 2й раз в жизни))
вроде еще есть тупой алгоритм бросания на рандомную прямую, работает за O(N3 / 2). видимо ты его и написал, и прямая y=0, z=0 тут оказалась рандомной :D
Понятно, что на случайных точках это работает быстро.
А при взгляде на файл не бросается в глаза какая-либо неслучайность координат точек.
да, согласен. увы, kd-дерево пришло мне в голову раньше, а про это решения я как то и не вспомнил.
Там меня что-то маркнули как спам, напишу сюда.
У меня получилось расстояние 85.982556... (Квадрат расстояния 7393).
Первая звезда 166820 (0-based): 637957 813791 458265.
Вторая звезда 342967 (0-based): 637999 813818 458335.
Язык C++.
Процесс решения занял 15-20 минут, программа работает чуть меньше пяти секунд (могу выложить куда-нибудь).
Комментарии помечаются как спам, чтобы их никто кроме автора блога не видел до конца конкурса.
637999 813818 458335
637957 813791 458265
85.9826
Аналогичный результат. Просто использовал http://e-maxx.ru/algo/nearest_points . http://pastebin.com/Ps3KQvzX
А ничего, что по ссылке 2D, а в задаче 3D?
там можно обобщить, но на первый взгляд это не совсем очевидно как
За nlog2n вроде очевидно. А за nlogn — там какая-то магия. Там какая-то внезапная теорема нужна, про то что есть измерение в котором что-то-там будет маленьким.
ну я пока за
и обобщил. такой сложности уже хватает.
Вроде же есть несложное обобщение за O(N * log2N). Делаем все так же, как в 2D, при слиянии двух полупространств получаем некоторую область, заключенную между двумя параллельными плоскостями небольшой ширины, а в этой области решаем задачу почти как в 2D.
да, именно оно
Казалось бы, причём тут ФП?..
ФП ФП ФП...
http://it-talk.org/topic15619.html
а задача то NP-полная. мужики то и не знают...
Сортировка по расстояние от удалённой на "Ура" заходит...
Хватает посмотреть 80 в каждую сторону.
Что-то не так... :D
Ну, лэндмарки всегда хорошо работали на рандоме, все в порядке :)