"Сатанинская" звезда

somewhere · 20 окт 2006, 14:43

Есть такая прога 3D World Map, так вот в ней есть списки городов с
координатами, численностью, ну и т.д. Выцепил я эту инфу, и стало
интересно, какой город имеет наибольшее число "расстояний" до других городов, равных 666, 6666 км., а также прочая статистика в духе доктора Мулдашева (если кто читал его произведения). Все это уже есть и работает, теперь вопрос...

Как найти города, образующие "сатанинскую" звезду?

Городов много, более 30000 ...
Какие будут идеи?

Daemon · 23 окт 2006, 18:39

А что собственно понимается по "Сатанинской" звездой? Какая-т фигура или просто набор векторов по 666.666км сходящихся к одной точке?

somewhere · 23 окт 2006, 19:48

Под этим понимается набор точек на шаре (земном), которые являются вершинами пятиконечной звезды. Не важно, какое расстояние будет между точками. Т.е. группа из пяти городов, которые лежат на окружности, каждые 72 градуса.

31 окт 2006, 18:00

Аналитическая геометрия - всему ответ! А вообще для таких задач daemon писать надо....

C_O_D_E · 12 май 2008, 21:17

Возникает вопрос, а сколько таких наборов может быть вообще?
И как вычислять окружность, если Земля имеет округлую форму(имеется ввиду, что окружностью может являться неправильное сечение Земли)?

somewhere · 12 май 2008, 23:47

Наборов на самом деле не очень много с учетом геометрии звезды, линии могут быть как прямыми, так и дугами окружности. На данный момент задача уже решена для обоих способов и существуют такие довольно крупные города, которые образуют сатанинскую звезду. Есть даже такие, которые являются центрами правильных многоугольников, вершины которого есть города с населением более 30К жителей. Подавляющее большинство имеют богатую культурную и религиозную историю. Остальным, видимо, еще предстоит многое пережить ))

C_O_D_E · 13 май 2008, 20:04

Если Вам не трудно, по возмодности приведите пару примеров. Мне действительно интересно!

somewhere · 16 май 2008, 20:58

Результаты к сожалению не сохранились. Зато сохранились прога и база данных. Когда я написал алгоритм расчета пятиконечной звезды для пяти точек и сделал полный перебор и расчет всех комбинаций из 33741 города, то при замере скорости работы я должен был получить ответ через 613 тыс. лет. Оптимизация на ассемблере не намного, в моем понимании, сократила срок ответа - всего около 120-150 тыс. лет. Поэтому алгоритм пришлось срочно менять и сильно упрощать. Сейчас оценка результата на AMD X2 6000+ в однопоточном режиме составляет около 80 часов. Однако в момент разработки сервер на работе, который постоянно работает, выполнил задачу почти за неделю. Поэтому придется немного подождать с ответом