Problem Description

There are $n$ line segments on the plane.

There are $m$ queries. In each query, an axis-aligned rectangle is given. You need to find the ratio of: the sum, over every segment that intersects the rectangle, of the length of the intersection between that segment and the rectangle, to the sum of the lengths of all segments. Output the answer such that the relative error or absolute error compared with the standard answer is at most $10^{-6}$.

Each segment is given in the form $x_1\;y_1\;x_2\;y_2$, meaning a segment with endpoints $(x_1,y_1)$ and $(x_2,y_2)$. It is guaranteed that any two segments have no intersection point and no overlapping part, and that $x_1\ne x_2, y_1\ne y_2$.

Each rectangle is given in the form $x_1\;y_1\;x_2\;y_2$, meaning the rectangle $\{(x,y)\mid x_1\le x\le x_2, y_1\le y\le y_2\}$. It is guaranteed that $x_1< x_2$ and $y_1< y_2$.

Input Format

The first line contains an integer $n$.

The next $n$ lines each contain four integers separated by spaces: $x1,y1,x2,y2$, describing a line segment.

The next line contains an integer $m$.

The next $m$ lines each contain four integers separated by spaces: $x1,y1,x2,y2$, describing the query rectangle.

Output Format

For each query, output one line: a decimal number between $0$ and $1$, representing the answer.

2
1 1 4 4
2 1 4 3
4
1 1 6 6
1 1 3 3
2 1 3 3
1 2 2 4

1
0.6
0.4
0

Hint

Idea: nzhtl1477 & ccz181078, Solution: ccz181078, Code: ccz181078, Data: ccz181078.

For $100\%$ of the testdata, $1\le n,m\le 10^5$ and $1\le x_1,y_1,x_2,y_2\le 10^6$.

Translated by ChatGPT 5