|
Мусорщик
(Время: 1 сек. Память: 16 Мб Сложность: 45%)
Всем известно, что работа уборщицы становится все менее престижной, чем работа программиста. Поэтому, все больше становится программистов и все меньше уборщиц. И скоро, возможно, совсем некому будет делать уборку помещений, а чистота – она всегда актуальна и важна для работы, например, для тех же программистов.
Сотрудники одной из фирм разработали специальную машину «Мусорщик-001», которая предназначена для уборки прямоугольных пустых помещений. Машина не совершенна и может пока двигаться на 1 метр только влево, вправо и вперед (вдоль оси OY). Каждое помещение можно разбить на квадратные сектора со стороной в 1 метр и обозначить те, которые загрязнены. Для уборки помещения достаточно, чтобы машина-уборщик побывала в каждом из загрязненных секторов. Известно, что перед уборкой машина всегда находится в клетке (1,1) .
Одна из компаний, где в штате нет уборщицы, но имеется полный штат программистов, приобрела «Мусорщик-001». Пока программистам никак не удается написать программу, определяющую по заданному плану загрязнения помещения минимально возможную длину маршрута машины-уборщика, необходимого для уборки данной территории. Возможно, Вам удастся им помочь!
Входные данные
Первая строка входного файла INPUT.TXT содержит натуральное число n (n ≤ 1000). Следующие n строк содержат по два натуральных числа: xi и yi – координаты загрязненных секторов в заданном помещении (xi, yi ≤ 50).
Выходные данные
В выходной файл OUTPUT.TXT выведите целое число, соответствующее минимальной длине маршрута в метрах, необходимого для уборки.
Пример
№ | INPUT.TXT | OUTPUT.TXT |
1 | 7 2 1 3 2 5 2 5 4 1 4 3 6 6 6 | 18 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| |