Intersection Ratio of Line Segments with Query Rectangle

Given n line segments in the plane and m queries. Each line segment is specified by four numbers \(x_1, y_1, x_2, y_2\) representing its endpoints \((x_1,y_1)\) and \((x_2,y_2)\). It is guaranteed that \(x_1 \neq x_2\) and \(y_1 \neq y_2\), and any two segments do not intersect or overlap.

Each query provides an axis‐aligned rectangle specified by four numbers \(x_1, y_1, x_2, y_2\) which represents the closed rectangle \[ \{(x,y) \mid x_1 \le x \le x_2,\; y_1 \le y \le y_2\}\] \] with \(x_1 < x_2\) and \(y_1 < y_2\).

For each query, compute the ratio \[ R = \frac{\text{(sum of intersection lengths between each segment and the rectangle)}}{\text{(sum of lengths of all segments)}} \] Output the ratio such that the relative or absolute error is at most \(10^{-6}\). If a segment does not intersect the rectangle, its contribution is 0.

Note: The intersection length of a line segment with the rectangle may be computed using a line clipping algorithm (e.g., the Liang-Barsky algorithm).

inputFormat

The first line contains an integer n representing the number of line segments.

Then n lines follow, each containing four space-separated numbers: \(x_1\; y_1\; x_2\; y_2\), representing the endpoints of a segment.

The next line contains an integer m representing the number of queries.

Then m lines follow, each containing four space-separated numbers: \(x_1\; y_1\; x_2\; y_2\), representing an axis aligned rectangle defined as \(\{(x,y) \mid x_1 \le x \le x_2,\; y_1 \le y \le y_2\}\).

outputFormat

For each query, output one line containing a real number representing the ratio \(R\). The answer for each query must have a relative or absolute error not exceeding \(10^{-6}\).

sample

3
0 0 1 1
2 2 3 3
0 1 1 0
2
0 0 2 2
1 0 3 2

0.666666666667
0.000000000000