Задача E. Все плоско
Задачу добавил: DK
Успешно сдано решений: 8
Задача E. Все плоско
Ограничение по времени: 1 секунда
Ограничение по памяти: 64 МБ
Название задачи (англ.): Plane Plane Plane
Как известно, папа у Васи силен в математике. И папа предложил Васе следующую игру. Папа отмечает на плоскости N точек. Вася должен проводить отрезки между точками так, чтобы
1. Любой отрезок соединял две поставленные папой точки, и не проходил через какую-либо другую.
2. Любые два отрезка, нарисованные Васей, не должны пересекаться, за исключением, возможно, одной общей точки, поставленной папой.
Вася очень увлекся этой игрой, и ему захотелось узнать - какое максимальное количество отрезков он мог бы провести, если бы папа поставил точки так как сказал Вася?
Входной файл.
В единственной строке входного файла целое число N (2 <= N <= 31) - количество точек.
Выходной файл.
В первой строке выходного файла целое число M - максимальное количество отрезков. Далее в следующих N строках Xi и Yi - координаты точек, которые должен будет поставить папа (0 <= Xi,Yi <= 1000). Все Xi и Yi должны быть целыми. В следующих M строках пары чисел - точки, которые соединит Вася.
|
Входной файл input.txt |
Выходной файл output.txt |
|
2 |
1 0 0 0 1 1 2 |
|
3 |
3 0 0 0 10 5 5 1 2 2 3 3 1 |
|
6 |
12 0 0 10 0 5 5 2 1 8 1 5 4 1 2 2 3 3 1 4 5 5 6 4 6 1 4 2 5 3 6 3 4 1 5 2 6 |
Подсказка к примеру 3
Примечание. Пример 3 не совпадает с тестом 3