题目描述

具身智能部的相机画面中，常需要用一个小模板在灰度图上寻找最像的位置，例如定位按钮角标或工件纹理。这里模板已经固定为一个 K x K 的权重矩阵。

给定一张 H x W 灰度图和模板矩阵，请在所有不越界的位置计算有效互相关响应。互相关不翻转模板，也不进行 padding。输出响应最大的模板左上角坐标和响应值。

输入格式

• 第一行输入两个整数 H W。
• 随后输入 H*W 个浮点数，按行优先表示灰度图。
• 接着输入整数 K。
• 最后输入 K*K 个浮点数，按行优先表示模板权重。

输出格式

• 输出 x y score，其中 (x, y) 为最佳位置的左上角坐标，score 保留 6 位小数。

判定规则

使用标准输出比较。

• 对每个合法左上角 (x, y)，响应为 sum(image[y+dy][x+dx] * kernel[dy][dx])。
• 若最大响应并列，先取 y 较小者，再取 x 较小者。

样例

输入样例 1

3 3
1 2 3 4 5 6 7 8 9
2
1 0 0 1

输出样例 1

1 1 14.000000

样例解释 1

模板只取左上和右下两个位置，左上角为 (1,1) 时响应为 5+9=14，最大。

输入样例 2

3 3
1 1 1 1 1 1 1 1 1
2
1 1 1 1

输出样例 2

0 0 4.000000

样例解释 2

所有位置响应相同，按规则选择最靠上的、再最靠左的位置 (0,0)。