Внутрішні точки решітчатого многокутника#2447

Внутрішні точки решітчатого многокутника

1 секунда

64 мегабайти

Дуже легка

Точка решітки — це точка з цілочисельними координатами. Решітчастий многокутник — це многокутник, усі вершини якого є точками решітки.

Точки решітки на межі многокутника є граничними точками (незаповнені точки на рисунку вище), а внутрішні точки — це точки решітки, які лежать всередині многокутника і не належать його межі (заповнені точки на рисунку вище).

Многокутник називається опуклим, якщо будь-який відрізок між двома точками многокутника повністю лежить або всередині, або на межі многокутника. Це еквівалентно тому, що внутрішній кут при кожній вершині менший за $180$ градусів. Зауважте, що будь-який відрізок між двома внутрішніми точками (які не на межі) повністю лежить всередині многокутника і не належить межі.

Внутрішні точки опуклого решітчастого многокутника на будь-якій горизонтальній прямій утворюють єдиний сегмент від крайньої лівої точки до крайньої правої (які можуть співпадати). Зауважте, що може не бути жодної внутрішньої точки (A), лише одна (B) або ізольовані внутрішні точки (C), як показано на рисунках нижче.

Напишіть програму, яка читає вершини опуклого решітчастого многокутника у стандартному порядку і виводить перелік його внутрішніх точок у вигляді списку горизонтальних відрізків. Вершини решітчастого многокутника задано у стандартному порядку, якщо:

[(a)] Перша вершина має найбільше значення $y$ . Якщо дві вершини мають однакове $y$ , то першою вказується вершина з меншим $x$ .
[(b)] Вершини задано за годинниковою стрілкою навколо многокутника.

Вхідні дані

Перший рядок вхідного файлу містить одне ціле число $P$ ( $1 \leq P \leq 1000$ 1 \leq P \leq 1000), що означає кількість наборів тестових даних. У першому рядку кожного набору даних вказується номер тесту, а далі через пробіл кількість вершин $N$ ( $3 \leq N \leq 50$ 3 \leq N \leq 50) многокутника. Інші рядки кожного набору містять вершини у стандартному порядку, по одній у рядку. Кожен рядок містить $x$ і $y$ — цілі координати.

Вихідні дані

Для кожного набору даних виведіть кілька рядків. Перший рядок — номер тесту, пробіл і кількість горизонтальних прямих, що містять внутрішні точки (це число може дорівнювати нулю ( $0$ ) або бути більшим). Рядки з внутрішніми точками, якщо вони є, подаються по одному у порядку спадання $y$ . Кожен рядок містить $y$ -координату, $x$ -координату крайньої лівої точки і $x$ -координату крайньої правої точки, розділені пробілами.

Приклади

Приклад 1