{"raw_statement":[{"iden":"statement","content":"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.\n\nYou 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.\n\nThe first line of input contains a single integer $T$ ($1 <= T <= 8000$), the number of test cases.\n\nThe first line of each test case contains two space-separated integers $n$ and $a$ ($1 <= n <= 2 times 10^5$)($2 <= a <= 10^9$), where $n$ is the number of students, and $a$ represents that the wall behind the students is located at $z = a$.\n\nThe 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^(t h)$ student is ($x_i, 0, z_i$). All locations are distinct.\n\nThe next line contains an integer $q$ ($1 <= q <= 2 times 10^5$), the number of queries.\n\nThe next $q$ lines each contains two space-separated integers $x_i$ and $y_i$ ($-10^9 < x_i < 10^9$)($1 <= y_i <= 10^9$), representing that the location of the point in the $i^(t h)$ query is ($x_i, y_i, a$).\n\nThe sum of $n$ over all test cases doesn't exceed $1. 5 times 10^6$. Same goes for $q$.\n\nFor 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)$.\n\n"},{"iden":"input","content":"The first line of input contains a single integer $T$ ($1 <= T <= 8000$), the number of test cases.The first line of each test case contains two space-separated integers $n$ and $a$ ($1 <= n <= 2 times 10^5$)($2 <= a <= 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^(t h)$ student is ($x_i, 0, z_i$). All locations are distinct.The next line contains an integer $q$ ($1 <= q <= 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 <= y_i <= 10^9$), representing that the location of the point in the $i^(t h)$ query is ($x_i, y_i, a$).The sum of $n$ over all test cases doesn't exceed $1. 5 times 10^6$. Same goes for $q$."},{"iden":"output","content":"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)$."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case:  \n- Let $ n \\in \\mathbb{Z} $ be the number of students.  \n- Let $ a \\in \\mathbb{R} $ be the $ z $-coordinate of the back wall ($ z = a $).  \n- Let $ S = \\{ (x_i, z_i) \\mid i \\in \\{1, \\dots, n\\} \\} $ be the set of student positions, where each student $ i $ is at $ (x_i, 0, z_i) $.  \n- Let $ Q = \\{ (x_j, y_j) \\mid j \\in \\{1, \\dots, q\\} \\} $ be the set of query points, each at $ (x_j, y_j, a) $ on the back wall.  \n\n**Constraints**  \n1. $ 1 \\le T \\le 8000 $  \n2. $ 1 \\le n \\le 2 \\times 10^5 $, $ 2 \\le a \\le 10^9 $  \n3. $ -10^9 < x_i < 10^9 $, $ 0 < z_i < a $ for all students  \n4. $ 1 \\le q \\le 2 \\times 10^5 $  \n5. $ -10^9 < x_j < 10^9 $, $ 1 \\le y_j \\le 10^9 $ for all queries  \n6. $ \\sum n \\le 1.5 \\times 10^6 $, $ \\sum q \\le 1.5 \\times 10^6 $  \n\n**Objective**  \nFor each query point $ P = (x_p, y_p, a) $, find the minimum area of an axis-aligned rectangular mirror on the front wall $ z = 0 $ such that every student can see $ P $ via reflection.  \n\nThe mirror is defined by its projections on the $ x $- and $ y $-axes:  \n- Let $ x_{\\min} = \\min_{i} \\left( x_i + \\frac{z_i}{a - z_i} (x_p - x_i) \\right) $  \n- Let $ x_{\\max} = \\max_{i} \\left( x_i + \\frac{z_i}{a - z_i} (x_p - x_i) \\right) $  \n- Let $ y_{\\min} = \\min_{i} \\left( \\frac{z_i}{a - z_i} y_p \\right) $  \n- Let $ y_{\\max} = \\max_{i} \\left( \\frac{z_i}{a - z_i} y_p \\right) $  \n\nThen the minimum mirror area is:  \n$$\n\\text{Area} = (x_{\\max} - x_{\\min}) \\cdot (y_{\\max} - y_{\\min})\n$$","simple_statement":"For each query, find the smallest rectangular mirror on the front wall (z=0) that lets all students see a given point on the back wall (z=a). The mirror must be axis-aligned. Output the minimum area of such a mirror.","has_page_source":false}