 |
|
|
||||||||||||||||||||
Решение задачАвиалинииПри решении данной задачи можно было использовать достаточно эффективный алгоритм Флойда для начального построения матрицы кратчайших расстояний между городами (при этом в качестве "бесконечного" расстояния использовалось просто очень большое целое число). Далее при добавлении очередной авиалинии данная матрица пересчитывается (некоторые участники и для пересчета матрицы кратчайших расстояний использовали алгоритм Флойда "в лоб", что несколько замедляло работу программы, но приводило к нужному результату). Ограничение на время тестирование вводилось для того, чтобы отсечь неэффективные алгоритмы решения задачи (часто участники использовали разнообразные алгоритмы пересчета расстояний, но они либо не работали со сложными тестами, либо явно не укладывались во временные ограничения). Луч света в углуПри решении данной задачи можно было воспользоваться таким соображением: рассмотрим многократное отражение самого угла. При этом траектория отражающегося луча света (ломаная линия) перейдет в прямую, пересекающую стороны "размноженного" угла. При этом точки пересечения уже прямого луча с прямыми, образующими стороны углов, соответствуют точкам отражения данного луча света от сторон данного в условии угла, а количество точек пересечения соответствует количеству отражений (именно отсюда следует тот факт, что количество точек конечно, а для приведенных в задаче ограничений не превосходит 179).
При этом нас при решении будет интересовать как раз количество пересечений (а значит, и отражений) и координаты точки последнего пересечения (по которой легко восстановить точку последнего отражения). Заметим, что этим будет достигаться и большая точность по сравнению с прямым пересчетом точек отражения, так как погрешность не будет накапливаться.
Со всеми вопросами обращайтесь:
|
||||||||||||||||||||||
