Клика Tapşırığı#11522
Klik problemi NP-tam məsələlərdən ən məşhurlarından biridir. Bu problem müəyyən şərtlər altında belə ifadə olunur: Qeyri-yoğun qraf verilmişdir. Sizdən tələb olunur ki, elə bir maksimum ölçülü altmüxtəlifliyi tapın ki, bu altmüxtəlifliyin hər hansı iki elementi qraf -də bir kənarla birləşdirilmiş olsun. Sadə səslənir, elə deyilmi? Hal-hazırda qrafın ölçüsündən asılı olaraq bu problemi polinomial vaxtda həll edən bir alqoritm məlum deyil. Lakin, bir çox digər NP-tam məsələlərdə olduğu kimi, klik problemi də xüsusi növ qraflar üçün daha asan olur.
Gəlin düz xətt üzərində müxtəlif nöqtəni nəzərdən keçirək. -ci nöqtənin koordinatı x_i və çəkisi w_i olsun. Bu nöqtələrdən ibarət qraf yaradaq, burada kənarlarla yalnız o cüt nöqtələr birləşdirilir ki, bu nöqtələr arasındakı məsafə onların çəkilərinin cəmindən az olmasın, yəni: |x_i - x_j| \ge w_i + w_j.
Belə bir qrafda maksimum klik ölçüsünü tapın.
Birinci sətirdə n~(1 \le n \le 2 \cdot 10^5) — nöqtələrin sayı verilir.
Sonrakı sətirdə hər biri üçün iki ədəd x_i, w_i~(0 \le x_i \le 10^9, 1 \le w_i \le 10^9) — növbəti nöqtənin koordinatı və çəkisi verilir. Bütün koordinatlar x_i fərqlidir.
Bir ədəd çıxarın — yaradılmış qrafda maksimum klikdəki zirvələrin sayı.
Əgər siz bu məsələnin həllini, məsələnin şərtində təqdim olunan qrafın xüsusi xüsusiyyətlərini istifadə etmədən bacarırsınızsa, sizə bir milyon dollar mükafatı verilir!
Test üçün şəkil.
Nümunə 1