题目描述
给定 n 个点 (xi,yi,ci),i=1,2,…,n,共有 m 次查询操作,每次查询给定 A,B,C,问满足 Axi+Byi+C<0,Axj+Byj+C<0,ci=cj 的二元组 (i,j) 的个数。
输入格式
第一行两个整数 n m;
接下来 n 行,每行三个整数 xi yi ci,i=1,2,…,n;
接下来 m 行,每行三个整数 A B C。
输出格式
共 m 行,每行一个整数,表示答案。
样例数据
样例输入
5 2 2 -1 1 0 -3 5 1 -3 2 1 3 5 3 2 2 1 2 4 1 -2 -9
样例输出
2 9
样例解释:
第一个查询对应 (2,2)(3,3);
第二个查询对应 (1,1)(2,2)(2,4)(3,3)(3,5)(4,2)(4,4)(5,3)(5,5)。
子任务
对 5% 的数据,n,m≤103;
对另外 10% 的数据,ci≤2;
对另外 15% 的数据,ci≤100;
对另外 15% 的数据,max;
对另外 15\% 的数据,|A|=|B|=1;
对另外 10\% 的数据,n\le 20000,\;m\le 200000;
对于其余数据,无特殊约束。
每部分数据构成子任务,无依赖关系。
所有数据满足:
1\le n\le 50000;
1\le m\le 500000;
A^2+B^2>0;
-10^9\le x_i,y_i,A,B,C\le 10^9;
1\le c_i\le n;
所有数值为整数;
当 i\ne j 时,x_i\ne y_i 或 x_j\ne y_j。
对于除了子任务 4 以外的数据,满足 n 个点的 x,y 坐标分别在某个预设的区间内均匀随机选取,并保证没有重复的点,且对于第 i 个点,c_i 和 x_i,y_i 是分别独立地随机选取的,但 c_i 的分布没有特殊限制。