python编写分治法凸包问题

分治法是求解凸包问题的一种常用方法，Python也可以使用分治法来解决凸包问题。具体步骤如下：

1. 首先，将所有点按照x坐标从小到大排序，如果x坐标相同，则按照y坐标从小到大排序。

2. 将排序后的点集分成两个子集，分别求解每个子集的凸包。

3. 将两个子集的凸包合并成一个凸包。

4. 合并凸包的过程中，需要找到左侧和右侧的最高点，具体方法是：从左侧和右侧分别向中间扫描，找到最高点。

5. 重复上述步骤，直到所有点都被包含在凸包中。

下面是Python代码示例：

def cross(a, b, c):
    return (b[0]-a[0])*(c[1]-a[1]) - (b[1]-a[1])*(c[0]-a[0])

def convex_hull(points):
    points = sorted(set(points))
    if len(points) <= 1:
        return points
    def build(points):
        hull = []
        for p in points:
            while len(hull) >= 2 and cross(hull[-2], hull[-1], p) < 0:
                hull.pop()
            hull.append(p)
        return hull
    return build(points) + build(reversed(points[:-1]))

points = [(0, 0), (1, 1), (2, 2), (3, 3), (2, 0), (3, 1)]
print(convex_hull(points))