| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 10 초 | 1024 MB | 8 | 1 | 1 | 100.000% |
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 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}$.
<<Random points>> means that each coordinate is chosen uniformly and independently between $-10^9$ and 10ドル^9$.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 12 | $n_i \le 10,ドル $N \le 2000,ドル $q_i \le 10,ドル $Q \le 2000$ |
| 2 | 9 | $n_i \le 2000,ドル $N \le 2000,ドル $q_i \le 2000,ドル $Q \le 2000$ |
| 3 | 13 | $n_i \le 5000,ドル $N \le 5000,ドル $q_i \le 10,000円,ドル $Q \le 10,000円$ |
| 4 | 11 | $n_i \le 100,000円,ドル $N \le 100,000円,ドル $q_i \le 100,000円,ドル $Q \le 100,000円,ドル Random points |
| 5 | 8 | Random points |
| 6 | 12 | $n_i \le 5000,ドル $N \le 5000,ドル $q_i \le 100,000円,ドル $Q \le 100,000円$ |
| 7 | 11 | $n_i \le 5000,ドル $N \le 5000$ |
| 8 | 10 | $n_i \le 100,000円,ドル $N \le 100,000円,ドル $q_i \le 100,000円,ドル $Q \le 100,000円$ |
| 9 | 14 |
2 0 5 2 0 0 1 1 0 2 -1 3 0 4 1 2.5 8 4 0 0 6 11 7 13 4 14 0 15 -4 14 -7 13 -6 11 2 1 1.25 1.5
4.000000 5.385165 28.000000 15.000000 17.500000 21.000000
Olympiad > Moscow Open Olympiad in Informatics > Moscow Open Olympiad in Informatics 2021-22 > Day 2 A번