Задача C. Наилучшее приближение

Автор:Зимние сборы 2005   Ограничение времени:2 сек
Входной файл:best.in   Ограничение памяти:64 Мб
Выходной файл:best.out  

Условие

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

Формат входного файла

В первой строке входного файла задано число n. В последующих n строках заданы координаты точек (xi, yi).

Формат выходного файла

В первой строчке необходимо вывести минимум суммы квадратов расстояний от прямой до точек набора. Во второй строчке должны быть выведены числа a, b, c из уравнения прямой в виде ax+by=c. Числа должны удовлетворять условиям a^2+b^2=1, c≥0. Все числа необходимо выводить с 6 знаками после запятой.

Ограничения

1 ≤ n ≤ 100 000, Все координаты — целые числа, по модулю не превосходящие 1000.

Примеры тестов

Входной файл (best.in) Выходной файл (best.out)
1
3
0 0
1 0
1 1
0.333333
0.707107 -0.707107 0.235702

0.062s 0.008s 13