Если я не ошибаюсь, можно попытаться воспользоваться теоремой Дезарга
Потенциальное решение
Будем строить два треугольника из теоремы. Концы отрезка возьмём за одну из пар вершин. Строим прямую, на которой будут пересекаться пары сторон треугольников. Отмечаем три точки на этой прямой, делаем это произвольно. Дальше строим стороны треугольников, проходящие через концы отрезка (по условию теоремы они должны пересекаться на только что построенной прямой с тремя выбранными точками). А вот третью пару сторон нужно строить так, чтобы прямые, их соединяющие, проходили мимо пятна. Поэтому на произвольность выбора трёх точек пересечения пар сторон накладывается ограничение - мы должны иметь возможность построить третьи стороны шире пятна. Это делать нужно «на глаз», так что это скользкий момент, не уверен, что здесь все честно. В общем, остаётся построить третью пару сторон, чтобы точка пересечения прямых, соединяющих концы этих сторон оказалась «по ту сторону пятна». Так мы построим одну точку с искомой прямой, немного «пошевелив» одну сторону из третьей пары, получим вторую точку.
Распределение по батчам выполняется за линейное время и требует O(n) дополнительной памяти.
Кажется, что для решения исходной задачи необязательно раскидывать элементы по батчам и достаточно у каждого подсчитывать минимум и максимум. Таким образом, можно добиться O(кол-во непустых батчей), ну и заодно сократить количество проходов по массиву.
Если я не ошибаюсь, можно попытаться воспользоваться теоремой Дезарга
Потенциальное решение
Будем строить два треугольника из теоремы. Концы отрезка возьмём за одну из пар вершин. Строим прямую, на которой будут пересекаться пары сторон треугольников. Отмечаем три точки на этой прямой, делаем это произвольно. Дальше строим стороны треугольников, проходящие через концы отрезка (по условию теоремы они должны пересекаться на только что построенной прямой с тремя выбранными точками). А вот третью пару сторон нужно строить так, чтобы прямые, их соединяющие, проходили мимо пятна. Поэтому на произвольность выбора трёх точек пересечения пар сторон накладывается ограничение - мы должны иметь возможность построить третьи стороны шире пятна. Это делать нужно «на глаз», так что это скользкий момент, не уверен, что здесь все честно. В общем, остаётся построить третью пару сторон, чтобы точка пересечения прямых, соединяющих концы этих сторон оказалась «по ту сторону пятна». Так мы построим одну точку с искомой прямой, немного «пошевелив» одну сторону из третьей пары, получим вторую точку.
Кажется, что для решения исходной задачи необязательно раскидывать элементы по батчам и достаточно у каждого подсчитывать минимум и максимум. Таким образом, можно добиться O(кол-во непустых батчей), ну и заодно сократить количество проходов по массиву.