分数: 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。