You are given the set of vectors on the plane, each of them starting at the origin. Your task is to find a pair of vectors with the minimal non-oriented angle between them.

Non-oriented angle is non-negative value, minimal between clockwise and counterclockwise direction angles. Non-oriented angle is always between 0 and π. For example, opposite directions vectors have angle equals to π.


-----Input-----

First line of the input contains a single integer n (2 ≤ n ≤ 100 000) — the number of vectors.

The i-th of the following n lines contains two integers x_{i} and y_{i} (|x|, |y| ≤ 10 000, x^2 + y^2 > 0) — the coordinates of the i-th vector. Vectors are numbered from 1 to n in order of appearing in the input. It is guaranteed that no two vectors in the input share the same direction (but they still can have opposite directions).


-----Output-----

Print two integer numbers a and b (a ≠ b) — a pair of indices of vectors with the minimal non-oriented angle. You can print the numbers in any order. If there are many possible answers, print any.


-----Examples-----
Input
4
-1 0
0 -1
1 0
1 1

Output
3 4

Input
6
-1 0
0 -1
1 0
1 1
-4 -5
-4 -6

Output
6 5

Source: codeforces | Difficulty: HARD
Tags: Geometry

Sorting


Solutions:
from collections import namedtuple
from math import sqrt
from functools import cmp_to_key
Vec = namedtuple('Vec', 'x y index')
Fraction = namedtuple('Fraction', 'num denom')

def fraction_comp(a, b):
	return a.num * b.denom > b.num * a.denom

def angle_comp(v):
	result = v.x / sqrt(v.x * v.x + v.y * v.y)
	if v.y < 0:
		result = -2 - result
	return result

def angle(v1, v2):
	(x1, y1) = (v1.x, v1.y)
	(x2, y2) = (v2.x, v2.y)
	result = (x1 * x2 + y1 * y2) / (sqrt(x1 * x1 + y1 * y1) * sqrt(x2 * x2 + y2 * y2))
	sign = -1 if x1 * x2 + y1 * y2 < 0 else 1
	return Fraction(sign * (x1 * x2 + y1 * y2) ** 2, (x1 * x1 + y1 * y1) * (x2 * x2 + y2 * y2))
n = int(input())
points = []
for i in range(n):
	(x, y) = tuple(map(int, input().split()))
	points.append(Vec(x, y, i))
points.sort(key=angle_comp)
points.reverse()
ans = (points[0].index + 1, points[n - 1].index + 1)
minAngleCos = angle(points[0], points[n - 1])
for i in range(n - 1):
	currAngleCos = angle(points[i], points[i + 1])
	if fraction_comp(currAngleCos, minAngleCos):
		minAngleCos = currAngleCos
		ans = (points[i].index + 1, points[i + 1].index + 1)
print(ans[0], ans[1], sep=' ')


from math import atan2

def dot(a, b):
	return a[0] * b[0] + a[1] * b[1]

def cross(a, b):
	return a[0] * b[1] - a[1] * b[0]
n = int(input())
a = []
for i in range(0, n):
	[x, y] = list(map(int, input().split()))
	a.append([i + 1, [x, y]])
a.sort(key=lambda x: atan2(x[1][0], x[1][1]))
a.append(a[0])
for i in range(1, len(a)):
	a[i - 1].append([dot(a[i - 1][1], a[i][1]), abs(cross(a[i - 1][1], a[i][1]))])
best = a[0]
ma = [a[0][0], a[1][0]]
for i in range(1, len(a)):
	if cross(a[i][2], best[2]) > 0:
		best = a[i]
		ma = [a[i][0], a[i + 1][0]]
print(ma[0], ma[1])


def work():

	def dot(x, y):
		return x[0] * y[0] + x[1] * y[1]
	n = int(input())
	p = []
	for i in range(n):
		(x, y) = list(map(int, input().split(' ')))
		k = (20000 if y > 0 else -20000) if x == 0 else y / x
		l2 = x * x + y * y
		p.append((x, y, i + 1, x >= 0, k, l2))
	p.sort(key=lambda item: (item[3], item[4]))
	p.append(p[0])
	ans1 = p[0][2]
	ans2 = p[1][2]
	ans_up = dot(p[0], p[1])
	ans_down = p[0][5] * p[1][5]
	for i in range(1, n):
		now_up = dot(p[i], p[i + 1])
		now_down = p[i][5] * p[i + 1][5]
		if now_up >= 0 and ans_up <= 0 or (now_up > 0 and ans_up > 0 and (now_up * now_up * ans_down > ans_up * ans_up * now_down)) or (now_up < 0 and ans_up < 0 and (now_up * now_up * ans_down < ans_up * ans_up * now_down)):
			ans_up = now_up
			ans_down = now_down
			ans1 = p[i][2]
			ans2 = p[i + 1][2]
	print(ans1, ans2)

def __starting_point():
	work()
__starting_point()


from math import atan2
inner = lambda a, b: a[0] * b[0] + a[1] * b[1]
outer = lambda a, b: a[0] * b[1] - a[1] * b[0]
N = int(input())
vectors = []
for i in range(N):
	(x, y) = map(int, input().split())
	vectors.append((atan2(y, x), (x, y), i + 1))
vectors.sort()
diff = []
for i in range(N):
	diff.append([inner(vectors[i][1], vectors[(i + 1) % N][1]), abs(outer(vectors[i][1], vectors[(i + 1) % N][1])), vectors[i][2], vectors[(i + 1) % N][2]])
min_diff = diff[0]
for d in diff:
	if outer(d[:2], min_diff[:2]) > 0:
		min_diff = d
print(min_diff[2], min_diff[3])


from math import atan2
s = lambda a, b: a[0] * b[0] + a[1] * b[1]
v = lambda a, b: a[0] * b[1] - a[1] * b[0]
p = []
for i in range(int(input())):
	(x, y) = map(int, input().split())
	p.append((atan2(x, y), (x, y), i + 1))
p.sort()
d = [(s(a, b), abs(v(a, b)), i, j) for ((x, a, i), (y, b, j)) in zip(p, p[1:] + p[:1])]
x = d[0]
for y in d:
	if v(y[:2], x[:2]) > 0:
		x = y
print(x[2], x[3])


from math import atan2
from functools import cmp_to_key
N = int(input())
V = [tuple(map(int, input().split())) for _ in range(N)]
A = []
for i in range(N):
	(x, y) = V[i]
	arg = atan2(y, x)
	A.append((arg, i))
A.sort()
D = []
for i in range(N):
	(x1, y1) = V[A[i][1]]
	(x2, y2) = V[A[i - 1][1]]
	D.append((x1, x2, y1, y2, A[i][1] + 1, A[i - 1][1] + 1))

def func(d1, d2):
	(x11, x12, y11, y12, _, _) = d1
	(x21, x22, y21, y22, _, _) = d2
	if x11 * x12 + y11 * y12 > 0 and x21 * x22 + y21 * y22 < 0:
		return 1
	if x11 * x12 + y11 * y12 < 0 and x21 * x22 + y21 * y22 > 0:
		return -1
	a1 = (x11 * x12 + y11 * y12) ** 2 * (x21 ** 2 + y21 ** 2) * (x22 ** 2 + y22 ** 2)
	a2 = (x21 * x22 + y21 * y22) ** 2 * (x11 ** 2 + y11 ** 2) * (x12 ** 2 + y12 ** 2)
	if a1 == a2:
		return 0
	if x11 * x12 + y11 * y12 >= 0 and x21 * x22 + y21 * y22 >= 0:
		return -1 if a1 < a2 else 1
	if x11 * x12 + y11 * y12 <= 0 and x21 * x22 + y21 * y22 <= 0:
		return -1 if a1 > a2 else 1
res = max(D, key=cmp_to_key(func))
print(res[4], res[5])


from functools import cmp_to_key
from math import atan2

def skal(a, b):
	return a[0][0] * b[0][0] + a[0][1] * b[0][1]

def vect(a, b):
	return a[0][0] * b[0][1] - b[0][0] * a[0][1]

def top(a):
	if a[0][1] < 0 or (a[0][1] == 0 and a[0][0] < 0):
		return 1
	else:
		return -1

def myfun(a, b):
	if top(a) != top(b):
		return top(a)
	if vect(a, b) > 0:
		return 1
	else:
		return -1
n = int(input())
a = []
for i in range(n):
	(x, y) = map(int, input().split())
	a.append([[x, y], i + 1])
a.sort(key=lambda x: atan2(x[0][1], x[0][0]))
a.append(a[0])
c = [[skal(a[0], a[1]), abs(vect(a[0], a[1]))], [a[0][1], a[1][1]]]
for i in range(1, n):
	d = [[skal(a[i], a[i + 1]), abs(vect(a[i], a[i + 1]))], [a[i][1], a[i + 1][1]]]
	if vect(d, c) > 0:
		c = d
print(c[1][0], c[1][1])


from functools import cmp_to_key
n = int(input())
x = [0 for i in range(n)]
y = [0 for i in range(n)]
for i in range(n):
	(x[i], y[i]) = map(int, input().strip().split(' '))
vp = []
vm = []
for i in range(n):
	if y[i] >= 0:
		vp.append(i)
	else:
		vm.append(i)

def cmp1(i, j):
	xi = 1 if x[i] > 0 else -1
	xj = 1 if x[j] > 0 else -1
	b = xi * x[i] * x[i] * (x[j] * x[j] + y[j] * y[j]) > xj * x[j] * x[j] * (x[i] * x[i] + y[i] * y[i])
	return -1 if b else 1

def cmp2(i, j):
	xi = 1 if x[i] > 0 else -1
	xj = 1 if x[j] > 0 else -1
	b = xi * x[i] * x[i] * (x[j] * x[j] + y[j] * y[j]) < xj * x[j] * x[j] * (x[i] * x[i] + y[i] * y[i])
	return -1 if b else 1
vp = sorted(vp, key=cmp_to_key(cmp1))
vm = sorted(vm, key=cmp_to_key(cmp2))
vp = vp + vm
vp.append(vp[0])
a = 0
b = 0
man = -2
mad = 1
for i in range(n):
	j = vp[i]
	k = vp[i + 1]
	tan = x[j] * x[k] + y[j] * y[k]
	p = tan > 0
	tan = tan * tan * (1 if p else -1)
	tad = (x[j] * x[j] + y[j] * y[j]) * (x[k] * x[k] + y[k] * y[k])
	if man * tad < tan * mad:
		man = tan
		mad = tad
		a = j
		b = k
print('{} {}'.format(a + 1, b + 1))


from math import atan2
inner = lambda a, b: a[0] * b[0] + a[1] * b[1]
outer = lambda a, b: a[0] * b[1] - a[1] * b[0]
vectors = []
for i in range(int(input())):
	(x, y) = map(int, input().split())
	vectors.append((atan2(y, x), (x, y), i + 1))
vectors.sort()
diff = [(inner(vec1, vec2), abs(outer(vec1, vec2)), i, j) for ((angle1, vec1, i), (angle2, vec2, j)) in zip(vectors, vectors[1:] + vectors[:1])]
min_diff = diff[0]
for d in diff:
	if outer(d[:2], min_diff[:2]) > 0:
		min_diff = d
print(min_diff[2], min_diff[3])


from math import *
a = []
n = int(input())
for i in range(n):
	(x, y) = map(int, input().split())
	t = acos(x / sqrt(x ** 2 + y ** 2))
	a.append((i + 1, [2 * pi - t, t][y >= 0], x, y))
cmp = lambda x: x[1]
a = sorted(a, key=cmp)
b = []
for i in range(n):
	(i1, i2) = (a[i][0], a[(i + 1) % n][0])
	(x1, y1) = a[i][2:]
	(x2, y2) = a[(i + 1) % n][2:]
	inner_prod = x1 * x2 + y1 * y2
	inner_prod *= abs(inner_prod)
	norm_prod = (x1 ** 2 + y1 ** 2) * (x2 ** 2 + y2 ** 2)
	b.append((i1, i2, inner_prod, norm_prod))
better = lambda p1, p2: p1[2] * p2[3] > p2[2] * p1[3]
ans = b[-1]
for i in range(n):
	if better(b[i], ans):
		ans = b[i]
print(ans[0], ans[1])


import math as m

class Point(object):

	def __init__(self, x, y, id):
		self.X = x
		self.Y = y
		self.id = id

def scalar(x1, y1, x2, y2):
	return x1 * x2 + y1 * y2

def vector(x1, y1, x2, y2):
	return x1 * y2 - x2 * y1
n = int(input())
dx2 = 0
dy2 = 0
a = []
for i in range(n):
	(x, y) = [int(j) for j in input().split()]
	a.append(Point(x, y, i + 1))
a.sort(key=lambda item: m.atan2(item.Y, item.X))
a.append(a[0])
minx = scalar(a[0].X, a[0].Y, a[1].X, a[1].Y)
miny = abs(vector(a[0].X, a[0].Y, a[1].X, a[1].Y))
(min1, min2) = (a[0].id, a[1].id)
for i in range(1, len(a)):
	dx2 = scalar(a[i - 1].X, a[i - 1].Y, a[i].X, a[i].Y)
	dy2 = abs(vector(a[i - 1].X, a[i - 1].Y, a[i].X, a[i].Y))
	if vector(dx2, dy2, minx, miny) > 0:
		(min1, min2) = (a[i - 1].id, a[i].id)
		minx = dx2
		miny = dy2
print(min1, min2)


from math import atan2

def skal(a, b):
	return a[0][0] * b[0][0] + a[0][1] * b[0][1]

def vect(a, b):
	return a[0][0] * b[0][1] - b[0][0] * a[0][1]
n = int(input())
a = []
for i in range(n):
	(x, y) = map(int, input().split())
	a.append([[x, y], i + 1])
a.sort(key=lambda x: atan2(x[0][1], x[0][0]))
a.append(a[0])
c = [[skal(a[0], a[1]), abs(vect(a[0], a[1]))], [a[0][1], a[1][1]]]
for i in range(1, n):
	d = [[skal(a[i], a[i + 1]), abs(vect(a[i], a[i + 1]))], [a[i][1], a[i + 1][1]]]
	if vect(d, c) > 0:
		c = d
print(c[1][0], c[1][1])


from functools import cmp_to_key
n = int(input())

def dot(p1, p2):
	(x1, y1) = p1
	(x2, y2) = p2
	return x1 * x2 + y1 * y2

def cross(p1, p2):
	(x1, y1) = p1
	(x2, y2) = p2
	return x1 * y2 - x2 * y1

def top(p):
	(x, y) = p
	return y > 0 or (y == 0 and x > 0)

def polarCmp(p1, p2):
	res = False
	ta = top(p1)
	tb = top(p2)
	if ta != tb:
		res = ta
	else:
		res = cross(p1, p2) > 0
	return -1 if res else 1

def angleLess(a1, b1, a2, b2):
	p1 = (dot(a1, b1), abs(cross(a1, b1)))
	p2 = (dot(a2, b2), abs(cross(a2, b2)))
	return cross(p1, p2) > 0
vals = []
for _ in range(n):
	(x, y) = map(int, input().split())
	vals.append((x, y))
svals = sorted(vals, key=cmp_to_key(polarCmp))
(idx1, idx2) = (0, 1)
for k in range(2, n):
	if angleLess(svals[k - 1], svals[k], svals[idx1], svals[idx2]):
		(idx1, idx2) = (k - 1, k)
if angleLess(svals[n - 1], svals[0], svals[idx1], svals[idx2]):
	(idx1, idx2) = (n - 1, 0)
res1 = res2 = -1
for k in range(n):
	if vals[k] == svals[idx1]:
		res1 = k
	if vals[k] == svals[idx2]:
		res2 = k
print(res1 + 1, res2 + 1)


from math import atan2
from functools import cmp_to_key
N = int(input())
V = []
for i in range(N):
	(x, y) = map(int, input().split())
	V.append((x, y, i))
V.sort(key=lambda z: atan2(z[1], z[0]))
D = [(V[i - 1], V[i]) for i in range(N)]

def cmp(z1, z2):
	(v11, v12) = z1
	(v21, v22) = z2
	(x11, y11, _) = v11
	(x12, y12, _) = v12
	(x21, y21, _) = v21
	(x22, y22, _) = v22
	p1 = x11 * x12 + y11 * y12
	p2 = x21 * x22 + y21 * y22
	if p1 >= 0 and p2 <= 0:
		return 1
	if p1 <= 0 and p2 >= 0:
		return -1
	q1 = p1 ** 2 * (x21 ** 2 + y21 ** 2) * (x22 ** 2 + y22 ** 2)
	q2 = p2 ** 2 * (x11 ** 2 + y11 ** 2) * (x12 ** 2 + y12 ** 2)
	if q1 == q2:
		return 0
	if p1 >= 0 and p2 >= 0:
		return 1 if q1 > q2 else -1
	if p1 <= 0 and p2 <= 0:
		return 1 if q1 < q2 else -1
(a1, a2) = max(D, key=cmp_to_key(cmp))
(_, _, idx1) = a1
(_, _, idx2) = a2
print(idx1 + 1, idx2 + 1)


(V, N, X, Y, L) = range(5)

def sec(x, y):
	if x > 0 and y >= 0:
		s = 1
	elif x <= 0 and y > 0:
		s = 2
	elif x < 0 and y <= 0:
		s = 3
	else:
		s = 4
	return s

def val(a, b, s):
	if s == 1:
		a = -a + b
	elif s == 2:
		a = a + b
	elif s == 3:
		a = -a + 3 * b
	else:
		a = a + 3 * b
	return a / b

def vec(n, x, y):
	a = x * x
	b = l = x * x + y * y
	s = sec(x, y)
	v = val(a, b, s)
	return (v, n, x, y, l)

def ang(v1, v2):
	v = v1[X] * v2[X] + v1[Y] * v2[Y]
	s = 1 if v > 0 else 2
	a = v * v
	b = v1[L] * v2[L]
	return val(a, b, s)

def quiz():
	n = int(input())
	a = []
	for i in range(n):
		(x, y) = map(int, input().split())
		a.append(vec(i + 1, x, y))
	a.sort(key=lambda x: x[V])
	(imin, vmin) = (0, 3)
	for i in range(0, n):
		v = ang(a[i - 1], a[i])
		if v < vmin:
			vmin = v
			imin = i
	print(a[imin - 1][N], a[imin][N])
quiz()


import math

def dot(a, b):
	return a[0] * b[0] + a[1] * b[1]

def cross(a, b):
	return abs(a[0] * b[1] - a[1] * b[0])
n = int(input())
vectors = []
for i in range(n):
	(x, y) = [int(x) for x in input().strip().split()]
	vectors.append((i + 1, math.atan2(y, x), (x, y)))
vectors.sort(key=lambda x: x[1])
vectors.append(vectors[0])
mind = dot(vectors[0][2], vectors[1][2])
minc = cross(vectors[0][2], vectors[1][2])
lpair = (vectors[0][0], vectors[1][0])
for i in range(1, len(vectors) - 1):
	td = dot(vectors[i][2], vectors[i + 1][2])
	tc = cross(vectors[i][2], vectors[i + 1][2])
	if td * minc - tc * mind > 0:
		mind = td
		minc = tc
		lpair = (vectors[i][0], vectors[i + 1][0])
print(*lpair)


from math import *
n = int(input())
dx1 = 0
dx2 = 0
dy1 = 0
dy2 = 0
a = []
for i in range(n):
	(x, y) = [int(x) for x in input().split()]
	a.append([x, y, i])
a.sort(key=lambda item: atan2(item[1], item[0]))
a.append(a[0])
dx1 = a[0][0] * a[1][0] + a[0][1] * a[1][1]
dy1 = abs(a[0][0] * a[1][1] - a[1][0] * a[0][1])
minx = dx1
miny = abs(dy1)
(min1, min2) = (a[0][2], a[1][2])
for i in range(1, len(a)):
	dx2 = a[i - 1][0] * a[i][0] + a[i - 1][1] * a[i][1]
	dy2 = abs(a[i - 1][0] * a[i][1] - a[i][0] * a[i - 1][1])
	if dx2 * miny - dy2 * minx > 0:
		(min1, min2) = (a[i - 1][2], a[i][2])
		minx = dx2
		miny = dy2
print(min1 + 1, min2 + 1)


import sys

def getkos(x, y):
	temp = x[0] * y[0] + x[1] * y[1]
	mul = -1 if temp < 0 else 1
	return (mul * temp ** 2, (x[0] ** 2 + x[1] ** 2) * (y[0] ** 2 + y[1] ** 2))

class Drob:

	def __init__(self, num, denom):
		self.num = num
		self.denom = denom

	def __lt__(self, object):
		return self.num * object.denom < object.num * self.denom
n = int(sys.stdin.readline())
positive = []
negative = []
for i in range(n):
	x = tuple(map(int, sys.stdin.readline().split())) + (i,)
	if x[1] > 0:
		positive.append(x)
	else:
		negative.append(x)
positive.sort(key=lambda x: Drob((-1 if x[0] > 0 else 1) * x[0] ** 2, x[1] ** 2 + x[0] ** 2))
negative.sort(key=lambda x: Drob((1 if x[0] > 0 else -1) * x[0] ** 2, x[1] ** 2 + x[0] ** 2))
all = positive + negative
biggest = [-1.1, 1]
bi = 0
bj = 1
for i in range(n):
	nxt = (i + 1) % n
	prev = (i + n - 1) % n
	kos1 = getkos(all[i], all[nxt])
	if kos1[1] * biggest[0] < kos1[0] * biggest[1]:
		biggest = kos1
		bi = all[i][2]
		bj = all[nxt][2]
	kos2 = getkos(all[i], all[prev])
	if kos2[1] * biggest[0] < kos2[0] * biggest[1]:
		biggest = kos2
		bi = all[i][2]
		bj = all[prev][2]
print('%d %d' % (bi + 1, bj + 1))


import sys
from math import atan2

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

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

def input():
	return sys.stdin.readline().strip('\n')

def dotp(a, b):
	return a[0] * b[0] + a[1] * b[1]

def crossp(a, b):
	return abs(a[0] * b[1] - a[1] * b[0])
n = int(input())
l = []
for i in range(n):
	(x, y) = get_ints()
	l.append((x, y, i + 1))
l.sort(key=lambda x: atan2(x[1], x[0]))
l.append(l[0])
a = l[0][:2]
b = l[1][:2]
x = l[0][2]
y = l[1][2]
(dot, cross) = (dotp(a, b), crossp(a, b))
(mx, my) = (dot, cross)
for i in range(1, n + 1):
	a = l[i - 1][:2]
	b = l[i][:2]
	(ndot, ncross) = (dotp(a, b), crossp(a, b))
	if ndot * my - ncross * mx > 0:
		x = l[i - 1][2]
		y = l[i][2]
		mx = ndot
		my = ncross
print(x, y)


from math import sqrt

class vector:
	(x, y, index) = (0, 0, -1)

	def __init__(self, x, y, index):
		self.x = x
		self.y = y
		self.index = index

	def __lt__(self, other):
		if self.x * other.x < 0:
			return self.x > 0
		if self.x == 0 and other.x == 0:
			return self.y > other.y
		if self.x == 0 and other.x < 0 or (self.x < 0 and other.x == 0):
			self.y * other.x > other.y * self.x
		return self.y * other.x < other.y * self.x

	def __str__(self):
		return str(self.x) + ' ' + str(self.y) + ' ' + str(self.index)

def dot(A, B):
	res = A.x * B.x + A.y * B.y
	if res < 0:
		return -res * res
	else:
		return res * res

def mod_sq(A):
	return A.x * A.x + A.y * A.y
n = int(input())
arr = []
for i in range(n):
	temp = [int(i) for i in input().split()]
	arr.append(vector(temp[0], temp[1], i))
arr.sort()
for i in range(n):
	arr.append(arr[i])
ans = [0, 1]
(D, M) = (dot(arr[0], arr[1]), mod_sq(arr[0]) * mod_sq(arr[1]))
for i in range(2 * n - 1):
	(tD, tM) = (dot(arr[i], arr[i + 1]), mod_sq(arr[i]) * mod_sq(arr[i + 1]))
	if tD * M > D * tM:
		D = tD
		M = tM
		ans = [i, i + 1]
print(arr[ans[0]].index + 1, arr[ans[1]].index + 1)