# AP325 Q-3-14. 線性函數(@@)
###### tags: `程式設計`
online judge: TCIRC
link: https://judge.tcirc.tw/ShowProblem?problemid=d038

## 題目敘述
有 $N$ 線性函數 $f_i(x)=a_ix+b_i，1\leq i \leq N$。定義 $F(x)=max_if_i(x)$。輸入 $c[i], 1\leq i \leq m$，請計算 $\sum_{i=1}^nF(c[i])$。

## 輸入說明
第一行是 $N$ 與 $m$。接下來有 $N$ 行，依序每行兩個整數 $a_i$ 與 $b_i$，最後一行有$m$個整數$c[1],c[2],⋯,c[m]$。每一行的相鄰數字間以空白隔開。$N\leq 10^5$， $m\leq 5\times10^4$，輸入整數絕對值不超過 $10^7$，答案不超過 $10^{15}$。

### 範例輸入

4 5
-1 0
1 0
-2 -3
2 -3
4 -5 -1 0 2

### 範例輸出

15

**範例的圖**

### AP325的提示

## 想法
先找到提示中，組成紅色線的那些線，並把其他不相關的線刪掉，再記錄紅色線轉彎地方的點的$x$座標，以知道哪些$c[i]$要用哪一條線去算$y$值，最後再將$c[i]$由小到大，依序求解。

### 1.尋找符合的線
維護一個stack，裡面的線皆是當前的解，依斜率由小到大加入，如果即將加入的線，比他前面的線還好時，就可以把前面的線pop掉。

- 如何判斷當前的線是否比上一條好?


數字代表放入stack的順序，令$x_{a,b}$代表**直線a**和**直線b**交的$x$座標。
當**直線3**沒有比**直線2**好的時候，如左圖，$x_{1,2} \lt x_{2,3}$。
而**直線3**比**直線2**好的時候，如右圖，$x_{1,2} \gt x_{2,3}$。
所以得到一個結論，當$x_{n-1,n-2} \gt x_{n,n-1}$，**直線n-1**就不會是可以找到最大值的線。
- 例外
當兩直線平行時，會找不到兩線所交的點，此時就按照兩線的$b$來比，較大的會在較上面，所以就捨棄掉較小的。

### 2.找到各c[i]的最大y值
過濾掉一些不會用到的線之後，用一個陣列去紀錄線與線之間的$x$座標，去找$c[i]$所對應到的直線，並帶入求解。(參考Code 67 ~ 73行)

## Code

#include<iostream>
#include<algorithm>
#define a first
#define b second
#define x first
#define y second
#define MAX_N 100020
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;

pll line[MAX_N];
pll dq[MAX_N]; // actually it's a stack
ll C[MAX_N];
double pos[MAX_N];

int lf = 0, rt = 0;

pdd getPoint(pll p1, pll p2) {
	pdd res;
	double a1 = p1.a, b1 = p1.b;
	double a2 = p2.a, b2 = p2.b;
	res.x = (b2 - b1) / (a1 - a2);
	res.y = (a2*b1 - a1*b2) / (a2 - a1);
	return res;
}

bool discardLast(int idx) {
	if (line[idx].a == dq[rt-1].a) {
		return true;
	}
	pdd p = getPoint(line[idx], dq[rt-1]);
	pdd lp = getPoint(dq[rt-1], dq[rt-2]);
	if (p.x > lp.x) {
		return false;
	} else {
		return true;
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int N, M;
	cin >> N >> M;
	for (int i = 0;i < N;i++) {
		cin >> line[i].a >> line[i].b;
	}
	for (int i = 0;i < M;i++) {
		cin >> C[i];
	}
	sort(line, line+N);
	sort(C, C+M);
	for (int i = 0;i < N;i++) {
		while (rt - lf >= 2 && discardLast(i)) {
			--rt;
		}
		dq[rt++] = line[i];
	}
	for (int i = lf, idx = 0;i <= rt-2;i++, idx++) {
		pdd p = getPoint(dq[i], dq[i+1]);
		pos[idx] = p.x;
	}
	ll ans = 0;
	int idx = 0;
	for (int i = 0;i < M;i++) {
		while (idx < rt-lf-1 && C[i] > pos[idx]) {
			idx++;
		}
		pll p = dq[lf+idx];
		ans += (p.a*C[i] + p.b);
	}
	cout << ans << '\n';
	return 0;
}

### Result

- 最後更新 [time=Fri, Sep 24, 2021 10:54 AM]