Сглаживание трека
Бобу поручено спроектировать гоночную трассу определенной длины. Он решил, что отличной идеей будет создать выпуклый многоугольник, который имеет точно такую же длину. Однако ему сообщили, что гоночные автомобили не могут проходить такие острые углы, как в его плане.
Теперь ему нужно обеспечить минимальный радиус для всех поворотов на трассе. Бобу нравится форма его трассы, поэтому он не хочет сильно ее изменять. Его план состоит в том, чтобы уменьшить масштаб трассы относительно центра тяжести многоугольника, который определяет его трассу. Затем он хочет нарисовать новую трассу линией, которая находится на постоянном расстоянии от уменьшенной трассы. Это расстояние должно быть минимальным, чтобы удовлетворять заданному ограничению на минимальный радиус. Он просит вас написать программу для вычисления коэффициента масштабирования для данной трассы и минимального радиуса так, чтобы результирующая трасса имела ту же длину, что и в его первоначальном плане.
Боб сделал несколько рисунков первого тестового случая:
Входные данные
Входные данные начинаются с числа тестовых случаев t (0 < t ≤ 100). Каждый тестовый случай начинается с строки, содержащей два целых числа: минимально требуемый радиус r и количество точек n оригинального многоугольника трассы (0 ≤ r ≤ 1000, 3 ≤ n ≤ 10000). Затем следуют n строк, где каждая строка задает 2D-координаты в виде двух целых чисел x_i и y_i (-10000 ≤ x_i, y_i ≤ 10000). (0, 0) — это нижний левый угол. Это координаты оригинальной трассы в направлении против часовой стрелки. Вы можете безопасно предположить, что площадь данного многоугольника не пуста.
Выходные данные
Для каждого тестового случая выведите одну строку. Если возможно построить трассу в соответствии с вышеописанным, выведите коэффициент масштабирования, "Not possible" в противном случае. Коэффициент должен иметь относительную или абсолютную ошибку меньше, чем 10^{-5}.