【Clique Problem】

题目描述

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 GG . It is required to find a subset of vertices CC of the maximum size such that any two of them are connected by an edge in graph GG . 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 nn distinct points on a line. Let the ii -th point have the coordinate x_{i}xi​ and weight w_{i}wi​ . Let's form graph GG , whose vertices are these points and edges connect exactly the pairs of points (i,j)(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}∣xi​−xj​∣>=wi​+wj​ .

Find the size of the maximum clique in such graph.

输入输出格式

输入格式：

 

The first line contains the integer nn ( 1<=n<=2000001<=n<=200000 ) — the number of points.

Each of the next nn lines contains two numbers x_{i}xi​ , w_{i}wi​ ( 0<=x_{i}<=10^{9},1<=w_{i}<=10^{9}0<=xi​<=109,1<=wi​<=109 ) — the coordinate and the weight of a point. All x_{i}xi​ are different.

 

输出格式：

 

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

 

输入输出样例

输入样例#1： 

42 33 16 10 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.

 

简单翻译一下（语文较差，转载@Asougi_Kazuma的翻译）：

题目描述

数轴上有n 个点，第i 个点的坐标为xi，权值为wi。两个点i,j之间存在一条边当且仅当 abs(xi-xj)>=wi+wj。 你需要求出这张图的最大团的点数。（团就是两两之间有边的顶点集合）

输入数据

第一行一个整数n，接下来n行每行两个整数 xi,wi。

输出数据

一行一个整数表示答案。

样例输入

4 2 3 3 1 6 1 0 2

样例输出

3

数据范围

对于20%的数据，n<=10。        对于60%的数据，n<=1000。        对于100%的数据n<=200000，0<=|xi|,wi<=10^9。 那么这样粗粗一看，很简单啊，控制好左边的端点以及右边的端点，既然输入为x[i]与y[i]； 那么左端点就为x-y；右端点就为x+y； 快排sort从头到尾迅速排一遍，然后枚举暴力搜索勉强通过：

var  n,i,x,y,R,ans:longint;  pt:array[1..200000,1..2]of longint;//因为是二维数组，别开的过分大，也可以试试recordprocedure sort(l,r:longint);//快排，不多说var  i,j,x,y: longint;      begin         i:=l;         j:=r;         x:=pt[(l+r) div 2,1];//注意，我们要以pt[i,1]作为标准来排序         repeat           while pt[i,1]
     
      j;         if l
      
       =R then//枚举+处理     begin       ans:=ans+1;       R:=pt[i,2];     end;   end;   writeln(ans);//输出 end.
      
     

如有疑惑，请点击

点一下 【关注我】↓再走呗，蟹蟹您的阅读