Triangle

Time limit2sMemory limit512 MB

Summary
Given N plane points and Q query points, count epsilon-isosceles triangles having the query point as vertex and two distinct given points as the others, where two side lengths differ by less than 0.0001.
Level

Medium6 of 10

Topics
Geometry, Hash map, Math
Solved
No attempts yet

Problem

In the plane, N distinct points are given whose coordinates are decimal fractions. Write a program that handles Q queries. Each query gives 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 equal to 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. For that triangle we do not require a pair of its vertices to be necessarily non-coincident points, and we do not require its three vertices to be necessarily non-collinear.

Input

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, the 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.

Output

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.

Constraints

  • 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 epsilon-isosceles. That is, 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

Hint

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.

Examples1

  1. Example 1

    Input
    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
    Expected output
    2
6
0