Задача B. Отладка шарика

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб
Максимальный балл:100  

Условие

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

Для отладки Вася сделал скриншоты своего приложения (шар на них должен превратиться в круг). Скриншот представлен прямоугольным массивом символов, в котором символ "#" представляет красный пиксель, а символ "." — чёрный пиксель.

Если шар нарисован правильно, то красными будут только те пиксели, координаты которых (x; y) удовлетворяют условию (x − x0)2 + (y − y0)2 ≤ r2, где x0, y0, r — неизвестные целые числа.

Требуется написать программу, которая по изображению выяснит, правильно ли на нём нарисован шар (спроецированный в круг), и если да, то определит значения x0, y0, r.

Формат входных данных

Первая строка входных данных содержит целые числа X Y — ширину и высоту прямоугольника. Следующие Y строк содержат по X символов "#" и "." каждая — описание изображения.

Формат выходных данных

Выходные данные должны содержать целые числа 1x0 y0 r, если изображение является правильным, и число 0 в противном случае. Координаты отсчитываются от верхнего левого угла.

Ограничения

3 ≤ X, Y ≤ 2000, r ≥ 1

1 ≤ x0 − r < x0 + r ≤ X, 1 ≤ y0 − r < y0 + r ≤ Y

Примеры тестов

Стандартный вход Стандартный выход
1
3 3
.#.
###
.#.
1 2 2 1

Разбор

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

Таким образом, следует найти ограничивающий прямоугольник (то есть найти минимальные и максимальные координаты красных пикселей по каждой оси), проверить, что он является квадратом с нечётной длиной стороны, найти потенциальный центр круга как центр ограничивающего квадрата. Затем следует проверить, что внутри квадрата красными являются те и только те пиксели, которые удовлетворяют условию (x − x0)2 + (y − y0)2 ≤ r2.


0.131s 0.020s 13