13027번 - Clique Problem

문제

Clique Problem은 NP-complete 문제로 우리에게 잘 알려져 있다. 간단한 정의는 다음과 같다. 무향 그래프 G가 있다고 생각해 보자. 이제 그래프 G에 속한 정점들 중 부분집합인 C를 고른다. 이때 부분그래프 C에 속한 모든 정점들의 쌍은 서로 연결이 되어 있어야 한다. 즉 C는 완전 그래프라는 말과 동치다. 이때 부분그래프 C의 정점의 개수를 가장 많은 경우를 찾는것이 Clique Problem이다.

위 문단을 읽었으면 우리가 무엇을 할 것인지 감이 잡힐 것이다.

N개의 중복되지 않은 점들이 X축 위에 존재한다. 이때 i번 째 점의 좌표를 x_i, 무게를 w_i라고 하자. 이때 N개의 점들을 가지고 그래프를 만들 수 있다. 서로 다른 두 점 i, j가 w_i + w_j ≤ |x_i - x_j|을 만족 한다면 연결되어 있다고 생각한다.

이렇게 만들어진 그래프에서 가장 Clique Problem을 푸는것이 우리의 목표다.

입력

첫 번째 줄에 n (1 ≤ n ≤ 200,000) 이 주어진다. 이는 X축 위에 존재하는 점의 개수이다.

두 번째 줄부터 n개의 줄에 걸쳐 두 개의 수 x_i, w_i(1 ≤ x_i, w_i ≤ 10⁹) 이 주어진다.

모든 x_i는 다르다는 것이 보장된다.

출력

첫 번째 줄에 입력받은 점들로 만든 그래프의 부분집합 중 완전그래프가 되는 가장 큰 부분집합의 크기를 출력한다.

제한

힌트