Playing in Threes

Time limit2sMemory limit128 MB

Summary
Given N points and fixed integer side lengths A, B, C for a right triangle, count triples of points forming exactly that right triangle.
Level

Hard8 of 10

Topics
Hash map, Geometry, Math
Solved
No attempts yet

Problem

There are N distinct points on a two-dimensional plane. Choose three of them and count how many choices form a right triangle whose side lengths are exactly A, B, and C.

The lengths satisfy A < B < C and C^2 = A^2 + B^2, so A and B are the two perpendicular sides. Each set of three points is counted once.

Input

The first line contains four integers N, A, B, and C: the number of points and the three side lengths of the right triangle.

  • 1 <= N <= 500,000
  • 1 <= A < B < C <= 250,000
  • C^2 = A^2 + B^2

Each of the next N lines contains two integers x and y, the coordinates of one point.

  • -1,000,000,000 <= x, y <= 1,000,000,000
  • All N points are distinct.

Output

Print the number of valid choices of three points.

Examples1

  1. Example 1

    Input
    4 3 4 5
0 0
3 0
3 4
0 4
    Expected output
    4