幸福安德问题

Question

幸福结局问题 (实际上是一个定理)指出：

平面上一般位置的五个点的集合都有四个点的子集，这些点构成凸四边形的顶点。

问题是由保罗·埃尔德·őS命名，两位第一次研究这个问题的数学家Ester和George订婚后结婚了。

澄清：

• 一般立场在这里意味着没有三个点是共线的。
• 由四个顶点形成的四边形将始终被认为是不相交的，而不管各点的顺序如何。例如，给定四点[1 1]、[1 2]、[2 1]、[2 2]，预期的四边形是正方形，而不是领结：

• 一个非相交的四边形是凸性，如果没有内部角超过180度；或者，如果两个对角线都位于四边形内。

挑战

给定具有正整数坐标的5个点，输出形成凸四边形的4个点。

规则

如果有几个解决方案(即几组4分)，您可以始终选择输出其中一个或全部。

输入和输出格式与往常一样灵活(数组、列表、列表列表、带有合理分隔符的字符串等)。

密码高尔夫，最少字节获胜。

测试用例

1. 输入：6 8 6 6 8 10只有一个可能的输出：6 8 6 6
2. 输入：3 8 6 9 5 1有五种解决方案：3 8 6 9 3 8 6 9 3 8 7 8 3 8 7 8 7 5 7 8
3. 输入：4 8 9 9 1 6有三种解决方案：4 8 10 2 4 8 10 2 1 9 10 2来说明，这里有三种解决方案：

Answer 1

MATLAB，67字节

I=input('');for k=~eye(5);if nnz(convhull(I(k,:)))>4;I(k,:),end;end

输入采用2D矩阵的形式，其中列分别为X和Y：

[6 8; 1 10; 6 6; 5 9; 8 10]
[3 8; 7 5; 6 9; 7 8; 5 1]
[4 8; 1 9; 9 9; 10 2; 1 6]

生成凸四元数的所有4组点都以相同的格式显示。

下面是对演示进行了一些修改，使其与Octave一起工作

解释

该解决方案采用输入的4个点的所有子集(顺序不重要)。为此，我们创建恒等矩阵并否定它：~eye(5)。我们遍历这个矩阵的列，k (循环索引)是一个逻辑数组，它指定要考虑的四个点中的哪一个。然后我们使用它从输入(I(k,:))中获取这4个XY点。

然后计算这四个点(convhull)的凸包。convhull的输出是与构成凸包的点相对应的输入指标(第一个索引重复以关闭船体)。

对于凸四边形，所有四个点都是相同点的凸包(nnz(convhull(points)) > 4)的一部分。如果我们检测到这种情况，就会显示用于这个特定迭代的点。