AT_abc439_e [ABC439E] Kite
题目描述
有 $N$ 个人,编号从 $1$ 到 $N$,打算在河边放风筝。
河流沿着直线流淌,我们建立一个二维坐标系:将河流的流向设为 $x$ 轴,高度方向设为 $y$ 轴。
第 $i$ 个人站在坐标点 $(A_i ,0)$ 处,想要把风筝放飞到坐标点 $(B_i ,1)$ 的位置。
不过,为了避免人员、风筝发生碰撞,同时防止风筝线相互缠绕,当且仅当满足以下条件时,第 $i$ 个人和第 $j$ 个人 $(i \ne j)$ 不能同时放风筝:
- 连接点 $(A_i ,0)$ 与 $(B_i,1)$ 的线段,和连接点 $(A_j,0)$ 与 $(B_j,1)$ 的线段存在交点(包含线段端点相互接触的情况)。
在遵守上述限制条件的前提下,最多有多少人可以同时放风筝?
输入格式
输入数据通过标准输入按以下格式给出:
>$N\\$
$A_1\ B_1\\$
$A_2\ B_2\\$
$\vdots\\$
$A_N\ B_N\\$
输出格式
输出可以同时放风筝的最大人数。
说明/提示
#### 样例解释 #1
第 $1$ 人与第 $2$ 人、第 $2$ 人与第 $3$ 人可以同时放风筝,但第 $1$ 人与第 $3$ 人无法同时放风筝。
因此,只要选择合适的组合,最多可以让 $2$ 人同时放风筝,而 $3$ 人同时放风筝是不可能的。故答案为 $2$。
#### 数据范围
- $1 \le N \le 2×10^5$
- $0 \le A_i \le 10^9$
- $0 \le B_i \le 10^9$
- 输入的所有数值均为整数