P13545 [OOI 2022] Plane stretching

Igor is a big fan of geometry, so he bought himself a plane together with a set $P$ of $n$ distinct points, $i$-th of them is located at $(x_i,y_i)$. It was extremely easy for Igor to find two points among them furthest away from each other. He quickly got bored and decided to come up with $q$ real numbers $\alpha_1$, $\alpha_2$, $\alpha_3$, $\ldots$, $\alpha_q$. For each of these numbers Igor is interested in the maximum possible distance between any two of the points if he scales the $x$-coordinate of each point by $\alpha_j$. Formally speaking, he is interested in finding the two furthest points in a set $(x_i \cdot \alpha_j, y_i)$. Please help Igor!

Each input contains multiple test cases. The first line contains two integers $t$ and $g$ ($1 \le t \le 250\,000$, $0 \le g \le 9$) --- the number of test cases and the group number to indicate additional constraints those test cases might satisfy. Then $t$ test cases follow. Each test case starts with two integers $n$ and $q$ $(2 \le n \le 500\,000, 1 \le q \le 500\,000)$ --- the number of points and the number of queries. The following $n$ lines contain the coordinates of each point $x_i$ and $y_i$ $(-10^9 \le x_i, y_i \le 10^9)$. It is guaranteed that all points within a test case are distinct. The following $q$ lines contain the queries, each of them is identified by a single $\textbf{real}$ number $\alpha_j$ $(1 \le \alpha_j \le 10^9)$ --- the scaling coefficients. Let us denote the sum of values $n_i$ among all test cases as $N$, and the sum of values $q_i$ as $Q$. It is guaranteed that $N, Q \le 500\,000$.

For each test case output $q$ real numbers: the answer to $i$-th query. Your answer will be accepted if its absolute or relative error does not exceed $10^{-6}$. More precisely, if $a$ is your answer, and $b$ is the judges' answer, then your answer will be considered correct in case $\frac{|a-b|}{\max(b,1)} \le 10^{-6}$.

### Scoring The testset for this problem consists of 9 test groups. You get points for a group only if your solution passes all tests from this group and from all the required groups. $\textbf{Offline-evaluation}$ means that you will not get immediate feedback for this group and you will be able to see the outcome only after the end of the competition. Random points means that each coordinate is chosen uniformly and independently between $-10^9$ and $10^9$. | Group | Points | Additional constraints | < | < | < | Required groups | Comment | |:-----:|:------:|:---------------------:|:-:|:-:|:-:|:---------------:|:-------:| | | | $n_i$ | $N$ | $q_i$ | $Q$ | | | | 0 | 0 | -- | -- | -- | -- | -- | Sample test cases | | 1 | 12 | $n_i \le 10$ | $N \le 2000$ | $q_i \le 10$ | $Q \le 2000$ | 0 | | | 2 | 9 | $n_i \le 2000$ | $N \le 2000$ | $q_i \le 2000$ | $Q \le 2000$ | 0 -- 1 | | | 3 | 13 | $n_i \le 5000$ | $N \le 5000$ | $q_i \le 10\,000$ | $Q \le 10\,000$ | 0 -- 2 | | | 4 | 11 | $n_i \le 100\,000$ | $N \le 100\,000$ | $q_i \le 100\,000$ | $Q \le 100\,000$ | -- | Random points | | 5 | 8 | -- | -- | -- | -- | 4 | Random points | | 6 | 12 | $n_i \le 5000$ | $N \le 5000$ | $q_i \le 100\,000$ | $Q \le 100\,000$ | 0 -- 3 | | | 7 | 11 | $n_i \le 5000$ | $N \le 5000$ | -- | -- | 0 -- 3, 6 | | | 8 | 10 | $n_i \le 100\,000$ | $N \le 100\,000$ | $q_i \le 100\,000$ | $Q \le 100\,000$ | 0 -- 4, 6 | | | 9 | 14 | -- | -- | -- | -- | 0 -- 8 | **Offline-evaluation** |