Задачі
Многокутник та еліпси
Многокутник та еліпси
На площині задано \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