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$ - 输入的所有数值均为整数