Description

Xiaofu, who likes geometry, encountered the following problem: one day he drew $n$ lines on a white sheet of paper, and then cut out a small $m$-gon (simple polygon).

He wants to place this small paper piece on the sheet so that the total length of the lines it covers is maximized. The polygon piece cannot be flipped or rotated; it can only be translated. If some portion of a line happens to coincide with an edge of the polygon, then that segment is considered covered.

Can you help him solve this problem?

Input Format

Read from the file input.txt. The first line contains two numbers $n$ and $m$, where $1 \leq n, m \leq 10$, denoting the number of lines and the number of edges of the polygon, respectively.

Each of the next $n$ lines describes a line, with $4$ real numbers $x_1, y_1, x_2, y_2$, representing a line passing through $\left(x_1, y_1\right)$ and $\left(x_2, y_2\right)$.

Each of the next $m$ lines gives the vertices of the polygon in either clockwise or counterclockwise order, with $2$ real numbers $x, y$, representing the coordinates of a vertex.

Assume all input real numbers are between $-10000$ and $10000$, and have no more than $2$ decimal places. The input polygon is guaranteed to be non-self-intersecting, and no three consecutive points are collinear.

Output Format

The output file output.txt contains only one number $L$, the maximum total length of line segments that the input polygon can cover, accurate to $3$ decimal places.

3 5
6 1 2 5
1 2 8 4
4 -1 5 6
1 0
5 -1
4 2
7 3
4 4

11.933

Hint

Translated by ChatGPT 5