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:
from collections import deque
def solve():
    N = int(input())
    X = [0]*N
    Y = [0]*N
    balls = [0]*N
    ans = N
    dic = {}
    f = {}
    for i in range(N):
        X[i],Y[i] = map(int, input().split())
        dic[(X[i],Y[i])] = i
        balls[i] = [X[i],Y[i]]
    
    balls = sorted(balls, key=lambda x:(x[0],x[1]))

    for x1, y1 in zip(X,Y):
        for x2, y2 in zip(X,Y):
            p = x2 - x1
            q = y2 - y1
            if p == 0 and q == 0:
                continue
            collected = [False]*N
            collected[dic[(x1,y1)]]=True
            collected[dic[(x2,y2)]]=True
            d = deque(balls)
            cnt = 1
            x = x2 + p
            y = y2 + q
            while (x,y) in dic:
                collected[dic[(x,y)]] = True
                x += p
                y += q
            while len(d)>0: 
                if p<0 or p==0 and q<0:
                    x,y = d.pop()
                else:
                    x,y = d.popleft()
                if collected[dic[(x,y)]] == True:
                    continue
                cnt += 1
                while (x,y) in dic:
                    collected[dic[(x,y)]] = True
                    x += p
                    y += q
            ans = min(ans, cnt)
    return ans
print(solve())

Submission status: Accepted

Solution code:
import collections

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

moves = collections.defaultdict(list)
mmax = 0
vmax = None
for i in range(N):
    for j in range(i):
        x1, y1 = balls[i]
        x2, y2 = balls[j]
        if y1 > y2 or (y1 == y2 and x1 > x2):
            x1, x2 = x2, x1
            y1, y2 = y2, y1
        moves[x2-x1, y2-y1].append((j, i))
        m = len(moves[x2-x1, y2-y1])
        if m > mmax:
            mmax = m
            vmax = (x2-x1, y2-y1)

#print(mmax, vmax)
print(N - mmax)

Submission status: Accepted

Solution code:
import collections
n=int(input())
xy=[list(map(int,input().split())) for _ in range(n)]
xy.sort()
count={}
ans=0
for i in range(n):
    for j in range(i+1,n):
   #     print(i,j)
        x=xy[i][0]-xy[j][0]
        y=xy[i][1]-xy[j][1]
        if (x,y) in count:
            count[x,y]+=1
        else:
            count[x,y]=1
#print(count)
for v in count.values():
    ans=max(ans,v)
print(n-ans)

Submission status: Accepted

Solution code:
n = int(input())
data = []
for i in range(n):
    data.append(list(map(int, input().split())))
dif = dict()
data.sort()
for i in range(n):
    for j in range(i+1, n):
        x = data[i][0] - data[j][0]
        y = data[i][1] - data[j][1]
        if (x,y) in dif:
            dif[(x,y)] += 1
        else:
            dif[(x,y)] = 1
if len(dif.keys()) == 0:
    print(n)
    exit()
print(n - max([dif[i] for i in dif.keys()]))

Submission status: Accepted

Solution code:
N = int(input())
co = [[int(i) for i in input().split()] for i in range(N)]
co = sorted(co)
d = {}
m = 0
for i in range(N):
    for j in range(i+1, N):
        a = co[i][0]-co[j][0]
        b = co[i][1]-co[j][1]
        if (a, b) in d:
            d[a,b] += 1
        else:
            d[a,b] = 1
for k in d.values():
    m = max(m, k)
print(N-m)

Submission status: Accepted

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

d=dict()
r=[]
for i in range(N):
    for j in range(N):
        if i==j:
            continue
        p = x[i]-x[j]
        q = y[i]-y[j]
        c=(p,q)
        if c in d:
            d[c]+=1
        else:
            d[c]=1
ans=0
#print(d)
for i,j in d.items():
    ans=max(ans,j)

print(N-ans)

Submission status: Accepted

Solution code:
# まず、xの値でソート（同値の場合はyでソート）する。
# この状態で、全ての2点について、x,yの差を求める
# 差の情報(p,q)の回数が最も大きいものが答えの候補
# (p,q)で到達できる点にはコスト0で行けるグラフの最短距離を解く

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

ball=sorted(ball,key=lambda x:(x[0],x[1]))

from collections import defaultdict
dic = defaultdict(list)

for i in range(N-1):
  for j in range(i+1,N):
    # 点iから点jへは(p,q)で到達できる
    dic[(ball[j][0] - ball[i][0],ball[j][1] - ball[i][1])].append((i,j))

pq=None
target=[]
for item in dic.items():
  if len(item[1]) > len(target):
    target = item[1]
    pq=item[0]
    
# targetの要素で、同じ点を持つものは結合して1つの点にできる。
# UnionFind

# 0-indexed
class UnionFind:
  N=0
  parent=None
  size=None
  def __init__(self,N):
    self.N=N
    self.parent=[i for i in range(self.N)]
    self.size=[1]*self.N
    
  def root(self,x):
    while x!=self.parent[x]:
      self.parent[x]=self.parent[self.parent[x]]
      x=self.parent[x]
    return x
  
  def same(self,x,y):
    return self.root(x)==self.root(y)
  
  def unite(self,x,y):
    x=self.root(x)
    y=self.root(y)
    if x==y:
      return
    if self.size[x]>self.size[y]:
      # 大きい方にくっつける
      self.parent[y]=x
      self.size[x]+=self.size[y]
    else:
      self.parent[x]=y
      self.size[y]+=self.size[x]
      
  def get_group_size(self,x):
    return self.size[self.root(x)]
  
  def get_roots(self):
    r=set()
    for i in range(self.N):
      r.add(self.root(i))
    return r
  
  def show_parent(self):
    print(self.parent)
    
  def show_size(self):
    print(self.size)

UF=UnionFind(N)
for i,j in target:
  UF.unite(i,j)
  
print(len(UF.get_roots()))

Submission status: Accepted

Solution code:
from collections import defaultdict
n = int(input())
li = []
for i in range(n):
    xi,yi = map(int,input().split())
    li.append((xi,yi))
if n == 1:
    print(1)
    exit()
dic = defaultdict(int)
for i in range(n):
    for j in range(n):
        if i != j:
            xi = li[i][0]
            yi = li[i][1]
            xj = li[j][0]
            yj = li[j][1]
            dic[(xi-xj,yi-yj)] += 1
print(n-max(dic.values()))

Submission status: Accepted

Solution code:
N,*L = map(int, open(0).read().split())
ls = [0]*N
for i,c in enumerate(zip(*[iter(L)]*2)):
  ls[i] = c
ls.sort()
pls = []
for i in range(N):
  for j in range(i+1,N):
    a,b = ls[i]
    x,y = ls[j]
    pls += [(x-a,y-b)]
ans = 10**10
for X,Y in pls:
  s = set()
  m = 0
  for x,y in ls:
    if (x-X, y-Y) not in s:
      m += 1
    s.add((x,y))
  ans = min(m,ans)
if N==1:
  ans = 1
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
p = [[0, 0] for _ in range(n)]
for i in range(n):
  p[i] = list(map(int, input().split()))
p.sort()

st = dict()
for i in range(n-1):
  for j in range(i+1, n):
    st[(p[j][0]-p[i][0], p[j][1]-p[i][1])] = st.get((p[j][0]-p[i][0], p[j][1]-p[i][1]), 0) + 1
  
mx = 0
for key in st:
  mx = max(mx, st[key])
  
print(n-mx)

Submission status: Accepted

Solution code:
import sys

N=int(input())
if N<=2:
  print(1)
  sys.exit(0)

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

pqset=set()
for i in range(N):
  x1,y1=xylist[i]
  for j in range(i+1,N):
    x2,y2=xylist[j]
    p=x2-x1
    q=y2-y1
    pqset.add((p,q))
#print(len(pqset))
    
answer=50
for p,q in pqset:
  comp_num=N
  for i in range(N):
    x1,y1=xylist[i]
    for j in range(i+1,N):
      x2,y2=xylist[j]
      if p==x2-x1 and q==y2-y1:
        comp_num-=1
        
  answer=min(answer,comp_num)
    
print(answer)

Submission status: Accepted

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

def get_par(x):
  if x == par_list[x]:
    return x
  else:
    par_list[x] = get_par(par_list[x])
    return par_list[x]

def merge(x,y):
  par_x = get_par(x)
  par_y = get_par(y)
  if par_x != par_y:
    par_list[par_y] = par_x

def is_same(x,y):
  return get_par(x) == get_par(y)

N=int(input())
if N<=2:
  print(1)
  sys.exit(0)

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

pqset=set()
for i in range(N):
  x1,y1=xylist[i]
  for j in range(i+1,N):
    x2,y2=xylist[j]
    p=x2-x1
    q=y2-y1
    pqset.add((p,q))
#print(len(pqset))
    
answer=50
for p,q in pqset:
  par_list=list(range(N))
  for i in range(N):
    x1,y1=xylist[i]
    for j in range(i+1,N):
      x2,y2=xylist[j]
      if p==x2-x1 and q==y2-y1:
        merge(i,j)
        
  comp_set=set()
  for i in range(N):
    comp_set.add(get_par(i))
  answer=min(answer,len(comp_set))
    
print(answer)

Submission status: Accepted

Solution code:
n=int(input())
dic={}
d=[list(map(int,input().split())) for i in range(n)]
for i in range(n-1):
    for j in range(i+1,n):
        if (d[i][0]-d[j][0],d[i][1]-d[j][1]) in dic:
            dic[(d[i][0]-d[j][0],d[i][1]-d[j][1])]+=1
            dic[(d[j][0]-d[i][0],d[j][1]-d[i][1])]+=1
        else:
            dic[(d[i][0]-d[j][0],d[i][1]-d[j][1])]=1
            dic[(d[j][0]-d[i][0],d[j][1]-d[i][1])]=1
ans=0
for i in dic.values():
    ans=max(ans,i)
print(n-ans)

Submission status: Accepted

Solution code:
from itertools import combinations

N = int(input())
l = [tuple(map(int, input().split())) for _ in range(N)]
t = {i for i in l}

if N==1 or N==2:
    print(1)
else:
    ans = N
    for i in range(N):
        for j, k in combinations([l[j] for j in range(N) if j!=i], 2):
            x1, y1 = j
            x2, y2 = k
            x, y = x1-x2, y1-y2

            b = 1
            for m in range(N):
                if i==m:continue
                x3, y3 = l[m]
                if not (x3-x, y3-y) in t:
                    b += 1
            ans = min(ans, b)
    print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

n = int(input())
M = []
for i in range(n):
    x, y = map(int, input().split())
    M.append([x, y])
M.sort(key=lambda x: (x[0], x[1]))
X = defaultdict(int)
for i in range(n - 1):
    for j in range(i + 1, n):
        a = M[i][0] - M[j][0]
        b = M[i][1] - M[j][1]
        X[(a, b)] += 1
print(n - max(X.values(), default=0))

Submission status: Accepted

Solution code:
from collections import defaultdict as de
X=de(int)
n=int(input())
a=sorted([list(map(int,input().split()))for i in range(n)])
for i in range(n):
    for j in range(i):
        X[(a[i][0]-a[j][0],a[i][1]-a[j][1])]+=1
print(n-max(X.values(),default=0))

Submission status: Accepted

Solution code:
n=int(input())
M=[]
for i in range(n):
    x,y=map(int,input().split())
    M.append([x,y])
M.sort(key=lambda x:(x[0],x[1]))
X=[]
Y=[]
for i in range(n-1):
    for j in range(i+1,n):
        a=M[i][0]-M[j][0]
        b=M[i][1]-M[j][1]
        if not [a,b] in Y:
            Y.append([a,b])
            X.append(1)
        else:
            X[Y.index([a,b])]+=1
ans=n
for i in range(len(Y)):
    ans=min(ans,n-X[i])
print(ans)

Submission status: Accepted

Solution code:
import itertools
from collections import defaultdict
n = int(input())
xy = [list(map(int, input().split())) for _ in range(n)]
dd = defaultdict(int)
for xy1, xy2 in itertools.combinations(xy, 2):
    x1, y1 = xy1
    x2, y2 = xy2
    unit_vect = (x1-x2, y1-y2)
    dd[unit_vect] += 1
    unit_vect = (x2-x1, y2-y1)
    dd[unit_vect] += 1

if n == 1:
    ans = 1
else:
    ans = n-max(dd.values())
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
xy = [list(map(int, input().split())) for _ in range(n)]
xy.sort()
vectors = set()
for i in range(n-1):
    for j in range(i+1, n):
        xi, yi = xy[i]
        xj, yj = xy[j]
        if xj-xi == 0 and yj-yi == 0:
            continue
        unit_vector = (xj-xi, yj-yi)
        vectors |= {unit_vector}
ans = n
for vector in vectors:
    cnt = 0
    for i in range(n-1):
        for j in range(i+1, n):
            xi, yi = xy[i]
            xj, yj = xy[j]
            if vector == (xj-xi, yj-yi):
                cnt += 1
    ans = min(ans, n-cnt)
print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time


def I(): return int(input())


def MI(): return map(int, input().split())


def S(): return input()


def MS(): return map(str, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


def input(): return sys.stdin.readline().rstrip()


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


def print_matrix(mat):
    for i in range(len(mat)):
        print(*mat[i])


YNL = {False: 'No', True: 'Yes'}
YNU = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**10
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
# sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']


# show_flg = True
show_flg = False

def cost(x, y, initial, N):
    a = x[initial]
    b = y[initial]
    for i in range(N):
        if i == initial:
            continue

    return 0


def main():
    N = I()
    x = [0] * N
    y = [0] * N
    ans = 0
    dist = [[None] * N for i in range(N)]

    if N == 1:
        print(1)
        return

    for i in range(N):
        x[i], y[i] = MI()

    for i in range(N):
        for j in range(N):
            if i == j:
                continue
            dist[i][j] = str(x[j] - x[i]) + "," + str(y[j] - y[i])

    # print_matrix(dist)

    c = defaultdict(int)
    ans = 1
    for i in range(N):
        for j in range(N):
            if dist[i][j] == None:
                continue
            c[dist[i][j]] += 1

    mcost = max(c.values())
    print(N - mcost)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import combinations
n = int(input())
if n == 1:
  print(1)
  exit(0)
pos = []
for i in range(n):
  pos.append(tuple(map(int,input().split())))
ans = 1e100
def cost(p,q):
  ret = 0
  for i,j in pos:
    ret += 1 - ((i+p,j+q) in pos)
  return ret
for a,b in combinations(pos, 2):
  ans = min(ans, cost(a[0]-b[0],a[1]-b[1]))
print(ans)

Submission status: Accepted

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

count = 0
for i in range(n-1):
    for j in range(i+1, n):
        p, q = xy[j][0] - xy[i][0], xy[j][1] - xy[i][1]
        count = max(count, sum((x-p,y-q) in s_xy for x, y in s_xy))

print(n - count)

Submission status: Accepted

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

count = 0
for i in range(n-1):
    for j in range(i+1, n):
        p, q = xy[j][0] - xy[i][0], xy[j][1] - xy[i][1]
        count = max(count, sum((x-p,y-q) in set(xy) for x, y in xy))

print(n - count)

Submission status: Accepted

Solution code:
#https://atcoder.jp/contests/diverta2019-2/submissions/11229318
n = int(input())
t = [tuple(map(int, input().split())) for _ in range(n)]
s = set(t)
cnt = 0
for i in range(n-1):
  for j in range(i+1,n):
    u,v = t[i]
    x,y = t[j]
    p = u-x; q = v-y
    c = sum((x-p, y-q) in s for x,y in t)
    if cnt < c: cnt = c
print(n-cnt)

Submission status: Accepted

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

count = 0
for i in range(n-1):
    for j in range(i+1, n):
        ix, iy = xy[i]
        jx, jy = xy[j]
        p = jx - ix
        q = jy - iy
        tc = sum((x-p,y-q) in xy for x, y in s_xy)

        count = max(count, tc)

print(n-count)

Submission status: Accepted

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

count = 0
for i in range(n-1):
    for j in range(i+1, n):
        ix, iy = xy[i]
        jx, jy = xy[j]
        p, q = jx - ix, jy - iy
        tc = sum((x-p,y-q) in xy for x, y in s_xy)

        count = max(count, tc)

print(n-count)

Submission status: Accepted

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

count = 0
for i in range(n-1):
    for j in range(i+1, n):
        p, q = xy[j][0] - xy[i][0], xy[j][1] - xy[i][1]
        tc = sum((x-p,y-q) in xy for x, y in s_xy)
        if count <= tc:
            count = tc
            
print(n-count)

Submission status: Accepted

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

count = 0
for i in range(n-1):
    for j in range(i+1, n):
        p, q = xy[j][0] - xy[i][0], xy[j][1] - xy[i][1]
        tc = sum((x-p,y-q) in xy for x, y in s_xy)
        count = max(count, tc)

print(n-count)

Submission status: Accepted

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

count = 0
for i in range(n-1):
    for j in range(i+1, n):
        p, q = xy[j][0] - xy[i][0], xy[j][1] - xy[i][1]
        count = max(count, sum((x-p,y-q) in xy for x, y in s_xy))

print(n-count)

Submission status: Accepted

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

count = 0
for i in range(n-1):
    for j in range(i+1, n):
        p, q = xy[j][0] - xy[i][0], xy[j][1] - xy[i][1]
        count = max(count, sum((x-p,y-q) in xy for x, y in set(xy)))

print(n-count)

Submission status: Accepted

Solution code:

import numpy as np
from functools import *
import sys
sys.setrecursionlimit(100000)
input = sys.stdin.readline




def acinput():
    return list(map(int, input().split(" ")))


def II():
    return int(input())

directions=np.array([[1,0],[0,1],[-1,0],[0,-1]])
directions = list(map(np.array, directions))

mod = 10**9+7


def factorial(n):
    fact = 1
    for integer in range(1, n + 1):
        fact *= integer
    return fact



def serch(x, count):
    #print("top", x, count)
            

    for d in directions:
        nx = d+x
        #print(nx)
        if np.all(0 <= nx) and np.all(nx < (H, W)):
            if field[nx[0]][nx[1]] == "E":
                count += 1 
                field[nx[0]][nx[1]] = "V"
                count = serch(nx, count)  
                continue
            if field[nx[0]][nx[1]] == "#":
                field[nx[0]][nx[1]] = "V"
                count = serch(nx, count)    
                 
    return count

N=int(input())

x= [np.array(acinput())for i in range(N)]
#x = [acinput() for i in range(N)]
#print(tmp)
#x=sorted(tmp)

import itertools as it

from collections import defaultdict
#es=10**10

#dc={}
dc=defaultdict(int)

for cb in it.combinations(x,2):
    d=cb[0]-cb[1]
    d2=tuple(-d)
    d=tuple(d)
    dc[d]+=1
    dc[d2]+=1

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

Submission status: Accepted

Solution code:
n = int(input())
t = [tuple(map(int, input().split())) for _ in range(n)]
s = set(t)
cnt = 0
for i in range(n-1):
  for j in range(i+1,n):
    u,v = t[i]
    x,y = t[j]
    p = u-x; q = v-y
    c = sum((x-p, y-q) in s for x,y in t)
    if cnt < c: cnt = c
print(n-cnt)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10000000)
from collections import defaultdict
mod = 10**9+7

N = int(input())
xy = [list(map(int, input().split())) for i in range(N)]
cnt = defaultdict(int)
for i in range(N):
    for j in range(i+1, N):
        a, b = xy[j][0]-xy[i][0], xy[j][1]-xy[i][1]
        cnt[(a, b)] += 1
        cnt[(-a, -b)] += 1
if N == 1:
    print(1)
else:
    print(N-max(cnt.values()))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10000000)
from collections import defaultdict
mod = 10**9+7

N = int(input())
xy = [list(map(int, input().split())) for i in range(N)]
xy.sort()
Ans = N
for i in range(N):
    for j in range(i+1, N):
        a, b = xy[j][0]-xy[i][0], xy[j][1]-xy[i][1]
        ans = N
        for k in range(N):
            for l in range(k+1, N):
                if xy[k][0]+a == xy[l][0] and xy[k][1]+b == xy[l][1]:
                    ans -= 1
        Ans = min(Ans, ans)
print(Ans)

Submission status: Accepted

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

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

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

d = defaultdict(int)
for i, j in itertools.combinations(range(N), 2):
    d[(balls[j][0] - balls[i][0], balls[j][1] - balls[i][1])] += 1
print(N - max(d.values()))

Submission status: Accepted

Solution code:
from collections import *
from heapq import *
from itertools import *
from fractions import gcd
import sys
from decimal import *
input=lambda :sys.stdin.readline().rstrip()

N=int(input())
if N==1:
    print(1)
    exit()
XY=[list(map(int,input().split())) for i in range(N)]
itelst=combinations(range(N),2)

alst=[]
for a,b in itelst:
    x1,y1=XY[a]
    x2,y2=XY[b]
    Y=y1-y2;X=x1-x2
    if X and Y:
        alst.append([X,Y])
    elif Y or X:
        alst.append([X,Y])



value=50
idlemax=10**18
for Xa,Ya in alst:
    n=set([x+idlemax*y for x,y in XY])

    count=0
    for x,y in XY:
        if x+idlemax*y in n:
            count+=1
            a=0;b=0
            A=x+Xa+a+idlemax*(y+Ya+b)
            while A in n:
                n.remove(A)
                a+=Xa;b+=Ya
                A=x+Xa+a+idlemax*(y+Ya+b)

            a=0;b=0
            A=x-Xa-a+idlemax*(y-Ya-b)
            while A in n:
                n.remove(A)
                a+=Xa;b+=Ya
                A=x-Xa-a+idlemax*(y-Ya-b)
    value=min(value,count)
print(value)

Submission status: Accepted

Solution code:
from collections import defaultdict


def solve():
    N = int(input())
    if N == 1:
        print(1)
        exit()
    xy = [[0, 0] for _ in range(N)]
    for i in range(N):
        xy[i][0], xy[i][1] = map(int, input().split())
    
    dxy = defaultdict(int)
    for i in range(N - 1):
        for j in range(i + 1, N):
            dxy[(xy[i][0] - xy[j][0], xy[i][1] - xy[j][1])] += 1
            dxy[(xy[j][0] - xy[i][0], xy[j][1] - xy[i][1])] += 1
    
    zeros = max(dxy.values())
    print(N - zeros)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
from collections import Counter
N = int(input())
P = list(tuple(map(int, input().split())) for _ in range(N))
P = sorted(P)

p_q_cand = []
for i in range(N):
    for j in range(i+1, N):
        diff_p = P[j][0]-P[i][0]
        diff_q = P[j][1]-P[i][1]
        p_q_cand.append((diff_p, diff_q))

if N == 1:
    print(1)
else:
    C = Counter(p_q_cand)
    ans = float('inf')
    for v, c in C.items():
        p = v[0]
        q = v[1]
        tmp = 0
        used = set()
        for a, b in sorted(list(P), key=lambda x: (x[0], x[1])):
            if (a-p, b-q) not in used:
                tmp += 1
            used.add((a, b))
        ans = min(ans, tmp)
    print(ans)

Submission status: Accepted

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

count = []
for ((x1,x2),(x3,x4)) in combinations(xy, 2):
    count.append((x1-x3,x2-x4))
    count.append((x3-x1,x4-x2))
    
c = Counter(count)
m = 0
for i in c.values():
    m = max(m, i)

if N == 1:
    print(1)
else:
    print(N-m)

Submission status: Accepted

Solution code:
n=int(input())
if n==1:
  print(1)
  exit()
l=[list(map(int,input().split())) for _ in range(n)]
d=[]
for i in range(n):
  for j in range(n):
    if i!=j:
      d.append((l[i][0]-l[j][0],l[i][1]-l[j][1]))
from collections import Counter as c
print(n-c(d).most_common()[0][1])

Submission status: Accepted

Solution code:
import sys
from collections import Counter

readline = sys.stdin.readline
n = int(readline())
xy = [list(map(int, readline().split())) for _ in range(n)]

d = []
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]
        d.append((p, q))
        d.append((-p, -q))

if n > 1:
    ans = n - max(Counter(d).values())
else:
    ans = 1

print(ans)

Submission status: Accepted

Solution code:
def main():
    balls = int(input())
    coordinates = []
    answer = 1
    count_delta = {}
    for _ in range(balls):
        coordinates.append(list(map(int, input().split())))
    coordinates.sort()
    if balls > 1:
        for i in range(balls):
            for j in range(i + 1, balls):
                d = (coordinates[j][0] - coordinates[i][0], coordinates[j][1] - coordinates[i][1])
                if d in count_delta:
                    count_delta[d] += 1
                else:
                    count_delta[d] = 1
        answer = balls - max(count_delta.values())
    print(answer)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

li = {}
for i in range(N):
    for j in range(N):
        if i==j:
            continue

        x1,y1 = XY[i][0],XY[i][1]
        x2,y2 = XY[j][0],XY[j][1]

        mm1 = x2-x1
        mm2 = y2-y1
        # if mm1<0 and mm2<0:
        #     mm1 *= -1
        #     mm2 *= -1
        PQ = (mm1, mm2)

        if PQ in li:
            li[PQ] += 1
        else:
            li[PQ] = 1

mm = 0
for i in li:
    mm = max(mm,li[i])
print(N-mm)

Submission status: Accepted

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

if n == 1:
    print(1)
    exit()
    
pq = []
for i in range(n):
    for j in range(n):
        if i != j:
            pq.append((xy[i][0] - xy[j][0] ,xy[i][1] - xy[j][1]))

ans = float("inf")
for p, q in pq:
    tmp = 0
    for i in range(n):
        for j in range(n):
            if i != j and (p, q) == (xy[i][0] - xy[j][0] ,xy[i][1] - xy[j][1]):
                tmp += 1
        ans = min(ans, n - tmp)
            
print(ans)

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    a = [None]*n
    for i in range(n):
        x, y = map(int, input().split())
        a[i] = [x, y]
    p, q = 0, 0
    cnt = 0
    for i in range(n):
        for j in range(n):
            if i == j:
                continue
            sp, sq = a[i][0]-a[j][0], a[i][1]-a[j][1]
            scnt = 0
            for k in range(n):
                for l in range(n):
                    if k == l:
                        continue
                    if a[k][0]-a[l][0] == sp and a[k][1]-a[l][1] == sq:
                        scnt += 1
            if scnt > cnt:
                cnt = scnt
                p = sp
                q = sq
    print(n-cnt)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
N = int(input())

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

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

#
import collections
xy_frq_dict = collections.defaultdict(int)
for i in range(N):
    for j in range(N):
        if i == j:
            continue

        x, y = X[i] - X[j], Y[i] - Y[j]
        xy_frq_dict[(x, y)] += 1

xy_frq_pairs = list(xy_frq_dict.items())
xy_frq_pairs.sort(key=lambda x: x[1])
ret = N - xy_frq_pairs[-1][1]
print(ret)

Submission status: Accepted

Solution code:
from collections import Counter
n= int(input())
if n==1:
  print(1)
  exit()
xy=[[int(x) for x in input().split()] for _ in range(n)]
gr = [[[0,0]for _ in range(n)]for _ in range(n)]
for i in range(n):
  a,b = xy[i]
  for j in range(n):
    gr[i][j] = [xy[j][0]-a,xy[j][1]-b]
gr1 = []
for i in gr:
  for j in i:
    gr1.append(tuple(j))
#print(gr1)
c = Counter(gr1)
l,f = c.most_common()[0]
if l!=(0,0):
  print(n-f)
else:
  l,f = c.most_common()[1]
  print(n-f)

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    A = [[int(i) for i in input().split()] for j in range(N)]
    if N == 1:
        return print(1)
    A.sort()
    from collections import defaultdict
    cnt = defaultdict(int)
    for i in range(N):
        for j in range(i+1, N):
            # print(A[i], A[j], (A[j][0] - A[i][0], A[j][1] - A[i][1]))
            cnt[(A[j][0] - A[i][0], A[j][1] - A[i][1])] += 1
    # print(cnt.values())
    ans = (N-1) - (sorted(cnt.values())[-1] - 1)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())

points = [list(map(int, input().split(" "))) for _ in range(n)]
X = 0
Y = 1
ans = 10 ** 14
if n == 1:
    ans = 1
else:
    for i in range(n):
        for j in range(n):
            if i == j:
                continue
            x1, y1 = points[i]
            x2, y2 = points[j]
            p = x1 - x2
            q = y1 - y2
            cost = n
            for point1 in points:  # そのpointからcost0で遷移できる先があるかどうか
                fromx, fromy = point1
                for point2 in points:
                    tox, toy = point2
                    if fromx - tox == p and fromy - toy == q:
                        cost -= 1
                        break
            if ans > cost:
                ans = cost
print(ans)

Submission status: Accepted

Solution code:
N = int(input())

pos = []
for _ in range(N):
    tmp = tuple(map(int, input().split()))
    pos.append(tmp)

pos.sort()

dic = dict()
for i in range(N):
    for j in range(i+1,N):
        distance = (pos[j][0]-pos[i][0], pos[j][1]-pos[i][1])
        #print(f'{distance=}')
        if distance in dic:
            dic[distance] += 1
        else:
            dic[distance] = 1
if dic :
    max_frenquency = max(dic.values())

    print(N-max_frenquency)
else:
    print(N)