← 返回题目列表

Codeforces · 527/D

D. 派系问题

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

派系问题是最著名的 NP 完全问题之一。经过一定程度的简化,它可以表述如下。考虑一个无向图 G。需要找到最大尺寸的顶点 C 的子集,使得其中任意两个顶点通过图 G 中的边连接。听起来很简单,不是吗?目前还没有人知道有一种算法可以在图大小的多项式时间内找到该问题的解决方案。然而,与许多其他 NP 完全问题一样,如果考虑特定类型的图,派系问题会更容易。

考虑一条线上的 n 个不同点。令第 i 个点的坐标为 xi,权重为 wi。让我们形成图 G,其顶点是这些点,边恰好连接点对 (i, j),使得它们之间的距离不小于它们的权重之和,或更正式地说:|xi - xj| ≥wi+wj。

找出该图中最大团的大小。

输入

第一行包含整数 n (1 ≤ n ≤ 200 000) — 点数。

接下来的 n 行每行包含两个数字 xi, wi (0 ≤ xi ≤ 109, 1 ≤ wi ≤ 109) — 点的坐标和权重。所有的xi都是不同的。

输出

打印单个数字 — 给定图的最大团中的顶点数。

示例

输入 #1

4
2 3
3 1
6 1
0 2

输出 #1

3

注意

如果您碰巧知道如何在不使用问题陈述中制定的图的特定属性的情况下解决此问题,那么您将可以获得一百万美元的奖金!

样本测试图片。