Logo
(追記) (追記ここまで)

19959번 - No 스페셜 저지다국어

시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB49161329.545%

문제

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

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

Будем считать, что Луна на снимке выглядит как круг с центром в точке изображения $C$ и целым неотрицательным радиусом $r,ドル то есть как множество белых точек, расстояние от центров которых до точки $C$ не больше $r$. Луна полностью поместилась на снимке.

Также некоторые достаточно яркие звезды могут присутствовать на снимке в виде отдельных белых точек. Таких точек не больше 25ドル$. Объектов, отличных от Луны и звезд, на снимке не изображено.

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

입력

В первой строке ввода записаны целые числа $w$ и $h$ --- горизонтальное и вертикальное разрешение снимка, соответственно (1ドル \leqslant w, h \leqslant 50$). В следующих $h$ строках записано по $w$ символов <<.>> (черная точка) или <<*>> (белая точка).

출력

В первой строке выведите натуральное число --- максимальный радиус изображения Луны. Во второй строке выведите координаты (столбец, затем строку) центра изображения Луны с данным радиусом. Столбцы и строки нумеруются с единицы, слева направо и сверху вниз, соответственно.

Если центров может быть несколько, выведите любой. Гарантируется, что корректный ответ существует.

제한

예제 입력 1

7 8
.*.*...
.*****.
.*****.
*******
.*****.
.*****.
...*...
......*

예제 출력 1

3
4 4

예제 입력 2

5 4
.....
.....
..*..
.*...

예제 출력 2

0
2 4

힌트

출처

Olympiad > Russian Olympiad in Informatics > Russia High School Programming Contest > Russia High School Programming Contest 2010 D번

(追記) (追記ここまで)

출처

대학교 대회

  • 사업자 등록 번호: 541-88-00682
  • 대표자명: 최백준
  • 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
  • 전화번호: 02-521-0487 (이메일로 연락 주세요)
  • 이메일: contacts@startlink.io
  • 통신판매신고번호: 제 2017-서울서초-2193 호

AltStyle によって変換されたページ (->オリジナル) /