А ведь
Cave прав насчет необходимости более тщательной проработки задачки...
Не зря же в условии оговаривается целочисленность координат (лобовое решение достаточно универсально и может работать хоть на комплексной плоскости) и не уточняется количество станций. Думаю, необходимо найти способ
вычисления (именно вычисления) координаты станции по координатам поселков.
Предлагаю такую модельку. Разместим на железной дороге тележку и свяжем её пружинками одинаковой жесткости со всеми поселками, после чего минимизируем энергию системы. Идея в том, что абсцисса оптимально размещенной тележки после округления до ближайшего целого даст искомую координату железнодорожной станции (т.е., после оптимизации, энергию самой длинной пружины уже уменьшать будет некуда).
Просто нужно найти более аналитическое решение этой проблемы (чтобы не моделировать физику, а посчитать все в "один ход" по готовой формуле). Например, можно минимизировать энергию пружин с учетом привязки тележки к железной дороге смесью МНК и лагранжевых множителей. Но этот подход эквивалентен первоначальной идеи
ИС'а о проецировании на ось абсцисс центра тяжести облака поселков. Это неправильное решение, так как при этом теряются ординаты поселков, а они должны учитываться, например, как некоторые веса в выражении для энергии пружин.
То есть, если поселки расположены почти на прямой, параллельной железной дороге, то достаточно найти центр тяжести и спроецировать его на железную дорогу с последующим округлением. А вот если один из поселков сильно удален от железной дороги, то искомая станция будет находится не около проекции центра тяжести всех поселков, а около проекции этого самого удаленного поселка.
Какие идеи? Что можно использовать вместо центра тяжести? Ведь по-сути решается задача минимизации отклонения длины пружины от её среднего значения (мат. ожиданя), i.e. что-то вроде минимизации "дисперсии" расстояний от искомой станции до всех поселков.