80. 靜態凸包搜尋

0 Judge

Code: 0


靜態凸包搜尋

題目敘述

平面上有 $n$ 條直線函數 $f_i(x) = a_i x + b_i$,有 $m$ 個詢問 $x_j$,每次詢問請輸出 $\max_{i} f_i(x_j) - \min_{i} f_i(x_j)$

輸入

每筆測資只有一個輸入

第一行有兩個數字 $n, m$

接下來有 $n$ 行,每行有兩個數字 $a_i, b_i$ 代表一個直線函數 $f_i(x) = a_i x + b_i$

接下來下面一行有 $m$ 個數字,第 $j$ 個數字代表 $x_j$

$$ 1 \leq n, m \leq 10^5 $$

$$ |x_j|, |a_i|, |b_i| \leq 10^6 $$

輸出

輸出 $m$ 行,第 $j$ 行有一個數字 $\max_{i} f_i(x_j) - \min_{i} f_i(x_j)$

Sample Input

5 5
1 -7
3 -3
0 7
-5 -6
10 9
-15
-3
-8
7
11

Sample Output

210
30
105
120
180

Sample Input

5 5
-9 -6
8 14
0 -1
-10 -8
-13 -12
9
5
13
-6
9

Sample Output

215
131
299
100
215

Hint

可以參考講義程式碼(講義有一部分有誤)

https://gist.github.com/rareone/aeb1d7ca0633d84aea6599a302cfb049


Judge Setting

run-time limit: 5000 ms
memory limit: 268435456 byte
測資數量: 5