Codeforces Round #573 (Div. 1) D. Tokitsukaze and Strange Rectangle

https://codeforces.com/contest/1190/problem/D

If there is a point on the boundary of the rectangle, strictly speaking, this point is not contained in the rectangle, but we can consider it is contained in. The reason why we can include it by slightly expand the rectangle. Each the left side, right side and bottom side of the rectangle has at least one point on itself. The reason why we can shrink the rectangle until collides some points.

In this condition, there exists at least one point on the bottom side, then focus on the left-most point among them.

Let us count the rectangles such that point P is on its bottom side and is the left-most point. If we can solve this problem, we can obtain the answer by summing up the answer for each P.

To solve this problem, we should know the number of possible left sides and right sides, respectively. Line sweep and BIT will be useful.