Задачи
Многоугольник и эллипсы
Многоугольник и эллипсы
На плоскости задан \textbf{n}-угольник (без самопересечений и самокасаний) и \textbf{m} эллипсов. Эллипс в данной задаче -- это фигура, задаваемая неравенством
\includegraphics{https://static.e-olymp.com/content/d6/d60714e223d4f1e71e006e39ac0d89e1d9477e5a.jpg}
.
Необходимо найти длину части границы многоугольника, не покрытой эллипсами.
Кроме этого задано вещественное число \textbf{L}. Необходимо найти минимальное количество отрезков длины \textbf{L}, которые нужны, чтобы покрыть не покрытую эллипсами часть границы многоугольника.
\InputFile
Первая строка входного файла содержит целое число \textbf{n}, \textbf{1} ≤ \textbf{n} ≤ \textbf{1500}. Далее идут \textbf{n} строк, описывающих вершины многоугольника -- каждая из них содержит два целых числа -- координаты вершины (они не превосходят \textbf{10^6} по модулю). Многоугольник может быть задан как по часовой стрелке, так и против часовой стрелки. Далее идет строка, содержащая \textbf{m} (\textbf{1} ≤ \textbf{m} ≤ \textbf{1500}) -- число эллипсов. После неё идут \textbf{m} строк, описывающих эллипсы -- каждая из них содержит \textbf{4} числа -- \textbf{x_c}, \textbf{y_c}, \textbf{a}, \textbf{b}. Эти числа целые и не превосходят \textbf{10^6} по модулю. Последняя строка содержит вещественное число \textbf{L} (\textbf{10}^\{-3 \}≤ \textbf{L} ≤ \textbf{10^6}).
\OutputFile
Первая строка выходного файла должна содержать ответ на первый вопрос задачи. Он должен быть найден с точностью не хуже \textbf{10^\{-6\}}. Вторая строка должна содержать ответ на второй вопрос задачи.
Входные данные #1
4 -1 -1 1 -1 1 1 -1 1 1 100000 -100000 1000000 1000000 2
Выходные данные #1
0.0000000000 0