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






Задача B. В четырех соснах...

Задачу добавил: alef

Успешно сдано решений: 18

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

— Да, все сделано, закрываю наряд, — одобрил работу проверяющий. — Ох, чуть не забыл! На этом газоне тоже решили посадить немного цветов. Озеленители просили вбить 4 колышка, чтобы им было проще посадить цветы ровно. Ну, их вбить можно за пять минут! Сделаете?

И, даже не дождавшись ответа, он быстро зашагал дальше.

— Конечно, сделаем. Четыре колышка, делов-то... — сказал один из рабочих.

— Подожди, а как их вбить-то надо? Озеленители, может, фигуру какую хотели... — спросил его второй.

— Может, и хотели. Да кого теперь спросишь — его и след простыл! Вот как вобъем, так и посадят! — решительно ответил первый.

Озеленители хотели выполнить посадку так, чтобы она состояла из треугольников, образованных цветами одного сорта. А чтобы стороны треугольников оказались ровными, они собирались натянуть между колышками нити. Нити не должны пересекаться (т.е. треугольники могут иметь общие ребра и (разумеется) вершины, но не внутренность).

По заданным координатам колышков определите, какое максимальное количество сортов цветов они смогут посадить в виде треугольников.

 

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

Файл содержит четыре строки. В каждой из строк два целых числа через пробел — координаты X и Y (0 <= X, Y <= 100) одного из четырех вбитых колышков.

Гарантируется, что никакие два колышка не вбиты в одну и ту же точку.

 

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

Первая строка — целое число M, максимальное количество сортов цветов, которые можно посадить в виде треугольников.
В следующих М строках по три целых числа - вершины соответствующего треугольника.
Если ответов несколько, выведите любой из них.

Пример входного файла — 1

0 0

5 5

10 10

20 20

 

Пример выходного файла — 1

0

 

Пример входного файла — 2

0 0

0 10

10 0

10 10

 

Пример выходного файла — 2

2

1 4 2

1 4 3

 

Пример входного файла — 3

0 0

5 5

10 0

5 3

 

Пример выходного файла — 3

3

1 2 4

1 3 4

2 3 4


Сдать задачу

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