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.

Difficulty: interview

Starter code:

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):
        # ax+by+c=0
        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

# nosym = []
# for p in points:
#     psym = dcenter-p
#     if psym not in points:
#         nosym.append(p)

sym_points_set = set()
for p in points:
    sym_points_set.add(dcenter-p)
nosym = list(points - sym_points_set)

#print(nosym)
# print("preproc:", time.time()-true_start)

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

    # sorting strat
    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:
        #print("ok", supp)
        #print(distances)
        #print(mydict)
        good_lines.add(supp.direction())

    #print("setup: {}\tprojs: {}\tsort: {}\tdone: {}".format(time_setup, time_projs, time_sorting, time.time()-start))

#print("total:", time.time()-true_start)
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):
        # ax+by+c=0
        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:
    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 = abs(dd)
        if dda not in mydict:
            mydict[dda] = 1
        else:
            mydict[dda] += 1
    for k in mydict:
        if mydict[k] % 2 == 1 and k != 0:
            ok = False
            break
    if ok:
        good_lines.add(line.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):
        # ax+by+c=0
        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)
    return


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))

# This one is accepted on CF