80. 靜態凸包搜尋

靜態凸包搜尋

題目敘述

平面上有 $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