2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




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

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

 
 
 
 Re: Russian Code Cup
Сообщение25.05.2012, 23:39 
Аватара пользователя
Переехали в Программирование

 
 
 
 Re: Russian Code Cup
Сообщение25.05.2012, 23:46 
Да, считать лучше целочисленной векторной арифметикой, чтобы избежать ошибок округления.

 
 
 
 Re: Russian Code Cup
Сообщение26.05.2012, 12:56 
Аватара пользователя
venco
Я не совсем понял, что означает "определить положение рельс по перпендикулярному направлению"..

 
 
 
 Re: Russian Code Cup
Сообщение26.05.2012, 16:10 
_AliEn_ в сообщении #576571 писал(а):
venco
Я не совсем понял, что означает "определить положение рельс по перпендикулярному направлению"..
Провести перпендикулярную ось, и определить координаты каждой рельсы на этой оси. На самом деле практически то же самое можно получить, используя целочисленное векторное произведение, чтобы не терять точность в double.

 
 
 [ Сообщений: 6 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group