24966번 - The Cross Covers Everything 다국어

A cross-shaped infinite area on the $x$-$y$ plane can be specified by two distinct points as depicted on the figure below.

Figure J.1. The cross area specified by two points numbered $2$ and $4$

Given a set of points on the plane, you are asked to figure out how many pairs of the points form a cross-shaped area that covers all the points. To be more precise, when $n$ points with coordinates $(x_i , y_i$) ($i = 1, \dots , n$) are given, the ordered pair $<p, q>$ is said to cover a point $(x, y)$ if $x_p ≤ x ≤ x_q$, $y_p ≤ y ≤ y_q$, or both hold. Your task is to find how many pairs $<p, q>$ cover all the $n$ points. No two given points have the same $x$-coordinate nor the same $y$-coordinate.

The input consists of a single test case of the following format.

$\begin{align*}& n \\ & x_1 \, y_1 \\ & \vdots \\ & x_n \, y_n\end{align*}$

The first line contains an integer $n$ ($2 ≤ n ≤ 2 × 10^5$), which is the number of points given. Two integers $x_i$ and $y_i$ in the $i$-th line of the following $n$ lines are the coordinates of the $i$-th point ($1 ≤ x_i ≤ 10^6$, $1 ≤ y_i ≤ 10^6$). You may assume that $x_j \ne x_k$ and $y_j \ne y_k$ hold for all $j \ne k$.

Print in a line the number of ordered pairs of points that satisfy the condition.

Figure J.1 depicts the cross specified by two points numbered 2 and 4, that are the second and the fourth points of the Sample Input 1. This is one of the crosses covering all the points.