Там проблема, що в кластерах має бути не більш як N людей (за числом гелікоптерів). А кількість кластерів, де менше N людей, теж жорстко обмежена. Наприклад, якщо в гелікоптер влазить 2 людей, то ось вам карта (фактично на одній прямій):

(3 людини поруч) (1000 м) (1 людина) (100 м) (4 людини)

1 людина в центрі за будь-чим аналоговим буде тягнутися до 4 праворуч від неї; але розв'язок тут - навпаки, їй іти 500 метрів ліворуч (а одному з трьох - 500 метрів праворуч).
Мені здається, тут треба відрізати групи по N людей з країв множини; але тоді в результаті буде неповна група, вочевидь, неоптимальна. І як її далі балансувати по інших - я гадки не маю.

Доречі для результату беруть найдовший маршрут взагалі, а не суму найдовших маршрутів до кожного вертольота.
Тобто треба оптимізувати максимальне значення а не середнє.

А захисту нема, щоб твій код ті кому розшарив не ламали?

до речі, в принципі, метод Кластеризації к–середніх можна якось поміняти, щоб він шукав не загальне середнє значення, а максимальне. Тільки питання в тому, чи буде така модифікація алгоритму збіжною, і чи буде збігатися до оптимального значення

Дивно, що приклад ще не поламали. А то я вже майже натиснув був ctrl+s