You are given a set of n points on the plane. A line containing the origin is called good, if projection of the given set to this line forms a symmetric multiset of points. Find the total number of good lines.

Multiset is a set where equal elements are allowed.

Multiset is called symmetric, if there is a point P on the plane such that the multiset is centrally symmetric in respect of point P.


-----Input-----

The first line contains a single integer n (1 ≤ n ≤ 2000) — the number of points in the set.

Each of the next n lines contains two integers x_{i} and y_{i} ( - 10^6  ≤  x_{i},  y_{i}  ≤  10^6) — the coordinates of the points. It is guaranteed that no two points coincide.


-----Output-----

If there are infinitely many good lines, print -1.

Otherwise, print single integer — the number of good lines.


-----Examples-----
Input
3
1 2
2 1
3 3

Output
3

Input
2
4 3
1 2

Output
-1



-----Note-----

Picture to the first sample test:

[Image] 

In the second sample, any line containing the origin is good.

Source: codeforces | Difficulty: MEDIUM


Solutions:
from fractions import Fraction
import time
from collections import Counter

class Point:

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

	def to_tuple(self):
		return (self.x, self.y)

	def __repr__(self):
		return 'Point({}, {})'.format(self.x, self.y)

	def __eq__(self, other):
		return self.to_tuple() == other.to_tuple()

	def __hash__(self):
		return hash(self.to_tuple())

	def __neg__(self):
		return Point(-self.x, -self.y)

	def __add__(self, other):
		return Point(self.x + other.x, self.y + other.y)

	def __sub__(self, other):
		return self + -other

	def scalar_mul(self, mu):
		return Point(mu * self.x, mu * self.y)

	def int_divide(self, den):
		return Point(self.x // den, self.y // den)

	def __lt__(self, other):
		if self.x == other.x:
			return self.y < other.y
		return self.x < other.x

	def dot(self, other):
		return self.x * other.x + self.y * other.y

class Line:

	def __init__(self, a, b, c):
		self.a = a
		self.b = b
		self.c = c

	def __repr__(self):
		return '{}*x + {}*y + {} = 0'.format(self.a, self.b, self.c)

	@classmethod
	def between_two_points(cls, P, Q):
		return cls(P.y - Q.y, Q.x - P.x, P.x * Q.y - P.y * Q.x)

	def evaluate(self, P):
		return self.a * P.x + self.b * P.y + self.c

	def direction(self):
		if self.a == 0:
			return (0, 1)
		return (1, Fraction(self.b, self.a))
true_start = time.time()
n = int(input())
points = set()
center = Point(0, 0)
for i in range(n):
	row = input().split(' ')
	cur = Point(int(row[0]), int(row[1])).scalar_mul(2 * n)
	center += cur
	points.add(cur)
center = center.int_divide(n)
dcenter = center + center
sym_points_set = set()
for p in points:
	sym_points_set.add(dcenter - p)
nosym = list(points - sym_points_set)
if len(nosym) == 0:
	print(-1)
	return
cnt = 0
p0 = nosym[0]
good_lines = set()
for p in nosym:
	start = time.time()
	m = (p + p0).int_divide(2)
	supp = Line.between_two_points(m, center)
	time_setup = time.time() - start
	distances = list(map(supp.evaluate, nosym))
	time_projs = time.time() - start
	ok = True
	SORTING = False
	if SORTING:
		distances = sorted(distances)
		time_sorting = time.time() - start
		m = len(distances)
		for i in range(m // 2):
			if distances[i] != -distances[m - 1 - i]:
				ok = False
				break
	else:
		mydict = {}
		for dd in distances:
			dda = abs(dd)
			if dda not in mydict:
				mydict[dda] = 1
			else:
				mydict[dda] += 1
		time_sorting = time.time() - start
		for k in mydict:
			if mydict[k] % 2 == 1 and k != 0:
				ok = False
				break
	if ok:
		good_lines.add(supp.direction())
print(len(good_lines))


from fractions import Fraction
import time

class Point:

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

	def to_tuple(self):
		return (self.x, self.y)

	def __repr__(self):
		return 'Point({}, {})'.format(self.x, self.y)

	def __eq__(self, other):
		return self.to_tuple() == other.to_tuple()

	def __hash__(self):
		return hash(self.to_tuple())

	def __neg__(self):
		return Point(-self.x, -self.y)

	def __add__(self, other):
		return Point(self.x + other.x, self.y + other.y)

	def __sub__(self, other):
		return self + -other

	def scalar_mul(self, mu):
		return Point(mu * self.x, mu * self.y)

	def int_divide(self, den):
		return Point(self.x // den, self.y // den)

class Line:

	def __init__(self, a, b, c):
		self.a = a
		self.b = b
		self.c = c

	def __repr__(self):
		return '{}*x + {}*y + {} = 0'.format(self.a, self.b, self.c)

	@classmethod
	def between_two_points(cls, P, Q):
		return cls(P.y - Q.y, Q.x - P.x, P.x * Q.y - P.y * Q.x)

	def evaluate(self, P):
		return self.a * P.x + self.b * P.y + self.c

	def direction(self):
		if self.a == 0:
			return (0, 1)
		return (1, Fraction(self.b, self.a))

def abs_sgn(x):
	if x == 0:
		return (0, 0)
	if x < 0:
		return (-x, -1)
	return (x, 1)
true_start = time.time()
n = int(input())
points = set()
center = Point(0, 0)
for i in range(n):
	row = input().split(' ')
	cur = Point(int(row[0]), int(row[1])).scalar_mul(2 * n)
	center += cur
	points.add(cur)
center = center.int_divide(n)
dcenter = center + center
sym_points_set = set()
for p in points:
	sym_points_set.add(dcenter - p)
nosym = list(points - sym_points_set)
if len(nosym) == 0:
	print(-1)
	exit(0)
cnt = 0
p0 = nosym[0]
good_lines = set()
for p in nosym:
	m = (p + p0).int_divide(2)
	line = Line.between_two_points(m, center)
	distances = list(map(line.evaluate, nosym))
	ok = True
	mydict = {}
	for dd in distances:
		(dda, sgn) = abs_sgn(dd)
		if dda not in mydict:
			mydict[dda] = sgn
		else:
			mydict[dda] += sgn
	for k in mydict:
		if mydict[k] != 0:
			ok = False
			break
	if ok:
		good_lines.add(line.direction())
print(len(good_lines))