Partitioned Plane Regions Area Calculation

Given n lines in the 2D plane, these lines divide the plane into several regions. However, some regions have infinite area. To avoid this, an extra boundary is imposed by four lines: \(x=L,\ x=-L,\ y=L,\ y=-L\) so that all regions inside this box have finite area. You are given m query points (all strictly inside the boundary) and for each query point you are to determine the area of the region in which it lies.

Each of the original n lines is given by an equation of the form \(A\,x+B\,y+C=0\). Note that for a query point \((x_q,y_q)\), if \(A\,x_q+B\,y_q+C>0\) then the region containing that query point is defined by the half‐plane \(A\,x+B\,y+C\ge0\); otherwise, if \(A\,x_q+B\,y_q+C<0\) the region is defined by \(A\,x+B\,y+C\le0\). Taking the intersection of the half‐planes for all n lines with the bounding box \([-L,L]\times[-L,L]\) yields a convex polygon. Compute the area of that polygon.

Note: It is guaranteed that for every query point and every given line, the distance from the point to the line is greater than \(10^{-7}\), so numerical issues with points lying exactly on a boundary can be ignored.

inputFormat

The first line contains three numbers: an integer n (number of lines), an integer m (number of query points), and a real number L (the bound for the rectangle).

The next n lines each contain three real numbers: A, B and C, describing the line \(A\,x+B\,y+C=0\).

The next m lines each contain two real numbers representing the coordinates \(x\) and \(y\) of a query point.

It is guaranteed that each query point lies strictly inside the rectangle defined by \(x=L, x=-L, y=L, y=-L\) and that the distance from any query point to any line is at least \(10^{-7}\).

outputFormat

For each query point, output a line with the area of the corresponding region. Print the answer as a real number with at least 6 digits after the decimal point.

sample

1 2 10.0
0 1 0
0 1
0 -1

200.000000
200.000000