Nəzarət Nöqtələri
Joe bacarıqlı bir proqramçıdır. Magistral yol polisi idarəsi magistral yoldakı nəqliyyatı idarə etmək istəyir və bu məqsədlə onu aşağıdakı problemi həll etmək üçün işə götürüb. Magistral yolda bəzi sabit nəzarət nöqtələri mövcuddur. Magistral yol polisi idarəsi bu nöqtələrdən məlumat toplamaq üçün xüsusi cihazlar yerləşdirmək istəyir. Belə bir cihaz çox bahalıdır və yalnız bir metr intervalı (sol son nöqtəni daxil etməklə, sağ son nöqtəni isə istisna etməklə) əhatə edə bilir. İdarəetmə bütün nəzarət nöqtələrini əhatə etmək üçün minimum sayda cihaz yerləşdirmək istəyir. Joe bu problemi səmərəli şəkildə həll etməlidir.
Giriş verilənləri
Proqramın girişi mətn faylından alınır. Fayldakı hər bir məlumat dəsti nəzarət nöqtələrinin xüsusi konfiqurasiyasını təmsil edir. Məlumat dəsti əvvəlcə nəzarət nöqtələrinin sayı olan n (n ≤ 100000) rəqəmi ilə başlayır, sonra isə nəzarət nöqtələrinin koordinatlarını təsvir edən artan qaydada real qiymətlər gəlir (magistral yol real xətt kimi qəbul edilir). Koordinatlar metrlə ifadə olunur. Girişdə boşluqlar sərbəst şəkildə ola bilər. Giriş məlumatları faylın sonu ilə bitir.
Çıxış verilənləri
Hər bir məlumat dəsti üçün proqram bütün nəzarət nöqtələrini əhatə etmək üçün lazım olan minimum cihaz sayını standart çıxışa çap etməlidir.
Aşağıdakı cədvəldə giriş/çıxış nümunəsi verilmişdir. İki məlumat dəsti var. Birinci halda, 2 nöqtə var: 3.56 və 4. Yalnız bir cihaz lazımdır.