Олимпиадный тренинг

Задача . E1. Задача от Бобра - 2


Задача

Темы: *1900

Уже начинает становиться традицией предлагать участникам ABBYY Cup'а задачу, придуманную Умным Бобром. Он предложил следующую задачу.

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

Белый цвет на заданном изображении соответствует фону. Также на изображении присутствуют геометрические фигуры. Они имеют черный цвет. Известно, что изображение может содержать только два типа фигур: квадраты и круги. Вам требуется посчитать число кругов и число квадратов, которые содержатся на заданном изображении.

Квадраты на изображении могут быть повернуты произвольным образом. Кроме этого, в изображении возможен шум, устроенный следующим образом: каждый пиксель исходного изображения может с вероятностью 20% поменять свой цвет на противоположный.

Пример изображения, в котором нет шума и стороны квадратов параллельны осям координат (два круга и три квадрата).
Пример изображения, в котором нет шума и квадраты повёрнуты произвольным образом (два круга и три квадрата).
Пример изображения, в котором есть шум и квадраты повёрнуты произвольным образом (один круг и три квадрата).
Входные данные

Первая строка входных данных содержит единственное целое число n (1000 ≤ n ≤ 2000), являющееся длиной и шириной исходного изображения.

Следующие n строк описывают матрицу цветов пикселей изображения. В i-ой строке содержится ровно n целых чисел aij (0 ≤ aij ≤ 1), разделенных пробелами. Значение aij = 0 соответствует белому пикселю, а aij = 1 — чёрному.

Гарантируется, что длины сторон квадратов и диаметры кругов на изображении не менее 15 пикселей, а расстояние между любыми двумя фигурами не менее 10 пикселей. Также гарантируется, что человек всегда может легко посчитать количество соответствующих фигур на исходном изображении. Общее число фигур на изображении не превышает 50.

Ограничения на входные данные для получения 20 баллов:

  • В этих тестах нет шума и стороны квадратов параллельны осям координат.

Ограничения на входные данные для получения 50 баллов:

  • В этих тестах нет шума, однако квадраты повёрнуты произвольным образом.

Ограничения на входные данные для получения 100 баллов:

  • В этих тестах есть шум и квадраты повёрнуты произвольным образом.
Выходные данные

Выведите ровно два целых числа, разделенных единичным пробелом — число кругов и число квадратов в заданном изображении, соответственно.

Примечание

Для каждого уровня сложности вам предлагается пример исходных данных. Скачать примеры можно на http://cf.m27.workers.dev/static/materials/contests/178/e-samples.zip.


time 5000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
Комментарий учителя

Ваш ответ

выберите язык и введите исходный код


Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!
     

Загруженные файлы
Нет