← 返回题目列表

AtCoder · abc439_e

H. 风筝

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

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