Группировка рекомендуемых точек подачи на прямой

Нашел интересную задачку и не смог найти что-то даже аналога, что бы попробовать воспроизвести и попытаться понять.

[https://tproger.ru/problems/ytcf-problems-solutions/][1]

Описание решения с сайта

Для начала переведём задачу в математическую постановку.

Нужно выбрать такое наименьшее количество точек на числовой прямой, чтобы расстояние от каждой имеющейся точки до выбранной нами не превосходило R. Можно считать, что каждая выбранная нами точка вырезает на плоскости отрезок длиной 2R, и после вырезаний должны пропасть все точки. Для решения задачи нам сначала надо отсортировать точки. После сортировки у нас появляется самая левая точка. Легко доказать, что эта точка в оптимальном решении должна входить ровно в один отрезок, причём этот отрезок должен быть максимально отодвинут вправо. Чтобы выбрать наиболее подходящую точку, мы проходимся циклом по точкам слева направо и ищем самую правую, у которой расстояние до первой точки не превосходит R. Потенциально это может быть и самая правая точка.

Как только мы нашли эту точку, мы виртуально вырезаем отрезок длиной 2R и пропускаем все точки, что находятся внутри него (слева от первой и справа от последней точки отрезка).

После этого действия у нас снова остался отсортированный список точек, к которому мы применяем тот же алгоритм. Осталось посчитать, сколько точек нам удалось выбрать.

Прошу помощи в алгоритме. Вот часть кода, которую мне посчастливилось написать. Вроде как я попал в условия для "a", но не понимаю, как продолжить...

while((a >= 0 && a <= Math.pow(10, 5))) {            //a - число точек (0 ≤ N ≤ 10^5)
                System.out.println("Введите количество точек. Нужно ввести " + а);
                for (int i = 1; i <= 2*R; i++) {                                      String X = scan.nextLine();
                String[] part = X.split(" ");               // разбиваем строку на значения через пробелы

                int one = Integer.parseInt(X);              //делаем из строки число
                if (one < a || one > a) {
                    throw new ArithmeticException("\n=================================\n\tОшибка: Количество чисел должно быть равно " + a);
                }

На этом моменте код завершается с exit code 1: NumberFormatException: For input string: "" Но строка с вводом количества точек даже не появилась... Почему-то компиляция считает, что строка пустая (string: "").


Ответы (0 шт):