e-olymp
Задачи

Красные и синие квадраты

Красные и синие квадраты

Петя и Вася готовились к контрольной работе по теме ”Периметр и площадь фигур”. Петя нарисовал геометрическую фигуру, закрасив на листе в клеточку некоторые клеточки синим цветом, а Вася вычислял периметр образованной фигуры и дорисовывал максимальное количество квадратов красным цветом таким образом, чтобы периметр новообразованной фигуры оставался таким же.

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

prb48

Входные данные

В первой строке находится количество синих квадратов n (0 < n < 40404). Далее идут n строк, каждая из которых содержит координаты x, y (-101x, y101) левых нижних углов синих квадратов.

Каждый синий квадрат имеет хотя бы одну общую точку хотя бы с одним другим синим квадратом. Фигура, образованная синими квадратами, является связной.

Выходные данные

Вывести количество красных квадратов.

Лимит времени 1 секунд
Лимит использования памяти 128 MiB
Входные данные #1
3
1 2
2 1
3 1
Выходные данные #1
3