Старик со старухой сидят за столом и пишут письма. На столе перед ними в точках с координатами (xi, yi) стоят N карандашей. Диаметр карандашей 0, и все они стоят вертикально. Старик и старуха решили разделить карандаши на две равные группы. Чтобы сделать это, старик берёт нитку и кладёт её на стол в форме окружности. Окружность должна проходить через три карандаша. Старик хочет, чтобы одна группа карандашей была в круге, а вторая вне круга.
Исходные данные
В первой строке ввода находится одно нечётное целое число 3 ≤ N ≤ 5000. В следующих N строках находятся координаты карандашей. Никакие три карандаша не лежат на одной прямой, и никакие четыре карандаша не лежат на одной окружности. Все координаты целые и по модулю не превосходят 108.
Результат
Выведите 6 целых чисел — координаты трёх карандашей, через которые пролегла нитка. Карандашей внутри круга должно быть (N−3)/2. На окружности должны лежать три указанных карандаша. Остальные карандаши, также (N−3)/2, должны лежать вне круга. Если решения нет, нужно вывести "No solution". Если решений больше одного, выведите любое из них.
Пример
исходные данные | результат |
---|
7
0 0
1 0
2 -1
2 1
1 1
0 2
-3 -1
| 0 0
1 0
2 1
|
Автор задачи: Катя Овечкина
Источник задачи: Tetrahedron Team Contest May 2001