Опукла оболонка точок ґратки#2446
Точкою ґратки називається точка з цілими координатами. Багатокутник ґратки — це багатокутник, усі вершини якого є точками ґратки.
Багатокутник називається опуклим, якщо будь-який відрізок, що з'єднує дві його точки, повністю лежить всередині (або на межі) багатокутника. Інакше кажучи, кожен внутрішній кут багатокутника менший за градусів.
Опукла оболонка множини точок ґратки — це найменший опуклий (ґратковий) багатокутник, що містить усі точки з цієї множини. (Вершини опуклої оболонки мають бути серед точок ґратки .) Якщо всі точки лежать на одній прямій, їх опукла оболонка — це відрізок (у цьому випадку це вироджений багатокутник — як показано на правому малюнку нижче). На діаграмах нижче точки множини позначено суцільними кружечками, вершини опуклої оболонки — знаком , сама оболонка зображена відрізками, що з'єднують вершини. Не всі точки опуклої оболонки є її вершинами.
Вершини ґраткового багатокутника записані у стандартному порядку, якщо:
a) Перша вершина має найбільшу -координату. Якщо таких декілька, то першою іде та, у якої -координата менша.
b) Вершини перераховані за годинниковою стрілкою.
Напишіть програму, яка зчитує множину ґраткових точок і виводить вершини опуклої оболонки у стандартному порядку.
У першому рядку міститься одне ціле число (1 \leq P \leq 1000) — кількість наборів даних. Для кожного набору даних перший рядок містить його номер, пробіл та (3 \leq N \leq 50) — кількість точок. Далі йдуть точки множини, не більше точок у рядку (останній рядок може містити менше). Кожна точка задається двома цілими числами — координатами та , розділеними пробілом.
Для кожного набору даних виведіть кілька рядків. У першому рядку зазначте номер набору і кількість вершин опуклої оболонки. Далі виведіть вершини опуклої оболонки у стандартному порядку, по одній у рядку. Кожен рядок містить координати та вершини, розділені пробілом.
Приклад 1