Problem:


Score : 300 points

Problem Statement

There are N balls in a two-dimensional plane. The i-th ball is at coordinates (x_i, y_i).

We will collect all of these balls, by choosing two integers p and q such that p \neq 0 or q \neq 0 and then repeating the following operation:

Choose a ball remaining in the plane and collect it. Let (a, b) be the coordinates of this ball. If we collected a ball at coordinates (a - p, b - q) in the previous operation, the cost of this operation is 0. Otherwise, including when this is the first time to do this operation, the cost of this operation is 1.

Find the minimum total cost required to collect all the balls when we optimally choose p and q.

Constraints

1 \leq N \leq 50

|x_i|, |y_i| \leq 10^9

If i \neq j, x_i \neq x_j or y_i \neq y_j.

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
x_1 y_1
:
x_N y_N

Output

Print the minimum total cost required to collect all the balls.

Sample Input 1

2
1 1
2 2

Sample Output 1

1

If we choose p = 1, q = 1, we can collect all the balls at a cost of 1 by collecting them in the order (1, 1), (2, 2).

Sample Input 2

3
1 4
4 6
7 8

Sample Output 2

1

If we choose p = -3, q = -2, we can collect all the balls at a cost of 1 by collecting them in the order (7, 8), (4, 6), (1, 4).

Sample Input 3

4
1 1
1 2
2 1
2 2

Sample Output 3

2



Sample input:
2
1 1
2 2


Sample output:
1

Submission status: Accepted

Solution code:
N = int(input())
X = []
for _ in range(N):
    a, b = map(int, input().split())
    X.append((a, b))
mi = 1000
X = sorted(X)
for i in range(N):
    for j in range(i+1, N):
        p = X[j][0]-X[i][0]
        q = X[j][1]-X[i][1]
        if p == 0 and q == 0:
            continue
        if p < 0:
            p, q = -p, -q
        if p == 0 and q < 0:
            q = -q
        c = 0
        for k in range(N):
            for l in range(k):
                if X[l][0] == X[k][0] - p and X[l][1] == X[k][1] - q:
                    break
            else:
                c += 1
        mi = min(mi, c)
print(mi if mi < 1000 else 1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
from __future__ import division, print_function

import os
import sys
from io import BytesIO, IOBase

if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip

import random
import collections
import math
import itertools

def real_main():
    N = read_int()
    balls = []
    for _ in range(N):
        balls.append(read_int_array())
    print(solve(N, balls))


def solve(n, balls):
    bdict = collections.defaultdict(set)
    for x, y in balls:
        bdict[x].add(y)

    def score(p, q):
        out = n
        for x, y in balls:
            nx, ny = x + p, y + q
            if ny in bdict.get(nx, []):
                out -= 1
        return out

    tried = set()
    ans = n
    for i in range(n):
        for j in range(i):
            p, q = balls[j][0] - balls[i][0], balls[j][1] - balls[i][1]
            if (p, q) not in tried:
                tried.add((p, q))
                tried.add((-p, -q))

                points = score(p, q)
                if points < ans:
                    ans = points
    return ans



def main():
    if False and 'PYCHARM_HOSTED' in os.environ:
        main_pycharm()
    else:
        real_main()


from copy import deepcopy
def main_pycharm():
    solution = solve

    test_inputs = None
    test_outputs = None
    judge = None
    slow_solution = None
    if solution is not None:
        if test_outputs is not None:
            test_with_answers(solution, test_inputs, test_outputs)
        if judge is not None:
            test_with_judge(solution, test_inputs, judge)
        if slow_solution is not None:
            test_with_slow_solution(solution, test_inputs, slow_solution)


def test_with_answers(solution, inputs_answers):
    total, wrong = 0, 0
    for args, test_ans in inputs_answers:
        ans = solution(*args.copy())
        if ans != test_ans:
            print('WRONG! ans=%s, test_ans=%s, args=%s' % (ans, test_ans, args))
            wrong += 1
        else:
            print('GOOD')
        total += 1
    print('ALL %d TESTS PASSED' % total if not wrong else '%d out of %d tests are WRONG' % (wrong, total))


def test_with_judge(solution, inputs_gen, judge):
    total, wrong = 0, 0
    for args in inputs_gen:
        ans = solution(*deepcopy(args))
        if not judge(deepcopy(ans), *deepcopy(args)):
            print('WRONG! ans=%s, args=%s' % (ans, args))
            wrong += 1
        total += 1
    print('ALL %d TESTS PASSED' % total if not wrong else '%d out of %d tests are WRONG' % (wrong, total))


def test_with_slow_solution(solution, inputs_gen, solution_slow):
    total, wrong = 0, 0
    for args in inputs_gen:
        ans = solution(*deepcopy(args))
        slow = solution_slow(*deepcopy(args))
        if ans != slow:
            print('WRONG! ans=%s, slow=%s, args=%s' % (ans, slow, args))
            wrong += 1
        total += 1
    print('ALL %d TESTS PASSED' % total if not wrong else '%d out of %d tests are WRONG' % (wrong, total))


# region fastio

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

input = lambda: sys.stdin.readline().rstrip("\r\n")

read = input
read_int = lambda: int(input())
read_array = lambda sep=None, maxsplit=-1: input().split(sep, maxsplit)
read_int_array = lambda: [int(a) for a in read_array()]

# endregion

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import collections
LX=[]
LY=[]
def Solve():
    N=int(input())
    for i in range(N):
        x,y=(int(t) for t in input().split())
        LX.append(x)
        LY.append(y)
        
    if N==1:
        return 1
    
    LLX=[]
    LLY=[]
    for i,x1 in enumerate(LX):
        for j,x2 in enumerate(LX):
            if i==j:
                continue
            LLX.append(x2-x1)

    for i,y1 in enumerate(LY):
        for j,y2 in enumerate(LY):
            if i==j:
                continue
            LLY.append(y2-y1)


    LLL=[str(dx)+'&'+str(dy) for dx,dy in zip(LLX,LLY)]

    return N-collections.Counter(LLL).most_common(1)[0][1]

print(Solve())

Submission status: Accepted

Solution code:
n = int(input())
l = [list(map(int, input().split())) for i in range(n)]
u =[]
for i in range(n):
    ll = []
    for j in range(n):
        if j != i :
            ll.append([l[i][0] - l[j][0], l[i][1] - l[j][1]])
    u += ll
su = 0
for i in u:
    a = u.count(i)
    su = max(su, a)
print(n - su)

Submission status: Accepted

Solution code:
from collections import defaultdict
N = int( input())
ans = 50
X = [ tuple( map( int, input().split())) for _ in range(N)]
X.sort(reverse=True)
for i in range(N-1):
    for j in range(i+1,N):
        if i == j:
            continue
        p = X[i][0] - X[j][0]
        q = X[i][1] - X[j][1]
        d = defaultdict( int)
        now = 0
        for k in range(N):
            if d[X[k]] == 0:
                now += 1
            d[(X[k][0], X[k][1])] = 1
            d[(X[k][0]+p, X[k][1]+q)] = 1
            d[(X[k][0]-p, X[k][1]-q)] = 1
        if now < ans:
            ans = now
if N == 1:
    ans = 1
print(ans)

Submission status: Accepted

Solution code:
#    !/usr/bin/env python3
#    encoding: UTF-8
#    Modified: <15/Jun/2019 05:47:43 PM>


#    ✪ H4WK3yE乡
#    Mohd. Farhan Tahir
#    Indian Institute Of Information Technology (IIIT), Gwalior


import sys
import os
from io import IOBase, BytesIO


def main():
    n = int(input())
    arr = [0] * n
    for i in range(n):
        arr[i] = tuple(get_ints())
    if n == 1 or n == 2:
        print(1)
        return
    arr.sort()
    d = {}
    for i in range(n):
        for j in range(i + 1, n):
            if (arr[j][0] - arr[i][0], arr[j][1] - arr[i][1]) not in d:
                d[(arr[j][0] - arr[i][0], arr[j][1] - arr[i][1])] = 0
            d[(arr[j][0] - arr[i][0], arr[j][1] - arr[i][1])] += 1

    from operator import itemgetter
    sorted_d = sorted(d.items(), key=itemgetter(1), reverse=True)
    # print(sorted_d)

    print(n - sorted_d[0][1])


BUFSIZE = 8192


class FastIO(BytesIO):
    newlines = 0

    def __init__(self, file):
        self._file = file
        self._fd = file.fileno()
        self.writable = "x" in file.mode or "w" in file.mode
        self.write = super(FastIO, self).write if self.writable else None

    def _fill(self):
        s = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
        self.seek((self.tell(), self.seek(0, 2), super(FastIO, self).write(s))[0])
        return s

    def read(self):
        while self._fill():
            pass
        return super(FastIO, self).read()

    def readline(self):
        while self.newlines == 0:
            s = self._fill()
            self.newlines = s.count(b"\n") + (not s)
        self.newlines -= 1
        return super(FastIO, self).readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.getvalue())
            self.truncate(0), self.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        py2 = round(0.5)
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        if py2:
            self.write = self.buffer.write
            self.read = self.buffer.read
            self.readline = self.buffer.readline
        else:
            self.write = lambda s: self.buffer.write(s.encode("ascii"))
            self.read = lambda: self.buffer.read().decode("ascii")
            self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)


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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import numpy as np
n=int(input())
a=np.int32([list(map(int, input().split())) for i in range(n)])
all_diffs = np.expand_dims(a, axis=1) - np.expand_dims(a, axis=0)
d=dict()
for i in all_diffs:
    for j in i:
        d[tuple(j)]=d.get(tuple(j),0)+1
ans=n
ma=0
for i in d:
    if i!=(0,0):
        ma=max(ma,d[i])
print(ans-ma)

Submission status: Accepted

Solution code:
import itertools
import collections
n=int(input())
X=[]
for i in range(n):
  X.append([int(i) for i in input().split()])
X.sort(key=lambda x:(x[0],x[1]))
Y=[]
for c in itertools.combinations(range(n),2):
  x1,y1,x2,y2=X[c[0]][0],X[c[0]][1],X[c[1]][0],X[c[1]][1]
  Y.append((x2-x1,y2-y1))
yy=collections.Counter(Y)
print(1 if n==1 else n-yy.most_common()[0][1])

Submission status: Accepted

Solution code:
n = int(input())

cords = [list(map(int, input().split() )) for _ in range(n)]

cord_dif_dict = {}

for i in range(n):
	for j in range(n):
		if i == j:
			continue

		dif_tuple = (cords[i][0] - cords[j][0], cords[i][1] - cords[j][1])

		if dif_tuple in cord_dif_dict:
			cord_dif_dict[dif_tuple] += 1
		else:
			cord_dif_dict[dif_tuple] = 1

m = 0
for key in cord_dif_dict:
	if cord_dif_dict[key] > m:
		m = cord_dif_dict[key]

print(n - m)
# print(cord_dif_dict)

Submission status: Accepted

Solution code:


def main():
    n = input()
    if n == 1:
        print 1
        return
    xy = []
    for _ in xrange(n):
        x, y = map(int, raw_input().split())
        xy.append([x, y])
    count = {}
    for i in xrange(n):
        x0, y0 = xy[i]
        for j in xrange(n):
            if i == j:
                continue
            x1, y1 = xy[j]
            key = (x1 - x0, y1 - y0)
            try:
                count[key] += 1
            except KeyError:
                count[key] = 1
    print n - max(count.values())


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import Counter


def main():
    N = int(input())
    points = []
    for _ in range(N):
        x, y = [int(i) for i in input().split()]
        points.append([x, y])

    diffs = []
    if N == 1:
        print(1)
        return

    for i in range(N):
        for j in range(N):
            if i == j:
                pass
            else:
                x = points[i][0] - points[j][0]
                y = points[i][1] - points[j][1]
                diffs.append("{}_{}".format(x, y))

    c = Counter(diffs).most_common(1)[0][1]
    print(N-c)


main()

Submission status: Accepted

Solution code:
import sys

cin = sys.stdin
N, = map(int, cin.readline().split())
if N==1:
    print(1)
    exit(0)

x = [None] * N
for i in range(N):
    x[i] = tuple(map(int, cin.readline().split()))
x.sort()

from collections import Counter
c = Counter()
for i in range(N):
    for j in range(i):
        x0d, x1d = x[i][0] - x[j][0], x[i][1] - x[j][1]
        c[(x0d, x1d)] += 1
cMax = max(c.values())
print(N - cMax)

Submission status: Accepted

Solution code:
n = int(input())
xy = []
for i in range(n):
    xy.append(list(map(int, input().split())))
xy.sort(key = lambda x: x[1])
xy.sort()
if n == 1:
    print(1)
else:
    dif = []
    for i in range(n):
        for j in range(i + 1, n):
            dif.append((xy[j][0] - xy[i][0], xy[j][1] - xy[i][1]))
    count_dif = {}
    for i in dif:
        count_dif.setdefault(i, 0)
        count_dif[i] += 1
    print(n - max(count_dif.values()))

Submission status: Accepted

Solution code:
N = int(input())

XYs = []

for i in range(N):
    x,y = map(int,input().split())
    tmp = (x,y)
    XYs.append(tmp)


if N == 1:
    print(1)
    exit()

distances = {}

for index_fr in range(N):
    for index_to in range(N):
        if index_fr == index_to:
            continue
        fr = XYs[index_fr]
        to = XYs[index_to]
        key = str(fr[0] - to[0]) + str(fr[1] - to[1])
        if key in distances.keys():
            distances[key] += 1
        else:
            distances[key] = 1


print(N - max(distances.values()))

Submission status: Accepted

Solution code:
n = int(input())
c = [tuple(map(int, input().split())) for _ in range(n)]
s = {(0, 0): 0}
for i in range(n):
    for j in range(n):
        if i != j:
            (p, q) = [b - a for a, b in zip(c[i], c[j])]
            s[(p, q)] = s.get((p, q), 0) + 1
print(n - max(s.values()))

Submission status: Accepted

Solution code:
n = int(input())
L = [tuple(map(int, input().split())) for _ in range(n)]
if n == 1:
    print(1)
    exit()
L.sort()
sub = lambda x, p: (x[0] - p[0], x[1] - p[1])
add = lambda x, p: (x[0] + p[0], x[1] + p[1])
def check(p):
    res = 0
    l = L[:]
    while len(l):
        res += 1
        e = l.pop(0)
        while add(e, p) in l:
            l.remove(add(e, p))
            e = add(e, p)
    return res
res = float('inf')
for i in range(n):
    for j in range(i + 1, n):
        res = min(res, check(sub(L[j], L[i])))
print(res)

Submission status: Accepted

Solution code:
from collections import Counter
N = int(input())
P = [tuple(map(int, input().split())) for _ in range(N)]
P.sort()
if N == 1:
  print(1)
  exit()

ct = Counter()
for i in range(len(P)):
  x1, y1 = P[i]
  for j in range(i+1, len(P)):
    x2, y2 = P[j]
    dx, dy = x2-x1, y2-y1
    if dx < 0:
      dx, dy = -dx, -dy
    ct[(dx, dy)] += 1

print(N - ct.most_common(1)[0][1])

Submission status: Accepted

Solution code:
N = int(input())

lst = []
for i in range(N):
    lst += [list(map(int, input().split()))]

lst.sort()
ans = N
for i in range(N):
    for j in range(N):
        count = N
        if i == j:
            pass
        else:
            p = lst[i][0]-lst[j][0]
            q = lst[i][1]-lst[j][1]
            for k in range(N):
                if [lst[k][0]-p, lst[k][1]-q] in lst:
                    count -= 1
                ans = min(count, ans)

print (ans)

Submission status: Accepted

Solution code:
def inverse(a):
    return pow(a, mod - 2, mod)

def main():
    n = int(input())
    a = [0] * n
    b = [0] * n
    for i in range(n):
        x, y = map(int, input().split())
        a[i] = x
        b[i] = y
    from collections import defaultdict
    if n == 1:
        print(1)
        return 
    d = defaultdict(lambda: 0)
    for i in range(n):
        for j in range(i+1, n):
            t = a[i] - a[j]
            y = b[i] - b[j]
            tmp = 1 if (t > 0 or (t == 0 and y > 0)) else -1
            d[(tmp * t, tmp * y)] += 1

    print(n-max(d.values()))

main()

Submission status: Accepted

Solution code:
import sys
import re
sys.setrecursionlimit(10 ** 7)


def LI(): return [int(x) for x in sys.stdin.readline().split()]


def SI(): return input()


def main():
    N = int(input())
    X = []
    A = {(0, 0): 0}
    for _ in range(N):
        x, y = LI()
        X.append((x, y))
    for i in range(N):
        for j in range(i+1, N):
            x, y = X[i]
            xi, yi = X[j]
            dx = x-xi
            dy = y-yi
            if (dx, dy) in A:
                A[(dx, dy)] += 1
            else:
                A[(dx, dy)] = 1
            if (-dx, -dy) in A:
                A[(-dx, -dy)] += 1
            else:
                A[(-dx, -dy)] = 1
    print(N-max(A.values()))


main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# coding: utf-8

from collections import Counter

def ri():
    return int(input())

def rl():
    return list(input().split())

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

def main():
    n = ri()
    lx, ly = [], []
    for _ in range(n):
        x, y = rli()
        lx.append(x)
        ly.append(y)
    dd = {}
    dc = Counter()
    for i in range(n):
        for j in range(n):
            if i == j:
                continue
            d = (lx[i]-lx[j], ly[i]-ly[j])
            dd[(i, j)] = d
            dc[d] += 1
    if len(dc) == 0:
        print(n)
    else:
        v = dc.most_common()[0][1]
        print(n-v)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import combinations
from collections import defaultdict

N = int(input())
if N == 1:
    print(1)
    exit()

X = [-1] * N
Y = [-1] * N

counts = defaultdict(int)

for i in range(N):
    X[i], Y[i] = map(int, input().split())

# calc all combination
max_cost = N


for i in range(N):
    for j in range(N):
        if i == j:
            continue
        x = X[i] - X[j]
        y = Y[i] - Y[j]
        counts[(x, y)] += 1

max_tmp = max(counts.values())

print(max_cost - max_tmp)

Submission status: Accepted

Solution code:
from itertools import permutations

n = int(input())
a = set()
l = []
for i in range(n):
    x, y = map(int, input().split())
    a.add((x,y))
    l.append((x,y))

ans = n

for i, j in permutations(range(n), 2):
    ans_tmp = n
    x1, y1 = l[i]
    x2, y2 = l[j]
    p = x2 - x1
    q = y2 - y1
    if p == q == 0:
        continue
    for k in range(n):
        x, y = l[k]
        if (x-p, y-q) in a:
            ans_tmp -= 1
    ans = min(ans_tmp, ans)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
d = {}
xy = []
for i in range(N):
    x, y = map(int, input().split())
    xy.append([x, y])

for x1, y1 in xy:
    for x2, y2 in xy:
        if x1 == x2 and y1 == y2:
            continue
        dis = (x2-x1, y2-y1)
        if dis not in d:
            d[dis] = 1
        else:
            d[dis] += 1

ans = 0
if N == 1:
    ans = 1
else:
    ans = N - max(d.values())
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
x_list=[]
y_list=[]
for i in range(n):
    x,y=map(int,input().split())
    x_list.append(x)
    y_list.append(y)
ans=n
for i in range(n):
    for j in range(i+1,n):
        temp=n
        x_d=x_list[j]-x_list[i]
        y_d=y_list[j]-y_list[i]
        for l in range(n):
            for m in range(l+1,n):
                if (x_list[m]-x_list[l]==x_d and y_list[m]-y_list[l]==y_d) or (x_list[m]-x_list[l]==-x_d and y_list[m]-y_list[l]==-y_d):
                    temp=temp-1
        ans=min(ans,temp)
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

N = int(input())
pos = [list(map(int,input().split())) for _ in range(N)]

if N == 1:
    print(1)
    exit()

pos.sort(reverse = True)

cnt = Counter()

for i in range(N):
    a,b = pos[i]
    for j in range(i+1,N):
        c,d = pos[j]
        t = (a - c, b - d)
        cnt[t] += 1

ans = N - cnt.most_common()[0][1]
print(ans)

Submission status: Accepted

Solution code:
rr = raw_input
rrm = lambda: map(int, rr().split())

class DSU:
    def __init__(self, N):
        self.par = list(range(N + 1))
        self.rnk = [0] * (N + 1)
        self.sz = [1] * (N + 1)

    def find(self, x):
        if self.par[x] != x:
            self.par[x] = self.find(self.par[x])
        return self.par[x]

    def union(self, x, y):
        xr, yr = self.find(x), self.find(y)
        if xr == yr: return
        if self.rnk[xr] < self.rnk[yr]:
            xr, yr = yr, xr
        if self.rnk[xr] == self.rnk[yr]:
            self.rnk[xr] += 1

        self.par[yr] = xr
        self.sz[xr] += self.sz[yr]

    def size(self, x):
        return self.sz[self.find(x)]
    
def solve(N, A):
    B = {tuple(p):i for i,p in enumerate(A)}
    def solve2(dx, dy):
        dsu = DSU(N)
        for i, (px,py) in enumerate(A):
            nei = (px+dx, py+dy)
            if nei in B:
                dsu.union(i, B[nei])
        return len({dsu.find(i) for i in xrange(N)})
    
    ans = N
    for i, (px,py) in enumerate(A):
        for j, (qx,qy) in enumerate(A):
            if i != j:
                dx = px-qx
                dy = py-qy
                ans = min(ans, solve2(dx,dy))
    return ans

N = int(rr())
A = [rrm() for _ in xrange(N)]
print solve(N, A)

Submission status: Accepted

Solution code:
n = int(input())
xy = [list(map(int, input().split())) for i in range(n)]

xy.sort()
if n==1:
    print(1)
    exit()
ans = float('inf')

for i in range(n-1):
    for j in range(i+1,n):
        p = xy[j][0]-xy[i][0]
        q = xy[j][1]-xy[i][1]
        a = 0
        for k in range(n):
            if [xy[k][0]-p, xy[k][1]-q] not in xy:
                a+=1
        ans = min(a,ans)

print(ans)

Submission status: Accepted

Solution code:
import sys, math, collections, heapq, itertools
def gcd(a, b):
    a, b = max(a, b), min(a, b)
    while a % b > 0: a, b = b, a % b
    return b
  
def solve():
    file = sys.stdin.readline #single: int(file()), line: map(int, file().split())
    INF = 10 ** 25
    mod = 7 + 10 ** 9
    N = int(file())
    b = [[int(i) for i in input().split()] for j in range(N)]
    bset = set()
    for i in range(len(b)): bset |= {(b[i][0], b[i][1])}
    b.sort()
    maxpair = 0
    for i in range(len(b)):
        for j in range(i+1, len(b)):
            p, q = b[j][0] - b[i][0], b[j][1] - b[i][1]
            if p != 0 or q != 0:
                pair = 0
                for k in range(len(b)):
                    if (b[k][0] + p, b[k][1] + q) in bset:
                        pair += 1
                maxpair = max(maxpair, pair)
    print(N - maxpair)
    return 0
  
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
n = int(input())
xys = {}
xy = []
for _ in range(n):
  x, y = map(int, input().split())
  xys[(x,y)] = True
  xy.append((x,y))

scores = []

if n == 1:
  print(1)
  exit(0)
for i in range(n):
  for j in range(n):
    if i == j:
      continue
    xi, yi = xy[i]
    xj, yj = xy[j]
    p = xj-xi
    q = yj-yi
    score = n
    for k in range(n):
      xk, yk = xy[k]
      if (xk+p, yk+q) in xys:
        score -= 1
    scores.append(score)

print(min(scores))

Submission status: Accepted

Solution code:
from collections import Counter

N = int(input())

Map = []
for i in range(N):
    x,y = list(map(int,input().split()))
    Map.append([x,y])

dif_list = []

for i in range(N):
    for j in range(N):
        if i!=j:
            dif_list.append(str(Map[i][0]-Map[j][0])+" "+str(Map[i][1]-Map[j][1]))


c = Counter(dif_list)

max_count = 0
#print(c)
for key in c.keys():
    max_count=max(c[key],max_count)

print(N-max_count)

Submission status: Accepted

Solution code:
n = int(input())
p = [tuple(map(int,input().split())) for _ in range(n)]
d = {}
m = 0
for i in range(n):
    for j in range(n):
        if i == j:
            continue
        fx = p[i][0] - p[j][0]
        fy = p[i][1] - p[j][1]
        f = (fx, fy)
        if f not in d:
            d[f] = 0
        d[f] += 1
        m = max((m, d[f]))

print(n - m)

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    if N == 1:
        print(1)
        return
    P = [None] * N
    for i in range(N):
        x, y = map(int, input().split())
        P[i] = (x, y)
    P.sort()
    cnt = {}
    for i in range(N):
        for j in range(i+1, N):
            ix, iy = P[i]
            jx, jy = P[j]
            d = (jx - ix, jy - iy)
            if d not in cnt:
                cnt[d] = 0
            cnt[d] += 1
    print(N - max(cnt.values()))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict

N = int(input())
X, Y = [], []
for i in range(N):
    x, y = list(map(int, input().split()))
    X.append(x)
    Y.append(y)

diffs = defaultdict(int)
for i in range(N):
    for j in range(N):
        if i == j:
            continue
        diffs[(X[i]-X[j], Y[i]-Y[j])] += 1

maxans = -1
maxkey = 0
for k, v in diffs.items():
    if v > maxans:
        maxans = v
        maxkey = k

if N == 1:
    print(1)
else:
    print(N-maxans)

Submission status: Accepted

Solution code:
nl = lambda: list(map(int, input().split()))
sl = lambda: input().split()
n = lambda: int(input())
s = lambda: input()

import sys
N = n()

cords = []
for i in range(N):
    x, y = nl()
    cords.append([x, y])

if N == 1:
    print(1)
    sys.exit()

from collections import defaultdict

pats = defaultdict(int)
for i in range(N-1):
    for j in range(i+1, N):
        c1 = cords[i]
        c2 = cords[j]
        pats[(c1[0] - c2[0], c1[1] - c2[1])] += 1
        pats[(c2[0] - c1[0], c2[1] - c1[1])] += 1

print(N - sorted(list(pats.values()), reverse=True)[0])

Submission status: Accepted

Solution code:
N = int(input())
if N == 1:
    print(1)
    quit()
points = []
for _ in range(N):
    x, y = map(int, input().split())
    points.append((x, y))
diff = dict()
for i in range(N):
    for j in range(N):
        if i == j:
            continue
        x1, y1 = points[i]
        x2, y2 = points[j]
        pq = x1-x2, y1-y2
        diff[pq] = diff.get(pq, 0) + 1
val, key = max((v, k) for k, v in diff.items())
print(N-val)

Submission status: Accepted

Solution code:
import itertools
N = int(input())

XY = [[int(x) for x in input().split()] for _ in range(N)]

vectors = []

for xy1,xy2 in itertools.combinations(XY,2):
  p = xy2[0] - xy1[0]
  q = xy2[1] - xy1[1]
  vectors.append((p,q))
  vectors.append((-p,-q))

from collections import Counter
c = Counter(vectors)

if N >= 2:
  x = max(c.values())
  answer = N - x
else:
  answer = 1
print(answer)

Submission status: Accepted

Solution code:
from collections import defaultdict as di
import sys
range = xrange
input = raw_input

n = int(input())
if n == 1:
    print 1
    sys.exit()
pairs = []
for _ in range(n):
    x,y = [int(x) for x in input().split()]
    pairs.append((x,y))

diff = di(int)
for i in range(n):
    for j in range(n):
        if i != j:
            x1,y1 = pairs[i]
            x2,y2 = pairs[j]
            diff[x1-x2,y1-y2] += 1

maxi = max(diff[key] for key in diff)
print n - maxi

Submission status: Accepted

Solution code:
n = int(input())
a = [tuple(map(int,input().split())) for i in range(n)]
ans = 0
m = dict()
for i in range(n):
    for j in range(n):
        if i != j:
            x = a[i][0] - a[j][0]
            y = a[i][1] - a[j][1]
            p = (x,y)
            if p not in m:
                m[p] = 0
            m[p] += 1
            ans = max(ans, m[p])
print(n - ans)

Submission status: Accepted

Solution code:
import collections
N=int(input())
xy=[tuple([int(i) for i in input().split()])  for j in range(N)]
dist = []
if N!=1:
    for n,(x,y) in enumerate(xy):
        for m,(gx,gy) in enumerate(xy):
            if n==m:continue
            dx,dy = gx-x,gy-y
            dist.append((dx,dy))
    zerocost = max(collections.Counter(dist).values())
    print(N-zerocost)
else:
    print(1)

Submission status: Accepted

Solution code:
n = int(input())
info = [list(map(int, input().split())) for i in range(n)]

memo = {}

for i in range(n):
    for j in range(n):
        if i != j:
            p1, q1 = info[i]
            p2, q2 = info[j]
            p, q = p1 - p2, q1 - q2
            
            if p not in memo:
                memo[p] = {}
            if q not in memo[p]:
                memo[p][q] = 1
            else:
                memo[p][q] += 1

ans = 0
for i in memo:
    for j in memo[i]:
        ans = max(ans, memo[i][j])
print(n - ans)

Submission status: Accepted

Solution code:
N = int(input())
xy = [list(map(int, input().split())) for _ in range(N)]

ans = 0
for i in range(N):
  for j in range(N):
    if i == j:
      continue
    p, q = xy[i][0] - xy[j][0], xy[i][1] - xy[j][1]
    k = 0
    for x in range(N):
      for y in range(N):
        if x == y:
          continue
        if xy[x][0] - xy[y][0] == p and xy[x][1] - xy[y][1] == q:
          k += 1
    ans = max(ans, k)
print(N - ans)