| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 1 | 1 | 1 | 100.000% |
Юный Люк --- очень одаренный джедай. Кроме недюжинного таланта влезать в неприятности он умеет перемещать предметы, не касаясь их. К большому сожалению юноши, уроки телекинеза начинаются только с пятого класса школы джедаев, зато он нашел в библиотеке отца старинную книгу <<Телекинез для самых маленьких>>.
Первым упражнением в книге было перемещение печенья в пространстве силой мысли. У Люка как раз оказалась под рукой целая пачка четырехугольных печенюшек, поэтому он решил попробовать свои способности. Чтобы переместить куда-нибудь четырехугольную печенюшку силой мысли, как сказано в книге, нужно сначала разломить ее на ровно три трапециевидных кусочка, после чего сосредоточиться и использовать силу.
Помогите Люку разломить печенье таким образом, чтобы образовалось ровно три кусочка, каждый из которых имеет форму трапеции (выпуклого четырехугольника, две стороны которого параллельны).
Во входном файле задан четырехугольник --- печенье. В четырех строках заданы координаты вершин четырехугольника в порядке обхода против часовой стрелки. В $i$-й строке два числа $x_i$ и $y_i$ --- координаты $i$-й вершины четырехугольника.
Никакие три точки не лежат на одной прямой.
Все координаты по модулю не превышают 10ドル{,円}000$.
В выходной файл выведите три четверки точек. Каждая четверка точек задает трапецию. Каждая трапеция описывается четырьмя строками, в каждой из которых по два вещественных числа: $x_i$ и $y_i$ --- координаты $i$-й вершины трапеции в порядке обхода против часовой стрелки. Трапеция должна иметь ненулевую площадь. После каждого описания трапеции требуется вывести пустую строку. Все точки трапеции должны находится внутри или на границе исходного четырехугольника. Трапеции не должны иметь пересечений ненулевой площади, и каждая точка исходного четырехугольника должна быть покрыта хотя бы одной из трех трапеций.
Если существует несколько решений, выведите любое. При проверке ответа на корректность площади будут равны если относительная либо абсолютная погрешность не больше 10ドル^{-5},ドル точка лежит на прямой, если расстояние от точки до прямой не больше 10ドル^{-8}$. Прямые параллельны, если синус угла между ними не больше 10ドル^{-7}$.
0 0 2 0 2 2 0 2
0 0 1 0 1 1 0 1 1 0 2 0 2 1 1 1 0 1 2 1 2 2 0 2
0 0 20 20 0 10 -20 20
0 0 11 11 3 7 -2 2 3 7 11 11 20 20 0 10 -2 2 3 7 0 10 -20 20
Обращаем ваше внимание на то, что у получившихся у вас трапеций обе пары противоположных сторон могут быть параллельны друг другу. Такой случай рассматривается в первом примере.
Второй пример изображен на следующем рисунке: