Многокутник та еліпси
На площині задано n-кутник (без самоперетинів та самодотикань) і m елепсів. Еліпс у даній задачі – це фігура, яка задається нерівністю
.
Необхідно знайти довжину частини границі многокутника, не покритої еліпсами.
Крім цього задано дійсне число L. Необхідно знайти мінімальну кількість відрізків довжини L, які потрібні, щоб покрити не покриту еліпсами частину границі многокутника.
Вхідні дані
Перший рядок вхідного файлу містить ціле число n, 1 ≤ n ≤ 1500. Далі йде n рядків, які описують вершини многокутника – кожен з них містить два цілих числа – координати вершини (вони не перевищують 10^6 по модулю). Многокутник може бути задано як за годинниковою стрілкою, так і проти годинникової стрілки. Далі йде рядок, який містить m (1 ≤ m ≤ 1500) – число еліпсів. Післе нього йде m рядків, які описують еліпси – кожен з них містить 4 числа – x_c, y_c, a, b. Ці числа цілі і не перевищують 10^6 по модулю. Останній рядок містить дійсне число L (10^{-3 }≤ L ≤ 10^6).
Вихідні дані
Перший рядок вихідного файлу повинен містити відповідь на перше питання задачі. Вона повинна бути знайдена з точністю не гірше 10^{-6}. Другий рядок повинен містити відповідь на друге питання задачі.