시간 제한메모리 제한제출정답맞힌 사람정답 비율
10 초 1024 MB811100.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$.

번호배점제한
112

$n_i \le 10$, $N \le 2000$, $q_i \le 10$, $Q \le 2000$

29

$n_i \le 2000$, $N \le 2000$, $q_i \le 2000$, $Q \le 2000$

313

$n_i \le 5000$, $N \le 5000$, $q_i \le 10\,000$, $Q \le 10\,000$

411

$n_i \le 100\,000$, $N \le 100\,000$, $q_i \le 100\,000$, $Q \le 100\,000$, Random points

58

Random points

612

$n_i \le 5000$, $N \le 5000$, $q_i \le 100\,000$, $Q \le 100\,000$

711

$n_i \le 5000$, $N \le 5000$

810

$n_i \le 100\,000$, $N \le 100\,000$, $q_i \le 100\,000$, $Q \le 100\,000$

914

예제 입력 1

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

예제 출력 1

4.000000
5.385165
28.000000
15.000000
17.500000
21.000000

채점 및 기타 정보

  • 예제는 채점하지 않는다.
  • 이 문제의 채점 우선 순위는 2이다.