eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Уборка снега

Уборка снега

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

Зимой, когда дни стают короче, а ночи длиннее, необходимо задуматься об уборке снега с улиц. Поскольку бюджет нашего города очень маленький, у нас в распоряжении только один снегоход. Несмотря на это дороги должны быть прочищены. И каждый раз, когда выпадает много снега, ночью снегоход нашего города выезжает со своего гаража и объезжает весь город, очищая дороги. Какое минимальное время нужно снегоходу, чтобы очистить все проезжие полосы всех дорог и вернуться назад?

При этом известно, что:

  • Снегоход может очищать только одну проезжую полосу дороги за один проход.

  • Все дороги прямые с одной полосой движения в каждом направлении.

  • Снегоход может поворачивать на любом перекрестке в любую сторону, а также может развернуться в тупике.

  • Во время очистки снега снегоход двигается со скоростью 20 км/час, и со скоростью 50 км/час по уже очищенной дороге.

  • Возможность проехать все дороги всегда существует.

Входные данные

Первая строка содержит два числа x и y (-30000x, y30000) - координаты ангара (в метрах), откуда начинает свое движение снегоход. Далее в каждой отдельной строке заданы координаты (в метрах) начала и конца улиц (по 4 числа в строке). В городе может быть до 100 улиц.

Выходные данные

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

Пример

Входные данные #1
0 0
0 0 10000 10000
5000 -10000 5000 10000
5000 10000 10000 10000
Выходные данные #1
3:55