102254: [AtCoder]ABC225 E - 7

Problem Statement

There are $N$ 7's drawn in the first quadrant of a plane.

The $i$-th 7 is a figure composed of a segment connecting $(x_i-1,y_i)$ and $(x_i,y_i)$, and a segment connecting $(x_i,y_i-1)$ and $(x_i,y_i)$.

You can choose zero or more from the $N$ 7's and delete them.

What is the maximum possible number of 7's that are wholly visible from the origin after the optimal deletion?

Here, the $i$-th 7 is wholly visible from the origin if and only if:

• the interior (excluding borders) of the quadrilateral whose vertices are the origin, $(x_i-1,y_i)$, $(x_i,y_i)$, $(x_i,y_i-1)$ does not intersect with the other 7's.

Constraints

• $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)$
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

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

Output

Print the maximum possible number of 7's that are wholly visible from the origin.

Sample Input 1

3
1 1
2 1
1 2

Sample Output 1

2

If the first 7 is deleted, the other two 7's ― the second and third ones ― will be wholly visible from the origin, which is optimal.

If no 7's are deleted, only the first 7 is wholly visible from the origin.

Sample Input 2

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

Sample Output 2

10

It is best to keep all 7's.

问题描述

在平面的第一象限中画出了$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的最大可能数量。

样例输入1

3
1 1
2 1
1 2

样例输出1

2

如果删除第一个7，那么剩下的两个7——第二个和第三个——将从原点完全可见，这是最优的。

如果删除0个7，那么只有第一个7从原点完全可见。

样例输入2

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

样例输出2

10

最好保留所有的7。