405470: GYM101968 F Mirror

There are $$$n$$$ students in a classroom, this classroom can be seen as a Cuboid in which the students are looking in the direction of the negative $$$z$$$-axis. The positive $$$x$$$-axis is to their right and the positive $$$y$$$-axis points upward. The wall in front of the students is the plane $$$z = 0$$$, and the wall behind them is the plane $$$z = a$$$. The walls to their right and left are the planes $$$x = 10^9$$$ and $$$x = -10^9$$$, respectively.

You will be given $$$q$$$ queries of the form ($$$x_i, y_i, a$$$), meaning that there's a point on the wall behind the students at those coordinates. You need to put a rectangular mirror with minimum area on the front wall so that all $$$n$$$ students can see that point through the mirror(The mirror needs to be axially aligned). Find that area for each query independently.

The first line of input contains a single integer $$$T$$$ ($$$1 \le T \le 8000$$$), the number of test cases.

The first line of each test case contains two space-separated integers $$$n$$$ and $$$a$$$ ($$$1 \leq n \leq 2\times10^5$$$)($$$2 \le a \le 10^9$$$), where $$$n$$$ is the number of students, and $$$a$$$ represents that the wall behind the students is located at $$$z=a$$$.

The next $$$n$$$ lines each contains two space-separated integers $$$x_i$$$ and $$$z_i$$$ ($$$-10^9 < x_i < 10^9$$$)($$$0 < z_i < a$$$), representing that the location of the $$$i^{th}$$$ student is ($$$x_i,0,z_i$$$). All locations are distinct.

The next line contains an integer $$$q$$$ ($$$1 \le q \le 2\times 10^5$$$), the number of queries.

The next $$$q$$$ lines each contains two space-separated integers $$$x_i$$$ and $$$y_i$$$ ($$$-10^9 < x_i < 10^9$$$)($$$1 \le y_i \le 10^9$$$), representing that the location of the point in the $$$i^{th}$$$ query is ($$$x_i,y_i,a$$$).

The sum of $$$n$$$ over all test cases doesn't exceed $$$1.5\times10^6$$$. Same goes for $$$q$$$.

For each query, print a single line with the minimum area of the mirror needed. Your answer will be considered correct if its absolute or relative error does not exceed $$$10^{-6}$$$.

1
3 3
-2 1
7 2
3 1
3
2 5
-2 4
8 10

4.5000000000
3.2400000000
10.3500000000