The Cross Covers Everything
Time limit3sMemory limit1024 MB
Count ordered point pairs whose cross, formed by the x-range and y-range between the two points, covers every given point.
- Level
Medium6 of 10
- Topics
- Sorting, Prefix sum, Geometry
- Solved
- No attempts yet
Problem
A cross-shaped infinite area on the - plane is specified by two distinct points, as shown in the figure below.

Figure J.1. The cross area specified by points 2 and 4
Given a set of points on the plane, count the ordered pairs that cover all the points. The pair covers a point if , or , or both hold. No two points share an -coordinate or a -coordinate.
Input
The first line contains an integer (), the number of points. Each of the following lines contains two integers and (, ), the coordinates of the -th point. For all , and . The input is a single test case.
Output
Print the number of ordered pairs of points that cover all the points, on one line.
Hint
The cross in the figure is specified by the second and fourth points of the first sample input. It is one of the crosses covering all the points.