Задача о клике — одна из самых известных NP-полных задач. После некоторых оговорок она формулируется следующим образом. Рассмотрим неориентированный граф G. Требуется найти такое подмножество вершин C максимального размера, что любые две из них соединены ребром в графе G. Звучит просто, не правда ли? К текущему моменту не известен алгоритм, который находит решение этой задачи за полиномиальное время от размера графа. Однако, как и в случае многих других NP-полных задач, задача о клике оказывается проще, если рассмотреть граф специфического вида.

Рассмотрим n различных точек на прямой. Пусть i-я точка имеет координату x_i и вес w_i. Образуем граф G, вершинами которого являются эти точки, а рёбрами соединены в точности те пары точек (i, j), для которых расстояние между этими точками не меньше суммы их весов, формально говоря: |x_i - x_j| ≥ w_i + w_j.

Найдите размер максимальной клики в таком графе.