만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

사진 속 달

면접 대비

시간 제한2초메모리 제한512 MB

요약
검은 점이 포함되지 않는 가장 큰 원의 반지름과 중심의 열, 행 좌표를 구합니다.
난이도

쉬움10점 중 3점

유형
완전 탐색, 기하
정답자
아직 제출이 없습니다

문제

초보 천문학자 다샤가 드디어 디지털 카메라를 샀다. 버튼을 눌러 밤하늘을 찍어 두고 나중에 분석하는 편이 훨씬 편하다.

카메라 센서의 해상도는 그리 높지 않고, 야간 사진은 검은색과 흰색 두 가지로만 구분된다. 다샤는 이미 아주 많은 사진을 찍었지만 저장 공간은 아직 남아 있다. 그녀는 각 사진에서 달의 위치를 알고 싶어 한다.

달은 중심이 점 CC이고 반지름이 0 이상의 정수 rr인 원으로 보인다. 즉, CC까지의 거리가 rr 이하인 흰 점들의 집합이다. 달은 사진 안에 완전히 들어 있다.

밝은 별은 흰 점 하나로 찍힐 수 있다. 별은 최대 25개이다. 사진에는 달과 별 말고 다른 대상이 없다.

사진에서 달에 해당하는 원의 최대 반지름과 그 반지름을 가지는 중심의 위치를 찾는 프로그램을 작성하라.

입력

첫 줄에 사진의 가로, 세로 해상도를 나타내는 정수 ww와 hh가 주어진다 (1⩽w,h⩽501 \leqslant w, h \leqslant 50). 이어지는 hh개의 줄에는 각각 ww개의 문자가 주어진다. "."은 검은 점, "*"은 흰 점이다.

출력

첫 줄에 달의 최대 반지름을 자연수로 출력한다. 둘째 줄에는 그 반지름을 가지는 달 중심의 좌표를 열, 행 순서로 출력한다. 열과 행은 각각 왼쪽에서 오른쪽, 위에서 아래로 1부터 번호를 매긴다.

가능한 중심이 여럿이면 그중 아무거나 출력하면 된다. 올바른 답이 존재함이 보장된다.

예제2

  1. 예제 1

    입력
    7 8
    .*.*...
    .*****.
    .*****.
    *******
    .*****.
    .*****.
    ...*...
    ......*
    
    예상 출력
    3
    4 4
    
  2. 예제 2

    입력
    5 4
    .....
    .....
    ..*..
    .*...
    
    예상 출력
    0
    2 4