gpt-4o-2024-11-20· OpenAI
WildChat-4.8M (AI2)
import time def readfromfile(filename): with open(filename, 'r') as f: s = f.read() arr…
- User
import time
def read_from_file(filename): with open(filename, 'r') as f: s = f.read() arr = list(map(float, s.split())) return [[arr[i], arr[i+1]] for i in range(0, len(arr), 2)]
def rotate(p, q, r): """ Returns positive if p-q-r are clockwise, negative if counterclockwise, and zero if collinear. """ return (q[1] - p[1]) * (r[0] - q[0]) - (q[0] - p[0]) * (r[1] - q[1])
def jarvis(A): n = len(A) if n < 3: return [] # Convex hull is not possible if there are less than 3 points
P = list(range(n)) # Convert range to a list to allow item deletion for i in range(1, n): if A[P[i]][0] < A[P[0]][0]: P[i], P[0] = P[0], P[i] H = [P[0]] del P[0] P.append(H[0]) while True: right = 0 for i in range(1, len(P)): if rotate(A[H[-1]], A[P[right]], A[P[i]]) < 0: right = i if P[right] == H[0]: break else: H.append(P[right]) del P[right] # Fixed typo here return [A[i] for i in H]Start timing
start_time = time.time()
Read points from the file
points = read_from_file('points_n_15000.txt')
Run the convex hull algorithm
convex_hull = jarvis(points)
End timing
end_time = time.time()
Print the convex hull and the runtime
print(convex_hull) elapsed_time = end_time - start_time print("RunTime: {:.8f}".format(elapsed_time))переведи все комментарии на русский
- Assistant
import time def read_from_file(filename): with open(filename, 'r') as f: s = f.read() arr = list(map(float, s.split())) return [[arr[i], arr[i+1]] for i in range(0, len(arr), 2)] def rotate(p, q, r): """ Возвращает положительное значение, если точки p-q-r расположены по часовой стрелке, отрицательное, если против часовой стрелки, и ноль, если они коллинеарны. """ return (q[1] - p[1]) * (r[0] - q[0]) - (q[0] - p[0]) * (r[1] - q[1]) def jarvis(A): n = len(A) if n < 3: return [] # Выполнить построение оболочки невозможно, если точек меньше трех P = list(range(n)) # Преобразуем range в список, чтобы можно было удалять элементы for i in range(1, n): if A[P[i]][0] < A[P[0]][0]: P[i], P[0] = P[0], P[i] H = [P[0]] del P[0] P.append(H[0]) # Добавляем первую точку в конец списка для обеспечения цикличности while True: right = 0 for i in range(1, len(P)): # Проверяем оставшиеся точки на поворот if rotate(A[H[-1]], A[P[right]], A[P[i]]) < 0: right = i if P[right] == H[0]: # Если достигли начальной точки, завершаем break else: H.append(P[right]) del P[right] # Исправлена опечатка здесь return [A[i] for i in H] # Начало замера времени start_time = time.time() # Чтение точек из файла points = read_from_file('points_n_15000.txt') # Выполнение алгоритма выпуклой оболочки convex_hull = jarvis(points) # Окончание замера времени end_time = time.time() # Печать выпуклой оболочки и времени выполнения print(convex_hull) elapsed_time = end_time - start_time print("RunTime: {:.8f}".format(elapsed_time))