P4605 [SDOI2018] Physics Experiment

Xiao T has a physics lab class this semester. To successfully finish the experiment in the next class, he plans to preview it before class. This experiment is conducted on a 2D plane. On the plane there is an infinitely long straight guide rail. On the rail, there is a laser emitter of length $L$. The laser emitter emits laser beams of width $L$ to both sides of the rail along the direction perpendicular to the rail. There are also $n$ baffles on the plane. Each baffle can be regarded as a line segment. Now each baffle does not touch the straight guide rail, and the angle between it and the rail is at most $85\degree$. Any two baffles also do not touch each other. The laser beams cannot pass through these baffles, and will be absorbed by them, not reflected. Xiao T wants to determine a position of the laser emitter such that the total length of baffles illuminated by the laser beams is maximized. You need to help Xiao T compute this maximum value.

The first line contains a positive integer $T$, indicating the number of testdata groups. For each testdata group, the first line contains an integer $n$, indicating the number of baffles. The next $n$ lines each contain four integers $x1, y1, x2, y2$, indicating that the two endpoints of the baffle are $(x1, y1)$ and $(x2, y2)$, guaranteeing $(x1, y1){=}\mathllap{/\,}(x2, y2)$. The $(n + 2)$-th line contains five integers $x1, y1, x2, y2, L$, indicating that the straight guide rail passes through points $(x1, y1)$ and $(x2, y2)$, and the length of the laser emitter is $L$, also guaranteeing $(x1, y1)\mathrlap{\,/}{=}(x2, y2)$.

For each testdata group, output one line containing a real number, representing the maximum total length of baffles that can be illuminated by the laser beams. The relative error must not exceed $10^{-6}$, that is, let your output be $a$ and the standard answer be $b$. If $\dfrac{|a-b|}{max(1,b)}$ $≤$ $10^{-6}$, then your output will be considered correct.

## Constraints - $T ≤ 100$. - $1 ≤ n ≤ 10^4$. - $1 ≤ L ≤ 2 × 10^9$. - The absolute value of all coordinates does not exceed $10^9$. ## SubTasks - Subtask 1 (40 points): $1 ≤ n ≤ 100$ and the absolute value of all coordinates does not exceed $10^4$. - Subtask 2 (40 points): the absolute value of all coordinates does not exceed $10^6$. - Subtask 3 (20 points): no additional constraints. Translated by ChatGPT 5