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