RECTANGL - Rectangles
You are given a set S of N points in the plane and must count the number of distinct axis-parallel rectangles whose four vertices all lie in S (that is, count those rectangles which have two sides parallel to the x-axis, and the other two sides parallel to the y-axis).
Input
The first line of the input is N (1 ≤ N ≤ 250000), the number of points in S. N lines then follow, where the i-th line is of the form "xi yi", giving the coordinates of a point (xi, yi) in S. All given points are distinct, and all coordinates fit into a 32-bit signed integer.
Output
Your output should consist of a single number, the number of distinct axis-parallel rectangles whose four vertices all lie in S, followed by a newline.
Example
Input: 6 -1 0 -1 1 0 0 0 1 1 0 1 1 Output: 3
hide comments
Renzo:
2020-05-15 16:54:29
Is the TL too strict?
|
Added by: | Minilek |
Date: | 2007-10-25 |
Time limit: | 1s-4.273s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ERL JS-RHINO NODEJS PERL6 VB.NET |
Resource: | MIT Individual Contest 2007 |