Given $$$n$$$ points $$$P_1, P_2, \cdots, P_n$$$ on 2D plane and $$$q$$$ queries. In $$$i$$$-th query, a point $$$A_i$$$ is given, and you should determine the number of tuples $$$(u, v)$$$ that $$$1 \le u < v \le n$$$ and $$$A_i, P_u, P_v$$$ form a non-degenerate right-angled triangle.
The first line contains two positive integers $$$n,q~(2\le n \le 2\,000, 1\le q \le 2\,000)$$$, denoting the number of given points and the number of queries.
Next $$$n$$$ lines each contains two integers $$$x_i, y_i~(|x_i|,|y_i| \le 10^9)$$$, denoting a given point $$$P_i$$$.
Next $$$q$$$ lines each contains two integers $$$x_i, y_i~(|x_i|,|y_i| \le 10^9)$$$, denoting a query point $$$A_i$$$.
It is guaranteed that the input $$$n+q$$$ points are all pairwise distinct.
Output $$$q$$$ lines each contains a non-negative integer, denoting the answer to corresponding query.
4 2 0 1 1 0 0 -1 -1 0 0 0 1 1
4 3
For query $$$(0,0)$$$, the 4 right-angled triangles are
For query $$$(1,1)$$$, the 3 right-angled triangles are
Name |
---|