61. Уборка снега

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

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

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

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

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

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

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

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

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

Пример входа	Пример выхода
0 0 0 0 10000 10000 5000 -10000 5000 10000 5000 10000 10000 10000	3:55

РЕШЕНИЕ

графы – Эйлеров цикл

Анализ алгоритма

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

Теорема Эйлера. Связный неориентированный граф содержит Эйлеров цикл тогда и только тогда, когда количество вершин нечетной степени равно нулю.

Из теоремы Эйлера следует, что граф содержит Эйлеров цикл, по которому как раз и может пройти снегоуборочная машина. То есть она всегда будет идти очищая снег со скоростью 20 км/час и пройдет расстояние, равное удвоенной сумме длин всех дорог.

Реализация алгоритма

Считываем информацию о дорогах, в переменной s подсчитываем суммарную их длину.

scanf("%lf %lf",&xx,&yy);

while(scanf("%lf %lf %lf %lf",&xx,&yy,&xx1,&yy1) == 4)

s += sqrt((xx1 - xx)*(xx1 - xx) + (yy1 - yy)*(yy1 - yy));

Длина пути, которую пройдет снегоуборочная машина, равна 2s метров. Поскольку скорость машины при уборке снега равна 20 км/час = (20 * 1000 / 60) м/мин, то общее время ее работы составит = минут.

time = (int)(3 * s / 500 + 0.5);

printf("%d:%d\n",time/60,time%60);

Java реализация

import java.util.*;

public class Main

{

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

double x = con.nextDouble();

double y = con.nextDouble();

double s = 0;

while(con.hasNext())

{

x = con.nextDouble();

y = con.nextDouble();

double x1 = con.nextDouble();

double y1 = con.nextDouble();

s += Math.sqrt((x1 - x)*(x1 - x) + (y1 - y)*(y1 - y));

}

int time = (int)(3 * s / 500 + 0.5);

System.out.println(time/60 + ":" + time%60);

con.close();

}

}

Python реализация

import sys

import math

x, y = map(float,input().split())

res = 0

for s in sys.stdin:

x, y, x1, y1 = map(float,s.split())

res += math.sqrt((x1 - x) * (x1 - x) + (y1 - y) * (y1 - y))

time = int(3 * res / 500 + 0.5)

print(time // 60, time % 60,sep=':',end='\n')