17649번 - Triangle 다국어

문제

In the plane are given N distinct points with coordinates that are decimal fractions. Write program that handles Q queries. Each query is given with two fractional numbers x and y. For each query, the program has to calculate the number of epsilon-isosceles triangles such that each of them has a vertex with coordinates - the point (x, y) and the other two vertices are two different points among the given N points.

We say that a triangle is epsilon-isosceles when the absolute value of the difference between the lengths of two of its sides is less than 0.0001 and for that triangle we do not require for a pair of its vertices to be necessarily non-coincident points and we do not require its three vertices to be necessarily non-collinear.

입력

The first line of the input contains the integers N and Q. Each of the next N lines of the input contains two decimal fractions - coordinates of the next given point. There are following Q lines, each containing two decimal fractions - the coordinates of a point in the next query.

출력

The program should output Q lines, each containing a single integer, equal to the answer to each of the queries printed in the order of the input.

제한

• 0 < N ≤ 1000
• 0 < Q ≤ 1000

The coordinates of all points are fractional numbers in the range [0; 1 000 000], written with a decimal point and with a maximum of 9 digits in the fractional part.

The tests are such that they do not have a triangle which can be counted in more than one way as epsilonisosceles, i.e., if we denote the lengths of the sides of the triangle with a, b and c , where a ≥ b ≥ c, it is not possible to have simultaneously a-b < 0.0001 and b-c < 0.0001.

The tests are such that the following definitions for an epsilon-isosceles triangle yield the same result:

• The absolute value of the difference between the lengths of two of its sides is less than 0.0001
• The absolute value of the difference between the lengths of two of its sides is less than 0.0003
• The absolute value of the difference between the lengths of two of its sides is less than 0.00003

힌트

For the point (5, 5) the epsilon-isosceles triangles are:

• (5, 5), (0, 5), (5, 0)
• (5, 5), (3, 4), (4, 3)

For the point (0, 0) the epsilon-isosceles triangles are:

• (0, 0), (0, 5), (3, 4)
• (0, 0), (0.5), (4, 3)
• (0, 0), (0, 5), (5, 0)
• (0, 0), (3, 4), (4, 3)
• (0, 0), (3, 4), (5, 0)
• (0, 0), (4, 3), (5, 0)

For the point (0, 9) there are no epsilon-isosceles triangles