https://contest.yandex.ru/contest/12698/problems/
make all- Ограничение времени 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 соответствующей дороге плоскости. Числа разделяйте пробелами. Выведенные параметры должны задавать корректную плоскость.
Результат представлен на изображении, где красные - исходные точки, синие - результирующая плоскость.
