[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\%$ 的数据,无特殊限制。