AT_abc225_e [ABC225E] フ

题目描述

在二维平面第一象限上有 $N$ 个“フ”字形。

第 $i$ 个“フ”字形（$1 \leq i \leq N$）由两条线段组成，分别连接 $(x_i-1, y_i)$ 与 $(x_i, y_i)$，以及 $(x_i, y_i-1)$ 与 $(x_i, y_i)$。

你可以从这 $N$ 个“フ”字形中选择 $0$ 个或多个进行删除。

请问，经过适当选择要删除的“フ”字形后，从原点能够完整看到的“フ”字形的最大数量是多少？

这里，从原点能够完整看到某个“フ”字形（记为第 $i$ 个）的充要条件如下：

• 以原点、$(x_i-1, y_i)$、$(x_i, y_i)$、$(x_i, y_i-1)$ 为顶点的四边形的内部（不包括边界）与其他任何“フ”字形没有公共部分。

输入格式

输入按以下格式从标准输入读入。

$N$
$x_1\ y_1$
$x_2\ y_2$
$\vdots$
$x_N\ y_N$

输出格式

输出从原点能够完整看到的“フ”字形的最大数量。

输入输出样例 #1

输入 #1

3
1 1
2 1
1 2

输出 #1

2

输入输出样例 #2

输入 #2

10
414598724 87552841
252911401 309688555
623249116 421714323
605059493 227199170
410455266 373748111
861647548 916369023
527772558 682124751
356101507 249887028
292258775 110762985
850583108 796044319

输出 #2

10

说明/提示

限制条件

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq x_i, y_i \leq 10^9$
• $(x_i, y_i) \neq (x_j, y_j)\ (i \neq j)$
• 所有输入均为整数

样例解释 1

当删除第 $1$ 个“フ”字形时，从原点可以看到第 $2$ 个和第 $3$ 个“フ”字形，共 $2$ 个，这是最大值。如果一个都不删，则从原点只能看到第 $1$ 个“フ”字形。

样例解释 2

不删除任何“フ”字形是最优的选择。

由 ChatGPT 4.1 翻译