Задача
Зимой, когда дни стают короче, а ночи длиннее, необходимо задуматься об уборке снега с улиц. Поскольку бюджет нашего города очень маленький, у нас в распоряжении только один снегоход. Несмотря на это дороги должны быть прочищены. И каждый раз, когда выпадает много снега, ночью снегоход нашего города выезжает со своего гаража и объезжает весь город, очищая дороги. Какое минимальное время нужно снегоходу, чтобы очистить все проезжие полосы всех дорог и вернуться назад?
При этом известно, что:
- Снегоход может очищать только одну проезжую полосу дороги за один проход.
- Все дороги прямые с одной полосой движения в каждом направлении.
- Снегоход может поворачивать на любом перекрестке в любую сторону, а также может развернуться в тупике.
- Во время очистки снега снегоход двигается со скоростью 20 км/час, и со скоростью 50 км/час по уже очищенной дороге.
- Возможность проехать все дороги всегда существует.
Входные данные
Первая строка содержит два числа $x$ и $y$ ($-30000 \leq x, y \leq 30000$) — координаты ангара (в метрах), откуда начинает свое движение снегоход. Далее в каждой отдельной строке заданы координаты (в метрах) начала и конца улиц (по $4$ числа в строке). В городе может быть до $100$ улиц.
Выходные данные
Время в часах и минутах, необходимое для очистки всех дорог и возврата в ангар. Время следует округлить до ближайшей минуты
Тесты
| Входные данные | Выходные данные |
|
$0$ $0$ $0$ $0$ $-1000$ $2000$ $0$ $0$ $1000$ $2000$ |
$0:27$ |
|
$0$ $1000$ $0$ $0$ $0$ $3000$ $0$ $0$ $1000$ $1000$ $0$ $0$ $3000$ $0$ $3000$ $0$ $3000$ $3000$ $3000$ $3000$ $0$ $3000$ $0$ $3000$ $1000$ $2000$ $3000$ $0$ $2000$ $1000$ $3000$ $3000$ $2000$ $2000$ |
$1:46$ |
|
$-500$ $0$ $-1000$ $0$ $0$ $0$ $0$ $0$ $1000$ $0$ $-1000$ $1000$ $0$ $0$ $-1000$ $1000$ $0$ $2000$ $0$ $2000$ $1000$ $1000$ $1000$ $1000$ $0$ $1000$ $0$ $1000$ $0$ $0$ |
$0:49$ |
|
$1000$ $500$ $-1000$ $0$ $1000$ $0$ $-1000$ $1000$ $1000$ $1000$ $-1000$ $0$ $-1000$ $1000$ $1000$ $0$ $1000$ $1000$ $-1000$ $0$ $1000$ $1000$ $1000$ $0$ $-1000$ $1000$ $-1000$ $1000$ $0$ $2000$ $0$ $2000$ $1000$ $1000$ |
$1:20$ |
|
$500$ $-500$ $0$ $0$ $1000$ $-1000$ $1000$ $-1000$ $2000$ $0$ $2000$ $0$ $3000$ $-1000$ $3000$ $-1000$ $4000$ $0$ $4000$ $0$ $5000$ $-1000$ $5000$ $-1000$ $6000$ $0$ $0$ $0$ $8000$ $0$ |
$1:39$ |
Код программы
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); scanner.nextDouble(); scanner.nextDouble(); double length = 0; while(scanner.hasNextDouble()) { double startX = scanner.nextDouble(); double startY = scanner.nextDouble(); double finishX = scanner.nextDouble(); double finishY = scanner.nextDouble(); length += Math.sqrt((finishX - startX) * (finishX - startX) + (finishY - startY) * (finishY - startY)); } long minutes = Math.round(3 * length / 500); System.out.print(minutes / 60 + ":" + minutes % 60); } } |
Решение задачи
Пусть граф $G = \left \langle V, U \right \rangle$ — граф, ребра которого — указанные в задаче дороги, а вершины — перекрестки. Граф $G$ — ориентированный, при чем, в силу того, что все дороги имеют двустороннее движение, из того, что $\left ( v_i, v_j \right ) \in U$ следует, что $\left ( v_j, v_i \right ) \in U.$ Из этого следует, что полустепень захода каждой вершины равна ее полустепени исхода, из чего, по критерию существования Эйлерова цикла, граф $G$ содержит Эйлеров цикл, т.е. существует путь, такой, что снегоход сможет очистить все дороги, пройдя по каждой ровно один раз в каждую сторону, следовательно длина такого пути будет равна удвоенной длине дорог. Снегоход всегда двигается со скоростью $V = 20 \text{км/час} = \frac{1000}{3} \text{м/мин}.$ По каждой из дорог снегоход проезжает два раза, таким образом общее искомое время минутах: $t = \frac{2L}{V} = \frac{3L}{500},$ где $L$ — длина всех дорог.
Замечание. Как видно из алгоритма решения, не имеет значения, где конкретно расположена точка начала движения, главное, чтобы она располагалась на одной из улиц.