PROBLEM LINKS
DIFFICULTY
EASY
EXPLANATION
The key point of this problem is: there is not any three of the points sharing a same X-coordinate; and the given points are all separate. So we can manage all “vertical” segments in a list by their X-coordinate and length. Then we group the same segments in length by sorting, for every group of K segments, we have K * (K-1)/2 respective rectangles. Sum up all results and print out!
Complexity: O(N x log2 N)
SETTER’S SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here.