给定一组点，找出这些点是否存在凸四边形而没有其他点，那么它的角就在里面

Question

我今年在高中学生的匈牙利竞争性节目竞赛中发现了这个问题。我无法解决这个问题，但之后没有找到解决方案的运气 - 我没有人问过他有过一个有用的想法。

问题（简而言之）： 给定一组N个点，确定这些点是否存在凸四边形（四边形角来自点集），其中不包含其他点（没有第五个点在内部或边缘上）四边形）。 如果存在这样的四边形，则以（任意）逆时针顺序返回点（输入中的点的索引）。 如果不存在这样的四边形，则返回0 0 0 0。

限制： 你得到1<=K<=10集与1<=N[i]<=100 000点坐标-1 000 000 <=x,y<=1 000 000 时间限制：0.2秒 内存限制：32MB

天真的解决方案：

For every subset with four points (N(N-1)(N-2)(N-3)/24):    
   Check if resulting quad is convex! If no, continue to next subset.
   For every other (N-4) points:
      Check if it is contained in the quad
   If no point is contained, return the quad.
If no quad was returned, return "0 0 0 0"

时间复杂：O(n^5)！

另一个想法（我不认为它是否有帮助）： 做一个点集三角测量，然后只检查相邻的三角形。问题是，一组点（see this）有很多可能的三角测量，我们可能会错过一个有效的解决方案。 如果可以证明三角测量（最大化角度或最小化面积或类似的东西）总能产生解决方案，这可能会起作用。

Answer 1

创建Delauny三角剖分。在凸包内找到两个相邻的三角形（这意味着它们中至少有一个不在凸包上）并报告！要找到有关Delauny三角测量的更多信息，请阅读here。

好像在四个相邻点之间存在任何凹角，它将被翻转我们可以说凸包内的每四个相邻点创建一个凸四边形。