Nəzarət Nöqtələri#1397
Co güclü proqramçıdır. Avtomobil yol polisi idarəsinin rəhbərliyi magistral yolda hərəkəti nəzarətdə saxlamaq istəyir və bu problemi həll etmək üçün onu işə götürüb. Magistral yolda bəziləri sabit olan nəzarət nöqtələri var. Yol polisi idarəsi bu nəzarət nöqtələrindən məlumat toplamaq üçün xüsusi cihazlar yerləşdirmək istəyir. Belə bir cihaz çox bahalıdır və təəssüf ki, yalnız bir metrlik bir intervalı əhatə edə bilir (intervalın sol son nöqtəsi daxil, sağ son nöqtəsi isə daxil deyil). Rəhbərlik bütün nəzarət nöqtələrini əhatə etmək üçün minimum sayda cihaz yerləşdirmək istəyir. Co bu məsələyə səmərəli həll tapmalıdır.
Proqramın girişi mətn faylındandır. Fayldakı hər bir verilənlər toplusu nəzarət nöqtələrinin müəyyən bir konfiqurasiyasını ifadə edir. Verilənlər toplusu (n \leq 100000) — nəzarət nöqtələrinin sayı ilə başlayır, ardınca isə artan ardıcıllıqla nəzarət nöqtələrinin koordinatları (magistral yol real düz xətt kimi qəbul olunur) verilir. Koordinatlar metrlə ifadə olunur. Girişdə boşluqlar sərbəst şəkildə ola bilər. Giriş məlumatları faylın sonu ilə başa çatır.
Hər bir verilənlər toplusu üçün proqram standart çıxışa bütün nəzarət nöqtələrini əhatə etmək üçün lazım olan minimum cihaz sayını çıxarmalıdır.
Nümunə giriş/çıxış aşağıdakı cədvəldə verilib. Burada iki verilənlər toplusu var. Birinci halda nöqtə var: və . Yalnız bir cihaz kifayətdir.
Nümunə 1