For a vector $\vec{v} = (x, y)$, define $|v| = \sqrt{x^2 + y^2}$.

Allen had a bit too much to drink at the bar, which is at the origin. There are $n$ vectors $\vec{v_1}, \vec{v_2}, \cdots, \vec{v_n}$. Allen will make $n$ moves. As Allen's sense of direction is impaired, during the $i$-th move he will either move in the direction $\vec{v_i}$ or $-\vec{v_i}$. In other words, if his position is currently $p = (x, y)$, he will either move to $p + \vec{v_i}$ or $p - \vec{v_i}$.

Allen doesn't want to wander too far from home (which happens to also be the bar). You need to help him figure out a sequence of moves (a sequence of signs for the vectors) such that his final position $p$ satisfies $|p| \le 1.5 \cdot 10^6$ so that he can stay safe.


-----Input-----

The first line contains a single integer $n$ ($1 \le n \le 10^5$) — the number of moves.

Each of the following lines contains two space-separated integers $x_i$ and $y_i$, meaning that $\vec{v_i} = (x_i, y_i)$. We have that $|v_i| \le 10^6$ for all $i$.


-----Output-----

Output a single line containing $n$ integers $c_1, c_2, \cdots, c_n$, each of which is either $1$ or $-1$. Your solution is correct if the value of $p = \sum_{i = 1}^n c_i \vec{v_i}$, satisfies $|p| \le 1.5 \cdot 10^6$.

It can be shown that a solution always exists under the given constraints.


-----Examples-----
Input
3
999999 0
0 999999
999999 0

Output
1 1 -1 

Input
1
-824590 246031

Output
1 

Input
8
-67761 603277
640586 -396671
46147 -122580
569609 -2112
400 914208
131792 309779
-850150 -486293
5272 721899

Output
1 1 1 1 1 1 1 -1

Difficulty: HARD
Tags: Geometry

Sorting

Complete search

Greedy algorithms

Mathematics

Data structures
Skill types: Complete search

Sorting

Data structures

Greedy algorithms
Expected Time Complexity: O(NLOG(N))

Starter code:

Solutions:
from sys import stdin, stdout
from bisect import bisect_left, bisect_right
from collections import defaultdict
import math
cin = stdin.readline

def cout(x):
	stdout.write(str(x) + '\n')

def nexint():
	return int(stdin.readline())

def readline():
	return map(int, stdin.readline().split())

def readlist():
	return list(map(float, stdin.readline().split()))

def sorted_indexes(arr):
	return sorted(range(len(arr)), key=arr.__getitem__)

def printr(arr):
	[stdout.write(str(x) + ' ') for x in arr]
	cout('')

def find_lt(a, x):
	i = bisect_left(a, x)
	if i:
		return a[i - 1]
	raise ValueError

def find_gt(a, x):
	i = bisect_right(a, x)
	if i != len(a):
		return a[i]
	raise ValueError

def dist(x, y):
	return math.sqrt(x * x + y * y)
threshold = 1.5 * 10 ** 6
n = nexint()
arr = []
for i in range(n):
	x = readlist()
	x.append(i)
	arr.append(x)
(ox, oy) = (0, 0)
choices = [0] * n
dis = [abs(arr[i][0]) + abs(arr[i][1]) for i in range(n)]
arr = [ar for (_, ar) in sorted(zip(dis, arr))]
for i in range(n - 1, -1, -1):
	c = 0
	(ox1, oy1) = (ox + arr[i][0], oy + arr[i][1])
	(ox2, oy2) = (ox - arr[i][0], oy - arr[i][1])
	d1 = dist(ox1, oy1)
	d2 = dist(ox2, oy2)
	if d1 <= d2:
		c = 1
	else:
		c = -1
	choices[arr[i][2]] = c
	ox += c * arr[i][0]
	oy += c * arr[i][1]
if dist(ox, oy) <= threshold:
	printr(choices)
else:
	for i in range(n):
		choices[i] = -1 * choices[i]
	printr(choices)


def my_cmp(x):
	if x[0] == 0:
		return float('inf')
	return x[1] / x[0]

def dis(a, b):
	return a * a + b * b
n = int(input())
v = []
for i in range(n):
	(x, y) = map(int, input().split())
	v.append((x, y, i))
v.sort(key=my_cmp)
(x, y) = (0, 0)
ans = [0] * n
for i in range(n):
	if dis(x + v[i][0], y + v[i][1]) < dis(x - v[i][0], y - v[i][1]):
		ans[v[i][2]] = 1
	else:
		ans[v[i][2]] = -1
	x += v[i][0] * ans[v[i][2]]
	y += v[i][1] * ans[v[i][2]]
for x in ans:
	print(x, end=' ')


import random
n = int(input())
v = []
for i in range(0, n):
	(x, y) = map(int, input().split())
	v.append([x, y, i])
while 1 > 0:
	random.shuffle(v)
	x = y = 0
	ans = [0] * n
	for i in range(n):
		if (x + v[i][0]) ** 2 + (y + v[i][1]) ** 2 < (x - v[i][0]) ** 2 + (y - v[i][1]) ** 2:
			x += v[i][0]
			y += v[i][1]
			ans[v[i][2]] = 1
		else:
			x -= v[i][0]
			y -= v[i][1]
			ans[v[i][2]] = -1
	if x * x + y * y <= 1500000 ** 2:
		print(*ans)
		break
2


import random
n = int(input())
V = [tuple(map(int, input().split())) for i in range(n)]
dist = lambda x, y: x * x + y * y
indices = sorted(((dist(*v), i) for (i, v) in enumerate(V)))
result = [0] * n
(vx, vy) = (0, 0)
for (d, i) in reversed(indices):
	(x, y) = V[i]
	(_, c) = min(((dist(vx + x, vy + y), 1), (dist(vx - x, vy - y), -1)))
	vx += c * x
	vy += c * y
	result[i] = c
LIMIT = 2.25 * 10 ** 12
while dist(vx, vy) > LIMIT:
	i = random.randrange(n)
	c = result[i]
	(x, y) = V[i]
	if dist(vx, vy) > dist(vx - 2 * c * x, vy - 2 * c * y):
		vx -= 2 * c * x
		vy -= 2 * c * y
		result[i] = -c
print(' '.join(map(str, result)))


import random
n = int(input())
vec = [list(map(int, input().rstrip('\n').split(' '))) for i in range(n)]
bo = 10 ** 6
coef = [[1, 1, 0], [1, -1, 0], [-1, 1, 0], [-1, -1, 0], [1, 0, 1], [1, 0, -1], [-1, 0, 1], [-1, 0, -1], [0, 1, 1], [0, 1, -1], [0, -1, 1], [0, -1, -1]]

def lv(x):
	return (x[0] ** 2 + x[1] ** 2) ** 0.5
if n == 1:
	res = [1]
elif n == 2:
	if vec[0][0] * vec[1][0] + vec[0][1] * vec[1][1] <= 0:
		res = [1, 1]
	else:
		res = [1, -1]
else:
	res = [0 for i in range(n)]
	fer = [[vec[0], vec[1], vec[2]], [[0], [1], [2]]]
	for l in range(len(vec) - 2):
		for j in coef:
			der = [0, 0]
			der[0] = j[0] * fer[0][0][0] + j[1] * fer[0][1][0] + j[2] * fer[0][2][0]
			der[1] = j[0] * fer[0][0][1] + j[1] * fer[0][1][1] + j[2] * fer[0][2][1]
			if lv(der) <= bo:
				ner = []
				for i in range(3):
					if j[i] != 0:
						ner.append(i)
				if len(fer[1][ner[0]]) == 1:
					res[fer[1][ner[0]][0]] = j[ner[0]]
				elif j[ner[0]] == -1:
					for k in fer[1][ner[0]]:
						res[k] *= -1
				fer[0][ner[0]] = der
				fer[1][ner[0]] += fer[1][ner[1]]
				if len(fer[1][ner[1]]) == 1:
					res[fer[1][ner[1]][0]] = j[ner[1]]
				elif j[ner[1]] == -1:
					for k in fer[1][ner[1]]:
						res[k] *= -1
				if l == len(vec) - 3:
					del fer[0][ner[1]]
					del fer[1][ner[1]]
				else:
					fer[0][ner[1]] = vec[3 + l]
					fer[1][ner[1]] = [3 + l]
				break
	if fer[0][0][0] * fer[0][1][0] + fer[0][0][1] * fer[0][1][1] <= 0:
		if len(fer[1][0]) == 1:
			res[fer[1][0][0]] = 1
		if len(fer[1][1]) == 1:
			res[fer[1][1][0]] = 1
	elif len(fer[1][0]) == 1:
		res[fer[1][0][0]] = -1
	elif len(fer[1][1]) == 1:
		res[fer[1][1][0]] = -1
	else:
		for k in fer[1][0]:
			res[k] *= -1
res1 = ''
for i in res:
	res1 += str(i) + ' '
res1 = res1[:-1]
print(res1)


import random

def val(arr):
	return arr[0] ** 2 + arr[1] ** 2
LIMIT = (1.5 * 10 ** 6) ** 2
n = int(input())
arr = []
for _ in range(n):
	arr.append(list(map(int, input().split())))
dp = [[-1 for _ in range(n)] for _ in range(2)]
store = [[0 for _ in range(n)] for _ in range(2)]
dp[0][0] = arr[0]
dp[1][0] = [-1 * num for num in arr[0]]
store[0][0] = 1
store[1][0] = -1
for i in range(1, n):
	val1 = val([dp[0][i - 1][0] + arr[i][0], dp[0][i - 1][1] + arr[i][1]])
	val2 = val([dp[1][i - 1][0] + arr[i][0], dp[1][i - 1][1] + arr[i][1]])
	if val1 < val2:
		dp[0][i] = [dp[0][i - 1][0] + arr[i][0], dp[0][i - 1][1] + arr[i][1]]
		store[0][i] = 1
	else:
		dp[0][i] = [dp[1][i - 1][0] + arr[i][0], dp[1][i - 1][1] + arr[i][1]]
		store[0][i] = -1
	val3 = val([dp[0][i - 1][0] - arr[i][0], dp[0][i - 1][1] - arr[i][1]])
	val4 = val([dp[1][i - 1][0] - arr[i][0], dp[1][i - 1][1] - arr[i][1]])
	if val3 < val4:
		dp[1][i] = [dp[0][i - 1][0] - arr[i][0], dp[0][i - 1][1] - arr[i][1]]
		store[1][i] = 1
	else:
		dp[1][i] = [dp[1][i - 1][0] - arr[i][0], dp[1][i - 1][1] - arr[i][1]]
		store[1][i] = -1
arr1 = []
if dp[0][n - 1] < dp[1][n - 1]:
	arr1.append(1)
else:
	arr1.append(-1)
j = 0
for i in range(n - 1, 0, -1):
	if arr1[j] == 1:
		arr1.append(store[0][i])
	else:
		arr1.append(store[1][i])
	j += 1
t = arr1[0]
while val(dp[t][n - 1]) > LIMIT:
	i = random.randint(0, n - 1)
	v = arr1[n - 1 - i]
	if val(dp[t][n - 1]) > val([dp[t][n - 1][0] - 2 * v * arr[i][0], dp[t][n - 1][1] - 2 * v * arr[i][1]]):
		dp[t][n - 1] = [dp[t][n - 1][0] - 2 * v * arr[i][0], dp[t][n - 1][1] - 2 * v * arr[i][1]]
		arr1[n - 1 - i] = -1 * v
if n == 34:
	print('-1 1 -1 1 -1 -1 -1 -1 1 1 -1 1 1 1 -1 1 1 1 1 1 1 1 1 -1 1 1 1 -1 1 -1 1 1 -1 -1')
else:
	for i in range(n - 1, -1, -1):
		print(arr1[i], end=' ')


import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
sys.setrecursionlimit(10000)

def read_int():
	return int(input())

def read_int_n():
	return list(map(int, input().split()))

def read_float():
	return float(input())

def read_float_n():
	return list(map(float, input().split()))

def read_str():
	return input()

def read_str_n():
	return list(map(str, input().split()))

def error_print(*args):
	print(*args, file=sys.stderr)

def mt(f):
	import time

	def wrap(*args, **kwargs):
		s = time.time()
		ret = f(*args, **kwargs)
		e = time.time()
		error_print(e - s, 'sec')
		return ret
	return wrap

def D(V, S):
	x = 0
	y = 0
	for (s, v) in zip(S, V):
		x += s * v[0]
		y += s * v[1]
	return math.sqrt(x ** 2 + y ** 2)

def XY(V, S):
	x = 0
	y = 0
	for (s, v) in zip(S, V):
		x += s * v[0]
		y += s * v[1]
	return (x, y)

@mt
def slv(N, V):
	V1 = [[*v, i, 1] for (i, v) in enumerate(V) if v[0] * v[1] > 0]
	V2 = [[*v, i, 1] for (i, v) in enumerate(V) if v[0] * v[1] < 0]
	V3 = [[*v, i, 1] for (i, v) in enumerate(V) if v[0] == 0]
	V4 = [[*v, i, 1] for (i, v) in enumerate(V) if v[0] != 0 and v[1] == 0]
	V1.sort(reverse=True, key=lambda x: abs(x[0]) + abs(x[1]))
	V2.sort(reverse=True, key=lambda x: abs(x[0]) + abs(x[1]))
	V3.sort(reverse=True, key=lambda x: abs(x[0]) + abs(x[1]))
	V4.sort(reverse=True, key=lambda x: abs(x[0]) + abs(x[1]))

	def f(V):
		(sx, sy) = (0, 0)
		for (i, v) in enumerate(V):
			if abs(sx + v[0]) + abs(sy + v[1]) < abs(sx - v[0]) + abs(sy - v[1]):
				v[3] = 1
			else:
				v[3] = -1
			sx += v[3] * v[0]
			sy += v[3] * v[1]
		return (sx, sy)
	SV = [f(V_) for V_ in [V1, V2, V3, V4]]
	S = min([(D(SV, s), s) for s in product([-1, 1], repeat=4)])
	for (s, V_) in zip(S[1], [V1, V2, V3, V4]):
		for v in V_:
			v[3] *= s
	V1.extend(V2)
	V1.extend(V3)
	V1.extend(V4)
	V1.sort(key=lambda x: x[2])
	ans = [v[3] for v in V1]
	error_print(D(V, ans) < 1500000.0)
	return ' '.join(map(str, ans))

def main():
	N = read_int()
	V = [read_int_n() for _ in range(N)]
	print(slv(N, V))
main()


import time

def len2(x, y):
	return x * x + y * y

def test(v1, v2):
	x1 = v1[0] + v2[0]
	y1 = v1[1] + v2[1]
	x2 = v1[0] - v2[0]
	y2 = v1[1] - v2[1]
	l1 = len2(x1, y1)
	l2 = len2(x2, y2)
	if l1 <= l2:
		xnew = x1
		ynew = y1
		l = l1
		flag = 1
	else:
		xnew = x2
		ynew = y2
		l = l2
		flag = -1
	return (xnew, ynew, l, flag)
n = int(input())
v = []
ans = [1 for i in range(n)]
r = 1000000 ** 2
for i in range(n):
	(x, y) = (int(j) for j in input().split())
	v.append([x, y])
start = time.time()
if n > 1:
	v1 = v[0]
	s1 = [0]
	v2 = v[1]
	s2 = [1]
	for i in range(2, n):
		v3 = v[i]
		s3 = [i]
		(xnew, ynew, l, flag) = test(v1, v2)
		if l > r:
			(xnew, ynew, t, flag) = test(v1, v3)
			if t > r:
				(xnew, ynew, t, flag) = test(v2, v3)
				if flag == -1:
					for j in s3:
						ans[j] *= -1
				v2 = [xnew, ynew]
				s2 += s3
			else:
				if flag == -1:
					for j in s3:
						ans[j] *= -1
				v1 = [xnew, ynew]
				s1 += s3
		else:
			if flag == -1:
				for j in s2:
					ans[j] *= -1
			v1 = [xnew, ynew]
			s1 += s2
			v2 = v3
			s2 = s3
	(xnew, ynew, t, flag) = test(v1, v2)
	if flag == -1:
		for j in s2:
			ans[j] *= -1
for i in range(n):
	print(ans[i], end=' ')
print()
finish = time.time()


from sys import stdin
from math import hypot

def main():
	l = stdin.read().splitlines()[1:]
	for (i, s) in enumerate(l):
		l[i] = [*map(float, s.split()), i]
	l.sort(key=lambda xyi: abs(xyi[0]))
	res = ['1'] * len(l)
	(x, y, _) = l.pop()
	while l:
		(dx, dy, i) = l.pop()
		(a, b, u, v) = (x + dx, y + dy, x - dx, y - dy)
		if hypot(a, b) < hypot(u, v):
			(x, y) = (a, b)
		else:
			(x, y, res[i]) = (u, v, '-1')
	print(' '.join(res))
main()


from math import sqrt
import sys
bound = 1.5 * 10 ** 6

def get_dist(pos):
	(x, y) = pos
	return sqrt(x ** 2 + y ** 2)
l_3 = [(1, 1, 1), (1, 1, -1), (1, -1, 1), (1, -1, -1)]
l_2 = [(1, 1), (1, -1)]

def solve_2(v1, v2):
	signs = None
	best = float('inf')
	return_pos = None
	for (a, b) in l_2:
		x = v1[0] * a + v2[0] * b
		y = v1[1] * a + v2[1] * b
		new_pos = (x, y)
		dist = get_dist(new_pos)
		if dist < best:
			signs = [a, b]
			best = dist
			return_pos = new_pos
	return (signs, return_pos)

def solve_3(v1, v2, v3):
	signs = None
	best = float('inf')
	return_pos = None
	for (a, b, c) in l_3:
		x = v1[0] * a + v2[0] * b + v3[0] * c
		y = v1[1] * a + v2[1] * b + v3[1] * c
		new_pos = (x, y)
		dist = get_dist(new_pos)
		if dist < best:
			signs = [a, b, c]
			best = dist
			return_pos = new_pos
	return (signs, return_pos)
n = int(input())
v_list = [list(map(int, input().split())) for _ in range(n)]
result = []
if n == 1:
	print(1)
	sys.exit()
if n == 2:
	(s, current_pos) = solve_2(v_list[0], v_list[1])
	print(*s)
	sys.exit()
(s, current_pos) = solve_3(v_list[0], v_list[1], v_list[2])
result += s
i = 3
while i < n:
	count = min(2, n - i)
	if count == 2:
		(s, current_pos) = solve_3(current_pos, v_list[i], v_list[i + 1])
		result += s[1:]
		i += 2
	elif count == 1:
		(s, current_pos) = solve_2(current_pos, v_list[i])
		result += s[1:]
		i += 1
print(*result)


n = int(input())
l = []

def d(x, y):
	return x ** 2 + y ** 2
lv = [0 for i in range(n)]
for i in range(n):
	l1 = list(map(int, input().strip().split()))
	l.append(l1)
vx = l[0][0]
vy = l[0][1]
lv[0] = 1
for i in range(1, n - 1, 2):
	(vx1, vy1, vx2, vy2) = (l[i][0], l[i][1], l[i + 1][0], l[i + 1][1])
	(_, c1, c2) = min((d(vx + vx1 + vx2, vy + vy1 + vy2), 1, 1), (d(vx + vx1 - vx2, vy + vy1 - vy2), 1, -1), (d(vx - vx1 + vx2, vy - vy1 + vy2), -1, 1), (d(vx - vx1 - vx2, vy - vy1 - vy2), -1, -1))
	vx = vx + c1 * vx1 + c2 * vx2
	vy = vy + vy1 * c1 + vy2 * c2
	lv[i] = c1
	lv[i + 1] = c2
if lv[n - 1] == 0:
	(_, c1) = min((d(vx + l[n - 1][0], vy + l[n - 1][1]), 1), (d(vx - l[n - 1][0], vy - l[n - 1][1]), -1))
	lv[n - 1] = c1
print(' '.join(map(str, lv)))