Внутрішні точки решітчатого многокутника
Внутрішні точки це точки з цілочисельними координатами. Решітчатий многокутник це многокутник з вершинами у точках з цілочисельними координатами.
Точки з цілочисельними координатами на границі многокутника є граничними точками (показані не зафарбованими точками на рисунку вище), а внутрішні точки знаходяться всередині многокутника і також мають цілочисельні координаты (показано зафарбованими точками на рисунку вище).
Многокутник називається опуклим якщо довільний його відрізок знаходиться або на його границі або всередині многокутника. Це твердження рівносильно тому, що довільний внутрішній кут многокутника менше 180 градусів. Зверніть увагу, що довільний відрізок між двома внутрішніми точками завжди знаходиться всередині многокутника, але не на його границі.
Внутрішні точки опуклого многокутника решітки на довільній горизонтальній лінії утворюють єдиний сегмент від лівої крайньої точки до правої крайньої точки (які можуть співпадати). Зверніть увагу, що може бути ніяких внутрішніх точок (А), або лише одна внутрішня точка (B), або ізольовані внутрішні точки (C), як це показано на рисунках нижче.
Напишіть програму, яка читає вершини опуклого многокутника гратки у стандартному порядку і виводить перелік його внутрішніх точок у вигляді списку горизонтальних відрізків. Вершини многокутника решітки знаходяться у стандартному порядку, якщо:
a) Перша вершина має найбільше значення координати y. Якщо дві вершини мають однакове значення y, то вершина з меншим значенням координати x вказується у першу чергу.
b) Вершини задано за годинниковою стрілкою навколо многокутника.
Вхідні дані
Перший рядок вхідного файлу містить одне ціле число P (1 ≤ P ≤ 1000) , яке вказує кількість наступних наборів тестових даних. У першому рядку кожного набору даних міститься номер тестового прикладу, а далі через пропуск вказано кількість вершин N (3 ≤ N ≤ 50) многокутника. Інші рядки у кожному наборі даних містять вершини, по одній у рядку у стандартному порядку. Кожен рядок містить спочатку координату х, а потім координату у. Усі координати цілі числа.
Вихідні дані
Для кожного набору даних вивести декілька рядків. У першому рядку вивести десяткове ціле число - номер тестового набору даних, а далі через пропуск десяткове ціле - кількість горизонтальних рядків, які містять внутрішні точки (воно може бути рівним нулю (0) або більше). Рядки внутрішніх точок, якщо такі є, йдуть по одной у рядку у порядку спадання значення у. Кожен рядок містить спочатку десяткове ціле число - у-координату рядка точок, а далі через пропуск спочатку десяткове ціле число х-координати самої лівої точки у цьому рядку, а потім х-координату самої правої точки у цьому ж рядку.