Оренда-Пікселя
Гаррієт Т. Еммел продає "нерухомість" на своєму веб-сайті у вигляді квадратних блоків пікселів розміром 10-на-10. Вона розділила свою веб-сторінку на прямокутну сітку, з лініями сітки через кожні 10 пікселів. Будь-хто може орендувати блоки розміром 10-на-10 пікселів у цій сітці для розміщення творів мистецтва, реклами або чого завгодно.
Гаррієт очікувала, що більшість клієнтів захочуть придбати прямокутні області блоків, але деякі хочуть бути більш креативними. Наприклад, оптик хотів придбати блоки у формі пари окулярів, а компанія з виготовлення луків і стріл хотіла орендувати простір у формі мішені (нижче кожен квадрат - це блок розміром 10-на-10 пікселів):
Рисунок 1
Гаррієт вирішила, що, в інтересах простоти, кожна покупка повинна бути єдиною "ортогонально опуклою" областю блоків. Це просто означає, що будь-який рядок або стовпець пікселів, коли перетинається з областю, повинен складатися або з нуля, або з одного з'єднаного сегмента. Для двох наведених вище прикладів найменші ортогонально опуклі області, що містять бажані блоки, є такими:
Рисунок 2
Як послугу для своїх клієнтів, Г. Т. Еммел дозволяє їм вибрати будь-який набір блоків, а потім вона обчислює найменшу ортогонально опуклу область, що їх містить. Хоча, загалом, ця обчислена область може бути роз'єднаною, ми припускаємо, для простоти, що вона є з'єднаною, тобто що існує ортогональний шлях пікселів, що з'єднує будь-яку пару пікселів в області. Напишіть програму, яка виконує це обчислення найменшої області.
Вхідні дані
Кожен тестовий випадок складатиметься з рядка, що містить додатне ціле число n, n ≤ 10000, яке вказує кількість блоків розміром 10-на-10 пікселів, запитаних користувачем.
Далі йде один або більше рядків, що містять загалом 2n цілих чисел r_{0 }c_{0 }r_{1 }c_{1 }... r_{n-1 }c_{n-1}, 0 ≤ r_i, c_i ≤ 10^9. Кожна пара r_i c_i дає номер рядка та стовпця верхнього лівого пікселя одного з цих блоків.
Усі ці координати будуть кратними 10, і жодна пара координат не повторюватиметься в межах тестового випадку. Кожен тестовий випадок гарантовано покривається єдиним, з'єднаним, мінімальним, ортогонально опуклим багатокутником. Рядок, що містить одне число 0, завершить введення.
Вихідні дані
Для кожного тестового випадку надрукуйте номер випадку, за яким слідують координати пікселів (рядок, стовпець) вершин найменшого ортогонально опуклого багатокутника, що містить блоки, описані у введенні. Перша координата повинна бути для блоку з найменшим номером рядка і, серед них, з найменшим номером стовпця. Координати повинні описувати обхід багатокутника за годинниковою стрілкою.
Примітка: Через обмеження простору, вихідні дані для Випадку 2 показані на декількох рядках. Насправді, вони будуть на одному рядку.