algorithm - 给定一组点，找出是否存在从这些点出发的凸四边形，除此之外没有其他点，那么它的角在里面

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 .

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