[Ynoi2000] hpi
题目描述
给定 $n$ 个互不相同的点 $(x_i,y_i)$,共 $m$ 次询问,每次询问给出 $A,B,C$,问满足 $x_i<x_j,\;y_i<y_j,\;Ax_i+By_i+C>0,\;Ax_j+By_j+C>0$ 的二元组 $(i,j)$ 的个数。
输入输出格式
输入格式
第一行两个数 $n,m$。
接下来 $n$ 行每行两个数 $x_i,y_i$,$i=1,\dots,n$。
接下来 $m$ 行每行一个三个数表示一个询问 $A,B,C$。
输出格式
对每个询问,输出一行,包含一个整数,表示这个询问的答案。
输入输出样例
输入样例 #1
5 2
2003 -553
-141 1230
-6854 9658
9319 -1777
7773 3306
1113 -3086 -15864589
162 550 -21287
输出样例 #1
0
1
说明
Idea:nzhtl1477&ccz181078,Solution:ccz181078,Code:ccz181078,Data:ccz181078
对于 $100\%$ 的数据,满足 $A^2+B^2>0$,$|A|,|B|,|C|\le 10^8$,$1\le n,m\le 2\times 10^5$,$|x_i|,|y_i|\le 10^4$,$x_i,y_i$ 均匀随机选取,但保证没有重复的点。
对于 $25\%$ 的数据,满足 $n,m\le 10^3$。
对于另外 $25\%$ 的数据,满足 $A=0$。
对于另外 $25\%$ 的数据,满足 $C=0$。
对于另外 $25\%$ 的数据,无特殊限制。