E - 7

得分: 500 分

问题描述

在平面上的第一象限内画了 $N$ 个数字 7。

第 $i$ 个数字 7 是由一条连接 $(x_i-1,y_i)$ 和 $(x_i,y_i)$ 的线段和一条连接 $(x_i,y_i-1)$ 和 $(x_i,y_i)$ 的线段组成的。

你可以选择从这 $N$ 个数字 7 中删去零个或多个。

在最优的删去操作后，从原点驻上看能够看到的数字 7 的最大可能个数是多少？

这里，第 $i$ 个数字 7 从原点驻上看是完全可见的，当且仅当：

• 以原点、$(x_i-1,y_i)$、$(x_i,y_i)$、$(x_i,y_i-1)$ 为顶点的四边形（不包括边界）的内部区域与其他数字 7 不相交。

约束

• $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)$
• 输入中的所有值都是整数。

输入

从标准输入读入数据，格式如下：

$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

如果删除第一个数字 7，那么其他两个数字 7，也就是第二个和第三个数字 7，从原点上是完全可见的，这是最优的操作。

如果不删除任何数字 7，那么只有第一个数字 7 从原点上是完全可见的。

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

10

最好的策略是保留全部的数字 7。