움직이는 물체 인식

물체가 얼마나 빠르게 움직이는지 알아야 하는 상황은 많다. 예를 들어 공항의 관제사는 착륙하는 비행기의 속도를 알고 너무 빠르거나 느리면 경고를 보내려 하고, 속도 감지 카메라는 경찰이 과속 운전자를 잡는 데 도움을 준다.

이 문제에서는 움직이는 물체의 속도를 인식하는 프로그램을 작성한다.

물체는 2차원 평면 위를 일정한 속도와 방향으로 움직인다고 가정한다. 카메라는 1초마다 한 장씩 사진을 찍는다. 카메라는 평면의 실제 모습을 그대로 기록한다고 가정한다(시야각은 신경 쓰지 않아도 된다).

배경은 검은색이고 물체만 흰색이지만, 카메라 때문에 약간의 잡음이 섞일 수 있다. 가장 큰 연속된 흰색 영역이 항상 물체이며, 그러한 가장 큰 영역은 항상 정확히 하나만 존재한다고 가정할 수 있다.

카메라가 찍은 여러 장의 사진이 주어질 때, 물체의 속도를 계산하여 출력한다.

한 장의 사진은 . 또는 x로만 이루어진 행렬로 표현되며, .는 검은색 블록, x는 흰색 블록을 뜻한다. 사진은 항상 두 장 이상 주어진다.

정의

물체의 속도는 물체의 기하학적 중심이 움직이는 속도로 정의하며, 다음과 같다.

$\left( \dfrac{\int_{(x,y)\in \text{Object}} x\,dx\,dy}{\int_{(x,y)\in \text{Object}} dx\,dy},\ \dfrac{\int_{(x,y)\in \text{Object}} y\,dx\,dy}{\int_{(x,y)\in \text{Object}} dx\,dy} \right)$

모든 물체는 정사각형 블록으로 이루어져 있고 한 블록의 기하학적 중심은 그 블록의 중심이므로, 물체의 기하학적 중심은 다음과 같이 계산할 수 있다.

$\left( \dfrac{\sum_{i \in \text{Object}} X[i]}{N},\ \dfrac{\sum_{i \in \text{Object}} Y[i]}{N} \right)$

여기서 $(X[i], Y[i])$는 $i$번째 블록 중심의 좌표이고, $N$은 물체를 이루는 블록의 개수이다.

평균 속도는 물리 교과서에서와 같이 다음과 같이 계산한다.

$\text{AvgSpeed} = \dfrac{\sum_{t=0}^{T-1} \dfrac{\text{pos}(t+T) - \text{pos}(t)}{T}}{T}$

여기서 $t$는 $0$부터 $T-1$까지의 관측 시각을 훑는다. $T$는 관측 지점 개수의 절반이며(관측 지점의 개수는 항상 짝수이다), $\text{pos}(t)$는 시각 $t$에서 관측된 물체 중심의 위치, 즉 $t$번째 사진에서 계산한 기하학적 중심이다.

그 밖의 정의:

• 각 블록은 한 변이 $1\text{ mm}$인 정사각형이다(행렬의 . 또는 x 하나가 $1\text{ mm} \times 1\text{ mm}$ 블록 하나에 해당한다).
• 흰색 영역은 흰색 블록들의 집합이다.
• 어떤 흰색 영역이 연속된 흰색 영역이라는 것은, 그 영역의 임의의 두 블록을 잇는 경로가 존재하고, 경로의 모든 블록이 그 영역 안에 있으며, 경로에서 이웃한 두 블록이 변을 공유(상하좌우 4방향 인접)하는 경우를 말한다.
• $X$축의 양의 방향은 왼쪽에서 오른쪽, $Y$축의 양의 방향은 위에서 아래이다.
• 가장 큰 연속된 흰색 영역이 항상 물체이며, 그 영역은 항상 유일하다.
• 서로 다른 사진에서 물체의 모양이 다르게 보일 수 있다.

입력은 여러 개의 데이터 케이스로 이루어진다. 각 케이스는 두 정수 $m$과 $k$가 적힌 줄로 시작한다. 그 뒤에 여러 개의 $m \times k$ 행렬($m$개의 열, $k$개의 행)이 이어지며, 각 행렬은 카메라가 찍은 사진 한 장이다. 사진은 항상 두 장 이상이다.

한 케이스 안에서 인접한 두 행렬 사이에는 -가 $m$개 있는 구분선이 들어간다. 케이스의 마지막 행렬 뒤에는 =가 $m$개 있는 종료선이 들어간다.

두 개의 0이 적힌 줄은 입력의 끝을 나타낸다.

각 사진의 크기는 최대 $256 \times 256$이고, 한 케이스에는 최대 $256$장의 사진이 들어간다.

각 테스트 케이스마다 한 줄에 두 수를 출력한다. 각각 물체의 $X$ 방향 속도와 $Y$ 방향 속도이며, 소수점 아래 둘째 자리까지 정확히 출력한다. 속도의 단위는 mm/s이다.