Шахматная доска

Из шахматной доски по границам клеток выпилили связную (не распадающуюся на части) фигуру без дыр. Требуется определить ее периметр.

Входные данные
Сначала вводится число N (1 ≤ N ≤ 64) – количество выпиленных клеток. В следующих N строках вводятся координаты выпиленных клеток, разделенные пробелом (номер строки и столбца – числа от 1 до 8). Каждая выпиленная клетка указывается один раз.

Выходные данные
Выведите одно число – периметр выпиленной фигуры (сторона клетки равна единице).

Примеры

Поиск прямоугольников

На поле NxM клеток (N строк и M столбцов) положили K прямоугольников один поверх другого в случайном порядке. Длины сторон прямоугольников выражаются целым числом клеток. Прямоугольники не выходят за границы поля. Границы прямоугольников совпадают с границами клеток поля.

Получившуюся ситуацию записали в таблицу чисел (каждой клетке поля соответствует клетка таблицы). Если клетка поля не закрыта прямоугольником, то в соответствующую клетку таблицы записали число 0. Если же клетка закрыта одним или несколькими прямоугольниками, то в соответствующую клетку таблицы записали число, соответствующее номеру самого верхнего прямоугольника, закрывающего эту клетку.

По содержимому таблицы требуется определить положение и размеры прямоугольников.

Гарантируется, что во входных данных содержится информация, которой достаточно для однозначного определения размеров прямоугольников.
 

Icy Perimeter

Фермер Джон собирается выпускать и продавать мороженое. Он построил машину, которая производит шарики мороженого, но, к несчастью, немного неправильной формы.

Конфигурация мороженого, которое производится машиной, может быть описано решёткой \(N \times N\) grid (\(1 \leq N \leq 1000\)):

##....
....#.
.#..#.
.#####
...###
....##

Каждый символ '.' представляет пустое место, а каждый символ '#' представляет \(1 \times 1\) квадратную ячейку мороженого.

К несчастью, сейчас машина работает не очень хорошо и может производить несколько несвязанных сгустков мороженого (на картинке сверху их два). Сгусток мороженого называется связным, если из любой ячейки сгустка можно добраться до любой другой ячейки, перемещаясь в соседнюю по одному из четырёх направлений (север, юг, запад, восток).

ФД хочет найти площадь и периметр сгустка, который имеет наибольшую площадь. Площадь сгустка равна количеству символов '#' в его картинке. Если несколько сгустков имеют одинаковую площадь, он хочет знать минимальный периметр из них. На рисунке выше, маленький сгусток имеет площадь 2 и периметр 6, а больший сгусток имеет площадь 13 и периметр 22.

Заметим, что сгусток может иметь "дыру" внутри (пустое пространство, окружённое мороженым). В таком случае граница "дыры" также учитывается в периметре сгустка. Сгусток может находиться внутри другого сгустка, в этом случае они рассматриваются как независимые сгустки. Например, ниже представлен сгусток площади 1 внутри сгустка площади 16:

#####
#...#
#.#.#
#...#
#####

Painting the Barn

Фермер Джон красит одну сторону амбара маленькими прямоугольниками. Но его отвлекают коровы, и некоторые части амбара красятся чаще, чем другие.

Мы можем описать эту сторону амбара как двумерную плоскость, на которой ФД рисует \(N\) прямоугольников, стороны которых параллельны осям координат, Прямоугольники описываются координатами левого нижнего и правого верхнего углов.

ФД хочет покрасить амбар в несколько слоёв, так чтобы не пришлось вскорости снова красить. Однако, он не хочет тратить время на лишнюю покраску. Сначала он решил, что оптимально покрасить \(K\) раз. Однако оглядев область Амбара, покрашенную ровно \(K\) раз, он решил добавить два прямоугольника, Так, чтобы максимально увеличить площадь, покрашенную ровно \(K\) раз, так чтобы эти прямоугольники не имели общей ненулевой площади пересечения. Заметим, что он может рисовать ноль новых прямоугольников или только один прямоугольник, если это может улучшить результат.

Как и уже нарисованные прямоугольники, новые должны иметь положительную площадь, а координаты их углов \(x\) и \(y\) должны быть в интервале \(0 \ldots 200\).

65997

Город имеет форму прямоугольника с вершинами в точках (-W,-H), (-W,H), (W,H),(W,-H).
Плоскость разбита на кварталы. Квартал — это единичная клетка, вершины которой имеют целочисленные координаты. Назовем квартал городским, если все вершины квартала находятся внутри города (считается, что точка на границе принадлежит городу). Всего в городе будет 4·W·H кварталов.
Дорожная сеть состоит из N дорог (часть дорог или все проходят через город).
Дорога — это прямая линия, не параллельная осям координат.
Дорога задается двумя различными точками на ней (точки могут находиться вне города).
Для каждого квартала определим "значимость". Значимость квартала равна количеству дорог, проходящих через этот квартал. Считается, что дорога проходит через квартал, если имеет с кварталом не менее двух общих точек.
Найдите значение "значимости" для каждого квартала. Для каждой полученной "значимости" определите количество кварталов, имеющих эту значимость.

Формат входных данных
В первой строке заданы значения W, H, N (9<W,H<201, 0<N<1001)
В следующих N строках задано по четыре числа (координаты двух точек прямой, определяющих дорогу).

Формат выходных данных
В первой строке выведите число K - количество различных ненулевых значений "значимости".
В следующих K строках выведите по два числа - значение "значимости" и количество кварталов, имеющих такое значение "значимости".


Примечание к примеру

Город расположен в прямоугольнике со сторонами 8 и 6 клеток (всего 48 кварталов)
Через город проходят 4 дороги AB, CD, EF, GH
Значимость 1 будет у 24 кварталов (коричневый цвет на рисунке)
Значимость 2 будет у 5 кварталов (зеленый цвет на рисунке)
Значимость 4 будет у 1 кварталов (красный цвет на рисунке)
18 кварталов будут иметь значимость равную 0 (на печать не выводиться)

История одной страны

На летние каникулы Петя приехал в Байтландию. Как оказалась, история этого государства весьма необычна.

Изначально, до появления Байтландии, на её территории были расположены n различных стран. Каждое государство владело своей территорией, которую можно было представить на карте как прямоугольник, стороны которого параллельны осям координат, а вершины расположены в целочисленных точках. Никакие две страны не пересекались, однако они могли касаться сторонами. Иногда в результате агрессивных переговоров и мирных военных походов две страны объединялись в одну. Слияние происходило только в том случае, если после объединения их владений снова получалась прямоугольная территория. В конце концов осталось только одно государство — Байтландия.

В начале времён территория каждой страны содержала внутри себя ровно один прямоугольный замок, где стороны этого замка параллельны осям координат, а вершины расположены в целочисленных точках. Допускается, что границы замка могли прилегать к границе соответствующей территории страны и к границам других замков. Удивительным образом, даже после всех переворотов, замки прекрасно сохранились. Но, к сожалению, это единственная информация, которая позволяет хоть как-то судить об изначальном расположении стран.
 

Примеры