描述

在许多场景中，我们需要知道物体运动的速度。例如，机场的空中交通管制员希望了解降落飞机的速度，并在其速度过快或过慢时发出警告。测速摄像头帮助警察抓捕超速驾驶员，等等。

在本题中，你应编写程序来识别运动物体的速度。

假设物体在二维平面上以恒定的速度和方向运动。摄像头每秒拍摄一张图像。假定摄像头能够真实记录平面情况——无需担心视角问题。

背景为黑色，且物体为白色（图像中可能存在一些噪点）。无论如何，你可以假定最大的连续白色区域始终是目标物体。本题中始终只有一个最大的连续白色区域。

给定摄像头拍摄的若干张图像，计算物体的速度。输出物体的速度。

一幅图像用仅包含 “.” 或 “x” 的矩阵表示，其中 “.” 表示黑色块，“x” 表示白色块。图像张数至少为两张。

以下是一些详细定义：

• 每个像素块的边长为 1 mm（即矩阵中的每个 “.” 或 “x” 表示一个 $1\text{ mm}\times1\text{ mm}$ 的方块）。
• “物体的速度”定义为物体几何中心的运动速度：。所有物体均由方块构成。单个方块的几何中心即该方块的中心。因此，物体的几何中心可计算为：，其中 $(X[i],Y[i])$ 为第 $i$ 个方块中心的坐标，$N$ 为方块总数。
• 白色区域是若干白色方块的集合。
• 当且仅当区域内任意两块方块间存在一条仅由该区域方块构成且相邻方块共用边的路径时，称该区域为“连续白色区域”。
• 平均速度按物理教材公式计算：，其中 $t$ 从 $0$ 到 $T-1$ 遍历所有离散观测时刻。本题中，观测点总数为偶数，记为 $2T$。$\mathrm{pos}(t)$ 为第 $t$ 帧图像计算得到的物体中心位置，即公式 。
• $X$ 轴正方向自左向右，$Y$ 轴正方向自上向下。

注意，不同图像中物体形状可能不同。

输入

输入文件包含若干数据集。每个数据集以一行包含两个数字 $m$ 和 $k$ 开始，随后给出若干幅 $k$ 行 $m$ 列的矩阵，每幅矩阵表示一张拍摄图像。矩阵之间总有一行由 $m$ 个 “-” 组成的分隔线，最后一幅矩阵之后跟一行由 $m$ 个 “=” 组成的结束标志。

一行 “0 0” 表示输入结束。

图像尺寸最多为 $256\times256$；每个测试集图像张数最多为 256。

输出

对于每个测试集，输出一行包含两个数字，分别表示物体在 $X$ 和 $Y$ 方向的平均速度，单位为 mm/s，保留小数点后两位。

输入

输入由若干数据集组成，每个数据集格式如下：

m k
（第一幅矩阵）
---
（第二幅矩阵）
---
…
===

• $m,k>0$，以 “0 0” 结束输入。
• 每幅矩阵间以一行 $m$ 个 ‘-’ 分隔，最后一幅后为一行 $m$ 个 ‘=’。
• 矩阵尺寸 $\le256\times256$，每个测试集图像张数不超过 256。

输出

对每个测试集，输出一行，包含物体在 $X$、$Y$ 方向的平均速度，单位 mm/s，保留两位小数。

输入数据1

10 5
.........x
.....xxx.x
....xxx...
.....xxx..
x.........
----------
.........x
.........x
...xxx....
..xxx.....
x..xxx....
==========
0 0

输出数据1

-2.00 1.00

来源

Beijing 2002