巧克力王国 BZOJ 2850

巧克力王国

【问题描述】

巧克力王国里的巧克力都是由牛奶和可可做成的。但是并不是每一块巧克力都受王国人民的欢迎，因为大家都不喜欢过于甜的巧克力。对于每一块巧克力，我们设x和y为其牛奶和可可的含量。由于每个人对于甜的程度都有自己的评判标准，所以每个人都有两个参数a和b，分别为他自己为牛奶和可可定义的权重，因此牛奶和可可含量分别为x和y的巧克力对于他的甜味程度即为ax + by。而每个人又有一个甜味限度c，所有甜味程度大于等于c的巧克力他都无法接受。每块巧克力都有一个美味值h。现在我们想知道对于每个人，他所能接受的巧克力的美味值之和为多少

【输入格式】

第一行两个正整数n和m，分别表示巧克力个数和询问个数。接下来n行，每行三个整数x,y,h，含义如题目所示。再接下来m行，每行三个整数a,b,c，含义如题目所示。

【输出格式】

输出m行，其中第i行表示第i个人所能接受的巧克力的美味值之和。

【样例输入】

3 3
1 2 5
3 1 4
2 2 1
2 1 6
1 3 5
1 3 7

【样例输出】

5
0
4

【数据范围】

1 <= n, m <= 50000，-10^9 <= a, b, x, y <= 10^9。

题解：

考虑 ax + by - c 其实是平面上的一条直线，x、y就是点的横坐标和纵坐标

要求 ax + by < c ，就是要求点在 ax + by - c 的下方

那么就用KD树就好了

程序中用了一个 nth_element(a + l, a + m, a + r + 1, cmp) 函数

就是按cmp定义的大小规则，将a数组中l到r中第m大的数放在第m位，比这个数小的数在第m位前，其他在第m位后（乱序）

  1 #include<algorithm>
  2 #include<iostream>
  3 #include<cstring>
  4 #include<cstdlib>
  5 #include<cstdio>
  6 #include<cmath>
  7 #define lc(i) tr[i].l
  8 #define rc(i) tr[i].r
  9 #define mi_x(i) tr[i].mi_x
 10 #define ma_x(i) tr[i].ma_x
 11 #define mi_y(i) tr[i].mi_y
 12 #define ma_y(i) tr[i].ma_y
 13 #define sum(i) tr[i].sum
 14 typedef long long lol;
 15 using namespace std;
 16 inline lol Get()
 17 {
 18     lol x;
 19     lol o = 1;
 20     char c;
 21     while((c = getchar()) < '0' || c > '9')
 22         if(c == '-')
 23             o = -1;
 24     x = c - '0';
 25     while((c = getchar()) >= '0' && c <= '9') x = x * 10 + c - '0';
 26     return x * o;
 27 }
 28 const int me = 1000233;
 29 const lol inf = 214748364721474836; 
 30 struct dot
 31 {
 32     int l, r;
 33     lol x, y, z, sum, mi_x, mi_y, ma_x, ma_y;
 34     dot()
 35     {
 36         mi_x = mi_y = inf;
 37         ma_x = ma_y = -inf;
 38     }
 39 };
 40 dot a[me], tr[me];
 41 lol x, y, z;
 42 int n, m;
 43 int flag;
 44 lol ans;
 45 inline bool operator < (const dot &a, const dot &b)
 46 {
 47     if(!flag) return a.x < b.x;
 48     return a.y < b.y;
 49 }
 50 inline void Update(const int &x)
 51 {
 52     int l = lc(x), r = rc(x);
 53     mi_x(x) = min(tr[x].x, min(mi_x(l), mi_x(r)));
 54     ma_x(x) = max(tr[x].x, max(ma_x(l), ma_x(r)));
 55     mi_y(x) = min(tr[x].y, min(mi_y(l), mi_y(r)));
 56     ma_y(x) = max(tr[x].y, max(ma_y(l), ma_y(r)));
 57     sum(x) = sum(l) + sum(r) + tr[x].z;
 58 }
 59 int Build(const int &l, const int &r, const int &e)
 60 {
 61     int mi = l + r >> 1;
 62     flag = e;
 63     nth_element(a + l, a + mi, a + r + 1);
 64     tr[mi] = a[mi];
 65     if(l < mi) lc(mi) = Build(l, mi - 1, e ^ 1);
 66     if(r > mi) rc(mi) = Build(mi + 1, r, e ^ 1);
 67     Update(mi);
 68     return mi;
 69 }
 70 inline int Check(const int &wx, const int &wy)
 71 {
 72     return (lol) wx * x + wy * y < z;
 73 }
 74 inline int Pos(const int &w)
 75 {
 76     if(!w) return 0;
 77     return Check(mi_x(w), mi_y(w)) + Check(mi_x(w), ma_y(w)) + Check(ma_x(w), mi_y(w)) + Check(ma_x(w), ma_y(w));
 78 }
 79 void Ask(const int &w)
 80 {
 81     int l = lc(w), r = rc(w);
 82     if(Check(tr[w].x, tr[w].y)) ans += tr[w].z;
 83     int le = Pos(l);
 84     if(le)
 85         if(le == 4) ans += sum(l);
 86         else Ask(l);
 87     int ri = Pos(rc(w));
 88     if(ri)
 89         if(ri == 4) ans += sum(r);
 90         else Ask(r);
 91 }
 92 int main()
 93 {
 94     n = Get(), m = Get();
 95     for(int i = 1; i <= n; ++i)
 96         a[i].x = Get(), a[i].y = Get(), a[i].z = Get();
 97     Build(1, n, 0);
 98     for(int i = 1; i <= m; ++i)
 99     {
100         x = Get(), y = Get(), z = Get();
101         ans = 0;
102         Ask(1 + n >> 1);
103         printf("%lld
", ans);
104     }
105 }