Контрольні точки#1397
Джо — досвідчений програміст. Керівництво дорожньої поліції бажає контролювати рух на шосе та найняло його для вирішення наступної задачі. На шосе існують фіксовані контрольні пункти. Дорожня поліція бажає встановити спеціалізовані пристрої, щоб збирати інформацію з усіх контрольних пунктів. Такий пристрій є дуже дорогим і, на жаль, може покривати лише інтервал довжиною один метр (включаючи ліву та виключаючи праву межу). Керівництво бажає встановити мінімальну кількість пристроїв, щоб покрити всі контрольні пункти. Джо повинен знайти ефективне рішення.
Програма отримує вхідні дані з текстового файлу. Кожен набір даних у файлі представляє конкретну конфігурацію контрольних пунктів. Набір даних починається з числа (n \leq 100000) — кількості контрольних пунктів, після чого йдуть дійсні числа у зростаючому порядку, що описують координати контрольних пунктів (шосе вважається дійсною прямою). Координати виражаються в метрах. У вхідних даних пропуски можуть стояти у довільних місцях. Вхідні дані завершуються кінцем файлу.
Для кожного набору даних програма повинна вивести на стандартний вихід мінімальну кількість пристроїв, необхідних для покриття всіх контрольних пунктів.
Відповідний приклад вхідних/вихідних даних наведено у таблиці нижче. Є два набори даних. У першому випадку є пункти: і . Потрібен лише один пристрій.
Приклад 1