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

Solution (Python):


class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1]*n 
 
    def root(self, x): 
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]
            x = self.parent[x]
        return x 
 
    def merge(self, x, y): 
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return False
        if self.size[x] < self.size[y]: 
            self.size[y] += self.size[x] 
            self.parent[x] = y 
        else:
            self.size[x] += self.size[y] 
            self.parent[y] = x 
        return True
 
    def issame(self, x, y): 
        return self.root(x) == self.root(y)
        
    def size(self,x): 
        return self.size[self.root(x)]

n = int(input())
xy = [[int(i) for i in input().split()] for j in range(n)] 

ans = n
s = {(x1-x2, y1-y2) for (x1,y1) in xy for (x2,y2) in xy}
s.remove((0,0))

for dx,dy in s:
    uf = UnionFind(n)
    c = 0
    for i, (xi,yi) in enumerate(xy):
        for j, (xj,yj) in enumerate(xy):


            if xj-xi == dx and yj-yi == dy:
                uf.merge(i,j)
                c+=1

    if ans > n-c:
        ans = n-c
                

print(ans)

Solution (Python):
import collections
N = int(input())
xy_array = [list(map(int, input().split())) for i in range(N)]
if N == 1:
    print(1)
    exit()

distance_array = []
for i in range(N):
    x_i, y_i = xy_array[i]
    for j in range(N):
        if i == j:
            continue
        x_j, y_j = xy_array[j]
        distance_array.append((x_i - x_j, y_i - y_j))

ans_array = collections.Counter(distance_array)
max_count = ans_array.most_common()[0][1]
print(N - max_count)

Solution (Python):
import collections

n = int(input())

x = []
y = []
for i in range(n):
    xx, yy = map(int, input().split())
    x.append(xx)
    y.append(yy)

vec = []
vec_set = []

for i in range(n):
    vec2 = []
    for j in range(n):
        vec2.append((x[i] - x[j], y[i] - y[j]))
        vec_set.append((x[i] - x[j], y[i] - y[j]))
    vec.append(vec2)

cc = collections.Counter(vec_set)

v_l = []
for key,value in cc.items():
    if key != (0,0):
        v_l.append(value)
if len(v_l) != 0:
    print(n - max(v_l))
else:
    print(1)

Solution (Python):
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().split())
Mat=[[(x[i]-x[j],y[i]-y[j]) for j in range(i+1,N)] for i in range(N)]
D=dict()
for i in range(N):
    for j in range(N):
        if i==j:
            continue
        dr=(x[i]-x[j],y[i]-y[j])
        if dr in D:
            D[dr]+=1
        else:
            D[dr]=1
maxk=0
for v in D:
    if D[v]>maxk:
        maxk=D[v]
print(N-maxk)

Solution (Python):
n=int(input())
A=[]
B=[]
for i in range(n):
  a,b=map(int,input().split())
  A.append([a,b])
  
for i in range(n):
  for j in range(i):
    B.append([A[i][0]-A[j][0],A[i][1]-A[j][1]])
  for j in range(i+1,n):
    B.append([A[i][0]-A[j][0],A[i][1]-A[j][1]])
    

l=0
for i in B:
  l=max(l,B.count(i))
print(n-l)

Solution (Python):
from itertools import combinations as c
from collections import Counter

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

if n==1:
    print(1)
else:
    l.sort()
    m=c(l,2)
    ans=[]
    for v in m:
        ans.append(str([v[1][0]-v[0][0],v[1][1]-v[0][1]]))
    a=Counter(ans).most_common()[0][1]
    print(n-a)

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

if N==1:
    print(1)
    exit(0)
diff={}
for i in range(N):
    for j in range(i+1, N):
        a=(xy[i][0]-xy[j][0], xy[i][1]-xy[j][1])
        diff[a]=diff.get(a,0)+1
print(N-max(diff.values()))

Solution (Python):
import collections

def solve(n, points):
    if n == 1:
        return 1
    a = []
    for i in range(n-1):
        for j in range(i + 1, n):
            x = points[i][0] - points[j][0]
            y = points[i][1] - points[j][1]
            if x > 0:
                a.append((x, y))
            elif x < 0:
                a.append((-x, -y))
            else:
                a.append((0, abs(y)))

    c = collections.Counter(a).most_common()[0][1]
    return n - c

n = int(input())
points = [list(map(int, input().split(' '))) for _ in range(n)]
print(solve(n, points))

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
xy = [LIST() for _ in range(N)]
xy.sort(key=lambda x:(x[0], x[1]))

delta = defaultdict(int)
if N == 1:
	print(1)
else:
	for i in range(N):
		for j in range(N):
			if i != j:
				delta[(xy[j][0]-xy[i][0], xy[j][1]-xy[i][1])] += 1
	print(1+(N-1)-max(delta.values()))

Solution (Python):
from collections import defaultdict

n = int(input())
if n == 1:
	print(1)
else:
	balls = [list(map(int, input().split())) for _ in range(n)]

	d = defaultdict(lambda: 0)
	for x in range(n):
		for y in range(n):
			d[(balls[x][0] - balls[y][0], balls[x][1] - balls[y][1])] += 1

	del d[(0, 0)]
	print(n - max(d.values()))

Solution (Python):
N = int(input())
src = [tuple(map(int,input().split())) for i in range(N)]
pq = []
for i in range(N):
    for j in range(N):
        if i==j: continue
        x0,y0 = src[i]
        x1,y1 = src[j]
        pq.append((x1-x0, y1-y0))

ss = set(src)

ans = N
for p,q in pq:
    tmp = 0
    for x,y in src:
        if (x+p, y+q) not in ss:
            tmp += 1
    ans = min(ans, tmp)
print(ans)

Solution (Python):
import sys
input=sys.stdin.readline
from collections import deque
from heapq import heappush,heappop
import re

def int_raw():
    return int(input())
 
def ss_raw():
    return input().split()
 
def ints_raw():
    return tuple(map(int, ss_raw()))


def mod_inv(a, b):
    r = a
    w = b
    u = 1
    v = 0
    while w != 0:
        t = r//w
        r -= t*w
        r, w = w, r
        u -= t*v
        u, v = v, u
    return (u % b+b) % b


DIV = 10**9+7

def ncr(n, r, mod=DIV):
	r = min(r, n-r)
	ret = 1
	for i in range(1, r+1):
		ret = ret * (n-i+1) % mod
		ret = ret * mod_inv(i, mod) % mod
	return ret


def main():
    ans = 0
    N = int_raw()
    bxys = [ints_raw() for _ in range(N)]
    if N==1:
        return 1
    bxys.sort()
    dtables = {}

    for idx in range(0,N):
        for idx2 in range(idx+1,N):
            dxy = (bxys[idx2][0]-bxys[idx][0],bxys[idx2][1]-bxys[idx][1])
            if dxy in dtables:
                dtables[dxy]+=1
            else:
                dtables[dxy]=1
    dmax = max(dtables.values())
    return N-dmax

print(main())

Solution (Python):
import itertools
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")


class UnionFind:
    def __init__(self, size=None, nodes=None):
        """
        size か nodes どっちか指定。
        nodes は set、size は list を使う。
        set の最悪計算量は O(N) なので size 指定のほうが若干速い
        :param int size:
        :param collections.Iterable nodes:
        """
        assert size is not None or nodes is not None
        if size is not None:
            self._parents = [i for i in range(size)]
            self._ranks = [0 for _ in range(size)]
            self._sizes = [1 for _ in range(size)]
        else:
            self._parents = {k: k for k in nodes}
            self._ranks = {k: 0 for k in nodes}
            self._sizes = {k: 1 for k in nodes}

    def unite(self, x, y):
        """
        x が属する木と y が属する木を併合
        :param x:
        :param y:
        :return:
        """
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return

        
        if self._ranks[x] > self._ranks[y]:
            
            self._parents[y] = x
            self._sizes[x] += self._sizes[y]
        else:
            
            self._parents[x] = y
            self._sizes[y] += self._sizes[x]
            if self._ranks[x] == self._ranks[y]:
                self._ranks[y] += 1

    def find(self, x):
        """
        x が属する木の root
        :param x:
        :return:
        """
        if self._parents[x] == x:
            return x
        self._parents[x] = self.find(self._parents[x])
        return self._parents[x]

    def size(self, x):
        """
        x が属する木のノード数
        :param x:
        :return:
        """
        return self._sizes[self.find(x)]


N = int(sys.stdin.readline())
X, Y = list(zip(*[map(int, sys.stdin.readline().split()) for _ in range(N)]))

min_x = min(X)
min_y = min(Y)
max_x = max(X)
max_y = max(Y)

coo = {}
for i, (x, y) in enumerate(zip(X, Y)):
    coo[(x, y)] = i

ans = N
for i, j in itertools.combinations(range(N), r=2):
    x1, x2 = X[i], X[j]
    y1, y2 = Y[i], Y[j]
    p = x1 - x2
    q = y1 - y2

    uf = UnionFind(size=N)
    for k in range(N):
        x, y = X[k], Y[k]
        if (x + p, y + q) in coo:
            uf.unite(k, coo[(x + p, y + q)])
        if (x - p, y - q) in coo:
            uf.unite(k, coo[(x - p, y - q)])
    roots = set()
    for k in range(N):
        roots.add(uf.find(k))
    ans = min(len(roots), ans)
print(ans)

Solution (Python):
n=int(input())
arr=[]
for i in range(n):
	x,y=map(int,input().split())
	arr.append((x,y))
arr.sort()
ans=1000000000000000
for i in range(n-1):
	for j in range(i+1,n):
		currp=arr[j][0]-arr[i][0]
		currq=arr[j][1]-arr[i][1]
		mark=[0]*n
		temp=0
		k=0
		while(k<n):
			if(mark[k]==0):
				xval=arr[k][0]
				yval=arr[k][1]
				l=k+1
				while(l<n):
					if(arr[l][0]==xval+currp and arr[l][1]==yval+currq):
						mark[l]=1
						xval=arr[l][0]
						yval=arr[l][1]
					l+=1
				temp+=1
			k+=1
		ans=min(ans,temp)
if(ans==1000000000000000):
	ans=1
print(ans)

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

d = dict()
for i in range(n):
    for j in range(n):
        if i == j:
            continue
        x1,y1 = l[i]
        x2,y2 = l[j]
        if d.__contains__((x2-x1,y2-y1)):
            d[(x2-x1,y2-y1)] += 1
        else:
            d[(x2-x1,y2-y1)] = 1

ll = list(d.values())
if ll == []:
    maxV = 0
else:
    maxV = max(list(d.values()))

print(n-maxV)

Solution (Python):
N=int(input())
B=sorted([list(map(int,input().split())) for i in range(N)])
d={}
for i in range(N):
    for j in range(i+1,N):
        x=(B[j][0]-B[i][0],B[j][1]-B[i][1])
        if x in d:
            d[x]+=1
        else:
            d[x]=1
if N==1:
    print(1)
else:
    print(N-max(d.values()))

Solution (Python):
N = int(input())
x, y = (
    zip(*(map(int, input().split()) for _ in range(N))) if N else
    ((), ())
)

class UnionFindTree:
    def __init__(self, n):
        self.p = [i for i in range(n + 1)]
        self.r = [0 for _ in range(n + 1)]

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

    def union(self, x, y):
        px = self.find(x)
        py = self.find(y)
        if px != py:
            if self.r[px] < self.r[py]:
                self.p[px] = py
            else:
                self.p[py] = px
                if self.r[px] == self.r[py]:
                    self.r[px] += 1

    def same(self, x, y):
        return self.find(x) == self.find(y)


ans = 10**10

for i in range(N):
    for j in range(N):
        p, q = (x[i] - x[j], y[i] - y[j])
        uft = UnionFindTree(N)
        for u in range(N - 1):
            for v in range(u + 1, N):
                if (x[u] - x[v], y[u] - y[v]) == (p, q) or (x[u] - x[v], y[u] - y[v]) == (-p, -q):
                    uft.union(u, v)
        ans = min(ans, len({uft.find(z) for z in range(N)}))

print(ans)

Solution (Python):
import collections
n = int(input())
xy =[]
for i in range(n):
    x,y = map(int,input().split())
    xy.append((x,y))
xy2 = xy[:]
c = collections.Counter()
for x,y in xy:
    for w,z in xy2:
        c[(x-w,y-z)] +=1
if n==1:
    print(1)            
else:    
    print(n-c.most_common(2)[1][1])

Solution (Python):
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)

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




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



if __name__ == "__main__":
    main()

Solution (Python):
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())

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):










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

Solution (Python):
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)

Solution (Python):
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])

Solution (Python):
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)

Solution (Python):


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

Solution (Python):
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()

Solution (Python):
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)

Solution (Python):
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()))

Solution (Python):
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()))

Solution (Python):
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()))

Solution (Python):
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)

Solution (Python):
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])

Solution (Python):
from itertools import combinations
from collections import Counter

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

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

X.sort()
diff = []
for i, j in combinations(range(N), 2):
    diff.append((X[i][0] - X[j][0], X[i][1] - X[j][1]))
print(N - Counter(diff).most_common()[0][1])

Solution (Python):
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)

Solution (Python):
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()

Solution (Python):
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()