Description

In the 2D plane, there are $n$ lines that partition the plane into regions. Given $m$ points, find the area of the region that contains each point.

A careful reader will notice that some regions have infinite area. The R-surnamed author has anticipated this and provides a real number $L$. Four extra lines $x = L, x = -L, y = L, y = -L$ bound a finite rectangular area, and all query points lie strictly inside this bounded region.

An even more careful reader will note that if a query point lies exactly on a line or extremely close to one, numerical error could severely affect the answer. The R-surnamed author has anticipated this as well: in the testdata, the distance from any query point to any line is greater than $10^{-7}$.

Input Format

Read from standard input.

The first line contains two positive integers $n, m$ and one positive real number $L$.

The next $n$ lines each contain three real numbers $A, B, C$, indicating a line with equation $Ax + By + C = 0$.

The next $m$ lines, the $i$-th line contains two real numbers $x_i, y_i$, which are the coordinates of the $i$-th point.

Output Format

Write to standard output.

Output $m$ lines, each containing one real number. The number on the $i$-th line is the area of the region containing the $i$-th point. Print with two decimal places.

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

4.00
8.50
8.50
15.00

Hint

For $20\%$ of the testdata, $n, m \le 10$.

For $40\%$ of the testdata, $n, m \le 300$.

For $100\%$ of the testdata, $n \le 500, m \le 100000$.

For $100\%$ of the testdata, the absolute value of every input number is $\le 10^7$, and each input number has at most two decimal places.

From the CodePlus 2017 December Contest, proudly presented by the Student Algorithms and Contest Association of the Department of Computer Science and Technology, Tsinghua University.

Credit: idea/Ru Yizhong; setter/Ru Yizhong; testers/Chen Yu, Wang Yuzhong.

Git Repo: https://git.thusaac.org/publish/CodePlus201712

Thanks to Tencent for supporting this contest.

Translated by ChatGPT 5