#P8261. [CTS2022] 袜子

[CTS2022] 袜子

题目描述

给定 nn 个点 (xi,yi,ci)(x_i,y_i,c_i)i=1,2,,ni=1,2,\dots,n,共有 mm 次查询操作,每次查询给定 A,B,CA,B,C,问满足 Axi+Byi+C<0Ax_i+By_i+C<0Axj+Byj+C<0Ax_j+By_j+C<0ci=cjc_i=c_j 的二元组 (i,j)(i,j) 的个数。

输入格式

第一行两个整数 n mn\ m

接下来 nn 行,每行三个整数 xi yi cix_i\ y_i\ c_ii=1,2,,ni=1,2,\dots,n

接下来 mm 行,每行三个整数 A B CA\ B\ C

输出格式

mm 行,每行一个整数,表示答案。

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)(2,2)(3,3)

第二个查询对应 (1,1)(2,2)(2,4)(3,3)(3,5)(4,2)(4,4)(5,3)(5,5)(1,1)(2,2)(2,4)(3,3)(3,5)(4,2)(4,4)(5,3)(5,5)

数据范围:

5%5\% 的数据,n,m103n,m\le 10^3

对另外 10%10\% 的数据,ci2c_i\le 2

对另外 15%15\% 的数据,ci100c_i\le 100

对另外 15%15\%​ 的数据,max(xi,yi)=106\max(|x_i|,|y_i|)=10^6​;

对另外 15%15\% 的数据,A=B=1|A|=|B|=1

对另外 10%10\% 的数据,n20000,  m200000n\le 20000,\;m\le 200000

对于其余数据,无特殊约束。

每部分数据构成子任务,无依赖关系。

所有数据满足:

1n500001\le n\le 50000

1m5000001\le m\le 500000

A2+B2>0A^2+B^2>0

109xi,yi,A,B,C109-10^9\le x_i,y_i,A,B,C\le 10^9

1cin1\le c_i\le n

所有数值为整数;

iji\ne j 时,xixjx_i\ne x_jyiyjy_i\ne y_j

对于除了子任务 4 以外的数据,满足 nn 个点的 x,yx,y 坐标分别在某个预设的区间内均匀随机选取,并保证没有重复的点,且对于第 ii 个点,cic_ixi,yix_i,y_i 是分别独立地随机选取的,但 cic_i 的分布没有特殊限制。