Задача Кліка#11522

Задача Кліка

2 секунди

256 мегабайтів

Середня

Задача про кліку — одна з найвідоміших NP-повних задач. Вона формулюється наступним чином. Розглянемо неорієнтований граф $G$ . Потрібно знайти таку підмножину вершин $C$ максимального розміру, що будь-які дві з них з'єднані ребром у графі $G$ . Звучить просто, чи не так? На даний момент не існує алгоритму, який знаходить розв'язок цієї задачі за поліноміальний час від розміру графа. Однак, як і у випадку багатьох інших NP-повних задач, задача про кліку стає простішою, якщо розглянути граф специфічного виду.

Розглянемо $n$ різних точок на прямій. Нехай $i$ -та точка має координату $x_{i}$ x_i і вагу $w_{i}$ w_i. Утворимо граф $G$ , вершинами якого є ці точки, а ребрами з'єднані в точності ті пари точок $(i, j)$ , для яких відстань між цими точками не менша суми їх ваг, формально кажучи: $∣ x_{i} - x_{j} ∣ \geq w_{i} + w_{j}$ |x_i - x_j| \ge w_i + w_j.

Знайдіть розмір максимальної кліки в такому графі.

Вхідні дані

У першому рядку задано число $n (1 \leq n \leq 2 \cdot 1 0^{5})$ n~(1 \le n \le 2 \cdot 10^5) — кількість точок.

У кожному з наступних $n$ рядків слідують по два числа $x_{i}$ x_i, $w_{i} (0 \leq x_{i} \leq 1 0^{9}, 1 \leq w_{i} \leq 1 0^{9})$ w_i~(0 \le x_i \le 10^9, 1 \le w_i \le 10^9) — координата і вага чергової точки. Усі координати $x_{i}$ x_i різні.

Вихідні дані

Виведіть одне число — кількість вершин у максимальній кліці утвореного графа.

Приклади

Якщо ви раптом вмієте розв'язувати цю задачу, не використовуючи специфічні властивості графа, представленого в умові задачі, то вам належить приз у мільйон доларів!

Картинка для тесту.

Приклад 1