c - 根据输入的四个点确定形状的高效算法

Question

我正在尝试解决Determine the shape乌瓦的问题。从阅读问题后我得到的信息来看，这是一个临时几何问题，我们必须使用一些几何定理来确定我们在 2D 平面上作为输入形式的四个点的形状。花了很多时间后，我仍然想不出任何有效的算法可以在给定的时间限制内有效地解决问题。我尝试使用距离公式和斜率，但没有多大帮助。请建议我可以用来解决的一些好的算法或定理这个问题。

Answer 1

我的第一个想法是:

1. 确定每条边的长度。使用公式 sqrt((a - x)^2 + (b - y)^2)。
2. 确定每个角度。
3. 确定哪种形状:
   • 如果所有角度都是 90
     • 如果所有边都相等，则返回 SQUARE
     • 否则，返回 RECTANGLE
   • 否则如果角度 1 = 3 和角度 2 = 4 相等
     • 如果所有边都相等，则返回 RHOMBUS
     • 否则，返回平行四边形
   • 否则，如果角度 1 + 2 == 180，或角度 3 + 4 == 180，则返回 TRAPEZIUM
   • 否则，返回普通四边形

但请考虑以下逻辑 here ;他们使用 vector 数学，简单地计算某物是否是直角或两条线是否平行，而不是计算所有角度。

1. 准备一些函数来计算两条线是否平行以及一个角度是否为直角(使用 vector 数学)。
2. 对点进行排序，使它们处于正确的旋转顺序(凹形状的实际顺序不明确，但没关系，仍应返回 ORDINARY QUAD)。
3. 确定每行的长度。
4. 根据长度以及线条是否平行或成直角确定形状。