Сережа разместил n точек на плоскости. Сейчас Сережа хочет разместить на плоскости две прямые, пересекающиеся под прямым углом, так, чтобы одна из прямых пересекала ось Ox под углом 45 градусов, а максимальное из расстояний от точек до прямых было бы минимально.
В данной задаче мы считаем, что расстояние между точками (x1, y1) и (x2, y2) равно |x1 - x2| + |y1 - y2|. Расстояние от точки до прямых — это минимальное из расстояний от точки до некоторой точки, принадлежащей одной из прямых.
Помогите Сереже, найдите максимальное расстояние от точек до оптимально расположенных прямых.
Выходные данные
В единственную строку выведите единственное вещественное число — ответ на задачу. Ответ будет считаться правильным, если его относительная или абсолютная погрешность не превышает 10 - 6.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
0 0
2 0
0 2
2 2
|
0.000000000000000
|
|
2
|
4
1 0
0 1
2 1
1 2
|
1.000000000000000
|