시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 14 | 1 | 1 | 7.143% |
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.
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:
4 3 0.0 5.0 3.0 4.0 4.0 3.0 5.0 0.0 5.0 5.0 0.0 0.0 0.0 9.0
2 6 0
For the point (5, 5) the epsilon-isosceles triangles are:
For the point (0, 0) the epsilon-isosceles triangles are:
For the point (0, 9) there are no epsilon-isosceles triangles