eolymp
bolt
Try our new interface for solving problems
Məsələlər

Секретная островная база

Секретная островная база

Zaman məhdudiyyəti 3 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

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

Остров представляет собой многоугольник на плоскости. Для каждого острова следует определить насколько далеко можно зайти в него от береговой линии. Расстояние от точки до береговой линии определяется как кратчайшее Евклидово расстояние (расстояние по прямой) от точки до точки на береговой линии.

Это конечно же должно остаться в секрете. Они обещают не убивать Вас, но Вы должны задание сохранить в секрете! Расстроить ниндзь - это последнее что Вы сможете делать в этом мире.

Giriş verilənləri

Первая строка содержит количество тестов. Структура каждого теста следующая:

  • первая строка содержит количество вершин n (3 n 20) береговой линии острова.

  • n строк, каждая из которых содержит два целых числа x и y (-100x, y 100) - координаты каждой вершины.

Вершины заданы в порядке обхода против часовой стрелки.

Çıxış verilənləri

Для каждого теста вывести в отдельной строке наибольшее расстояние, которое может отделять базу от побережья, при условии что база находится на острове. Выводимое значение должно иметь ошибку не более 10^{-3}.

Nümunə

Giriş verilənləri #1
1
3
0 0
10 0
3 8
Çıxış verilənləri #1
2.7421536261
Mənbə 2011 Benelux Algorithm Programming Contest, Preliminaries, Задача G