RECTCNT - Editorial

PROBLEM LINKS

Practice
Contest

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.

2 Likes