D. 最大交易联盟

    传统题 1000ms 256MiB

最大交易联盟

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

问题描述

在 MC 世界中,有一个村庄,村庄可以看作是一个数轴。

现在村庄里有 nn 个村民,第 ii 个村民的坐标为 aia_i,拥有的钻石数量为 bib_i

如果两个村民 (i,j)(i,j) 满足 aiajbi+bj|a_i-a_j|\le b_i+b_j,则两个村民可以进行交易。

请问史蒂夫最多可以选择多少个村民,使得这些村民都可以通过直接或间接的方式进行交易?

输入格式

第一行输入一个正整数 nn,表示村庄里的村民数量。

接下来 nn 行,每行输入两个整数 ai,bia_i,b_i,表示第 ii 个村民的坐标和钻石数量。

(1n105,1ai,bi105)(1\le n\le 10^5,1\le a_i,b_i\le 10^5)

输出格式

输出一个整数,表示史蒂夫最多可以选择的村民数量。

样例输入

7
1 4
11 1
7 5
14 0
19 0
21 1
22 9

样例输出

4

模拟赛

未参加
状态
已结束
规则
IOI
题目
4
开始于
2025-8-30 0:30
结束于
2025-9-11 12:30
持续时间
300 小时
主持人
参赛人数
9