在二维平面中有一组具有实值坐标的 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方法,请帮我看看哪里有问题吧,炸裂。