Задача №114797. Забор
У Дональда во владении есть небольшой дом на Манхэттене. Не так давно проходили выборы президента США, и, чтобы обезопаситься от потенциальных общественных возмущений, Дональд решил построить вокруг своего дома забор.
Дом Дональда можно представить как многоугольник, вершины которого имеют целые координаты. В доме все углы прямые, а каждая из стен идёт или параллельно оси восток-запад, или оси юг-север. Дональд хочет построить стену так, чтобы дом находился целиком внутри неё, а также чтобы забор был не слишком близко к дому. А именно, Дональд хочет, чтобы манхэттенское расстояние между любой точкой забора и любой точкой дома было не менее \(l\).
Напомним, что манхэттенским расстоянием между точками \((x_1, y_1)\) и \((x_2, y_2)\) называется величина \(|x_1 - x_2| + |y_1 - y_2|\).
Дональд хочет минимизировать расходы, поэтому он просит вас помочь ему найти минимальную возможную длину подходящего забора.
В первой строке записаны целые числа \(n\) и \(l\) (\(4 \le n \le 100\,000\), \(0 \le l \le 10^8\)).
Следующие \(n\) строк содержат целые координаты \(x_i\), \(y_i\) (\(|x_i|, |y_i| \le 10^8\)), описывающие границу дома в порядке обхода по часовой или против часовой стрелки.
Гарантируется, что дом невырожденный, не содержит самопересечений (отрезки не имеют общих точек, за исключением общего конца у соседних отрезков), никакие две заданные точки не совпадают, а все отрезки стены дома вертикальные или горизонтальные.
Выведите одно вещественное число — минимальную длину забора. Ваш ответ будет засчитан, если его абсолютная или относительная погрешность будет не более \(10^{-6}\).
4 3 -3 -3 -3 3 3 3 3 -3
40.9705627485
9 0 1 1 3 1 5 1 5 2 3 2 3 3 2 3 2 2 1 2
10.6502815399