Задача . C. Веселая Ферма 5

В игре Веселая Ферма 5 решили разработать механику выпаса коров. Игроку предлагается управлять пастухом. Коровы в игре очень ленивые, перемещаются очень медленно, можно даже считать, что они и вовсе стоят на месте. Однако от них нужно постоянно отгонять хищников.

Для этого юный игрок Вася решил заставить пастуха бегать вокруг коров по одному и тому же замкнутому маршруту. Очень важно, чтобы все коровы находились строго внутри территории, ограниченной этим маршрутом, потому как иначе некоторые коровы рано или поздно будут съедены. Для пущей надёжности Вася хочет, чтобы время прохождения маршрута было минимальным.

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