Задача №111979. Вращающаяся пластина
Мальчик Вася очень любит геометрию. Кроме того, ему очень нравится забивать гвозди в доску. Сегодня он изучает свою любимую металлическую пластину, которую он собирается прибить к деревянной доске.
Пластина имеет форму, ограниченную многоугольником без самопересечений и самокасаний. В первой вершине многоугольника пластина имеет маленькую петлю.
Сначала Вася кладет пластину на доску, лежащую на горизонтальном столе, и прибивает ее гвоздем к пластине через петлю в первой вершине. Вбитый гвоздь жестко закрепляет положение первой вершины, однако позволяет пластине вращаться вокруг нее.
Теперь Вася хочет забить в доску еще один гвоздь, который бы ограничил вращение пластины, но он еще не решил куда. Он наметил \(m\) возможных позиций, куда он хотел бы забить гвоздь, и для каждой из них хочет узнать, на какой угол он сможет поворачивать свою пластину, если забьет в доску гвоздь в этой точке. При этом как только пластина касается гвоздя, дальше ее поворачивать нельзя.
В первой строке входного файла задано число \(n\) (\(3 \le n \le 2\,000\)) - количество вершин многоугольника. В следующих \(n\) строках заданы координаты вершин многоугольника в порядке обхода.
В следующей строке задано число \(m\) (\(1 \le m \le 2\,000\)) - количество точек, которые Вася рассматривает как возможные положения второго гвоздя. В следующих \(m\) строках заданы координаты этих точек. Все эти точки находятся снаружи от исходного положения пластины.
Все координаты во входном файле целые и не превосходят \(10^6\) по модулю.
Выходной файл должен содержать \(m\) строк.
В \(i\)-й строке выведите два вещественных числа \(\alpha_i\) и \(\beta_i\), где \(\alpha_i\) - максимальный угол в градусах, на который можно повернуть пластину по часовой стрелке, если Вася забьет гвоздь в \(i\)-ю точку, а \(\beta_i\) - максимальный угол в градусах ,на который в этом случае можно повернуть пластину против часовой стрелки.
Если гвоздь не мешает пластине поворачиваться, выведите \(\alpha_i = \beta_i = 360\).
Ответ считается верным, если его абсолютная или относительная погрешность относительно правильного не превосходит \(10^{-6}\).
На рисунке выше изображен тест из примера. Прямоугольник показывает начальное положение пластины. Точками показаны позиции, в которые Вася планирует забить гвоздь.
Гвоздь, забитый в первую точку, не мешает пластине поворачиваться.
Гвоздь, забитый во вторую точку, позволяет повернуть пластину на \(45^\circ\) по часовой стрелке или на \(225^\circ\) против часовой стрелки.
4 0 0 -3 -3 0 -6 3 -3 3 -8 0 -2 0 2 -1
360.000000000000 360.000000000000 45.000000000000 225.000000000000 251.565051177078 18.434948822922