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



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

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


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)

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

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

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

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

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

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

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

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

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

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

print(N-max_count)

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

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

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

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

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

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

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

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

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

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

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

Solution (Python):
import sys

n = int(input())
balls = []

for line in sys.stdin:
    x, y = map(int, line.split())
    balls.append((x, y))

balls.sort()
ans = 0
for i in range(n - 1):
    x1, y1 = balls[i]
    for j in range(i + 1, n):
        x2, y2 = balls[j]
        p, q = x2 - x1, y2 - y1
        tmp = 0
        for x, y in balls:
            if (x - p, y - q) in balls:
                tmp += 1
        ans = max(ans, tmp)
print(n - ans)

Solution (Python):

import sys

input=sys.stdin.readline
mii=lambda:map(int,input().split())

n=int(input())

p=[list(mii()) for _ in range(n)]

d={}
for a in p:
    for b in p:
        if a==b: continue
        c=(b[0]-a[0],b[1]-a[1])
        if c in d:
            d[c]+=1
        else:
            d[c]=1

best=0
for i,j in d.items():
    best=max(best,j)

print(n-best)