凸包的时间复杂度是多少？

求解凸包的时间复杂度通常为O(n log n)，可以采用Graham扫描算法或Jarvis步进算法来实现。

以Graham扫描算法为例，以下是Python3的示例代码：

class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y

def orientation(p, q, r):
    val = (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y)
    if val == 0:
        return 0
    return 1 if val > 0 else 2

def graham_scan(points):
    n = len(points)
    if n < 3:
        return []
    hull = []
    l = 0
    for i in range(1, n):
        if points[i].y < points[l].y or (points[i].y == points[l].y and points[i].x < points[l].x):
            l = i
    hull.append(points[l])
    for i in range(n):
        if i == l:
            continue
        while len(hull) > 1 and orientation(hull[-2], hull[-1], points[i]) != 2:
            hull.pop()
        hull.append(points[i])
    return hull

该代码使用了类Point表示点的坐标，函数orientation判断三个点的方向，函数graham_scan实现了Graham扫描算法生成凸包。在主函数中，可以先构造好点的坐标，然后调用graham_scan函数即可求出凸包。