Задача
Зимой, когда дни стают короче, а ночи длиннее, необходимо задуматься об уборке снега с улиц. Поскольку бюджет нашего города очень маленький, у нас в распоряжении только один снегоход. Несмотря на это дороги должны быть прочищены. И каждый раз, когда выпадает много снега, ночью снегоход нашего города выезжает со своего гаража и объезжает весь город, очищая дороги. Какое минимальное время нужно снегоходу, чтобы очистить все проезжие полосы всех дорог и вернуться назад?
При этом известно, что:
- Снегоход может очищать только одну проезжую полосу дороги за один проход.
- Все дороги прямые с одной полосой движения в каждом направлении.
- Снегоход может поворачивать на любом перекрестке в любую сторону, а также может развернуться в тупике.
- Во время очистки снега снегоход двигается со скоростью $20$ км/час, и со скоростью $50$ км/час по уже очищенной дороге.
- Возможность проехать все дороги всегда существует.
Входные данные
Первая строка содержит два числа $x$ и $y$ $(-30000 ≤ x, y ≤ 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 |
#include <iostream> #include <cmath> using namespace std; int main() { double temp; cin >> temp >> temp; double lengthOfRoads = 0; double firstX, firstY, secondX, secondY; while (cin >> firstX >> firstY >> secondX >> secondY) { lengthOfRoads += sqrt((secondX - firstX)*(secondX - firstX)+(secondY - firstY)*(secondY - firstY)); } int minutes = round(3 * lengthOfRoads / 500); cout<< minutes / 60 << ":" << minutes % 60; return 0; } |
Решение задачи
Начало пути всегда находится на одной из данных дорог. Составим оптимальный алгоритм движения снегохода. По каждой из дорог необходимо проехать в одну и другую сторону. Снегоход может начинать движение в любую сторону. Во время движения ему необходимо двигаться прямо, не разворачиваясь, настолько долго, насколько это возможно. В случае, если на пути следования снегоходу встречается поворот, ему необходимо повернуть и далее работать по тому же алгоритму, принимая за начальную точку точку поворота. После возвращения из поворота снегоход должен продолжить движение по алгоритму. Когда снегоход попадает в тупик, возвращается на перекресток, на котором был совершен поворот или попадает в начальную точку, ему необходимо развернуться и двигаться обратно по той же траектории. По возвращении в начальную точку снегоход должен, в случае необходимости, двигаться во все оставшиеся стороны по такому же алгоритму. Таким образом, при движении по такому алгоритму, снегоход будет проезжать по каждой дороге по одному разу в каждую сторону, то есть не будет нигде проезжать «лишние» километры, следовательно время, за которое снегоход может объехать все дороги по одному разу в каждую сторону и есть искомым. Таким образом нам необходимо посчитать сумму длин всех дорог $L$, координаты начала и конца которых даны во входном потоке. Снегоход всегда двигается со скоростью $V = 20 км/час = \frac{1000}{3}м/мин$. По каждой из дорог снегоход проезжает два раза, таким образом общее искомое время минутах:
$t = \frac{2L}{V} = \frac{3L}{500}$.
Округлив полученное значение $t$ до целых минут и представив это время в виде часов и минут, получаем ответ.
Замечание. Как видно из алгоритма решения, не имеет значения, где конкретно расположена точка начала движения, главное, чтобы она располагалась на одной из улиц.
Ссылки
Условие задачи на e-olymp
Решение на e-olymp
Код решения на Ideone