Codeforces Beta Round 47 |
---|
Закончено |
В игре Веселая Ферма 5 решили разработать механику выпаса коров. Игроку предлагается управлять пастухом. Коровы в игре очень ленивые, перемещаются очень медленно, можно даже считать, что они и вовсе стоят на месте. Однако от них нужно постоянно отгонять хищников.
Для этого юный игрок Вася решил заставить пастуха бегать вокруг коров по одному и тому же замкнутому маршруту. Очень важно, чтобы все коровы находились строго внутри территории, ограниченной этим маршрутом, потому как иначе некоторые коровы рано или поздно будут съедены. Для пущей надёжности Вася хочет, чтобы время прохождения маршрута было минимальным.
Новая игра выпускается для различных платформ, в том числе и для мобильных. В связи с этим разработчики решили отказаться от арифметики с плавающей запятой и пользоваться только целочисленной арифметикой. Коровы и пастух в игре представлены в виде точек на плоскости с целыми координатами. Время в игре моделируется по ходам. Каждый ход пастух может остаться на месте либо шагнуть в одном из восьми направлений: по вертикали, по горизонтали или по диагонали. Поскольку координаты всегда должны оставаться целыми, то длина шага по вертикали и по горизонтали равна 1, а по диагонали . Коровы не перемещаются. Требуется минимизировать количество ходов, за которое пастух может оббежать вокруг стада.
В первой строке дано целое число N — количество коров в стаде (1 ≤ N ≤ 105). Каждая из последующих N строк содержит два целых числа Xi и Yi — координаты одной из коров (|Xi|, |Yi| ≤ 106). Несколько коров могут находиться в одной точке.
Выведите одно целое число — минимальное количество шагов в искомом маршруте.
4
1 1
5 1
5 3
1 3
16
Картинка к тесту из условия. Координатная сетка показана серым, оси координат чёрным, коровы красным, а искомый маршрут зелёным.
Название |
---|