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

Question

我在今年的匈牙利高中生编程竞赛中发现了这个问题。我无法解决它，但后来没有运气找到解决方案 - 我问过的人都没有可行的想法。

问题（简而言之）：
给定一组 N 个点，确定是否存在来自这些点的凸四边形（四边形角来自点集），inside which no other point is contained（没有第五个点在四边形的内部或边缘）。
如果存在这样的四边形，return 点（输入中点的索引）按（任意）逆时针顺序排列。
如果不存在这样的四边形，return 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。

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

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

Given a set of points, find if there exists a convex quad from these points with no points other then its corners are inside

algorithm

geometry

point

computational-geometry