Члены экипажа обнаружили место преступления предателя. Теперь команда корабля хочет огра-дить это место преступления.
Место преступления выглядит как выпуклый многоугольник A. Команда корабля хочет оградить его другим выпуклым многоугольником B. Причем, у B должно быть минимальное возможное число вершин. И все вершины многоугольника A должны лежать на границе многоугольника B.
Помогите команде выбрать такой многоугольник B.
В первой строке дано одно целое число t (1 ≤ t ≤ 1000) количество тестовых наборов. Далее дано описание t тестов.
В первой строке каждого теста дано одно целое число n (3 ≤ n ≤ 100) - количество вершин в многоугольнике A.
В следующих n строках даны по два целых числа x[i]
и y[i]
координаты i-й вершины многоугольника (|x[i]
|, |y[i]
| ≤ 1000). Вершины многоугольника даны в порядке обхода против часовой стрелки. Гарантируется, что многоугольник является строго выпуклым. То есть, в том числе, никакие три его последовательные вершины не лежат на одной прямой.
Для каждого теста сначала выведите одно целое число m - количество вершин в найденном многоугольнике B.
В следующих m строках выведите по два вещественных числа x[i]
и y[i]
координаты i-й вершины многоугольника. Выводите вершины многоугольника в порядке обхода против часовой стрелки. Выведенный многоугольник должен быть строго выпуклым. А также, все вершины исходного многоугольника должны находиться на расстоянии не более 10^(-6)
от границы выведенного многоугольника.