Polygon and Ellipses
In the plane, you are given a polygon with n sides (without self-intersections or self-tangencies) and m ellipses. An ellipse in this context is defined by the inequality:
Your task is to determine the length of the polygon's boundary that is not covered by any of the ellipses.
Additionally, you are provided with a real number L. You need to calculate the minimum number of segments, each of length L, required to cover the uncovered portion of the polygon's boundary.
Input
The input begins with an integer n (1 ≤ n ≤ 1500), followed by n lines, each containing two integers representing the coordinates of a vertex of the polygon. These coordinates do not exceed 10^6 in absolute value. The vertices may be listed in either clockwise or counterclockwise order. Next, a line contains the integer m (1 ≤ m ≤ 1500), indicating the number of ellipses. This is followed by m lines, each describing an ellipse with four integers: x_c, y_c, a, and b. These integers also do not exceed 10^6 in absolute value. The final line contains a real number L (10^{-3} ≤ L ≤ 10^6).
Output
The output should consist of two lines. The first line should provide the length of the polygon's boundary that is not covered by the ellipses, with an accuracy of at least 10^{-6}. The second line should state the minimum number of segments of length L needed to cover this uncovered portion.