Problem:


Score : 300 points

Problem Statement

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

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

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

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

Constraints

1 \leq N \leq 50

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

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

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
x_1 y_1
:
x_N y_N

Output

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

Sample Input 1

2
1 1
2 2

Sample Output 1

1

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

Sample Input 2

3
1 4
4 6
7 8

Sample Output 2

1

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

Sample Input 3

4
1 1
1 2
2 1
2 2

Sample Output 3

2



Sample input:
2
1 1
2 2


Sample output:
1

Submission status: Accepted

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


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

ans = 0
tar = list(set(res))
for t in tar:
    cnt = 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:
                cnt += 1
                break
    ans = max(ans, cnt)
print(N - ans)

Submission status: Accepted

Solution code:
from collections import Counter
N = int(input())
xy = [list(map(int, input().split())) for _ in range(N)]
 
counter = Counter(((b1[0] - b2[0], b1[1] - b2[1])for b1 in xy for b2 in xy if b1 != b2))
print(N - (list(counter.most_common())+[(0,0)])[0][1])

Submission status: Accepted

Solution code:
from collections import Counter
N = int(input())
xy = [tuple(map(int,input().split())) for i in range(N)]
ct = Counter()
for i in range(N):
  for j in range(i+1,N):
    dx = xy[i][0]-xy[j][0]
    dy = xy[i][1]-xy[j][1]
    ct[(dx,dy)] += 1
    ct[(-dx,-dy)] += 1
print(N-max(ct.values() if len(ct)>0 else [0]))

Submission status: Accepted

Solution code:
from collections import Counter
N = int(input())
xy = [list(map(int, input().split())) for _ in range(N)]
 
counter = Counter(((b1[0] - b2[0], b1[1] - b2[1])for b1 in xy for b2 in xy if b1 != b2))
print(N - (list(counter.most_common())+[(0,0)])[0][1])

Submission status: Accepted

Solution code:
# coding:utf-8
import sys


def main():
    N = int(input())
    # N,M = map(int,input().split())
    coordinate = []
    for i in range(N):
        x, y = map(int, input().split())
        coordinate.append([x, y])
    coordinate.sort()
    # print(coordinate)

    ans = N
    checklist = []

    for i in range(N-1):
        x1 = coordinate[i][0]
        y1 = coordinate[i][1]
        for j in range(i+1, N):
            x2 = coordinate[j][0]
            y2 = coordinate[j][1]
            p = x2 - x1
            q = y2 - y1
            if not [p, q] in checklist:
                checklist.append([p, q])

    for templ in checklist:
        pi = templ[0]
        qi = templ[1]
        count = N
        for i in range(N):
            for j in range(i, N):
                if i == j:
                    continue
                elif coordinate[i][0] + pi == coordinate[j][0] and coordinate[i][1] + qi == coordinate[j][1]:
                    count -= 1
        if count < ans:
            ans = count

    print(ans)
    return


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# coding:utf-8
import sys


def main():
    N = int(input())
    # N,M = map(int,input().split())
    coordinate = []
    maxx = 0
    maxy = 0
    for i in range(N):
        x, y = map(int, input().split())
        # if maxx < x:
        #     maxx = x
        # if maxy < y:
        #     maxy = y
        coordinate.append([x, y])
    coordinate.sort()
    # print(coordinate)

    ans = N
    checklist = []

    for i in range(N-1):
        x1 = coordinate[i][0]
        y1 = coordinate[i][1]

        for j in range(i+1, N):
            x2 = coordinate[j][0]
            y2 = coordinate[j][1]
            p = x2 - x1
            q = y2 - y1
            if not [p, q] in checklist:
                checklist.append([p, q])
    # print(checklist)

    # for i in range(5):
    #     for j in range(i, 5):
    #         if not i == j:
    #             print(i, j)

    for templ in checklist:
        pi = templ[0]
        qi = templ[1]
        count = N
        for i in range(N):
            for j in range(i, N):
                if i == j:
                    continue
                elif coordinate[i][0] + pi == coordinate[j][0] and coordinate[i][1] + qi == coordinate[j][1]:
                    count -= 1
        if count < ans:
            ans = count

    # arrivelist = []
    # for templ in checklist:
    #     pi = templ[0]
    #     qi = templ[1]
    #     for i in range(N):
    #         temp = []
    #         temp.append(i)
    #         nowx = coordinate[i][0] + pi
    #         nowy = coordinate[i][1] + qi
    #         for j in range(i, N):
    #             if nowx == coordinate[j][0] and nowy == coordinate[j][1]:
    #                 temp.append(j)
    #                 nowx += pi
    #                 nowy += qi
    #             elif nowx < coordinate[j][0]:
    #                 break
    #         if not temp in arrivelist:
    #             arrivelist.append(temp)

    # print(arrivelist)
    # arrivelist.sort(key=lambda x: len(x), reverse=True)
    # print(arrivelist)
    # dp = [[]]*len(arrivelist)

    # print(dp)
    print(ans)
    return


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
import itertools
import collections
sys.setrecursionlimit(10**7)
def lmi(): return list(map(int, input().split()))

n = int(input())
x = [0] * n
y = [0] * n
for i in range(n):
    x[i], y[i] = lmi()

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

c = collections.Counter(d)
if n != 1:
    c1 = c.most_common()[1]
    print(n - c1[1])
else:
    print(1)

Submission status: Accepted

Solution code:
import collections


def calc(balla, ballb):
    xa, ya = balla
    xb, yb = ballb
    return xa - xb, ya - yb


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

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

a = []
for i in range(0, n - 1):
    for j in range(i + 1, n):
        tmp = calc(balls[i], balls[j])
        a += [tmp, tuple(-i for i in tmp)]
counts = collections.Counter(a)

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

Submission status: Accepted

Solution code:
import statistics

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

p.sort()
delta = []
for i in range(N):
    for j in range(i+1,N):
        dx = p[j][0]-p[i][0]
        dy = p[j][1]-p[i][1]
        delta.append([dx,dy])
delta.sort()
best = [0,0]
bestc = 0
nowc = 0
for i in range(len(delta)):
    if i == 0:
        best = delta[i]
        bestc = 1
        nowc = 1
    else:
        if delta[i-1][0]==delta[i][0] and delta[i-1][1]==delta[i][1]:
            nowc += 1
            if nowc > bestc:
                best = delta[i]
                bestc = nowc
        else:
            nowc = 1
ans = 1+(N-1-bestc)
print(ans)

Submission status: Accepted

Solution code:
import sys
N = int(input())
li = []
if N == 1:
    a = list(map(int,input().split()))
    print(1)
    sys.exit()   
 
for i in range(N):
    a = list(map(int,input().split()))
    li.append(a)
 
cross = []
 
##計算量に余裕があるので全探索します
for i in range(N):
    for j in range (i+1, N):
        a = [li[j][0]-li[i][0],li[j][1]-li[i][1]]
        if a[0] <= 0 and a[1] <= 0:
            b = [abs(li[j][0]-li[i][0]),abs(li[j][1]-li[i][1])]
            cross.append(b)
        elif a[0] < 0 and a[1] >= 0:
            c = li[j][1]-li[i][1]
            b = [abs(li[j][0]-li[i][0]),-c]
            cross.append(b) ####
        else:
            cross.append(a) 
lencross = len(cross)
 
res = 0
ans = []
 
for i in range (lencross):
    res = 0
    for j in range (lencross):
        if cross[i] == cross[j]:
            res += 1
    ans.append(res)
reduce = max(ans)
 
print(N - reduce)

Submission status: Accepted

Solution code:
from collections import deque
import statistics
import math
from collections import Counter
N=int(input())
x=[]
y=[]
for a in range(N):
    b,c=(int(xxx) for xxx in input().split())
    x.append(b)
    y.append(c)
sa=deque([[0,0]])
if N>1:
    for a in range(N):
        for b in range(N-a-1):
            sx=x[a]-x[a+b+1]
            sy=y[a]-y[a+b+1]
            sa.append([sx,sy])
    sa.remove([0,0])
    ans=[]
    nagasa=len(sa)
    for a in range(nagasa):
        xx,yy=sa[a]
        ss=sa.count([xx,yy])+sa.count([-xx,-yy])
        ans.append(ss)
    kotae=max(ans)
    print(N-kotae)

else:
    print(1)

Submission status: Accepted

Solution code:
###template###
import sys
def input(): return sys.stdin.readline().rstrip()
def mi(): return map(int, input().split())
###template###

#Union-Find ****0スタートなので注意！****
class UnionFind():
  # 作りたい要素数（ノードの数）nで初期化
  # 使用するインスタンス変数の初期化
  def __init__(self, n):
    self.n = n
    # root[x]<0ならそのノードが根かつその値が木の要素数
    # rootノードでその木の要素数を記録する
    self.root = [-1]*(n) #元々はn+1になっていたが、nに直した
    # 木をくっつける時にアンバランスにならないように調整する
    self.rnk = [0]*(n) #元々はn+1になっていたが、nに直した

  # ノードxのrootノードを見つける
  def Find_Root(self, x):
    if(self.root[x] < 0):
      return x
    else:
      # ついでに経路圧縮（調べた辺を根に直接つなぎ直す）をかけておく
      self.root[x] = self.Find_Root(self.root[x])
      return self.root[x]

  # 木の併合、入力は併合したい集合に属する各ノード
  def Unite(self, x, y):
    # 入力ノードのrootノードを見つける
    x = self.Find_Root(x)
    y = self.Find_Root(y)
    # すでに同じ木に属していた場合、何もしないで返す
    if(x == y):
      return
    # 違う木に属していた場合rnkを見てくっつける方を決める
    elif(self.rnk[x] > self.rnk[y]):
      self.root[x] += self.root[y] #要素数を足す(根のrootは"-要素数")
      self.root[y] = x #ノードyの親をx（新しい集合の根）とする
    else:
      self.root[y] += self.root[x] #要素数を足す
      self.root[x] = y
      # rnkが同じ（深さに差がない場合）は1増やす（根(rnk1)+繋げる集合のrnkということで、1増えることになる）
      if(self.rnk[x] == self.rnk[y]):
          self.rnk[y] += 1

  # xとyが同じグループに属するか判断
  def isSameGroup(self, x, y):
    return self.Find_Root(x) == self.Find_Root(y)

  # ノードxが属する木のサイズを返す（根ノードの.root[idx]を-符号を外して返すだけ
  def Count(self, x):
    return -self.root[self.Find_Root(x)] #-符号を外す

  # 木の数（＝集合の数）を返す（根の数=rootに-符号を持つものの数を返すだけ）
  def Count_Trees(self):
    treecnt = 0
    for eachroot in self.root:
      if eachroot < 0: treecnt += 1
    return treecnt
#------Union-Findおわり-------------#

import collections

N = int(input())
XYs = [tuple(mi()) for _ in range(N)]

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

sa_list = []
cmb_with_same_diff = collections.defaultdict(list)
import itertools
diffidx = 0
for a in range(0, N):
  for b in range(0, N):
    if a>=b: continue
    #ここでa, bは各ボールのidx
    ax, ay = XYs[a]
    bx, by = XYs[b]
    if ax-bx==0: nowsa = (ax-bx,abs(ay-by))
    elif ay-by==0: nowsa = (abs(ax-bx), ay-by)
    elif ax-bx>0: nowsa = (ax-bx,ay-by)
    else: nowsa = (-(ax-bx),-(ay-by))
    sa_list.append(nowsa)
    cmb_with_same_diff[nowsa].append((a, b))


ans = N
for each_samesa_list in cmb_with_same_diff.values():
  UF = UnionFind(N) #ノード数はボールの数
#  print(each_samesa_list, 'における処理前の木の数は', UF.Count_Trees())
  for a, b in each_samesa_list:
    UF.Unite(a, b)
#  print(each_samesa_list, 'における処理後の木の数は', UF.Count_Trees())
  ans = min(ans, UF.Count_Trees())

print(ans)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
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 I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    n = I()
    xy = sorted([LI() for _ in range(n)])
    if n == 1:
        return 1
    d = collections.defaultdict(int)
    for i in range(n):
        x,y = xy[i]
        for j in range(i+1,n):
            x2,y2 = xy[j]
            d[(x-x2,y-y2)] += 1

    return n - max(d.values())


print(main())

Submission status: Accepted

Solution code:
###template###
import sys
def input(): return sys.stdin.readline().rstrip()
def mi(): return map(int, input().split())
###template###

#Union-Find ****0スタートなので注意！****
class UnionFind():
  # 作りたい要素数（ノードの数）nで初期化
  # 使用するインスタンス変数の初期化
  def __init__(self, n):
    self.n = n
    # root[x]<0ならそのノードが根かつその値が木の要素数
    # rootノードでその木の要素数を記録する
    self.root = [-1]*(n) #元々はn+1になっていたが、nに直した
    # 木をくっつける時にアンバランスにならないように調整する
    self.rnk = [0]*(n) #元々はn+1になっていたが、nに直した

  # ノードxのrootノードを見つける
  def Find_Root(self, x):
    if(self.root[x] < 0):
      return x
    else:
      # ついでに経路圧縮（調べた辺を根に直接つなぎ直す）をかけておく
      self.root[x] = self.Find_Root(self.root[x])
      return self.root[x]

  # 木の併合、入力は併合したい集合に属する各ノード
  def Unite(self, x, y):
    # 入力ノードのrootノードを見つける
    x = self.Find_Root(x)
    y = self.Find_Root(y)
    # すでに同じ木に属していた場合、何もしないで返す
    if(x == y):
      return
    # 違う木に属していた場合rnkを見てくっつける方を決める
    elif(self.rnk[x] > self.rnk[y]):
      self.root[x] += self.root[y] #要素数を足す(根のrootは"-要素数")
      self.root[y] = x #ノードyの親をx（新しい集合の根）とする
    else:
      self.root[y] += self.root[x] #要素数を足す
      self.root[x] = y
      # rnkが同じ（深さに差がない場合）は1増やす（根(rnk1)+繋げる集合のrnkということで、1増えることになる）
      if(self.rnk[x] == self.rnk[y]):
          self.rnk[y] += 1

  # xとyが同じグループに属するか判断
  def isSameGroup(self, x, y):
    return self.Find_Root(x) == self.Find_Root(y)

  # ノードxが属する木のサイズを返す（根ノードの.root[idx]を-符号を外して返すだけ
  def Count(self, x):
    return -self.root[self.Find_Root(x)] #-符号を外す

  # 木の数（＝集合の数）を返す（根の数=rootに-符号を持つものの数を返すだけ）
  def Count_Trees(self):
    treecnt = 0
    for eachroot in self.root:
      if eachroot < 0: treecnt += 1
    return treecnt
#------Union-Findおわり-------------#

import collections

N = int(input())
XYs = [tuple(mi()) for _ in range(N)]

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

sa_list = []
cmb_with_same_diff = collections.defaultdict(list)
import itertools
diffidx = 0
for a in range(0, N):
  for b in range(0, N):
    if a>=b: continue
    #ここでa, bは各ボールのidx
    ax, ay = XYs[a]
    bx, by = XYs[b]
    if ax-bx==0: nowsa = (ax-bx,abs(ay-by))
    elif ay-by==0: nowsa = (abs(ax-bx), ay-by)
    elif ax-bx>0: nowsa = (ax-bx,ay-by)
    else: nowsa = (-(ax-bx),-(ay-by))
    sa_list.append(nowsa)
    cmb_with_same_diff[nowsa].append((a, b))

#print(sa_list)
#print(cmb_with_same_diff)

#最も多い差の個数（これ-1を短縮できるはず）
print(N-collections.Counter(sa_list).most_common()[0][1])

#[((x, y), 回数), ...]　多い順で入っている
#sa_sorted = collections.Counter(sa_list).most_common()

ans = N
for each_samesa_list in cmb_with_same_diff.values():
  UF = UnionFind(N) #ノード数はボールの数
#  print(each_samesa_list, 'における処理前の木の数は', UF.Count_Trees())
  for a, b in each_samesa_list:
    UF.Unite(a, b)
#  print(each_samesa_list, 'における処理後の木の数は', UF.Count_Trees())
  ans = min(ans, UF.Count_Trees())

#print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
from itertools import combinations
N = int(input())
XY = [list(map(int, input().split())) for _ in range(N)]
XY.sort()
A = Counter()
for (x1, y1), (x2, y2) in combinations(XY, 2):
    A[(x1-x2, y1-y2)] += 1
if N == 1:
    print(1)
else:
    print(N - max(A.values()))

Submission status: Accepted

Solution code:
N = int(input())
balls = [
    [int(s) for s in input().split(' ')]
    for i in range(N)
]
balls.sort(key=lambda p: p[1])
balls.sort(key=lambda p: p[0])
d = {}
d_max = 0
for i in range(N):
    for j in range(i + 1, N):
        p = balls[j][0] - balls[i][0]
        q = balls[j][1] - balls[i][1]
        if not p in d:
            d[p] = {}
        d[p][q] = (d[p][q] if q in d[p] else 0) + 1
        d_max = max([d_max, d[p][q]])
print(N - d_max)

Submission status: Accepted

Solution code:
N = int(input())
xy = [list(map(int,input().split())) for i in range(N)]
x = [xy[i][0] for i in range(N)]
y = [xy[i][1] for i in range(N)]
if N == 1:
    print(1)
    exit()
else:
    ans = N
    for i in range(N):
        for j in range(N):
            if i == j:
                continue
            dx,dy = x[j]-x[i],y[j]-y[i]
            cnt = 0
            for k in range(N):
                for l in range(N):
                    if k == l:
                        continue
                    if dx == x[k]-x[l] and dy == y[k]-y[l]:
                        cnt += 1
            ans = min(ans,N-cnt)

print(ans)

Submission status: Accepted

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

counter = Counter(((b1[0] - b2[0], b1[1] - b2[1]) for b1 in xy for b2 in xy if b1 != b2))
print(N - (list(counter.most_common())+[(0,0)])[0][1])

Submission status: Accepted

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

dic={}
for e in xy:
	for f in xy:
		if e==f:continue
		tmp=(e[0]-f[0],e[1]-f[1])
		dic[tmp]=dic.get(tmp,0)+1

mx=max(dic.values()) if dic else 0
print(n-mx)

Submission status: Accepted

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

for i in range(n):
  for j in range(n):
    if i==j:
      continue
    xt = xy[i][0]-xy[j][0]
    yt = xy[i][1]-xy[j][1]
    tmp = n
    for k in range(n):
      if (xy[k][0]+xt, xy[k][1]+yt) in xy:
        tmp -= 1
    ans = min(ans, tmp)

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
arr=[list(map(int,input().split())) for _ in range(n)]
cnt={}
for i in range(n):
  for j in range(n):
    if i==j:
      continue
    p=arr[i][0]-arr[j][0]
    q=arr[i][1]-arr[j][1]
    if (p,q) not in cnt:
      cnt[(p,q)]=1
    else:
      cnt[(p,q)]+=1
if n==1:
  print(1)
else:
  ans=n-max(cnt.values())
  print(ans)

Submission status: Accepted

Solution code:
N=int(input())

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

x=[]
y=[]

for X,Y in XY:
    x.append(X)
    y.append(Y)
    
l1=[]
c=0
for i in range(N):
    for j in range(N):
        if i==j:
            continue;
        a=x[i]-x[j]
        b=y[i]-y[j]
        """
        if a<=0 and b>=0:
            a=-a
            b=-b
        elif a<=0 and b<=0:
            a=-a
            b=-b
        """
        l1.append(str(a)+"_"+str(b))
        #l1.append([a,b])
v=set(l1)
c=[]
for i in v:
    c.append(l1.count(i))
#c = collections.Counter(l1)      
#values, counts = zip(*c.most_common()) 
if c==[]:
    print(1)   
else:
    print(N-max(c))

Submission status: Accepted

Solution code:
N=int(input())
P=[tuple(map(int,input().split())) for i in range(N)]
ans=N
for i in range(N):
    for j in range(N):
        if i==j:
            continue
        p=P[i][0]-P[j][0]
        q=P[i][1]-P[j][1]
        cost=0
        for k in range(N):
            if (P[k][0]-p,P[k][1]-q) not in P:
                cost+=1
        ans=min(ans,cost)
print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations, permutations

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

for b1, b2 in combinations(balls, 2):
    p, q = b1[0] - b2[0], b1[1] - b2[1]
    if p != 0 or q != 0:
        sub = 0
        for b3, b4 in permutations(balls, 2):
            dx, dy = b3[0] - b4[0], b3[1] - b4[1]
            if dx == p and dy == q:
                sub += 1
        cost = min(cost, n - sub)

print(max(cost, 1))

Submission status: Accepted

Solution code:
from collections import Counter
n = int(input())
xy = [list(map(int,input().split())) for i in range(n)]
pq = []
if n == 1:
    print(1)
    exit()
for i in range(n):
    for j in range(n):
        r = (xy[i][0]-xy[j][0],xy[i][1]-xy[j][1])
        if i!=j:
            pq.append(r)
#print(pq)
ans = Counter(pq).most_common()
print(n-ans[0][1])

Submission status: Accepted

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

m = dict()


ans = 0


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(m[p], ans)



print(n-ans)

Submission status: Accepted

Solution code:
from itertools import combinations

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

for b1, b2 in combinations(balls, 2):
    p, q = b1[0] - b2[0], b1[1] - b2[1]
    if p != 0 or q != 0:
        sub = 0
        for b3, b4 in combinations(balls, 2):
            dx, dy = b3[0] - b4[0], b3[1] - b4[1]
            if dx == p and dy == q or -dx == p and -dy == q:
                sub += 1
        cost = min(cost, n - sub)

print(max(cost, 1))

Submission status: Accepted

Solution code:
import sys
import itertools

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

counts = dict()
for (x1, y1), (x2, y2) in itertools.combinations(xy_list, 2):
    for pq in ((x2 - x1, y2 - y1), (x1 - x2, y1 - y2)):
        counts.setdefault(pq, 0)
        counts[pq] += 1
max_count = max(counts.values())
print(n - max_count)

Submission status: Accepted

Solution code:
import collections

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

if N==1: print(1)
else:
  xy = sorted(xy, key=lambda x: (x[0], x[1]))
  xy_list = set(xy)

  pq_collections = [0]*int((N*(N-1))/2)
  pq_c_index = 0

  for i, xy1 in enumerate(xy):
    for xy2 in xy[i+1:]:
      p = xy2[0] - xy1[0]
      q = xy2[1] - xy1[1]
      pq_collections[pq_c_index] = (p, q)
      pq_c_index += 1

  c = collections.Counter(pq_collections)

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

Submission status: Accepted

Solution code:
import sys
from collections import Counter

N=int(input())
if N==1:
  print(1)
  sys.exit()
  
x=[0]*N
y=[0]*N
for i in range(N):
  x[i],y[i] = map(int, input().split())
a = []
for i in range(N):
  for j in range(N):
    if i==j:
      continue
    else:
      a.append(str(x[j]-x[i])+'&'+str(y[j]-y[i]))
    
a=Counter(a)
common = a.most_common(1)[0][1]
print(N-common)

Submission status: Accepted

Solution code:
from collections import Counter

def input_func():
    N = int(input())
    lis = []
    for i in range(N):
        x, y = map(int, input().split())
        lis.append([x,y])
        sort_lis = sorted(lis)
    return N,sort_lis


def evaluate(N, sort_lis):
    diff = []
    if N == 1:
        answer = 1
        
    else:
        for i in range(N-1):
            for j in range(i+1,N):
                diff.append((sort_lis[i][0] -sort_lis[j][0],sort_lis[i][1]-sort_lis[j][1]))
        count = Counter(diff).most_common()
        answer = len(sort_lis)-count[0][1]
    return answer 

if __name__ == '__main__':
    N, sort_lis = input_func()
    answer = evaluate(N,sort_lis)
    print(answer)

Submission status: Accepted

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

res = []
count = 0
for i in range(N):
  for j in range(i,N):
#コストの和の最小値を求める
#これ以上進めない点が何個あるか数えれば良い
    p = x[i] - x[j]
    q = y[i] - y[j]
    count = 0
    for item in xy:
      if [item[0]+p,item[1]+q] not in xy:
        count += 1
    if count != 0: res.append(count)

if res == []:
  res.append(1)

print(min(res))

Submission status: Accepted

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

s = set(P)

ans = 0
for i in range(N):
    xi, yi = P[i]
    for j in range(N):
        if i == j:
            continue
        xj, yj = P[j]
        dx = xi - xj; dy = yi - yj
        cnt = 0
        for x, y in P:
            if (x+dx, y+dy) in s:
                cnt += 1
        ans = max(ans, cnt)
print(N - ans)

Submission status: Accepted

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

if N == 1:
    ans = 1
else:
    ans = N
    for i in range(N):
        for j in range(N):
            if i == j:
                continue
            dx, dy = x[i] - x[j], y[i] - y[j]
            
            cnt = 0
            for k in range(N):
                for l in range(N):
                    if k == l:
                        continue
                    if (dx == x[k] - x[l]) and (dy == y[k] - y[l]):
                        cnt += 1
            
            ans = min(ans, N - cnt)

print(ans)

Submission status: Accepted

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

for i in range(n):
    for j in range(n):
        if i==j:
            continue
        t=(s[i][0]-s[j][0],s[i][1]-s[j][1])
        x.append(t)
        
ans = [x.count(i) for i in set(x)]
print(n-max(ans))

Submission status: Accepted

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

for i in range(n):
    for j in range(n):
        if i==j:
            continue
        t=(s[i][0]-s[j][0],s[i][1]-s[j][1])
        x.append(t)
        
ans = [x.count(x[i]) for i in range(len(x))]
print(n-max(ans))

Submission status: Accepted

Solution code:
n = int(input())
xy = set(tuple(map(int, input().split())) for _ in range(n))

costs = []
for a in xy:
    besides_a = xy - {a}
    for b in besides_a:
        p = b[0] - a[0]
        q = b[1] - a[1]
        arrow_num = 0
        for c in xy:
            if (c[0] + p, c[1] + q) in xy:
                arrow_num += 1
        cost = n - arrow_num
        costs.append(cost)

if n == 1:
    print(1)
else:
    print(min(costs))

Submission status: Accepted

Solution code:
import collections
import numpy as np

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

xy = np.array(xy)

dic_xy = {}

for i in range(N):
    for j in range(N):
        if i != j:
            diff_xy = xy[i] - xy[j]
            diff_xy = tuple(diff_xy)
            
            if dic_xy.get(diff_xy) is None:
                dic_xy[diff_xy] = 1
            else:
                dic_xy[diff_xy] += 1

max_diff = 0
for x in dic_xy:
    max_diff = max(max_diff, dic_xy[x])
    
print(N - max_diff)

Submission status: Accepted

Solution code:
from collections import Counter


class PickingUp:
    def __init__(self):
        self.N = int(input())
        self.points = []
        for n in range(self.N):
            self.points.append([int(n) for n in input().split()])

    def main(self):
        dif_list = []

        if self.N == 1:
            print(1)
            return

        for s in range(self.N):
            for e in range(self.N):
                if s == e:
                    continue
                dif = self.__cal_dif(self.points[s], self.points[e])
                dif_list.append("{},{}".format(dif[0], dif[1]))

        c = Counter(dif_list)
        most = c.most_common()[0][1]

        print(self.N - most)

    def __cal_dif(self, s, e):
        dif_x = s[0] - e[0]
        dif_y = s[1] - e[1]
        return [dif_x, dif_y]


pickingUp = PickingUp()
pickingUp.main()

Submission status: Accepted

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

dic = dict()
for cx, cy in xy:
    for x, y in xy:
        if cx != x or cy != y:
            w = (x-cx,y-cy)
            if dic.get(w) is None:
                dic[w] = 0
            dic[w] += 1

cnt = 1
m = 0
for x in dic:
    m = max(m, dic[x])
cnt += N - 1 - m
print(cnt)

Submission status: Accepted

Solution code:
#-*- coding: utf-8
#  -*-
"""
oj dl https://atcoder.jp/contests/abc116/tasks/abc116_d -d test-d
oj test -d test-d -c "python abc116d.py"
oj test -d test-d -c "python abc116d.py" test-d/sample-3.in
"""
from collections import defaultdict
import sys
import math
from datetime import datetime

def sol2(n, S):
    dp = defaultdict(int)
    pre_x = None
    pre_y = None
    for i, (x, y) in enumerate(S):
        #print(x, y, pre_x, pre_y)
        if i == 0:
            pre_x, pre_y = x, y
        else:
            dp[(x - pre_x, y - pre_y)] +=1
            pre_x, pre_y = x, y
    #print(dp)
    return n - max(dp.values())


def rec(S, pre, diff, n):
    if S == None or len(S) == 0 or len(S)==n: return 0

    tugi = (pre[0]+diff[0], pre[1]+diff[1])
    print("pre:%s, diff:%s, so tugi:%s while S:%s" % (str(pre), str(diff), str(tugi), S))
    if tugi in S:
        print("hit:%s" % str(tugi))
        S.remove(tugi)
        return 1 + rec(S, tugi, diff)
    else:
        print("end")
        return 0


def sol_botsu2(n, S):
    dp = defaultdict(int)
    if n == 1:
        return 1
    # n >= 2
    mx = 0
    tugi = S[1]
    for s in S:
        if tugi == s: continue
        tmp = rec(S[1:], s, (tugi[0]-s[0], tugi[1]-s[1]))
        mx = max(tmp, mx)

    return n - mx



def sol(n, S):
    PQ = []
    for s1 in S:
        for s2 in S:
            if s1 == s2: continue
            PQ.append((s2[0] - s1[0], s2[1] - s1[1]))
    mx = 0
    for p, q in set(PQ):
        tmp = 0
        for s1 in S:
            for s2 in S:
                if s1 == s2: continue
                if (s2[0] - s1[0], s2[1] - s1[1]) == (p, q):
                    tmp += 1
        mx = max(tmp, mx)

    return n - mx

do_submit = True
#do_submit = False

def input_parse(input_str):
    lines = [x.strip() for x in input_str.split("\n") if x.strip()]
    parsed_lines = [list(map(str, line.split())) for line in lines]
    #print(parsed_lines)
    n = int(parsed_lines[0][0])
    #W = [int(x) for x in parsed_lines[1]]
    S = []
    for i in range(1, n+1):
        x = int(parsed_lines[i][0])
        y = int(parsed_lines[i][1])
        S.append((x, y))
    # k = int(parsed_lines[0][1])
    # S = parsed_lines[1][0]
    # return n, k, S
    return n, S


if not do_submit:
    n, S = input_parse("""
    2
    1 1
    2 2
    """)
    #print(sol(n, S))

    n, S = input_parse("""
    3
    1 4
    4 6
    7 8
    """)
    #print(sol(n, S))

    n, S = input_parse("""
    4
    1 1
    1 2
    2 1
    2 2
    """)
    print(sol(n, S))


else:
    n = int(input())
    S = []
    for i in range(n):
        x ,y = list(map(int, input().split()))
        S.append((x, y))
    # print(sol(n, k, S))
    #S = input().strip()
    # S = input().strip()
    print(sol(n, S))