问O(n)时间中的凸壳如果每个点的每个坐标是一个有理数

EN

不要使用Jarvis，因为它具有O(nh)的时间复杂性。在最坏的情况下，h可能和n一样大。注意，h是船体上的点数。

相反，您应该使用格雷厄姆扫描，它的时间复杂度是O(nlogn)。在格雷厄姆扫描算法中，时间复杂度主要取决于对所有点的排序。请注意，基于比较的排序算法的时间复杂度为O(nlogn)。

在家庭作业问题中，您可以使用基类而不是任何基于比较的排序算法来击败O(nlogn)的上界，因为有一个假设，即所有点的坐标都是有界的。注意，当要排序的输入为有界基时，可以使用排序，这具有O(n)的复杂性。

有关各种凸壳算法的比较，请参见这里。