Task 61. Дорожная служба
UniLecsЗадача: дорожным службам нужно обработать дороги антигололедным реагентом. В каждом районе только одна машина, она должна ночью обьехать все дороги этого района. Машина выезжает из гаража и должна туда же вернуться.
- Машина может обрабатывать тольку одну проезжую полосу дороги за один проезд. Все дороги прямые и с одной полосой в каждом направлении.
- Машина может поворачивать на любом перекрестке в любую сторону, также может развернуться.
- Машина при обработке едет со скоростью 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 минут
Идея: давайте рассмотрим граф, вершинами будем считать перекрестки и тупики улиц.
Так как каждая улица должна быть обработана с двух сторон, тогда получим, что степень каждой вершины графа будет четной. А поскольку возможность проехать все дороги всегда существует, то граф является связным.
Вспомним теорему Эйлера (смотри вики):
Связный неориентированный граф содержит Эйлеров цикл тогда и только тогда, когда количество вершин нечетной степени равно нулю.
Из теоремы получаем, что граф содержит Эйлеров цикл, по которому как раз и может пройти машина.
Другими словами, машина всегда будет идти и обрабатывать дороги и в итоге пройдет расстояние, равное удвоенной сумме длин всех дорог.
Также нам понадобится формула из геометрии, чтобы посчитать расстояние между двумя точками на плоскости (формулу смотри вики).
- TotalDist - сумма длин всех дорог
- Получаем, что длина пути, ктр пройдет наша машина равна 2*TotalDist
Так как скорость машины при обработке будет постоянная (машина не будет ехать по уже обработанной полосе) - 20 км/час (или (20*1000/60) м/мин), то общее время ее работы будет равно:
2*TotalDist*60 / (20*1000) = 3*TotalDist / 500
Реализация:
https://gist.github.com/unilecs/3534a3f06c9c6f21d1e3e19fee0ccdc9
Тест: