AT_abc439_e.[ABC439E] Kite

普及+/提高

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

有 $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
```
3
3 5
1 4
2 6
```
输出#1
```
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

说明/提示

样例解释 #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$
输入的所有数值均为整数

输入解题思路，AI测评打分。不知道怎么写?

首页