QOJ.ac

QOJ

Time Limit: 3 s Memory Limit: 1024 MB Total points: 100

#3803. 十字覆盖一切

Statistics

$x$-$y$ 平面上一个十字形的无限区域可以由两个不同的点来确定,如下图所示。

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

给定平面上的一组点,你需要计算有多少对点形成的十字形区域覆盖了所有点。更准确地说,给定 $n$ 个坐标为 $(x_i, y_i)$ ($i = 1, \dots, n$) 的点,对于有序点对 $\langle p, q \rangle$(其中 $p=(x_p, y_p), q=(x_q, y_q)$),如果对于任意点 $(x, y)$,满足 $x_p \le x \le x_q$ 或 $y_p \le y \le y_q$(或两者同时满足),则称该点对覆盖了该点。你的任务是找出有多少个有序点对 $\langle p, q \rangle$ 能够覆盖所有 $n$ 个点。题目保证任意两个给定点的 $x$ 坐标互不相同,且 $y$ 坐标也互不相同。

此外,根据比赛期间的补充说明,所计数的有序点对 $\langle p, q \rangle$ 还必须满足 $x_p \le x_q$ 以及 $y_p \le y_q$ 的条件。

输入格式

输入包含单个测试用例,格式如下:

$n$ $x_1 \ y_1$ $\vdots$ $x_n \ y_n$

第一行包含一个整数 $n$ ($2 \le n \le 2 \times 10^5$),表示给定点的数量。接下来的 $n$ 行中,第 $i$ 行包含两个整数 $x_i$ 和 $y_i$,表示第 $i$ 个点的坐标 ($1 \le x_i \le 10^6, 1 \le y_i \le 10^6$)。你可以假设对于所有 $j \neq k$,都有 $x_j \neq x_k$ 且 $y_j \neq y_k$。

输出格式

输出一行,表示满足条件的有序点对的数量。

样例

样例输入 1

4
2 1
1 2
6 3
5 4

样例输出 1

4

样例输入 2

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

样例输出 2

9

说明

图 J.1 展示了由编号为 2 和 4 的两个点(即样例输入 1 中的第二个和第四个点)所确定的十字形区域。这是覆盖所有点的十字形区域之一。

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.