P2288 [HNOI2005] Paper Covering

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?

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.

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.

Translated by ChatGPT 5