凸包求助啊
  • 板块学术版
  • 楼主Liasisphus
  • 当前回复3
  • 已保存回复3
  • 发布时间2023/11/19 12:39
  • 上次更新2023/11/19 14:59:27
查看原帖
凸包求助啊
653511
Liasisphus楼主2023/11/19 12:39

在二维平面中有一组具有实值坐标的 n 个点,我们将这组点表示为 V,V 中的任何三个点都不是共线的。假设你有一个无限长的箭头位于这个二维平面的 P∈V 点上并指向东方。现在箭头开始逆向旋转,中心位于 P 点。一旦这个箭头击中一个点,就说点 Q。现在,旋转中心变为 Q,并继续该过程,直到箭头再次指向东方。 返回 V 中的一组点(由坐标表示),这样旋转过程就可以遍历 V 中的所有点。 运行时间: 10s 测试用例:1≤n≤〖10〗^6

示例 2: 输入: 4, {(0.0, 0.0), (2.0, -1.0), (3.0, 2.0), (2.0, 1.0)} 输出: {(0.0, 0.0), (2.0, 1.0)}

from math import atan2

def get_angle(p1, p2):
    "Get the angle of p1 w.r.t to p2 treating p2 as origin."
    return atan2(p1[1]-p2[1], p1[0]-p2[0])

def cross_product(o, a, b):
    "Calculate the cross product of vectors (o->a) x (o->b)."
    return (a[0]-o[0])*(b[1]-o[1]) - (b[0]-o[0])*(a[1]-o[1])

def rotating_arrow(points):
    # sort points lexicographically
    points.sort()

    # remove duplicates
    points = sorted(set(points))
    
    # Find the east-most (also bottom-most in case of tie), set as start_point
    east_most = max(points, key=lambda p: (p[0], -p[1]))

    path = []

    while len(points) > 0:
        # Remove start point from points list
        points.remove(east_most)

        # If no points left, break the loop
        if not points:
            break

        # Sort the points counterclockwise with respect to start point
        points.sort(key=lambda p: -get_angle(p, east_most))

        # Select the first point in the sorted list as the next point
        next_point = points[0]
        
        path.append(east_most)

        east_most = next_point

    # add start point to make sure path is closed from east to east
    path.append(path[0])

    return path

def main():
    points = [(1,1), (1,2), (2,2), (2,3), (0,1), (-1,-1), (-1,1), (1,-1)]
    print("Original points:", points)

    rotating_path = rotating_arrow(points)
    print("Result points:", rotating_path)

if __name__ == "__main__":
    main()

大佬们,我这个是graham方法,请帮我看看哪里有问题吧,炸裂。

2023/11/19 12:39
加载中...