数字 7

题目描述

在平面的第一象限中有 $N$ 个 7。

第 $i$ 个 7 由连接 $(x_i-1,y_i)$ 与 $(x_i,y_i)$ 的线段,以及连接 $(x_i,y_i-1)$ 与 $(x_i,y_i)$ 的线段组成。

你可以选择其中的任意多个(也可以一个都不选)进行删除。

经过最优删除后,从原点能完整看到的 7 的最大数量是多少?

这里,当且仅当以原点、$(x_i-1,y_i)$、$(x_i,y_i)$、$(x_i,y_i-1)$ 为顶点的四边形内部(不含边界)不与其他的 7 相交时,第 $i$ 个 7 是从原点完整可见的。

输入格式

输入按以下格式从标准输入给出:

$N$
$x_1$ $y_1$
$x_2$ $y_2$
$\hspace{0.45cm}\vdots$
$x_N$ $y_N$

输出格式

输出从原点完整可见的 7 的最大可能数量。

样例

3
1 1
2 1
1 2

2

如果删除第 1 个 7,那么另外两个 7——第 2 个和第 3 个——都能从原点完整看到,这是最优方案。

如果不删除任何 7,则只有第 1 个 7 能从原点完整看到。

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

10

全部保留是最优的。

数据范围

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