如何计算覆盖所有点的正方形菱形（Square Rhombus）的宽度W？

这里的「正方形菱形」指边与坐标轴呈45°夹角的菱形（等价于旋转45°的正方形），其宽度W定义为对边之间的垂直距离。具体计算步骤如下：

1. 坐标转换
   对每个点的原始坐标(x, y)，计算两个转换后的值：

   • u = x + y
   • v = x - y
     这个转换能把45°方向的菱形转换成uv坐标系下的轴对齐正方形，大幅简化计算逻辑。

2. 求极值范围
   遍历所有点，找出：

   • u值的最大值u_max和最小值u_min，得到u方向的范围差Δu = u_max - u_min
   • v值的最大值v_max和最小值v_min，得到v方向的范围差Δv = v_max - v_min

3. 计算宽度W
   覆盖所有点的最小正方形菱形的宽度W，就是Δu和Δv中的较大值：

   W = max(Δu, Δv)
   

   补充：如果需要求菱形的边长（即菱形边的长度），则边长为W / √2，但题目明确问的是宽度W（对边间距），直接取上述结果即可。

示例验证 #

• 示例1中的点集经过坐标转换后，计算出的Δu或Δv的较大值，就是图中覆盖所有点的菱形宽度。
• 示例2同理，通过转换坐标、计算极值差，就能得到对应的最小菱形宽度。

内容的提问来源于stack exchange，提问作者user1167761