Russian Code Cup

[_AliEn_]

Доброго времени суток!
В нашем университете вывесили объявление об этом самом состязании, и я как человек, считающий, что умею программировать, решил себя проверить. К моему стыду, больше двух задач из квалификационного тура (кстати, следующий - через сутки) прошлого года я решить не сумел (задачи А и B). Например, задача "Рельсы" (см. http://russiancodecup.ru/round/1/). Сколько голову не ломал, ничего разумного в голову не приходит. Прошу вас, умельцев, подкинуть идею, помочь зацепиться за решение этой и других задач!

[venco]

Сначала разбить все рельсы на группы с одинаковым направлением.
Затем в каждой группе определить положение рельс по перпендикулярному направлению, отсортировать и, взяв самую левую, перебрать все оставшиеся в качестве пары, проверить, разбиваются ли все рельсы группы на пары с этим расстоянием. В результате получится набор возможных расстояний между рельсами в группе.
Осталось найти пересечение наборов расстояний, и вернуть минимальное расстояние из пересечения.
Тут ещё можно оптимизировать, но этого алгоритма достаточно, чтобы уложиться в отведённое время, и ошибиться меньше шансов.

[Toucan]

Переехали в Программирование

[venco]

Да, считать лучше целочисленной векторной арифметикой, чтобы избежать ошибок округления.

[_AliEn_]

venco
Я не совсем понял, что означает "определить положение рельс по перпендикулярному направлению"..

[venco]

_AliEn_ в сообщении #576571 писал(а):

venco
Я не совсем понял, что означает "определить положение рельс по перпендикулярному направлению"..

Провести перпендикулярную ось, и определить координаты каждой рельсы на этой оси. На самом деле практически то же самое можно получить, используя целочисленное векторное произведение, чтобы не терять точность в double.