Contest.uni-smr.ac.ru :: соревнования по программированию
Русская версия || English version
Login:
Password:
Забыли пароль?
 пример поиска: Вася Пупкин
 






Задача 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

 

Сдать задачу

Задать вопрос жюри по этой задаче