#P6593. 覆盖所有点的十字形区域

覆盖所有点的十字形区域

题目描述

在 x−yx-y 平面上,可以通过两个不同的点来指定一个十字形的无限区域,如下图所示。

图 J.1. 由编号为 2 和 4 的两个点指定的十字区域。

给定一组平面上的点,你需要计算有多少对点形成一个覆盖所有点的十字形区域。更确切地说,当给定 nn 个点,坐标为 (xi,yi)(x_i, y_i)(i=1,…,ni = 1, \ldots, n),有序对 hp,qih_p, q_i 被称为覆盖点 (x,y)(x, y),如果满足以下条件之一:

  • xp≤x≤xqx_p \leq x \leq x_q 或 yp≤y≤yqy_p \leq y \leq y_q,或者两个条件同时成立。

你的任务是找出有多少对 hp,qih_p, q_i 覆盖所有的 nn 个点。所有给定的点的 xx 坐标和 yy 坐标都是不同的。

输入

输入由一个测试用例组成,格式如下:

nx1 y1⋮xn ynn \\ x_1\ y_1 \\ \vdots \\ x_n\ y_n

第一行包含一个整数 nn (2≤n≤2×105)(2 \leq n \leq 2 \times 10^5),表示给定点的数量。接下来的 nn 行包含两个整数 xix_i 和 yiy_i,表示第 ii 个点的坐标 (1≤xi≤106,1≤yi≤106)(1 \leq x_i \leq 10^6, 1 \leq y_i \leq 10^6)。你可以假设对于所有 j≠kj \neq k,都有 xj≠xkx_j \neq x_k 和 yj≠yky_j \neq y_k。

输出

在一行中输出满足条件的有序点对的数量。

4
2 1
1 2
6 3
5 4
4
20
15 9
14 13
2 7
10 5
11 17
13 8
9 3
8 12
6 4
19 18
12 1
3 2
5 10
18 11
4 19
20 16
16 15
1 14
7 6
17 20
9

补充说明

图 J.1 描述了由编号为 2 和 4 的两个点指定的十字形区域,这两个点分别是样例输入 1 中的第二个和第四个点。这是覆盖所有点的十字形区域之一。

修订

需要添加条件,使得有序对 hp,qih_p, q_i 需要满足 xp≤xqx_p \leq x_q 和 yp≤yqy_p \leq y_q。这一点在比赛期间进行了公告。

因此,最终的要求是:

  • 对于有序对 hp,qih_p, q_i,需要满足以下条件:
    • xp≤xqx_p \leq x_q
    • yp≤yqy_p \leq y_q

这意味着在计算覆盖所有点的十字形区域时,必须确保选择的两个点的 xx 和 yy 坐标符合上述不等式。