Многоугольник и эллипсы
На плоскости задан 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}. Вторая строка должна содержать ответ на второй вопрос задачи.