시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 20 | 5 | 5 | 25.000% |
Начинающий астроном Даша наконец-то обзавелась цифровым фотоаппаратом. Конечно, фиксировать звездное небо нажатием кнопки, а уже затем производить исследования --- гораздо удобней.
Разрешающая способность матрицы фотоаппарата оказалась не слишком высокой, да и на фотографиях ночного неба можно различить только два цвета: черный и белый. Впрочем, в этом есть и свои плюсы: Даша сделала уже огромное число снимков, а память все еще не закончилась. Теперь Дашу интересует положение Луны на каждом из снимков.
Будем считать, что Луна на снимке выглядит как круг с центром в точке изображения $C$ и целым неотрицательным радиусом $r$, то есть как множество белых точек, расстояние от центров которых до точки $C$ не больше $r$. Луна полностью поместилась на снимке.
Также некоторые достаточно яркие звезды могут присутствовать на снимке в виде отдельных белых точек. Таких точек не больше $25$. Объектов, отличных от Луны и звезд, на снимке не изображено.
Напишите программу, которая по изображению найдет наибольший возможный радиус круга, который соответствует Луне, а также ее возможное положение.
В первой строке ввода записаны целые числа $w$ и $h$ --- горизонтальное и вертикальное разрешение снимка, соответственно ($1 \leqslant w, h \leqslant 50$). В следующих $h$ строках записано по $w$ символов <<.
>> (черная точка) или <<*
>> (белая точка).
В первой строке выведите натуральное число --- максимальный радиус изображения Луны. Во второй строке выведите координаты (столбец, затем строку) центра изображения Луны с данным радиусом. Столбцы и строки нумеруются с единицы, слева направо и сверху вниз, соответственно.
Если центров может быть несколько, выведите любой. Гарантируется, что корректный ответ существует.
7 8 .*.*... .*****. .*****. ******* .*****. .*****. ...*... ......*
3 4 4
5 4 ..... ..... ..*.. .*...
0 2 4