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