Number of Rectangles
Time limit2sMemory limit128 MB
Given up to 5000 points, count axis-aligned rectangles whose four corners are all present among the points.
- Level
Medium5 of 10
- Topics
- Hash map, Combinatorics, Array
- Solved
- No attempts yet
Problem
You are given N distinct points on a two-dimensional plane. Choose four of these points and connect them. Count how many quadrilaterals formed this way are rectangles whose four sides are parallel to either the x-axis or the y-axis.
The rectangle must have positive area, so it must use two distinct x-coordinates and two distinct y-coordinates.
Input
The first line contains the number of points N. (1 <= N <= 5,000)
Each of the next N lines contains the coordinates x and y of one point. Every coordinate is an integer between -1,000,000,000 and 1,000,000,000, inclusive. No two points have the same coordinates.
Output
Print the number of rectangles that can be formed.