Solution for task for Yandex meet-up https://contest.yandex.ru/contest/12698/problems/
А. Выделить плоскость дороги в лидарном облаке точек
Ограничение времени: 15 секунд
Ограничение памяти: 64Mb
Ввод: стандартный ввод или input.txt
Вывод: стандартный вывод или output.txt
Беспилотный автомобиль стоит на ровной асфальтовой площадке, на крыше автомобиля установлен лидар. Даны измерения, полученные лидаром за один период сканирования. Измерения представляют собой множество из N точек, имеющих координаты x, y и z. Больше 50% точек принадлежат дороге. Моделью положения принадлежащих дороге точек в пространстве является плоскость с параметризацией:
A⋅x + B⋅y + C⋅z + D = 0
Точки, которые принадлежат дороге, отклоняются от модели не больше чем на заданную величину p. Необходимо найти параметры A, B, C, и D соответствующей дороге плоскости. Число точек, отклоняющихся от модели не больше чем на p, должно составлять не менее 50% от общего числа точек.
Формат ввода Входные данные заданы в текстовом формате. Первая строка содержит фиксированный порог p (0.01 ≤ p ≤ 0.5). Вторая строка содержит число точек N(3 ≤ N ≤ 25000). Следующие N строк содержат координаты x, y и z (−100 ≤ x, y, z ≤ 100) для каждой точки, разделителем является символ табуляции (формат строки "x[TAB]y[TAB]z"). Вещественные числа имеют не более 6 десятичных знаков.
Формат вывода Выведите параметры A, B, C, и D соответствующей дороге плоскости. Числа разделяйте пробелами. Выведенные параметры должны задавать корректную плоскость.
%EOF