ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

Timus Top Coders: First Challenge

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

F. Прямоугольники

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ

Вступление

Это был тёплый осенний день, под ногами шелестел ковёр опавшей листвы, лицо ласково обдувал лёгкий ветерок, и само солнце, казалось, тянуло к земле свои лучи...
Потомственный художник-абстракционист Аристарх Матвеевич Петрофф открыл глаза и выругался: "Блин, приснится же такое!" Кошмары мучили г-на Петроффа весь последний месяц, в течение которого он работал над серией картин под общим названием "Четырёхугольники". Заказчиком серии был какой-то эксцентричный миллионер, и теперь, после выполнения заказа, Аристарх Матвеевич планировал изрядно обогатиться. При мысли о деньгах г-н Петрофф хищно ухмыльнулся. И в этот самый момент раздался телефонный звонок:
"Алло... да, Петрофф... очень приятно, прекрасная сегодня пого... какие изменения?... Ах, совсем небольшие... как прямоугольники??! Но ведь мы же договари... не имеет значения? А что же мне делать с уже написанными... Вас не волнует?... Да, конечно... обязательно... никаких задержек... всего хорошего."
На то миллионер и был эксцентричный, чтобы в последний момент изменить свои требования. Теперь он, понимаешь ли, желает видеть на картинах не четырёхугольники, а прямоугольники, выполненные на высоком идейно-художественном уровне.
Разумеется, выбрасывать уже написанные картины Аристарх Матвеевич не собирается. Ну не может он уничтожить плоды собственного творчества, да и холсты тоже денег стоят, в конце концов. Но даже сейчас вдохновение не оставило г-на Петроффа, и ему в голову пришла идея (как всегда, гениальная).

Задача

Создавая каждую из N своих картин, Аристарх Матвеевич рисовал на холсте четыре опорные точки с координатами (x1[i], y1[i]), (x2[i], y2[i]), (x3[i], y3[i]) и (x4[i], y4[i]). Затем он соединял каждую пару опорных точек отрезками и закрашивал получившуюся фигуру. Впрочем, художник плохо разбирается в геометрии, поэтому иногда вместо четырёхугольника получался треугольник или даже отрезок. Более того, две или более опорные точки могли совпадать.
Теперь г-н Петрофф хочет нарисовать на каждой этих картин прямоугольник таким образом, чтобы каждая из четырёх уже нарисованных опорных точек лежала на одной из сторон этого прямоугольника (не обязательно на разных сторонах). Никакие две вершины прямоугольника не должны совпадать (т.е. точка или отрезок не являются прямоугольниками). При этом необходимо учесть, что каждая картина представляет собой квадрат 20000*20000 с центром в точке (0, 0), и, разумеется, прямоугольник не должен выходить за границы картины. Только настоящий художник может придумать такое. И только настоящий программист может такое реализовать!

Исходные данные

Первая строка содержит целое число N (0 ≤ N ≤ 10000). Каждая из следующих N строк содержит целые числа x1[i], y1[i], x2[i], y2[i], x3[i], y3[i], x4[i] и y4[i] (-5000 ≤ x1[i], y1[i], x2[i], y2[i], x3[i], y3[i], x4[i], y4[i] ≤ 5000) для соответствующей картины.

Результат

В каждую из N строк вывести через пробел символ "+" (плюс) и координаты вершин искомого прямоугольника для соответствующей картины. Вершины должны быть перечислены в порядке обхода (по часовой или против часовой стрелки). Координаты должны быть выведены не менее чем с шестью знаками после десятичной точки. Если для некоторой картины задача не имеет решения, то в соответствующую строку вывести символ "-" (минус). Если для некоторой картины задача имеет несколько решений, то в соответствующую строку вывести любое из них.

Пример

исходные данные
2
1 0 0 1 3 2 1 2
0 1 0 -1 1 0 -1 0
результат
+ 0.000000 0.000000 0.000000 2.000000 3.1234567890 2.000000 3.1234567890 0.000000 
+ 0.000000 -1.000000 1.000000 0.000000 0.000000 1.000000 -1.000000 0.000000
Автор задачи: Никита Рыбак, Дмитрий Ковалёв, Илья Гребнов
Источник задачи: Timus Top Coders: First Challenge
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1426. Прямоугольники