Description

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.

Input Format

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)$.

Output Format

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.

3
4
-3 2 -1 2
-1 -1 1 -1
0 1 2 1
2 -2 4 -2
0 0 1 0 2
4
1 1 3 3
2 1 4 2
3 1 5 1
3 -1 4 -1
0 0 -1 0 2
4
-2 0 1 2
1 3 -3 2
1 -3 5 -1
2 -1 4 3
0 0 1 1 2

3.000000000000000
3.118033988749895
4.251303782246768

Hint

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