作者热门文章
- iOS/Objective-C 元类和类别
- objective-c - -1001 错误,当 NSURLSession 通过 httpproxy 和/etc/hosts
- java - 使用网络类获取 url 地址
- ios - 推送通知中不播放声音
我在今年的匈牙利高中生竞争性编程竞赛中发现了这个问题。我无法解决它,但事后也没有找到解决方案 - 我问过的人都没有可行的想法。
问题(简而言之):
给定一组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 ) 有很多可能的三角剖分,我们可能会错过一个有效的解决方案。
如果可以证明三角测量(最大化角度或最小化面积或类似的东西)总是产生一个解决方案,这可能会奏效。
最佳答案
创建 Delauny 三角剖分。在凸包内找到两个相邻的三角形(这意味着至少其中一个不位于凸包上方)并报告!要了解有关 Delauny 三角测量的更多信息,请阅读 here .
好像四个相邻点之间有任何凹角,它会被翻转我们可以说凸包内的每四个相邻点创建一个凸四边形。
关于algorithm - 给定一组点,找出是否存在从这些点出发的凸四边形,除此之外没有其他点,那么它的角在里面,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/55446406/
我是一名优秀的程序员,十分优秀!