巧克力王国
【问题描述】
巧克力王国里的巧克力都是由牛奶和可可做成的。但是并不是每一块巧克力都受王国人民的欢迎，因为大家都不喜欢过于甜的巧克力。对于每一块巧克力，我们设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位后（乱序）
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#define lc(i) tr[i].l
#define rc(i) tr[i].r
#define mi_x(i) tr[i].mi_x
#define ma_x(i) tr[i].ma_x
#define mi_y(i) tr[i].mi_y
#define ma_y(i) tr[i].ma_y
#define sum(i) tr[i].sum
typedef long long lol;
using namespace std;
inline lol Get()
{
lol x;
lol o = ;
char c;
while((c = getchar()) < '' || c > '')
if(c == '-')
o = -;
x = c - '';
while((c = getchar()) >= '' && c <= '') x = x * + c - '';
return x * o;
}
const int me = ;
const lol inf = ;
struct dot
{
int l, r;
lol x, y, z, sum, mi_x, mi_y, ma_x, ma_y;
dot()
{
mi_x = mi_y = inf;
ma_x = ma_y = -inf;
}
};
dot a[me], tr[me];
lol x, y, z;
int n, m;
int flag;
lol ans;
inline bool operator < (const dot &a, const dot &b)
{
if(!flag) return a.x < b.x;
return a.y < b.y;
}
inline void Update(const int &x)
{
int l = lc(x), r = rc(x);
mi_x(x) = min(tr[x].x, min(mi_x(l), mi_x(r)));
ma_x(x) = max(tr[x].x, max(ma_x(l), ma_x(r)));
mi_y(x) = min(tr[x].y, min(mi_y(l), mi_y(r)));
ma_y(x) = max(tr[x].y, max(ma_y(l), ma_y(r)));
sum(x) = sum(l) + sum(r) + tr[x].z;
}
int Build(const int &l, const int &r, const int &e)
{
int mi = l + r >> ;
flag = e;
nth_element(a + l, a + mi, a + r + );
tr[mi] = a[mi];
if(l < mi) lc(mi) = Build(l, mi - , e ^ );
if(r > mi) rc(mi) = Build(mi + , r, e ^ );
Update(mi);
return mi;
}
inline int Check(const int &wx, const int &wy)
{
return (lol) wx * x + wy * y < z;
}
inline int Pos(const int &w)
{
if(!w) return ;
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));
}
void Ask(const int &w)
{
int l = lc(w), r = rc(w);
if(Check(tr[w].x, tr[w].y)) ans += tr[w].z;
int le = Pos(l);
if(le)
if(le == ) ans += sum(l);
else Ask(l);
int ri = Pos(rc(w));
if(ri)
if(ri == ) ans += sum(r);
else Ask(r);
}
int main()
{
n = Get(), m = Get();
for(int i = ; i <= n; ++i)
a[i].x = Get(), a[i].y = Get(), a[i].z = Get();
Build(, n, );
for(int i = ; i <= m; ++i)
{
x = Get(), y = Get(), z = Get();
ans = ;
Ask( + n >> );
printf("%lld\n", ans);
}
}