Фарбування підлоги#8329
Музей Bizarre Argentinean Pocket Calculators (BAPC) знайшов талановитого художника для створення красивої картини на підлозі музею. Усі стіни в музеї прямі, і будь-які дві сусідні стіни перетинаються під прямим кутом. Несусідні стіни не перетинаються між собою. Крім того, в кімнаті, де має бути картина, немає колон. Отже, це прямолінійний простий багатокутник.
Дизайн картини має форму квадрата. Музей прагне, щоб картина була якомога більшою. Вона повинна бути розміщена так, щоб її сторони були паралельні стінам. Знайдіть максимально можливу ширину для картини.
Перший рядок містить кількість тестів, не більше . Далі для кожного тесту:
перший рядок містить число (4 \le n \le 1000) - кількість кутів у кімнаті.
рядків, кожен з яких містить два цілі числа і (0 \le x, y \le 100\,000): координати кожного кута кімнати.
Кути задані за годинниковою стрілкою.
Для кожного тесту виведіть в окремому рядку максимальну ширину квадратної картини, яка може поміститися на підлозі музею.
Приклад 1