Rectangles for Four Friends
Time limit2sMemory limit128 MB
Given up to 500,000 distinct points, count axis-aligned rectangles with fixed side lengths A and B whose corners are all present in the point set.
- Level
Medium6 of 10
- Topics
- Hash map, Two pointers, Array
- Solved
- No attempts yet
Problem
There are N distinct points on a two-dimensional plane. Four people each choose one point, and the four chosen points should be the corners of a rectangle.
The rectangle's sides must be parallel to the x-axis or the y-axis. Its horizontal side length must be A, and its vertical side length must be B. Count how many such rectangles can be made using only the given points.
Input
The first line contains the number of points N. (5 <= N <= 500,000)
The second line contains the desired horizontal length A and vertical length B. (1 <= A <= 1,000, 1 <= B <= 1,000)
Each of the next N lines contains two integers x and y, the coordinates of one point. Each coordinate is between -1,000,000,000 and 1,000,000,000, inclusive. All N points are distinct.
Output
Print the number of rectangles that can be made.
The answer is at most 2^31 - 1.