← 返回题目列表

AtCoder · abc225_e

H. 七

中文机器翻译题面 查看原题

分数: 500 点

问题陈述

有 N 7 画在平面的第一象限。

的 i-th 7 是由连接线段组成的数字 (x_i-1,y_i) 和 (x_i,y_i),以及连接的段 (x_i,y_i-1) 和 (x_i,y_i).

您可以从以下选项中选择零个或多个 N 7 并删除它们。

最佳删除后从原点完全可见的 7 的最大可能数量是多少?

在这里, i-th 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(第二个和第三个 7)将从原点完全可见,这是最佳的。

如果没有删除 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。