Задача B. Минимальная площадь ≡

Условие

Примечание. Формат данной задачи не поддерживается в CATS. Предоставляется лишь текст условия для ознакомления. Ограничение по времени игнорировать. Подразумевается, что полученная программа должна завершить работу втечение пятичасового тура.

Рассмотрим n точек на плоскости внутри или на границе единичного квадрата. Построим все треугольники с вершинами в этих точках и вычислим площадь каждого из них. Расположите точки так, чтобы минимальная из этих площадей была как можно больше.

Оценка за решение — это сумма оценок за каждый тест, округленная до ближайшего целого числа. Оценка за отдельный тест вычисляется следующим образом. Каждому тесту T соответствует максимальное количество баллов B_T, которое можно за него получить. Если ответ на тесте некорректен, оценка равна нулю. В противном случае оценка — это L / M ⋅ B_T, где L — это минимальная площадь треугольника в конфигурации, полученной участником, а M — это максимальная изо всех минимальных площадей, полученных всеми участниками и жюри за всю олимпиаду на этом тесте. В частности, если участник расставил точки так, что L является максимальной площадью, которую удалось получить на этом тесте, оценка за тест T будет равна B_T. Максимальные баллы за каждый тест одинаковы. Сумма максимальных баллов по всем тестам равна 100.

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

В первой и единственной строке каждого входного файла записано целое число n — количество точек.

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

Выведите в каждый выходной файл n строк, где n — число из соответствующего входного файла. В каждой строке выведите координаты i-ой точки x_i и y_i через пробел. Точки должны лежать внутри или на границе единичного квадрата, то есть их координаты должны удовлетворять соотношениям 0 ≤ x_i ≤ 1, 0 ≤ y_i ≤ 1. Порядок точек не имеет значения.

Координаты и площади обрабатываются проверяющей программой как числа с плавающей точкой двойной точности (тип double в языках C/C++ и Pascal).

Ограничения

3 ≤ n ≤ 52

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

4

0.000000000000 0.000000000000
0.000000000000 1.000000000000
0.800000000000 0.300000000000
0.300000000000 0.800000000000