分数: 450 点
问题陈述
新年快乐!说到过年的户外活动,那就是放风筝了!
N 人数 1 to N 正在河边尝试放风筝。
面向河岸的河流是直线流动的,所以从现在开始,我们考虑一个二维坐标系,其中 x- 轴是河流的方向, y-轴是高度方向。
人 i 正站在该点 (A_i, 0) 并尝试在该点放风筝 (B_i, 1).
但是,为避免人与风筝碰撞,避免风筝线缠结,人员 i 和 j (i \neq j) 满足以下条件时不能同时放风筝:
- “连接线段 (A_i, 0) 和 (B_i, 1)“和”线段连接 (A_j, 0) 和 (B_j, 1)“有一个交点。 (这包括线段端点相互接触的情况。)
在遵守上述限制的情况下,最多可以有多少人同时放风筝?
约束
- 1 \leq N \leq 2\times 10^5
- 0 \leq A_i \leq 10^9
- 0 \leq B_i \leq 10^9
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N A_1 B_1 A_2 B_2 \vdots A_N B_N
输出
输出可以同时放风筝的最大人数。
示例输入 1
3 3 5 1 4 2 6
示例输出 1
2
人员 1 和 2,以及人员 2 和 3,可以同时放风筝,但人 1 和 3 不能同时放风筝。
因此,如果选择得当,两个人可以同时放风筝,而三个人同时放风筝是不可能的。因此,答案是 2.
示例输入 2
5 1 2 1 3 1 4 1 5 1 6
示例输出 2
1
示例输入 3
10 440423913 766294629 725560240 59187619 965580535 585990756 550925213 623321125 549392044 122410708 21524934 690874816 529970099 244587368 757265587 736247509 576136367 993115118 219853537 21553211
示例输出 3
4