Clique Problem

题意翻译

### 题目描述 数轴上有 $n$ 个点，第 $i$ 个点的坐标为 $x_i$，权值为 $w_i$。两个点 $i,j$ 之间存在一条边当且仅当 $abs(x_i-x_j)\geq w_i+w_j$ 。 你需要求出这张图的最大团的点数。 团的定义：两两之间有边的顶点集合。 ### 输入格式 第一行一个整数 $n$，接下来 $n$ 行每行两个整数 $x_i,w_i$ 。 ### 输出格式 一行一个整数表示答案。 感谢@Asougi_Kazuma 提供的翻译。 感谢@皎月半洒花 将翻译改成了正常人能看明白的翻译。

题目描述

The clique problem is one of the most well-known NP-complete problems. Under some simplification it can be formulated as follows. Consider an undirected graph $ G $ . It is required to find a subset of vertices $ C $ of the maximum size such that any two of them are connected by an edge in graph $ G $ . Sounds simple, doesn't it? Nobody yet knows an algorithm that finds a solution to this problem in polynomial time of the size of the graph. However, as with many other NP-complete problems, the clique problem is easier if you consider a specific type of a graph. Consider $ n $ distinct points on a line. Let the $ i $ -th point have the coordinate $ x_{i} $ and weight $ w_{i} $ . Let's form graph $ G $ , whose vertices are these points and edges connect exactly the pairs of points $ (i,j) $ , such that the distance between them is not less than the sum of their weights, or more formally: $ |x_{i}-x_{j}|>=w_{i}+w_{j} $ . Find the size of the maximum clique in such graph.

输入输出格式

输入格式

The first line contains the integer $ n $ ( $ 1<=n<=200000 $ ) — the number of points. Each of the next $ n $ lines contains two numbers $ x_{i} $ , $ w_{i} $ ( $ 0<=x_{i}<=10^{9},1<=w_{i}<=10^{9} $ ) — the coordinate and the weight of a point. All $ x_{i} $ are different.

输出格式

Print a single number — the number of vertexes in the maximum clique of the given graph.

输入输出样例

输入样例 #1

4
2 3
3 1
6 1
0 2

输出样例 #1

3

说明

If you happen to know how to solve this problem without using the specific properties of the graph formulated in the problem statement, then you are able to get a prize of one million dollars! The picture for the sample test.