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
ri = lambda: int(input())
#rl = lambda: [int(x) if x.isdecimal() else x for x in input().split()]
#rl = lambda: list(input().split()))
rl = lambda: map(int,input().split())
rr = lambda N: [list(l) for l in zip(*[rl() for _ in range(N)])]
YN = lambda b: print('YES') if b else print('NO')
yn = lambda b: print('Yes') if b else print('No')
OE = lambda x: print('Odd') if x%2 else print('Even')
INF = 10**18
MOD = 10**9+7

N = ri()
XY = []
for i in range(N):
    x,y=rl()
    XY.append((x,y))
XY.sort()
XYD = []
for i in range(N):
    x,y = XY[i]
    ret = []
    for j in range(i+1,N):
        ret.append((XY[j][0] - x, XY[j][1] - y))
    XYD.extend(ret)

import collections
c = collections.Counter(XYD).most_common()
if N == 1:
    print(1)
else:
    print(N-c[0][1])

Submission status: Accepted

Solution code:
import numpy as np
from collections import defaultdict
dic = defaultdict(int)

n = int(input())
lis = list(list(map(int, input().split())) for _ in range(n))

ans = n
ant = 0

arrx = np.zeros((n, n))
arry = np.zeros((n, n))

for i in range(n):
    for j in range(n):

        arrx[i][j] = lis[i][0] - lis[j][0]
        arry[i][j] = lis[i][1] - lis[j][1]

        dic[(arrx[i][j], arry[i][j])] += 1

        if i != j:
            if ant < dic[(arrx[i][j], arry[i][j])]:
                ant = dic[(arrx[i][j], arry[i][j])]

ans -= ant

print(ans)

Submission status: Accepted

Solution code:
import itertools

n = int(input())
balls = {i: list(map(int, input().split())) for i in range(n)}
dist_cnt = {}

for i, j in itertools.combinations(range(n), 2):
    x = balls[j][0] - balls[i][0]
    y = balls[j][1] - balls[i][1]
    
    if not x in dist_cnt.keys():
        dist_cnt[x] = {}
    if not x*(-1) in dist_cnt.keys():
        dist_cnt[x*(-1)] = {}
    if not y in dist_cnt[x].keys():
        dist_cnt[x][y] = 0
    if not y*(-1) in dist_cnt[x*(-1)].keys():
        dist_cnt[x*(-1)][y*(-1)] = 0

    dist_cnt[x][y] += 1
    dist_cnt[x*(-1)][y*(-1)] += 1
        

cnt = 0
for x, v in dist_cnt.items():
    cand = max(v.values())
    if cand > cnt:
            cnt  = cand
            
print(n - cnt)

Submission status: Accepted

Solution code:
n = int(input())

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

lst = []

for i in range(n):
    for j in range(i+1,n):
        if a[j][0]-a[i][0] < 0:
            lst.append([a[i][0]-a[j][0], a[i][1]-a[j][1]])
        if a[j][0]-a[i][0] == 0:
            lst.append([a[i][0]-a[j][0], abs(a[i][1]-a[j][1])])
        else:
            lst.append([a[j][0]-a[i][0], a[j][1]-a[i][1]])

if n ==1:
    print(1)
else:
    x = 0
    for i in range(len(lst)):
        c = 1
        for j in range(i+1,len(lst)):
            if lst[i] == lst[j]:
                c += 1
        x = max(x,c)
    print(n-x)

Submission status: Accepted

Solution code:
n = int(input())
a = [tuple(map(int, input().split())) for i in range(n)]
t = set(a)
assert len(t) == len(a)
minans = 1000000000000
for i in range(n):
    for j in range(i + 1, n):
        r = t.copy()
        p = a[i][0] - a[j][0]
        q = a[i][1] - a[j][1]
        curans = 0
        while r:
            curans += 1
            m = r.pop()
            z = m
            while (m[0] + p, m[1] + q) in r:
                m = (m[0] + p, m[1] + q)
                r.remove(m)
            m = z
            while (m[0] - p, m[1] - q) in r:
                m = (m[0] - p, m[1] - q)
                r.remove(m)
        minans = min(minans, curans)
if minans == 1000000000000:
    print(1)
else:
    print(minans)

Submission status: Accepted

Solution code:
from collections import defaultdict
N = int(input())
p = defaultdict(int)
balls = [list(map(int, input().split())) for i in range(N)]

c = 0
if len(balls) <= 2:
    print(1)
else:
    for i in balls:
        for j in balls:
            c += 1
            if i == j:
                continue
            p[(j[0]-i[0]), j[1]-i[1]] += 1
    print(N-max(p.values()))

Submission status: Accepted

Solution code:
N=int(input())
x=['']*N
y=['']*N
dic={(0,0):0}
for i in range(N):
    x[i],y[i]=map(int,input().split())

for i in range(N):
    for j in range(N):
        if i==j:
            continue
        else:
            p=y[j]-y[i]
            q=x[j]-x[i]
            if (p,q) in dic.keys():
                dic[(p,q)] += 1
            else:
                dic[(p,q)] = 1

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

Submission status: Accepted

Solution code:
from collections import Counter
n = int(input())
a = [tuple(map(int, input().split())) for _ in range(n)]
c = Counter((y[0] - x[0], y[1] - x[1]) for x in a for y in a if x < y)
print(n - max(c.values(), default=0))

Submission status: Accepted

Solution code:
n=int(input())

pts=[]
for i in range(n):
    pts.append(tuple(map(int,input().split())))

diffs={}
for i in range(n-1):
    for j in range(i+1,n):
        dx=pts[i][0]-pts[j][0]
        dy=pts[i][1]-pts[j][1]
        if dx<0 :
            dx=-dx
            dy=-dy
        elif dx==0 and dy<0:
            dy=-dy
        key="{},{}".format(dx,dy)
        if key in diffs:
            diffs[key]+=1
        else:
            diffs[key]=1

max=0
maxkey=""
for k,v in diffs.items():
    if v>max:
        max=v
        maxkey=k
        
print(n-max)

Submission status: Accepted

Solution code:
#B問題
N = int(input())
XY = [list(map(int,input().split())) for i in range(N)]
edges = []
for i in range(N):
    x1,y1 = XY[i][0],XY[i][1]
    for j in range(N-i-1):
        J = i+j+1
        x2,y2 = XY[J][0],XY[J][1]
        dx = x2-x1
        dy = y2-y1
        if dx <= 0:
            if dx == 0:
                if dy < 0:
                    dy = -dy
            else:
                dx = -dx
                dy = -dy
        edges.append([dx,dy])

listcount = []
count = []
if N == 1:
    listcount.append([0,0])
    count.append(1)

for edge in edges:
    if edge == [0,0]:
        if [0,0] not in listcount:
            listcount.append([0,0])
            count.append(1)
    elif edge in listcount:
        count[listcount.index(edge)]+=1
    else:
        listcount.append(edge)
        count.append(1)
        
most = max(count)
if N == 1:
    print(1)
else:
    print(N-most)

Submission status: Accepted

Solution code:
import sys

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

XY.sort(key=lambda x: x[0])
XY.sort(key=lambda x: x[1])

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

PQ = {}
for i in range(len(XY)):
    for j in range(len(XY)):
        pq = XY[i][0] - XY[j][0], XY[i][1] - XY[j][1]
        if pq == (0, 0):
            continue
        if pq in PQ.keys():
            PQ[pq] += 1
        else:
            PQ[pq] = 1

pq = max(PQ, key=lambda x: PQ[x])
print(N - PQ[pq])

Submission status: Accepted

Solution code:
from sys import stdin
from collections import Counter

input = stdin.readline

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

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

l = []
append = l.append
for i in range(n):
  for j in range(n):
    if not i == j:
      append((xy[j][0]-xy[i][0], xy[j][1]-xy[i][1]))
c = Counter(l)
print(n-c.most_common()[0][1])

Submission status: Accepted

Solution code:
from collections import defaultdict
from itertools import permutations
def solve():
    n = int(input())
    XY = [list(map(int, input().split())) for _ in range(n)]
    if n == 1:
        return 1
    m = defaultdict(int)
    for i, j in permutations(range(n), 2):
        m[(XY[i][0] - XY[j][0], XY[i][1] - XY[j][1])] += 1
    return n - max(m.items(), key=lambda x: x[1])[1]
print(solve())

Submission status: Accepted

Solution code:
import numpy as np
n = int(input())
if n == 1:
    print(1)
else:
    points = np.zeros((n, 2), dtype=np.int)
    for i in range(n):
        x, y = [int(x) for x in input().split()]
        points[i, 0] = x
        points[i, 1] = y

    diffs = {}
    for i in range(n):
        for j in range(n):
            if i != j:
                diff = (points[i, 0] - points[j, 0], points[i, 1] - points[j, 1])
                if diff in diffs:
                    diffs[diff] += 1
                else:
                    diffs[diff] = 1

    count = sorted(diffs.items(), key=lambda kv: kv[1])[-1][1]
    print(n-count)

Submission status: Accepted

Solution code:
def search(p,q):
  count = 0
  for i in range(n):
    for j in range(n):
      if a[i][0]-a[j][0] == p and a[i][1]-a[j][1] == q:
        count += 1
  return count
n = int(input())
a = []
for i in range(n):
  a.append(tuple(map(int,input().split())))
cc = 0
for i in range(n):
  for j in range(n):
    if i == j:
      continue
    else:
      p = a[i][0]-a[j][0]
      q = a[i][1]-a[j][1]
      cc = max(cc,search(p,q))
print(n-cc)

Submission status: Accepted

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

dist_list = []
count_list = []
for i in range(N):
    for j in range(i+1, N):
        p = x[i] - x[j]
        q = y[i] - y[j]
        for index, dist in enumerate(dist_list):
            x_dist, y_dist= dist
            if (x_dist == p and y_dist == q) or (x_dist == -p and y_dist == -q):
                count_list[index] += 1
                break
        else:
            dist_list.append([p, q])
            count_list.append(1)

if N == 1:
    print(1)
else:
    print(N - max(count_list))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000)

def intinput(): return map(int,sys.stdin.readline().split())


n=int(input())
p=[]
for _ in range(n):
    p.append(tuple(intinput()))
s={}
for x,y in p:
    for x1,y1 in p:
        if x==x1 and y==y1:
            continue
        if (x-x1,y-y1) in s:
            s[(x-x1,y-y1)]+=1
        else:
            s[(x-x1,y-y1)]=1
if n==1:
    print(1)
else:
    print(n-max(s.values()))

Submission status: Accepted

Solution code:
#!/usr/bin/env python

n = int( input() )
xy = []
for _ in range(n): xy.append( [ int(x) for x in input().strip().split() ] )
#
if n==1:
    print( 1 )
    exit()
#
xy.sort( key=lambda x: (x[0],x[1]) )
distmap = dict()
for i in range(n):
    xi,yi = xy[i]
    for j in range(i+1,n):
        xj, yj = xy[j]
        xd = xj - xi
        yd = yj - yi
        k = "{} {}".format(xd,yd)
        distmap[k]= distmap.get(k,0) + 1
#
d = max( distmap.values() )
print( n-d )

Submission status: Accepted

Solution code:
import numpy as np
import statistics
n = int(input())
x,y = [],[]
for i in range(n):
  a,b = map(int,input().split())
  x.append([a,b])
x = sorted(x, key=lambda x:(x[0],x[1]), reverse=False)
for i in range(0,n-1):
  for j in range(i+1,n):
    y.append(list(-np.array(x[i])+np.array(x[j])))
z = [y.count(i) for i in y]
if n == 1:
  print(1)
else:
  print(-max(z)+n)

Submission status: Accepted

Solution code:
n = int(input())
pos = [list(map(int, input().split())) for _ in range(n)]
d = {}
if n == 1:
  print(1)
else:
  for x, y in pos:
    for nx, ny in pos:
      dx = nx - x
      dy = ny - y
      key = (dx, dy)
      if key == (0, 0):
        continue
      if key in d:
        d[key] += 1
      else:
        d[key] = 1
  print(n - max([d[key] for key in d]))

Submission status: Accepted

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

xy.sort()
gap = []
gap2 = []

for i in range(len(xy)):
    for j in range(len(xy)):
        gap.append([xy[i][0]-xy[j][0],xy[i][1]-xy[j][1]])
     
gap2 = [i for i in gap if i != [0,0]] 
gap3=[]

for i in gap2:
    if i not in gap3:
        gap3.append(i)

m = 0

for i in gap3:
    rep = gap2.count(i)
    m = max(m,rep)

print(N-m)

Submission status: Accepted

Solution code:
import itertools
if __name__=='__main__':
    N = int(input())
    x = []
    y = []
    pq = []
    max_pq = 0
    for i in range(N):
        xi, yi = map(int, input().split())
        x.append(xi)
        y.append(yi)
    for i,j in itertools.combinations(range(N),2):
        p = x[i]-x[j]
        q = y[i]-y[j]
        if p < 0:
            p = -p
            q = -q
        elif p == 0 and q < 0:
            q = -q
        pq.append((p,q))
    for k in pq:
        max_pq = max(max_pq,pq.count(k))
    print(N-max_pq)

Submission status: Accepted

Solution code:
import sys
# input = sys.stdin.readline
inf = 10 ** 18

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

x = [xi for xi, yi in xy]
y = [yi for xi, yi in xy]

ans = inf
for i in range(N - 1):
    xi, yi = xy[i]
    for j in range(i + 1, N):
        xj, yj = xy[j]
        #
        p = xj - xi
        q = yj - yi
        #
        ans_tmp = 0
        for n, (xn, yn) in enumerate(xy):
            xm = xn - p
            ym = yn - q
            # print("##", (xm, ym))
            if [xm, ym] not in xy: ans_tmp += 1
        #
        # print("#", xy, ans_tmp)
        if ans > ans_tmp: ans = ans_tmp

if N == 1:
    print(1)
else:
    print(ans)

Submission status: Accepted

Solution code:
n=int(input())
if n==1:
  print(1)
else:
 x=[]
 y=[]
 for i in range(n):
  a,b=map(int,input().split())
  x.append(a)
  y.append(b)

 distance=[]
 for i in range(n):
  for k in range(n):
   if x[i]!=x[k] or y[i]!=y[k]:
    distance.append([x[i]-x[k],y[i]-y[k]])

 q=[]
 for i in range((n**2-n)):
  q.append(distance.count(distance[i]))

 print(n-max(q))

Submission status: Accepted

Solution code:
n = int(input())
a = sorted([list(map(int, input().split())) for _ in range(n)])
d = {}
ret = float('inf')
for i in range(n - 1):
    for j in range(i + 1, n):
        p, q = a[j][0] - a[i][0], a[j][1] - a[i][1]
        if p == 0 and q == 0:
            continue
        key = (p, q)
        d.setdefault(key, 0)
        d[key] += 1
print(n - (max(d.values()) if d  else 0))

Submission status: Accepted

Solution code:
N=int(input())
xy = [0]*N

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


ans = N

for i in range(N):
    x0 = xy[i][0]
    y0 = xy[i][1]
    # print(x0,y0)
    for j in range(i+1,N):
        ans_sub = N
        vecx = xy[j][0]-x0
        vecy = xy[j][1]-y0
        # print(vecx,vecy)
        for z in range(N):
            if [xy[z][0]+vecx,xy[z][1]+vecy] in xy:
                ans_sub -= 1
        
        if ans_sub < ans:
            ans = ans_sub

print(ans)

Submission status: Accepted

Solution code:
import sys
import collections

def input():
    return sys.stdin.readline()[:-1]

def main():
    n = int(input())
    x = [list(map(int, input().split())) for _ in range(n)]

    if n == 1:
        print(1)
    else:
        dist = [(x[j][0] - x[i][0], x[j][1] - x[i][1]) for j in range(n) for i in range(n)]
        c = collections.Counter(dist)
        ans = c.most_common()
        print(n - ans[1][1])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return int(input())
from collections import defaultdict, Counter
import bisect

sys.setrecursionlimit(10000000)

n = SI()
xy = [(0,0) for _ in range(n)]
div = defaultdict(int)
for i in range(n):
    x, y = LI()
    xy[i] = (x, y)
if n==1:
    print(1)
else:
    for i in range(n):
        for j in range(n):
            if i == j:
                continue
            else:
                div["{}_{}".format(xy[i][0] - xy[j][0], xy[i][1]- xy[j][1])] += 1

    max_ = max(div.values())
    print(n - max_)

Submission status: Accepted

Solution code:
n = int(input())
xy = []
lili = []
for i in range(n):
    x,y = map(int,input().split())
    xy.append([x,y])
for a in xy:
    for b in xy:
        aa = a[0]-b[0]
        bb = a[1]-b[1]
        if not (aa == 0 and bb == 0):
            lili.append([aa,bb])

kyoutuu = 0
for y in lili:
    if lili.count(y) > kyoutuu:
        kyoutuu = lili.count(y)

print(n-kyoutuu)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def YesNo(x): return 'Yes' if x else 'No'
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()
from itertools import product
from collections import Counter

def main():
    N = II()
    if N == 1:
        return 1
    XY = []
    for _ in range(N):
        XY.append(LI())
    cnt = Counter()
    for p0, p1 in product(XY, repeat=2):
        dx, dy = p1[0] - p0[0], p1[1] - p0[1]
        if dx != 0 or dy != 0:
            cnt[(dx, dy)] += 1
    ans = N - max(cnt.values())
    return ans

print(main())

Submission status: Accepted

Solution code:
#coding:utf-8
import numpy as np
from collections import Counter
ls_x = []
ls_y = []
diff = []
N = int(input())
for n in range(N):
    x,y = map(int,input().split())
    for i in range(len(ls_x)):
        diff.append(str((ls_x[i] - x))+"_"+str((ls_y[i] - y)))
        diff.append(str(-(ls_x[i] - x))+"_"+str(-(ls_y[i] - y)))
    ls_x.append(x)
    ls_y.append(y)
if N == 1:
    print (1)
    exit()
cnt = Counter(diff)
#print (cnt.most_common())
print (N-cnt.most_common(1)[0][1])

Submission status: Accepted

Solution code:
words = lambda t : list(map(t, input().split()))
n = int(input())
xys = []
for i in range(n):
    (x,y) = words(int)
    xys.append((x,y))

min_score = -1
for i in range(n):
    xy1 = xys[i]
    for j in range(i,n):
        a = set(xys)
        xy2 = xys[j]
        p = xy1[0] - xy2[0]
        q = xy1[1] - xy2[1]
        score = 0
        while len(a) > 0:
            score += 1
            (x,y) = a.pop()
            xup = x + p
            yup = y + q
            while (xup,yup) in a:
                a.remove((xup,yup))
                xup += p
                yup += q
            xdn = x - p
            ydn = y - q
            while (xdn,ydn) in a:
                a.remove((xdn,ydn))
                xdn -= p
                ydn -= q
        if min_score == -1:
            min_score = score
        else:
            min_score = min(min_score,score)
print(min_score)

Submission status: Accepted

Solution code:
n=int(input())
if n==1:
    print(1)
    exit()
x=[0]*n
y=[0]*n
for i in range(n):
    x[i],y[i]=map(int,input().split())

from collections import Counter
cnt = Counter()
    
for i in range(n):
    for j in range(n):
        if i!=j:
            cnt[str((x[j]-x[i],y[j]-y[i]))]+=1

print(n-cnt.most_common()[0][1])

Submission status: Accepted

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

from collections import Counter
def cal_diff(x1, x2):
    return (x1[0] - x2[0], x1[1] - x2[1])

if n != 1:
  hoge = [cal_diff(x1, x2) for x1 in X for x2 in X if x1 != x2]
  minus = Counter(hoge).most_common(1)[0][1]
  ans = n - minus
  print(ans)
elif n == 1:
  print(1)

Submission status: Accepted

Solution code:
from itertools import permutations


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

min_cost = n
for xyi, xyj in permutations(xys, 2):
    xi, yi = xyi
    xj, yj = xyj
    p = xj - xi
    q = yj - yi

    cost = n
    for x, y in xys:
        for xx, yy in xys:
            if x == xx - p and y == yy - q:
                cost -= 1
    min_cost = min(min_cost, cost)

print(min_cost)

Submission status: Accepted

Solution code:
import collections
N = int(input())
A = []
B = []
YHASHNUM = 1000000000
for i in range(N):
    A.append(list(map(int, input().split())))
#print(N, A)
if N == 1:
    print(1)
else:
    for i in A:
        #print(i[0], i[1])
        for j in A:
            if i == j:
                continue
            B.append(i[0] - j[0] + (i[1] - j[1]) * YHASHNUM)
    #print(B)
    C = collections.Counter(B)
    print(N - C.most_common()[0][1])

Submission status: Accepted

Solution code:
def most_frequent(List):
    counter = 0
    num = List[0]

    for i in List:
        curr_frequency = List.count(i)
        if(curr_frequency> counter):
            counter = curr_frequency
            num = i

    return num

n = int(input())
c = []
for i in range(n):
    x,y = map(int,input().split())
    c.append([x,y])
c = sorted(c)
l = []
for i in range(len(c)-1):
    for j in range(i+1,len(c)):
        l.append([c[j][0]-c[i][0],c[j][1]-c[i][1]])
if(n==1):
    z = most_frequent(c)
else:
    z = most_frequent(l)
l = 1
for i in range(1,len(c)):
    if([c[i][0]-z[0],c[i][1]-z[1]] not in c):
        l+=1
print(l)

Submission status: Accepted

Solution code:
N = int(input())

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

pqlist = []
for i in range(len(balls)):
    for j in range(i+1, len(balls)):
        pqlist.append((balls[j][0] - balls[i][0], balls[j][1] - balls[i][1]))

saishouti = 10**9 + 7

ballset = set(balls)
for pq in pqlist:
    count = 0
    for ball in ballset:
        if (ball[0] + pq[0], ball[1] + pq[1]) in ballset:
            count += 1

    saishouti = min(saishouti, len(balls)-count)

if len(balls) == 1:
    print(1)
else:
    print(saishouti)

Submission status: Accepted

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

diffs = {(0,0):0}

for i in range(N):
    for j in range(N):
        if i==j:
            continue
        diff = (pos[j][0] - pos[i][0], pos[j][1] - pos[i][1])
        if diff not in diffs:
            diffs[diff] = 0
        diffs[diff] += 1

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

Submission status: Accepted

Solution code:
import collections
N = int(input())
xy = [[int(i) for i in input().split()] for _ in range(N)]

diff = []

for i in range(N):
    for j in range(N):
        if i == j:
            continue
        else:
            if xy[i][0] > xy[j][0]:
                diff.append((xy[i][0] - xy[j][0], xy[i][1] - xy[j][1]))
            elif xy[i][0] == xy[j][0] and xy[i][1] >= xy[j][1]:
                diff.append((xy[i][0] - xy[j][0], xy[i][1] - xy[j][1]))
            elif xy[i][0] == xy[j][0] and xy[i][1] < xy[j][1]:
                diff.append((xy[j][0] - xy[i][0], xy[j][1] - xy[i][1]))
            else:
                diff.append((xy[j][0] - xy[i][0], xy[j][1] - xy[i][1]))

if N == 1:
    ans = 1
else:
    c = collections.Counter(diff)
    ans = N - sorted(list(c.values()))[-1] // 2
print(ans)

Submission status: Accepted

Solution code:
def count(xy, pq):

    cnt = 0
    for k in range(n):
        
        for l in range(k+1, n):
            if (xy[l][0] - xy[k][0] == pq[0]) and (xy[l][1] - xy[k][1] == pq[1]):
                cnt += 1
    return cnt
n = int(input())
xy = []
for i in range(n):
    x, y = map(int, input().split())
    xy.append([x,y])
if n == 1:
    print(1)
else:
    m = 0
    xy.sort()
    for i in range(n):
        for j in range(i+1, n):
            pq = [xy[j][0] - xy[i][0], xy[j][1] - xy[i][1]]
            if m < count(xy,pq):
                m = count(xy,pq)
    print(n-m)

Submission status: Accepted

Solution code:
N = int(input())
x = [0]*N
y = [0]*N
L1_dict = dict()
for i in range(N):
    x[i], y[i] = map(int, input().split())
xy = zip(x, y)
xy = sorted(xy, key=lambda x: (x[0], x[1]))
x, y = zip(*xy)
for i in range(N-1):
    for j in range(i, N):
        if i != j:
            x_diff = x[j] - x[i]
            y_diff = y[j] - y[i]
            if (x_diff, y_diff) not in L1_dict:
                L1_dict[(x_diff, y_diff)] = 1
            else:
                L1_dict[(x_diff, y_diff)] = 1 + L1_dict[(x_diff, y_diff)]
if L1_dict:
    M = max(L1_dict.values())
    print(N - M)
else:
    print(N)

Submission status: Accepted

Solution code:
import collections
N = int(input())
x = [0 for i in range(N)]
for i in range(N):
    x[i] = list(map(int, input().split()))
x.sort(key=lambda x: (x[0],x[1]))
salist = []
if N >= 2:
    for i in range(1,N):
        for k in range(1,N):
            if i >= k:
                lb, mb = x[i-k]
                l, m = x[i]
                salist.append((l-lb,m-mb))
    #print(salist)
    c = collections.Counter(salist)
    print( N - c.most_common()[0][1])
else:
    print(1)

Submission status: Accepted

Solution code:
N=int(input())
A=[]
for i in range(N):
  x,y=map(int,input().split())
  A.append((x,y))
if N==1:
  print(1)
  exit()
ans=10000000
for k in range(N):
  for j in range(k):
    p=A[k][0]-A[j][0]
    q=A[k][1]-A[j][1]
    c=0
    for s in range(N):
      flag=False
      for t in range(N):
        if A[s][0]-p==A[t][0] and A[s][1]-q==A[t][1]:
          flag=True 
          break
      if not flag:
        c+=1
    ans=min(c,ans)
print(ans)

Submission status: Accepted

Solution code:
#

import itertools
from collections import Counter
from collections import defaultdict
import bisect
from heapq import heappush, heappop

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

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

    xy.sort(key=lambda p: (p[0], p[1]))
    # print(xy)

    cand = defaultdict(lambda:0)

    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]
            key = '{},{}'.format(p, q)
            cand[key] += 1
    counter = Counter(cand)
    pq_count = counter.most_common()[0][1]
    # print(counter.most_common()[0])
    print(N - pq_count)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

import itertools
def combinations(array, choose):
    return list(itertools.combinations(array, choose))

def resolve():
    N = int(input())
    Pos = [list(map(int, input().split(" "))) for i in range(N)]
    Pos = sorted(Pos, key=lambda x: (x[0], x[1]), reverse=True)
    diffs = []
    comb = combinations(Pos, 2)
    for i in range(len(comb)):
        xdiff = comb[i][0][0] - comb[i][1][0]
        ydiff = comb[i][0][1] - comb[i][1][1]
        for d in diffs:
            if d[0] == xdiff and d[1] == ydiff:
                d[2] += 1
                break
        else:
            diffs.append([xdiff, ydiff, 1])
    
    maxcnt = 0
    for d in diffs:
        if maxcnt < d[2]:
            maxcnt = d[2]
    
    print(N-maxcnt)

if '__main__' == __name__:
    resolve()

Submission status: Accepted

Solution code:
"""
map(int,input().split())

X = input().split()
x = []
for i in range(0,len(X)):
    x.append(X[i])

"""

def search(l, x):
    if x in l:
        return l.index(x)
    else:
        return -1

N = int(input())



ball = []

for n in range(N):
    x,y = map(int,input().split(" "))
    ball.append((x,y))

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

#最適p,q計算
pqList = []
pqCount = []
for i in range(0,N):
    for j in range(0,N):
        if i != j:
           i_x = ball[i][0]
           i_y = ball[i][1]
           j_x = ball[j][0]
           j_y = ball[j][1]
           s = search(pqList,(i_x-j_x,i_y-j_y))
           if s != -1 :
               pqCount[s] += 1
           else:
               pqList.append((i_x-j_x,i_y-j_y))
               pqCount.append(1)

print(int(N - (max(pqCount))))

Submission status: Accepted

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

D = {}

for i in range(N-1) :
    ax,ay = L[i]
    for j in range(i+1,N) :
        bx,by = L[j]
        
        p = bx-ax
        q = by-ay
        tag = str(p)+str(q)
        if tag not in D :
            D[tag] = 1
        else :
            D[tag] += 1
if N == 1 :
    ans = 1
else :
    ans = N-max(D.values())

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
XY = sorted([tuple(map(int, input().split())) for _ in range(N)])
PQ = []
for i in range(N-1):
    for j in range(i, N):
        PQ.append((XY[j][0]-XY[i][0], XY[j][1]-XY[i][1]))
PQ = list(set(PQ))
ans = N
for p, q in PQ:
    tmp1 = 1
    check=[0]*N
    for i in range(N-1):
        if check[i]:
            continue
        else:
            check[i] = 1
            tmp2 = 1
        for j in range(i, N):
            if check[j]:
                continue
            else:
                if XY[j][0] - p == XY[i][0] and XY[j][1] - q == XY[i][1]:
                    check[j] == 1
                    tmp2 = 0
                    break
        tmp1 += tmp2        
    ans = min(ans, tmp1)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
xy = []
diff = []
for _ in range(n):
  tmp = list(map(int,input().split()))
  xy.append(tmp)
for i in range(n):
  for j in range(n):
    if j != i:
      tmpd = [ xy[j][0] - xy[i][0] , xy[j][1] - xy[i][1] ]
      flag = 0
      for mxy in diff:
        if mxy[1:] == tmpd:
            flag = 1
            mxy[0] += 1
            break
      if flag == 0:
        diff.append([0]+tmpd)
diff.sort()
diff.reverse()
if n == 1:
  print(1)
else:
  print(n-diff[0][0]-1)

Submission status: Accepted

Solution code:
import collections
def solve():
  n = int(input())
  queue = []
  queue2 = []
  if n == 1:
    print(1)
    exit()
  for i in range(n):
   x,y = (int(i) for i in input().split())
   queue.append((x,y))
  for i in range(n):
    for j in range(n):
      if i!=j:
        x1,y1 = queue[i]
        x2,y2 = queue[j]
        p = x2-x1
        q = y2-y1
        queue2.append((p,q))
  #print(queue2)
  
  c = collections.Counter(queue2)
  ans = n
  print(ans-c.most_common()[0][1])
solve()

Submission status: Accepted

Solution code:
N = int(input())
X = []
Y = []
for i in range(N):
  x, y = [int(item) for item in input().split()]
  X.append(x)
  Y.append(y)
if N == 1:
  print (1)
else:
  result={}
  maxv = -100
  for i in range(N):
      for j in range(N):
        dx, dy = X[j]-X[i], Y[j]-Y[i]
        if dx > 0 or dy > 0:
          if (dx, dy) not in result:
            result[(dx, dy)] = 1
          else:
            result[(dx, dy)] += 1
          if result[(dx, dy)]>maxv:
            maxv=result[(dx, dy)]
  print (N-maxv)