Опукла оболонка точок гратки
Точкою гратки будемо називати точку з цілочисельними координатами. Многокутником гратки будемо називати многокугтник, усі вершини якого є точками гратки.
Многокутник називається опуклим, якщо відрізок, що з'єднує дві довільні його точки, лежить всередині (або на границі) многокутника. Або що те ж саме, що кожен внутрішній кут многокутника менший 180 градусів.
Множиною S точок гратки опуклої оболонки називається наименший опуклий многокутник (многуктник гратки), який міститу у собі усі точки множини. (Вершини опуклої оболонки повинні належати множині точок гратки S). Якщо усі точки лежать на одній прямій, то їх опуклою оболонкою буде відрізок (вироджений многокутник – як показано на самому правому рисунку). На рисунках нижче точки множини відмічено жирними точками, вершини опуклої оболонки - позначено X, а опуклу оболонку відображено у вигляді відрізків, які з'єднуть її вершины. Не усі точки на опуклій оболонці є їївершинами.
Вершини многокутника гратки знаходяться у стандартному порядку, якщо:
a) Перша вершина має найбільшу y координату. Якщо дві вершини мають одинакову y координату, то пешою вважається та, у якій x менше.
b) Вершини многокутника задаються за годинниковою стрілкою.
Напишіть програму, яка читає множину точок гратки і виводить вершини опуклої оболонки у стандартному порядку.
Вхідні дані
Перший рядок містить єдине ціле число P, (1 ≤ P ≤ 1000) - кількість тестів. Перший рядок кожного тесту містить його номер, пропуск і кількість точок N (3 ≤ N ≤ 50) у множині. Далі задано точки множини, не більш 5 точок у кожному рядку (останній рядок може містити і менше). Кожна точка задається двома цілими числами, відокремлених пропуском, які описують її x та y координату.
Вихідні дані
Для кожного тесту потрібно вивести декілька рядків. Перший рядок містить номер тесту і кількість вершин в опуклій оболонці. Далі йдуть вершини опуклої оболонки у стандартному порядку, по одній вершині у рядку. Кожен рядок містить x та y координату вершини, відокремлені пропуском.