Капитан Смоллетт находится в форте с координатами (0, 0).
Из форта торчат n ружей, обозначенных векторами (xi, yi).
Неподалёку в точке с координатами (a, b) находится Джон Сильвер, который является кругом радиуса r.
Капитан Смоллетт по своему усмотрению повернёт форт на некоторый угол alpha (0 ≤ alpha < 360) против часовой стрелки, вместе с фортом повернутся все ружья.
Затем он k раз выстрелит из какого-то ружья, выбрав его равновероятно.
Во время каждого выстрела ружьё выбирается независимо от всех предыдущих выстрелов, ружья могут повторяться.
Джон Сильвер будет убит, если хотя бы один выстрел попадёт в него.
Попадания в границу круга тоже считаются.
Капитана волнуют q вопросов.
Вопрос номер i звучит так: на какой наименьший угол alphai нужно повернуть форт, чтобы поразить Джона Сильвера с вероятностью хотя бы pi.
Найдите ответы на все вопросы капитана.
Исходные данные
Первая строка содержит три целых числа n, k, q — количество ружей, количество выстрелов и количество вопросов (1 ≤ n ≤ 105, 1 ≤ k ≤ 10, 1 ≤ q ≤ 105).
Следующие n строк содержат два целых числа xi, yi — координаты вектора, обозначающего i-е ружьё (−109 ≤ xi, yi ≤ 109, xi2 + yi2 > 0 ).
Гарантируется, что никакие два ружья не смотрят в одном направлении.
Следующая строка содержит целые числа a, b, r — координаты Джона Сильвера и его радиус (−109 ≤ a, b ≤ 109, 1 ≤ r ≤ 109).
Гарантируется, что Джон Сильвер не пересекает ни одно ружьё.
Следующие q строк содержат вещественные числа pi — желаемые вероятности из запросов (0 ≤ pi ≤ 1, число pi содержит не более 5 знаков после запятой).
Результат
В q строках выведите по одному вещественному числу alphai — ответ на i-й вопрос (0 ≤ alphai < 360).
Если поразить Джона Сильвера с требуемой вероятностью невозможно, то выведите −1.
Ваш ответ будет считаться правильным, если его абсолютная или относительная погрешность не превосходит 10−3.
Формально, пусть ваш ответ будет a, а ответ жюри будет b. Ваш ответ будет принят тогда и только тогда, когда |a−b|/max(1, |b|) ≤ 10−3.
Пример
исходные данные | результат |
---|
6 2 5
5 -5
3 0
-3 -2
-3 -1
-3 0
-4 -1
4 2 2
0.3 0.5 0.75 0.8 0.9 | 0.0000000000
45.0000000000
165.9637565321
180.0000000000
-1 |
Замечания
Ниже приведена иллюстрация к первому примеру.
Обратите внимание, что после поворота форта ружья могут проходить через Джона Сильвера, при этом выстрел из них всё ещё будет считаться поражающим.
Автор задачи: Артём Кутузов
Источник задачи: Уральская командная олимпиада по программированию 2024