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

样例输入 #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.