Здравствуйте Bell, Вы писали:

fAX>>Самое непонятное тут, как изначально организовать точки. Если какой-нибудь алгоритм (Форда, если не ошибаюсь) из теории графов для нахождения минимальных расстояний между всеми точками, то ему нужно O(n^3), а при входе O(10^5) это очень дорого, но в крайнем случае, подойдёт. Кроме того, как эффективно построить граф из массива точек.

fAX>>Какие-то идеи?

fAX>>Заранее спасибо,
fAX>>fAX.

B>Очень похоже на задачу коммивояжера. Для решения этой задачи используется симплекс-метод.
B>Алгоритм Форда же предназначен для поиска кратчайших путей между всеми вершинами графа. Причем эти не обязательно проходят через все вершины.
B>Или я неправильно понял постановку?

Утешили. . Она-то — NP-полная! Хотя и есть хорошие приближения. Вопрос тут и в том, насколько они хороши на входе 10^5+. Но основная проблема — построить граф, как я уже писал.