Задача: Вращающаяся пластина
Мальчик Вася очень любит геометрию. Кроме того, ему очень нравится забивать гвозди в доску. Сегодня он изучает свою любимую металлическую пластину, которую он собирается прибить к деревянной доске.
Пластина имеет форму, ограниченную многоугольником без самопересечений и самокасаний. В первой вершине многоугольника пластина имеет маленькую петлю.
Сначала Вася кладет пластину на доску, лежащую на горизонтальном столе, и прибивает ее гвоздем к пластине через петлю в первой вершине. Вбитый гвоздь жестко закрепляет положение первой вершины, однако позволяет пластине вращаться вокруг нее.
Теперь Вася хочет забить в доску еще один гвоздь, который бы ограничил вращение пластины, но он еще не решил куда. Он наметил m возможных позиций, куда он хотел бы забить гвоздь, и для каждой из них хочет узнать, на какой угол он сможет поворачивать свою пластину, если забьет в доску гвоздь в этой точке. При этом как только пластина касается гвоздя, дальше ее поворачивать нельзя.
Формат входных данных
В первой строке входного файла задано число n (3 ≤ n ≤ 2 000) — количество вершин многоугольника. В следующих n строках заданы координаты вершин многоугольника в порядке обхода. В следующей строке задано число m (1 ≤ m ≤ 2 000) — количество точек, которые Вася рассматривает как возможные положения второго гвоздя. В следующих m строках заданы координаты этих точек. Все эти точки находятся снаружи от исходного положения пластины. Все координаты во входном файле целые и не превосходят 106 по модулю.
Формат выходных данных
Выходной файл должен содержать m строк. В i-й строке выведите два вещественных числа αi и βi , где αi — максимальный угол в градусах, на который можно повернуть пластину по часовой стрелке, если Вася забьет гвоздь в i-ю точку, а βi — максимальный угол в градусах ,на который в этом случае можно повернуть пластину против часовой стрелки. Если гвоздь не мешает пластине поворачиваться, выведите αi = βi = 360. Ответ считается верным, если его абсолютная или относительная погрешность относительно правильного не превосходит 10−6 .
| Ввод |
Вывод |
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 |
Пояснение
На рисунке выше изображен тест из примера. Прямоугольник показывает начальное положение пластины.
Точками показаны позиции, в которые Вася планирует забить гвоздь.
Гвоздь, забитый в первую точку, не мешает пластине поворачиваться.
Гвоздь, забитый во вторую точку, позволяет повернуть пластину на 45 гр. по часовой стрелке или на 225 гр. против часовой стрелки.
Ваш ответ: