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:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left, bisect_right
from copy import copy
inf=float('inf')
mod = 10**9+7
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():

    N = I()
    XY = LLIN(N)
    dic = defaultdict(lambda :-1)
    for i, (x, y) in enumerate(XY):
        dic[(x, y)] = i
    
        

    # UnionFind
    class UnionFind():
        def __init__(self, n):
            self.nodes=[-1] * n  # nodes[x]: 負なら、絶対値が木の要素数

        def get_root(self, x):
            # nodes[x]が負ならxが根
            if self.nodes[x] < 0:
                return x
            # 根に直接つなぎ直しつつ、親を再帰的に探す
            else:
                self.nodes[x]=self.get_root(self.nodes[x])
                return self.nodes[x]

        def unite(self, x, y):
            root_x=self.get_root(x)
            root_y=self.get_root(y)
            # 根が同じなら変わらない
            # if root_x == root_y:
            # pass
            if root_x != root_y:
                # 大きい木の方につないだほうが計算量が減る
                if self.nodes[root_x] < self.nodes[root_y]:
                    big_root=root_x
                    small_root=root_y
                else:
                    small_root=root_x
                    big_root=root_y
                self.nodes[big_root] += self.nodes[small_root]
                self.nodes[small_root]=big_root

    if N == 1:
        print(1)
        exit()
    ans = inf
    for i in range(N):
        for j in range(N):
            if i == j:
                continue
            p = XY[i][0] - XY[j][0]
            q = XY[i][1] - XY[j][1]
            uf = UnionFind(N)
            mini_ans = 0
            for (x, y) in XY:
                if dic[(x - p, y - q)] != -1:
                    uf.unite(dic[(x, y)], dic[(x - p, y - q)])
                if dic[(x + p, y + q)] != -1:
                    uf.unite(dic[(x, y)], dic[(x + p, y + q)])
            for i in range(N):
                if uf.nodes[i] < 0:
                    mini_ans += 1
            ans = min(mini_ans, ans)
    print(ans)
    """pre_exist = set()
    pre_exist.add((XY[i][0], XY[i][1]))
    mini_ans = 1
    for (x, y) in XY:
        found = False
        for (px, py) in pre_exist.copy():
            #print(pre_exist,x,y,px,py,mini_ans,"#",p,q)
            if (x, y) == (px, py):
                found = True
                continue
            dx = px - x
            dy = py - y
            if (dx-p==0 and dy-q==0) or (dx+p==0 and dy+q==0):
                found = True
                break
        pre_exist.add((x,y))
        if not found:
            mini_ans += 1"""
                        
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7

def LI(): return list(map(int,input().split()))
def I(): return int(input())
def LS(): return input().split()
def S(): return input()

def main():
  n=I()
  l=[]

  for i in range(n):
    l.append(LI())

  if n==1:
    return 1

  l2=[]
  for i in range(n):
    l3=[]
    for j in range(n):
      if i!=j:
        l3.append([l[j][0]-l[i][0],l[j][1]-l[i][1]])
    l2.append(l3)

  mx=0
  for i in range(n):
    _x=l2[i]

    for x in _x:
      sm=0
      for j in range(n):
        if i!=j:
          _y=l2[j]
          for y in _y:
            if x==y:
              sm+=1
      mx=max(mx,sm)

  return n-mx-1

print(main())

Submission status: Accepted

Solution code:
from collections import defaultdict
from operator import sub

def main():
    N = int(input())
    balls = [tuple(map(int,input().split())) for _ in range(N)]
    d = defaultdict(int)
    for i in range(N):
        for j in range(N):
            if i == j:
                continue
            d[tuple(map(sub, balls[i], balls[j]))] += 1
    try:
        mmax = N - max(d.values(), default=0)
        print(mmax)
    except ValueError:
        print(100)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

if n == 1:
    print(1)
    exit()
dic = {}
for x1,y1 in xy:
    for x2,y2 in xy:
        if x1 == x2 and y1 == y2:
            continue
        dx = x2 - x1
        dy = y2 - y1
        key = "{},{}".format(dx,dy)
        if key in dic:
            dic[key] += 1
        else:
            dic[key] = 1

for k, v in sorted(dic.items(), key=lambda x: -x[1]):
    print(n-v)
    break

Submission status: Accepted

Solution code:
N=int(input())
x=[]
y=[]
if N==1:
    print(1)
    quit()
xy=[]
for i in range(N):
    X,Y=map(int,input().split())
    x.append(X)
    y.append(Y)
    xy.append((X,Y))
c=[]
for i in range(N):
    for j in range(i+1,N):
        c.append((x[i]-x[j],y[i]-y[j]))
        c.append((x[j]-x[i],y[j]-y[i]))
ans=100
for p,q in c:
    s=0
    for i in range(N):
        if (x[i]-p,y[i]-q) in xy:
            pass
        else:
            s+=1
    ans=min(ans,s)
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter, defaultdict
import sys
N = int(input())
x = []
for i in range(N):
    a, b = map(int, input().split())
    x.append([a, b])
if N == 1:
    print(1)
    sys.exit()
x.sort()
cost = []
for i, y in enumerate(x):
    for j, z in enumerate(x):
        if i == j:
            continue
        else:
            num = 0
            a = z[0]-y[0]
            b = z[1]-y[1]
            for w in x:
                c = w[0]
                d = w[1]
                if [a+c, b+d] in x:
                    num += 1
            cost.append(N-num)
print(min(cost))

Submission status: Accepted

Solution code:
#!/usr/bin/python3

from itertools import permutations
from collections import Counter

def main():
  n = int(input())
  x = []
  y = []

  if n == 1:
    print(1)
    return

  for i in range(n):
    x_tmp, y_tmp = map(int, input().split(' '))
    x.append(x_tmp)
    y.append(y_tmp)

  cnt = Counter()

  for i, j in permutations(range(n), 2):
    dist = (x[i] - x[j], y[i]- y[j])
    cnt[dist] += 1

  dist, c = cnt.most_common(1)[0]
  print(n - c)

if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
from collections import Counter
import itertools

N = int(input())
xy = [list(map(int, input().split())) for i in range(N)]
xy.sort()
if N == 1:
        print(1)
        exit()

ptn=list(itertools.combinations(xy,2))
pq=[]
for idx,val in enumerate(ptn):
        if val[1][0]-val[0][0] <= 0 and val[1][1]-val[0][1] <= 0:
                pq.append(str(abs(val[1][0]-val[0][0])) + 'x' + str(abs(val[1][1]-val[0][1])))
        else:
                pq.append(str(val[1][0]-val[0][0]) + 'x' + str(val[1][1]-val[0][1]))

cpq = Counter(pq)

# pqans=cpq.most_common(1)[0][0]
redsc=cpq.most_common(1)[0][1]

# p,q = map(int,pqans.split('x'))
print(N-redsc)

Submission status: Accepted

Solution code:
from collections import Counter
n=int(input())
x=[]
y=[]
for i in range(n):
  a,b=map(int,input().split())
  x.append(a)
  y.append(b)
cost=n
list=[]
for i in range(n):
  for j in range(n):
    if i != j:
      list.append([x[i]-x[j],y[i]-y[j]])

if n ==1:
  print(cost)
else:
  c=Counter(map(tuple, list))
  mode=c.most_common(1)
  print(cost-mode[0][1])

Submission status: Accepted

Solution code:
from itertools import combinations

N = int(input())
P = []
for _ in range(N):
    x, y = map(int, input().split())
    P.append((x, y))

memo = dict()
for (a, b) in combinations(P, 2):
    p, q = a[0] - b[0], a[1] - b[1]
    if p < 0:
        p, q = -p, -q
    elif p == 0 and q < 0:
        q = -q
    if (p, q) in memo:
        memo[(p, q)] += 1
    else:
        memo[(p, q)] = 1

print(N - max(memo.values()) if N > 1 else 1)

Submission status: Accepted

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


sabun = []
for i in range(N):
    for j in range(N):
        if i == j:
            continue
        else:
            p = xy[i][0] - xy[j][0]
            q = xy[i][1] - xy[j][1]
            sabun.append([p,q])
count = [sabun.count(i)+sabun.count([-i[0],-i[1]]) for i in sabun]

if count == []:
    print("1")
else:
    print(int(N-(max(count))/2))

Submission status: Accepted

Solution code:
n = int(input())

if n == 1:
  print(1)
else:
  #print("n=",n)
  xy_s = [[int(v) for v in input().split()] for _ in range(n)]
  v = {}
  for i in range(n):
    for j in range(n):
      if i == j:
        continue
      dx = xy_s[i][0] - xy_s[j][0]
      dy = xy_s[i][1] - xy_s[j][1]
      pq = (dx, dy)
      if pq in v:
        v[pq] += 1
      else:
        v[pq] = 1
    
      #v.append([xy_s[i][0] - xy_s[j][0] , xy_s[i][1] - xy_s[j][1]])
  #print(v)
  counts = v.values()
  m = max(counts)
  ans = n - m
  #print("n={}, m={}, ans={}".format(n, m, ans))
  print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import deque
from collections import defaultdict
import math
import copy
input = sys.stdin.readline
sys.setrecursionlimit(20000000)
n = int(input())
a = set()
for i in range(n):
        x,y = map(int,input().split())
        a.add((x,y))
b = list(a)
c = copy.deepcopy(b)
c.sort()
ans = 500
for i in range(n):
        for j in range(n):
                a = copy.deepcopy(c)
                x = b[i][0] - b[j][0]
                y = b[i][1] - b[j][1]
                tmp = 0
                while a:
                        f,g = a.pop()
                        while (f-x,g-y) in a:
                                a.remove((f-x,g-y))
                                f = f-x
                                g = g-y
                        tmp += 1
                ans = min(ans,tmp)
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)

def main():
	n = int(input())
	xy = []
	for _ in range(n):
		xy +=[list(map(int,input().split()))]
	xy.sort(key=lambda x:(x[0],x[1]))
	dic = {}
	for i in range(n):
		for j in range(i+1,n):
			x,y = xy[i][0] - xy[j][0], xy[i][1] - xy[j][1]
			if x*y == 0:
				temp = "{}.{}".format(x,y)
			else:
				k = "" if x*y > 0 else "-"
				x = abs(x)
				y = abs(y)
				temp = "{}.{}{}".format(x,k,y)
			if temp in dic:
				dic[temp] = dic[temp]+1
			else:
				dic[temp] = 1
	mans = 0
	for i in dic:
		mans = max(mans, dic[i])
	ans = n - mans
	print(ans)
	return

main()

Submission status: Accepted

Solution code:
N=int(input())
s=[list(map(int,input().split())) for i in range(N)]
ans=N
for i in range(N):
    for j in range(i):
        cnt=N
        p=s[i][0]-s[j][0]
        q=s[i][1]-s[j][1]
        for k in range(N):
            if [s[k][0]+p,s[k][1]+q] in s:
                cnt-=1
        ans=min(ans,cnt)

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
balls = []
for _ in range(N):
	x, y = map(int, input().split())
	balls.append((x, y))

counts = {}
for i in range(N):
	x1, y1 = balls[i]
	for j in range(i):
		x2, y2 = balls[j]
		p = x2 - x1
		q = y2 - y1
		if p < 0 or (p == 0 and q < 0):
			p = -p
			q = -q
		diff = (p, q)
		if diff in counts:
			s, l = counts[diff]
			s.add(i)
			s.add(j)
			l.append((i, j))
		else:
			counts[diff] = ({i, j}, [(i, j)])


min_cost = N
min_pq = None
for pq in counts:
	s, l = counts[pq]
	n = len(s)
	c = len(l)
	cost = (N - n) + n - (c + 1) + 1
	if cost < min_cost:
		min_cost = cost
		min_pq = pq
print(min_cost)

Submission status: Accepted

Solution code:
from fractions import Fraction
from collections import defaultdict
N = int(input())
XY = [list(map(int, input().split())) for _ in range(N)]

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


def calc(p,q):
    result = defaultdict(set)
    for x,y in XY:
        result[x].add(y)

    count = 0
    for x in result.keys():
        for y in result[x]:
            if x-p in result and y-q in result[x-p]:
                continue
            count +=1

    return count


ans = 5000

for i in range(N-1):
    for j in range(i+1,N):
        p = XY[i][0] - XY[j][0]
        q = XY[i][1] - XY[j][1]
        # print(p,q,calc(p,q))
        ans = min(ans,calc(p,q))

if ans == 5000:
    raise ValueError
print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations
import sys

N = int(input()) 
X_Y = [0] * N

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


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

combo = list(combinations(X_Y, 2))
diff = [0] * (len(combo))

dict_diff = {}

for i, item in enumerate(combo):
    x_dif = item[0][0] - item[1][0]
    y_dif = item[0][1] - item[1][1]
    diff[i] = [x_dif, y_dif]
    if str(diff[i]) in dict_diff:
        dict_diff[str(diff[i])] += 1
    else:
        dict_diff[str(diff[i])] = 1
    
    x_dif = item[1][0] - item[0][0]
    y_dif = item[1][1] - item[0][1]
    diff[i] = [x_dif, y_dif]
    if str(diff[i]) in dict_diff:
        dict_diff[str(diff[i])] += 1
    else:
        dict_diff[str(diff[i])] = 1

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

Submission status: Accepted

Solution code:
from collections import Counter
n=int(input())
balls=[]
distance=[]
if n==1:
  print(1)
else:
  for i in range(n):
    balls.append(list(map(int,input().split())))
    balls.sort(key=lambda x:x[0]+x[1])
  for i in range(n-1):
    for j in range(i+1,n):
      distance.append(str(balls[i][0]-balls[j][0])+","+str(balls[i][1]-balls[j][1]))
  d=Counter(distance)
  print(n-d.most_common()[0][1])

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
 
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

import collections

n = ni()

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

balls = []
dis = []

for i in range(n):
    x,y = na()
    for b in balls:
        k = '_1' if (b[0]-x)*(b[1]-y) > 0 else '_0'
        dis.append(str(abs(b[0]-x))+'_'+str(abs(b[1]-y))+k)
    balls.append([x,y])

c = collections.Counter(dis)
m = c.most_common()

if len(m) == 1:
    print(1)
    exit()

u = m[0][1]

print(n-u)

Submission status: Accepted

Solution code:
from collections import Counter


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

vector = [0] * ((N * (N - 1)) // 2)
cnt = 0
for i in range(N):
    for j in range(i + 1, N):
        x = ball[i][0] - ball[j][0]
        y = ball[i][1] - ball[j][1]
        if x < 0:
            x, y = -x, -y
        elif x == 0:
            if y < 0:
                y = -y
        vector[cnt] = x * (10 ** 10) + y
        cnt += 1
C = Counter(vector)
if N == 1:
    print(1)
else:
    print(N - C.most_common()[0][1])

Submission status: Accepted

Solution code:
from collections import Counter
N = int(input())
if N == 1:
	print(1)
else:
	l = [[int(arr) for arr in input().split()] for i in range(N)]
	l.sort()
	tmp = [[b - a for a, b in zip(l[j],l[k])] for j in range(N-1) for k in range(j+1,N)]
	c = Counter(map(tuple, tmp))
	m = c.most_common(1)[0][1]
	print(N-m)

Submission status: Accepted

Solution code:
import sys
from itertools import combinations
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
MOD = 1000000007
def POW(x, y): return pow(x, y, MOD)
def INV(x, m=MOD): return pow(x, m - 2, m)
def DIV(x, y, m=MOD): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())

class UnionFindTree:
    def __init__(self, n):
        self.nodes = list(range(n+1))
    def find(self, x):
        if self.nodes[x] == x:
            return x
        parent = self.find(self.nodes[x])
        self.nodes[x] = parent
        return parent
    def unite(self, a, b):
        a = self.find(a)
        b = self.find(b)
        if a == b:
            return
        self.nodes[a] = self.nodes[b]
    def is_same(self, a, b):
        return self.find(a) == self.find(b)


N=II()
INL=[tuple(LI()) for i in range(N)]
INL.sort()

if N == 1:
    print(1)
    exit()
elif N == 2:
    print(1)
    exit()
elif N > 2:
    res = INTMAX
    for ptr1, ptr2 in combinations(INL,2):
        union = UnionFindTree(N)
        dx, dy = ptr2[0]-ptr1[0], ptr2[1]-ptr1[1] 
        for i in range(N):
            for j in range(i, N):
                if INL[i][0] + dx == INL[j][0] and INL[i][1]+dy == INL[j][1]:
                    union.unite(i,j)
        st = set()
        for i in range(N):
            st.add(union.find(i))
        res = min(res,len(st))
    print(res)

Submission status: Accepted

Solution code:
n=int(input())
XY=[tuple(map(int,input().split())) for _ in range(n)]
XY.sort()
PQset=set()
for i in range(n):
    for j in range(i+1,n):
        p=XY[j][0]-XY[i][0]
        q=XY[j][1]-XY[i][1]
        if p!=0 or q!=0:
            PQset.add((p,q))
ans=n
for p,q in PQset:
    cost=1
    for i in range(1,n):
        x,y=XY[i]
        if (x-p,y-q) not in XY:
            cost+=1
    ans=min(cost,ans)
print(ans)

Submission status: Accepted

Solution code:
import sys
from itertools import combinations
from collections import defaultdict

sys.setrecursionlimit(100000000)

class UnionFind(object):
    def __init__(self, N):
        self._parent = list(range(N))
        self.__num_components = [1] * N

    def root(self, x):
        if self._parent[x] == x:
            return x
        else:
            # root abbreviation
            self._parent[x] = self.root(self._parent[x])
            return self._parent[x]

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

    def num_connected(self, x):
        return self.__num_components[self.root(x)]

    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if (x == y):
            return
        rank_x = self.__num_components[x]
        rank_y = self.__num_components[y]
        if rank_x < rank_y:
            self._parent[x] = y
            self.__num_components[y] += rank_x
        else:
            self._parent[y] = x
            self.__num_components[x] += rank_y
        return


fin = sys.stdin.readline

N = int(fin())
coordinates = [[int(elem) for elem in fin().split()] + [i] for i in range(N)]

# p, qのペアを計算
all_dists = defaultdict(list)
for each_pair in combinations(coordinates, 2):
    each_p = each_pair[0][0]-each_pair[1][0]
    each_q = each_pair[0][1] - each_pair[1][1]
    if each_p < 0:
        each_p = -each_p
        each_q = -each_q
    if each_p * each_q == 0:
        each_p = abs(each_p)
        each_q = abs(each_q)
    each_pq = (each_p, each_q)
    all_dists[each_pq].append([each_pair[0][2], each_pair[1][2]])

# 適当にスタート，探索を行う
count_list = []
for each_pq in all_dists:
    uf = UnionFind(N)
    for x, y in all_dists[each_pq]:
        uf.unite(x, y)
    num_distinct_components = 0
    for i in range(N):
        if uf.root(i) == i:
            num_distinct_components += 1
    count_list.append(num_distinct_components)

if len(count_list) == 0:
    print(1)
else:
    print(max(min(count_list), 1))

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    n, k = LI()
    a = n - k
    if k == 1:
        print(0)
        return
    print(a)
    return

#B
def B():
    n = II()
    xy = LIR(n)
    if n == 1:
        print(1)
        return
    ans = inf
    for i in range(n):
        for k in range(n):
            if i != k:
                b = 1
                check = []
                check.append((i,k))
                p = xy[i][0] - xy[k][0]
                q = xy[i][1] - xy[k][1]
                for l in range(n):
                    for m in range(n):
                        if not((l,m) in check) and p == xy[l][0] - xy[m][0] and q == xy[l][1] - xy[m][1]:
                            b += 1
                            check.append((l, m))
                ans = min(ans, n-b)
    print(ans)

    return

#C
def C():
    m = II()
    a = LI()
    a.sort()
    check = [0] * m
    anslis = []
    ans = 0
    if m % 2:
        ans += a[m // 2]
        for i in range(m//2):
            anslis.append((a[i], a[-1 - i]))
            anslis.append((ans,-a[-1 - i]+a[i]))
            ans += a[-1 - i] - a[i]
    else:
        ans += a[m//2] - a[m//2-1]
        for i in range(m//2-1):
            anslis.append((a[i], a[-1 - i]))
            anslis.append((ans,-a[-1 - i]+a[i]))
            ans += a[-1 - i] - a[i]
    print(ans)
    for a, b in anslis:
        print(a,b)
    return

#D
def D():
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == '__main__':
    B()

Submission status: Accepted

Solution code:
from itertools import combinations as comb

N = int(input())
xy = []
xy_ap = xy.append

for i in range(N):
    xy_ap(list(map(int, input().split())))

ls = [i for i in range(N)]

result = []

xy.sort()

for i, j in comb(ls, 2):
    result.append([xy[i][0] - xy[j][0], xy[i][1] - xy[j][1]])

cnt = 0
for i in range(len(result)):
    if result.count(result[i]) >= cnt:
        cnt = result.count(result[i])

print(N - cnt)

Submission status: Accepted

Solution code:
N = int(input())
XY = {}
for i in range(N):
    x,y = map(int,input().split())
    XY[(x,y)] = 1
dis = {}

ans = N

for x,y in XY.keys():
    for xx,yy in XY.keys():
        if x != xx or y != yy:
            temp = (xx-x,yy-y)
            if not(temp in dis):
                dis[temp] = 1

for p,q in dis:
    test = 0
    copy = XY.copy()
    for x,y in copy:
            if (x+p,y+q) in copy.keys():
                test += 1
    if N - test < ans:
        ans = N - test
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
X = []
for i in range(N):
    xi,yi = map(int,input().split())
    X.append([xi,yi])

L = []
d = {}
for i in range(N):
    for j in range(N):
        if i == j:
            continue
    
        x,y = X[i][0]-X[j][0],X[i][1]-X[j][1]
        #L.append([x,y])
        if not x in d:
            d[x] = {}
        if not y in d[x]:
            d[x][y] = 1
        else:
            d[x][y] += 1
m = 0
for k in list(d.keys()):
    for kk in list(d[k].keys()):
        m = max(m,d[k][kk])
print(N-m)

Submission status: Accepted

Solution code:
N = int(input())

XY = []
for _ in range(N):
    x, y = map(int, input().split())
    XY.append((x,y))
    
from collections import defaultdict

dd = defaultdict(lambda:defaultdict(bool))

X = sorted(XY)

for x,y in XY:
    dd[x][y] = True

max_count = 0
for i, (x0, y0) in enumerate(X):
    for x1, y1 in X[i+1:]:
        diff_x, diff_y = (x1-x0, y1-y0)
        counter = 0
        for x, y in X:
            if dd[x+diff_x][y+diff_y]:
                counter += 1
        max_count = max(max_count, counter)
#print(max_count)

ans = N - max_count
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
import collections

N=int(input())
xlist=[]
ylist=[]
for i in range(N):
  x, y = map(int, stdin.readline().rstrip().split())
  xlist.append(x)
  ylist.append(y)

tupleList=[]
for i in range(N):
  for j in range(N):
    if i != j:
      tupleList.append((xlist[i] - xlist[j], ylist[i] - ylist[j]))

c = collections.Counter(tupleList)

maxNum=0
for val in c.values():
  maxNum = max(maxNum, val)

print(N-maxNum)

Submission status: Accepted

Solution code:
N = int(input())
X,Y = [],[]
for _ in range(N):
    x,y = map(int,input().split())
    X.append(x)
    Y.append(y)
inf = 10**10

d = {}
for i in range(N):
    for j in range(i+1,N):
        if X[i] > X[j]:
            r,l = i,j
        elif X[i] == X[j]:
            if Y[i] > Y[j]:
                r,l = i,j
            else:
                r,l = j,i
        else:
            r,l = j,i
        k = (X[r]-X[l],Y[r]-Y[l])
        if k in d.keys():
            d[k] += 1
        else:
            d[k] = 1

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

Submission status: Accepted

Solution code:
import collections
import copy
import sys
N = int(input())

cost = 0
diff_list = []
x_y_list = []

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

for n in range(N):
    x, y = map(int, input().split())
    x_y_list.append((x, y))
    cost += 1

x_y_list_copy = copy.copy(x_y_list)

for n in range(N):
    x_y = x_y_list.pop()
    x = x_y[0]
    y = x_y[1]
    for tmp_x, tmp_y in x_y_list:
        diff_list.append((x - tmp_x, y - tmp_y))

for n in range(N):
    x_y = x_y_list_copy.pop(0)
    x = x_y[0]
    y = x_y[1]
    for tmp_x, tmp_y in x_y_list_copy:
        diff_list.append((x - tmp_x, y - tmp_y))

counter = collections.Counter(diff_list)
print(cost - max(counter.values()))

Submission status: Accepted

Solution code:
import sys

N = int(input())

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

coor = []
for i in range(N):
    (x,y) = (int(i) for i in input().split())
    coor.append((x,y))
    
diffs = []
for i in range(N-1):
    for j in range(i+1, N):
        diffs.append((coor[j][0]-coor[i][0], coor[j][1]-coor[i][1]))
        diffs.append((coor[i][0]-coor[j][0], coor[i][1]-coor[j][1]))

m = 1

for i in range(N*(N-1)):
    times = 0
    for j in range(N*(N-1)):
        if diffs[i] == diffs[j]:
            times += 1
    if times > m:
        m = times

ans = N - m   

print(ans)

Submission status: Accepted

Solution code:
N = list(map(int, input().split()))
d = {0:0}

pos=[]
for x in range(N[0]):
    a = list(map(int, input().split()))
    for y in pos:
        key = (a[0]-y[0])*(10**11)+(a[1]-y[1])
        if key<0:
            key=-key
        if key not in d.keys():
            d[key] = 0
        d[key] += 1
    pos.append(a)
    
print(N[0]-max(d.values()))

Submission status: Accepted

Solution code:
# 2
import sys
sys.setrecursionlimit(10000)
args = sys.stdin.readlines()
N = int(args[0])
xy_list = [[int(y) for y in x.split(' ')] for x in args[1:]]

from collections import Counter, defaultdict

delta_dict = defaultdict(int)

if N == 1:
    print(1)
    exit()
for i in range(N):
    for j in range(N):
        if i != j:
            delta_dict[(xy_list[i][0] - xy_list[j][0], xy_list[i][1] - xy_list[j][1])] += 1
    
print(N - Counter(delta_dict).most_common()[0][1])

Submission status: Accepted

Solution code:
from sys import stdin
from collections import Counter
N = int(stdin.readline().rstrip())
data = [0] * N
if N != 1:
    for _ in range(N):
        A,B = [int(x) for x in stdin.readline().rstrip().split()]
        data[_] = (A,B)
    data=sorted(data)
    max_value = 0
    diff = []
    for j in range(0,N-1):
        for i in range(j+1,N):
            diff.append((data[j][0]-data[i][0],data[j][1]-data[i][1]))
    d=Counter(diff)
        #max_value = max(max_value,max(d.values()))
    print(N-max(d.values()))
else:
    print(1)

Submission status: Accepted

Solution code:
N = int(input())
items = []
for i in range(N):
    items.append(tuple(map(int, input().split())))


ans = 0
res = []
for i in range(N):
    for j in range(N):
        if i == j:
            continue
        x1, y1 = items[i]
        x2, y2 = items[j]
        res.append((x1-x2, y1 -y2))

tar = []
for i in range(len(res)):
    x, y = res[i]
    cnt = 0
    for j in range(len(res)):
        if i == j:
            continue
        if x == res[j][0] and y == res[j][1]:
            cnt += 1
    if ans <= cnt:
        ans = cnt
        tar.append((x, y))


ans2 = 0
tar = list(set(tar))
for t in tar:
    cnt2 = 0
    for i in range(N):
        x, y = items[i]
        for j in range(N):
            if i == j:
                continue
            x2, y2 = items[j]
            if x - t[0] == x2 and y - t[1] == y2:
                cnt2 += 1
                break

    ans2 = max(ans2, cnt2)

print(N - ans2)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

n = int(input())
xy = [list(map(int, input().split())) for i in range(n)]
if len(xy) == 1:
    print(1)
    exit()

xy.sort()
xy = xy[::-1]
aaa = []
for i in range(len(xy)-1):
    for j in range(i+1, len(xy)):
        a, b = xy[i]
        c, d = xy[j]
        aaa.append(str(a-c)+str(b-d))

# import itertools
#
# # itertools.permutations(xy, 2)
#
# aaa = []
# for i in list(itertools.combinations(xy, 2)):
#     a, b, c, d = sum(i, [])
#     aaa.append([str(a-c)+str(b-d)])
#     # print(a,b,c,d)
# # print(aaa)
# aaa = sum(aaa, [])
# print(aaa)
import collections
bbb = collections.Counter(aaa)
# print(bbb.most_common())
print(n-bbb.most_common()[0][1])