Moving Object Recognition

There are many situations in which we need to know how fast an object is moving. For example, an air-traffic controller at an airport wants to know the speed of a descending plane and warn if it is too fast or too slow, speed cameras help the police catch speeding drivers, and so on.

In this problem you must write a program that recognizes the speed of a moving object.

Assume an object moves on a two-dimensional plane with a constant speed and direction. A camera takes one shot every second. Assume the camera records the true scene of the plane (you do not need to worry about the viewing angle).

The background is black and the only object is white, except for some noise introduced by the camera. You may assume that the largest continuous white area is always the object, and there is always exactly one such largest area.

Given several pictures taken by the camera, compute and output the speed of the object.

A picture is a matrix containing only . or x, where . is a black block and x is a white block. There are always at least two pictures.

Definitions

The speed of the object is the moving speed of the object's geometric center, defined as

$$\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)$$

Every object is made of unit square blocks, and the geometric center of a single block is the block's own center, so the geometric center of the object can be computed as

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

where $(X[i], Y[i])$ is the coordinate of the center of the $i$-th block and $N$ is the number of blocks in the object.

The average speed is computed as in a physics textbook:

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

where $t$ ranges over the discrete observation times from $0$ to $T-1$. Here $T$ is half of the number of observation points (the number of observation points is always even), and $\text{pos}(t)$ is the observed position of the object's center at time $t$, that is, the geometric center computed from the $t$-th image.

Other definitions:

• Each block is a $1\text{ mm} \times 1\text{ mm}$ square (every . or x is one such block).
• A white area is a set of white blocks.
• A white area is a continuous white area if and only if any two of its blocks are joined by a path that stays inside the area and whose consecutive blocks share a common edge (4-directional adjacency).
• The positive $X$ direction is from left to right; the positive $Y$ direction is from top to bottom.
• The largest continuous white area is always the object, and it is always unique.
• The object may appear with a different shape in different pictures.

The input contains several data cases. Each case begins with a line containing two integers $m$ and $k$. It is followed by several $m \times k$ matrices ($m$ columns, $k$ rows); each matrix is one picture taken by the camera, and there are always at least two pictures.

Within one case, consecutive matrices are separated by a line of $m$ - characters. The last matrix of a case is followed by a line of $m$ = characters.

A line containing two zeros marks the end of the input.

Each picture is at most $256 \times 256$, and one case contains at most $256$ pictures.

For each test case, output one line with two numbers: the speed of the object in the $X$ and $Y$ directions respectively, each printed to exactly two digits after the decimal point. Speeds are in mm/s.