Задача №111780. Машинки
Лена играет в машинки. Для этого она вырезала из бумаги машинку (являющуюся многоугольником без самопересечений и самокасаний) и стала возить её по столу. К сожалению, во время игры она разлила чай и на столе образовалась река. Для того, чтобы продолжить игру, Лене нужно провезти машинку через реку. Для этого она решила построить мост — длинную ленту, по которой и поедет машинка. На столе машинку можно поворачивать на любой угол, но для того, чтобы проехать через реку, её границы не должны выходить за границы моста. Ниже расположена фотография игрового поля и предполагаемое решение проблемы. Лене стало интересно — какой минимальной ширины может быть мост, чтобы машинка смогла проехать через реку?
Внезапно Лена задумалась — ведь эта игра может стать прекрасной задачей по информатике, достойной финала международной студенческой олимпиады! Её Вам и предстоит решить.
Первая строка входного файла содержит T (Первая группа тестов: 0 < T < 11, вторая группа тестов: T = 1) -- количество тестов во входном файле. Далее следуют T тестов. Первая строка теста содержит число N (Первая группа тестов: 3 <= N <= 100. Вторая группа: 3 <= N <= 2 * 105) — количество вершин многоугольника.
Следующие N строк содержат по два числа — xi и yi (Первая группа тестов: 0 <= xi, yi <= 1000. Вторая группа: -105 <= xi, yi <= 105), задающие координаты многоугольника в порядке обхода. Гарантируется, что он не имеет самокасаний и самопересечений.
Для каждого теста на новой строке выведите одно число c точностью до двух знаков округляя в большую сторону — минимально требуемую ширину моста, при которой машинка сможет проехать через реку.
2 3 0 0 3 0 0 4 4 0 10 10 0 20 10 10 20
2.4000 14.1422