Submit Info #33792

Problem Lang User Status Time Memory
Sort Points by Argument pypy3 (anonymous) AC 1170 ms 104.96 MiB

ケース詳細
Name Status Time Memory
example_00 AC 50 ms 29.83 MiB
max_random_00 AC 1170 ms 101.94 MiB
max_random_01 AC 1097 ms 103.96 MiB
max_random_02 AC 1111 ms 103.96 MiB
near_arg_00 AC 887 ms 95.47 MiB
near_arg_01 AC 1103 ms 103.58 MiB
near_arg_02 AC 894 ms 97.08 MiB
near_arg_shuffle_00 AC 1113 ms 104.96 MiB
near_arg_shuffle_01 AC 1119 ms 102.96 MiB
near_arg_shuffle_02 AC 1146 ms 102.96 MiB
random_00 AC 973 ms 79.58 MiB
random_01 AC 927 ms 86.00 MiB
random_02 AC 806 ms 63.09 MiB
small_all_00 AC 55 ms 29.84 MiB

class arg_sort: def __init__(self): self.z = 0 def inner_product(self, a, b): return a[0] * b[0] + a[1] * b[1] def outer_product(self, a, b): return a[0] * b[1] - a[1] * b[0] def chk_zone(self, a): if a[0] >= 0 and a[1] == 0: return 0 if a[0] > 0 and a[1] > 0: return 1 if a[0] == 0 and a[1] > 0: return 2 if a[0] < 0 and a[1] > 0: return 3 if a[0] < 0 and a[1] == 0: return 4 if a[0] < 0 and a[1] < 0: return -3 if a[0] == 0 and a[1] < 0: return -2 if a[0] > 0 and a[1] < 0: return -1 def compare_argument(self, a, b): # chk arg(a) <= arg(b) #if a == (0, 0) or a == b: # return True #if b == (0, 0): # return False if self.chk_zone(a) != self.chk_zone(b): return self.chk_zone(a) < self.chk_zone(b) if self.outer_product(a, b): return self.outer_product(a, b) > 0 return self.inner_product(a, a) <= self.inner_product(b, b) def bubble_arg_sort(self, n, pool, reverse=False): res = [i for i in range(n)] for i in range(n-1, 0, -1): for j in range(i): if not (self.compare_argument(pool[res[j]], pool[res[j+1]]) ^ reverse): res[j], res[j+1] = res[j+1], res[j] res_vec = [pool[res[i]] for i in range(n)] return res_vec def merge_arg_sort(self, n, pool, reverse=False): if n == 1: return pool left = self.merge_arg_sort(n//2, pool[:n//2], reverse) right = self.merge_arg_sort(n-n//2, pool[n//2:], ~(reverse)) pnt_l = 0 pnt_r = n-n//2-1 idx_r = [0 for _ in range(n)] for i in range(n): if pnt_l >= n // 2: idx_r[i] = pnt_r + n // 2 pnt_r -= 1 elif pnt_r < 0: idx_r[i] = pnt_l pnt_l += 1 else: if self.compare_argument(left[pnt_l], right[pnt_r]): if reverse: idx_r[i] = pnt_r + n // 2 pnt_r -= 1 else: idx_r[i] = pnt_l pnt_l += 1 else: if reverse: idx_r[i] = pnt_l pnt_l += 1 else: idx_r[i] = pnt_r + n // 2 pnt_r -= 1 res = [(0, 0) for i in range(n)] for i in range(n): if idx_r[i] >= n // 2: res[i] = right[idx_r[i]-n//2] else: res[i] = left[idx_r[i]] return res N = int(input()) A = [tuple(map(int, input().split())) for _ in range(N)] A = arg_sort().merge_arg_sort(N, A) for i in range(N): print(A[i][0], A[i][1])