eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Покраска пола

Покраска пола

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB

Музей Bizarre Argentinean Pocket Calculators (BAPC) нашел замечательного живописца, чтобы сделать красивую картину пола в музее. Все стены в музее прямые, и любые две соседние стены пересекаются под прямым углом. Все несмежные стены попарно не пересекаются. Кроме того, в комнате, в которой должна появиться картина, нет столбов. Следовательно, это прямолинейный простой многоугольник.

Дизайн для картины квадратный. Музей хочет, чтобы картина была как можно больше. Кроме того, его следует поместить так, чтобы края квадрата были параллельны стенам. Найдите максимально возможную ширину для рисунка.

prb8329.gif

Вхідні дані

Первая строка содержит количество тестов, не более 100. Далее для каждого теста:

  • первая строка содержит число n (4n1 000) - число углов в комнате.

  • n строк, каждая из которых содержит два целых числа x и y (0x, y100 000): координаты каждого угла комнаты.

Углы заданы по часовой стрелке.

Вихідні дані

Для каждого теста вывести в отдельной строке максимальную ширину квадратной картины, которая помещается на полу музея.

Приклад

Вхідні дані #1
3
6
0 8
5 8
5 4
8 4
8 0
0 0
4
0 4
4 4
4 0
0 0
14
4 8
12 8
12 6
14 6
14 8
16 8
16 3
8 3
8 0
0 0
0 6
3 6
3 7
4 7
Вихідні дані #1
5
4
6
Джерело 2014 Benelux Algorithm Programming Contest (BAPC), Preliminaries, Problem C