eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Расстояние до многоугольника

Расстояние до многоугольника

Лимит времени 8 секунд
Лимит использования памяти 256 MiB

На плоскости дан выпуклый многоугольник. Вам необходимо вычислить результат выполнения заданного количества запросов.

Каждый запрос представляет собой координаты некоторой точки на плоскости. Результатом выполнения запроса является расстояние от этой точки до многоугольника (растояние от заданной точки до многоугольника - это минимальное расстояние от этой точки до какой-либо точки внутри или на границе многоугольника).

Входные данные

В первой строке дано число n (3n4000) - количество вершин многоугольника.

Далее в n строках перечислены координаты вершин многоугольника в порядке обхода против часовой стрелки. Никакие три вершины не лежат на одной прямой. Каждая вершина задается целочисленными координатами x, y (-15000x, y15000).

В следующей строке даны пять целых чисел: q, a, b, c, d (1q10^6, 0a, b, c, d15000) - количество запросов и коэффициенты пересчета, позволяющие вычислить координаты последующего запроса по координатам и результату выполнения предыдущего.

В последней строке входных данных записаны два целых числа x[1], y[1] (-15000x[1], y[1]15000) - координаты точки первого запроса.

Координаты точек каждого из последующих запросов вычисляются через координаты и результат выполнения предыдущих запросов следующим образом. Если в i-ом запросе координаты точки были x[i], y[i], а ответ на запрос равнялся d[i], то i + 1-ым запросом будет точка с координатами

x[i+1] = ((x[i] + 15000) * (round(d[i]) + a) + b) % 30001 - 15000;

y[i+1] = ((y[i] + 15000) * (round(d[i]) + c) + d) % 30001 - 15000;

Округление round(d[i]) ведется к ближайшему целому.

Выходные данные

Выведите единственное число - ответ на последний запрос с абсолютной или относительной погрешностью 10^(-8).

Пример

Входные данные #1
4
0 0
5000 0
5000 3000
0 3000
3 13 17 19 21
-1 -1
Выходные данные #1
9407.8057484197670
Автор А. Миланин
Источник 2011 ACM, Ukraine, First Stage, April 9