Task 61_1. Дорожная служба

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

- Машина может обрабатывать тольку одну проезжую полосу дороги за один проезд. Все дороги прямые и с одной полосой в каждом направлении.

- Машина может поворачивать на любом перекрестке в любую сторону, также может развернуться.

- Машина при обработке едет со скоростью 20 км/час, в обычном режиме - 50 км/час.

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

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

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

Даны координаты гаража (начальной точки) - x, y. 

Массив, каждый элемент ктр это координаты начала и конца дороги.

Напишите функцию, ктр вернет значение минимального времени (в минутах, округлите до целого), необходимое для обработки всех дорог и возврата обратно.

Пример:

x = 0, y = 0,

Arr = [ 

{ start: { x = 0, y = 0 }, end: { x = 10000, y = 10000 }},

{ start: { x = 5000, y = -10000 }, end: { x = 5000, y = 10000 }},

{ start: { x = 5000, y = 10000 }, end: { x = 10000, y = 10000 }}

]

Вывод: ~235 минут

Реализация:

1. @mikhail_01, реализация на Python. Довольно обьемное решение, обход дерева через рекурсию.

https://gist.github.com/unilecs/715d901961ad2e5fe9a191194d9ac2ce

2. @RuSHAru, реализация на PHP

https://gist.github.com/unilecs/5996da1f6ec4c9a56aa6a0e9922a80e6

3. @lPestl, реализация на Ruby

https://gist.github.com/lpestl/ab593d011559aea82cda08726571bc72

4. Антон, реализация на Rust

https://gist.github.com/AnthonyMikh/68cbd1c6e9d0fb7b5fdb1e69fff7f99b

Тест:

https://play.rust-lang.org/?gist=28da39035581ef6a5511775dd8589e3b&version=stable