406319: GYM102361 A Angle Beats
Description
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.
InputThe 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.
OutputOutput $$$q$$$ lines each contains a non-negative integer, denoting the answer to corresponding query.
ExampleInput4 2 0 1 1 0 0 -1 -1 0 0 0 1 1Output
4 3Note
For query $$$(0,0)$$$, the 4 right-angled triangles are
- $$$\{(0,0),(0,1),(1,0)\}$$$
- $$$\{(0,0),(0,1),(-1,0)\}$$$
- $$$\{(0,0),(0,-1),(1,0)\}$$$
- $$$\{(0,0),(0,-1),(-1,0)\}$$$
For query $$$(1,1)$$$, the 3 right-angled triangles are
- $$$\{(1,1),(0,1),(1,0)\}$$$
- $$$\{(1,1),(0,1),(0,-1)\}$$$
- $$$\{(1,1),(1,0),(-1,0)\}$$$