There are $n$ linear functions $f_i(x)=a[i]x+b[i], 1<= i <=n$. Define $F(x)=max{f_i(x) : 1<= i <=n}$.
Given $m$ x-values $c[1],c[2],…, c[m]$, please compute the sum of all $F(c[j])$, i.e., $F(c[1])+ F(c[2])+…+ F(c[m])$.
To be continued…
1#include <bits/stdc++.h>
2
3using namespace std;
4
5typedef long long ll;
6typedef pair<ll, ll> ii;
7
8bool cmp(const ii &a, const ii &b)
9{
10 if (a.first == b.first)
11 return a.second > b.second;
12 return a.first < b.first;
13}
14
15ll cal(ii coeff, ll x)
16{
17 return coeff.first * x + coeff.second;
18}
19
20double x_val(ii a, ii b)
21{
22 return (b.second - a.second) / (a.first - b.first);
23}
24
25#define EPS 1e-9
26
27void solve(int n, int m)
28{
29 ii coeff[n];
30 for (int i = 0; i < n; i++)
31 scanf("%lld %lld", &coeff[i].first, &coeff[i].second);
32 ll x[m];
33 for (int i = 0; i < m; i++)
34 scanf("%lld", &x[i]);
35
36 sort(coeff, coeff + n, cmp);
37 sort(x, x + m);
38
39 vector<ii> ok;
40 ok.push_back(coeff[0]);
41 for (int i = 1; i < n; i++) {
42 while (ok.size() > 1) {
43 int sz = ok.size() - 1;
44 if (ok[sz].first == coeff[i].first ||
45 (x_val(ok[sz], ok[sz - 1]) - x_val(ok[sz], coeff[i]) > -EPS))
46 ok.pop_back();
47 else
48 break;
49 }
50 ok.push_back(coeff[i]);
51 }
52
53 // for(auto i : ok)
54 // printf("%lld %lld\n", i.first, i.second);
55
56 ll ans = 0;
57 int idx = 0;
58 for (int i = 0; i < m; i++) {
59 while (idx != (int)ok.size() - 1 &&
60 cal(ok[idx], x[i]) < cal(ok[idx + 1], x[i])) {
61 idx++;
62 }
63 ans += cal(ok[idx], x[i]);
64 }
65
66 printf("%lld\n", ans);
67}
68
69int main()
70{
71 int n, m;
72 while (scanf("%d %d", &n, &m) == 2 && (n != 0)) {
73 solve(n, m);
74 }
75
76 return 0;
77}