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: Runtime Error

Solution code:
from collections import defaultdict
n=int(input())
xy=[list(map(int,input().split())) for _ in range(n)]
d=defaultdict(lambda:0)
for i in range(n-1):
  for j in range(i+1,n):
    dx=xy[i][0]-xy[j][0]
    dy=xy[i][1]-xy[j][1]
    d[(dx,dy)]+=1
    d[(-dx,-dy)]+=1
print(n-max(d.values()))

Submission status: Runtime Error

Solution code:
def main():
    import sys
    from collections import defaultdict
    input = sys.stdin.readline
    N = int(input())
    XY = sorted([tuple([int(x) for x in input().strip().split()]) for _ in range(N)], key=lambda x: x[0])
    dic = defaultdict(int)
    for d in range(1, N):
        for i in range(N-d):
            if XY[i+d][1] > XY[i][1]:
                dic[(XY[i+d][0]-XY[i][0], XY[i+d][1]-XY[i][1])] += 1

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

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from sys import stdin
import collections
import numpy as np
N= list(map(int, stdin.readline().strip().split()))[0]
XY=[list(map(int,input().split())) for i in range(N)]
pq=[]

for i in range(N-1):
    X = XY[i + 1][0] - XY[i][0]
    Y = XY[i + 1][1] - XY[i][1]
    pq.append((X,Y))
clist = collections.Counter(pq)
p,q=(clist.most_common()[0][0])
count=1
for i in range(1,N):
    X,Y=XY[i]
    XX,YY=XY[i-1]
    X-=p
    Y-=q
    if XX!=X or YY!=Y:
        count+=1
print(count)

Submission status: Runtime Error

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

D={}
for i in range(N-1):
    t1=L[i]
    L2=L[i+1:]
    for t2 in L2:
        x1,y1=t1
        x2,y2=t2
        d1=(x2-x1,y2-y1)
        d2=(x1-x2,y1-y2)
        if d1 in D:
            D[(x2-x1,y2-y1)]+=1
        else:
            D[(x2-x1,y2-y1)]=1
        if d2 in D:
            D[(x1-x2,y1-y2)]+=1
        else:
            D[(x1-x2,y1-y2)]=1

print(max(N-max(D.values()),0))

Submission status: Runtime Error

Solution code:
n=int(input())
x=[0]*n
y=[0]*n

for i in range(n):
    x[i],y[i]=map(int,input().split())
dis=[]
for i in range(n-1):
    for j in range(i+1,n):
        dis.append((x[j]-x[i],y[j]-y[i]))
        
from collections import Counter
c=Counter(dis).most_common()[0]
print(n-c[1])

Submission status: Runtime Error

Solution code:
n=int(input())
a=[[int(i) for i in input().split()] for i in range(n)]
x_dis=[0]*(n-1)
y_dis=[0]*(n-1)

for i in range(n-1):
    x_dis[i]=a[i+1][0]-a[i][0]
    y_dis[i]=a[i+1][1]-a[i][1]

import collections

cx=collections.Counter(x_dis).most_common()[0]
cy=collections.Counter(y_dis).most_common()[0]

print(n-min(cx[1],cy[1]))

Submission status: Runtime Error

Solution code:
import collections

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

div = []
for i in range(N):
    for j in range(N):
        if(i == j):
            continue
        div.append(tuple((X[i][0]-X[j][0], X[i][1]-X[j][1])))
        
c = collections.Counter(div)
c_s = sorted(c.items(), key=lambda x:x[1], reverse=True)

print(N-c_s[0][1])

Submission status: Runtime Error

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from collections import defaultdict

n = int(readline())
xy = [list(map(int, readline().split())) for _ in range(n)]
dict = defaultdict(int)
for i, check in enumerate(xy):
    for dxy in xy[i + 1:]:
        y, x = check[0], check[1]
        dy, dx = dxy[0], dxy[1]
        dict[(y - dy, x - dx)] += 1
print(n - max(dict.values()))

Submission status: Runtime Error

Solution code:
import sys
import math  # noqa
import bisect  # noqa
import queue  # noqa


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


def main():
    N = int(input())
    X = [0 for _ in range(N)]
    Y = [0 for _ in range(N)]
    for i in range(N):
        x, y = map(int, input().split())
        X[i] = x
        Y[i] = y

    cnt = {}
    for i in range(N):
        for j in range(N):
            if i == j:
                continue
            rx = X[i] - X[j]
            ry = Y[i] - Y[j]
            if (rx, ry) not in cnt:
                cnt[(rx, ry)] = 1
            else:
                cnt[(rx, ry)] += 1
            if (-rx, -ry) not in cnt:
                cnt[(-rx, -ry)] = 1
            else:
                cnt[(-rx, -ry)] += 1

    cnt = [[v, k] for k, v in cnt.items()]
    cnt.sort(reverse=True)
    res = N - cnt[0][0] // 2
    print(res)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

#pq=[[0]*n for _ in range(n)]

#初期値が0の辞書
from collections import defaultdict
pq_x = defaultdict(lambda: set([])) 
pq_y = defaultdict(lambda: set([])) 

for i,from_xy in enumerate(zahyou):
    for j,to_xy in enumerate(zahyou[i+1:]):
        #print(i,j+i+1)
        pq_x[(from_xy[0]-to_xy[0],from_xy[1]-to_xy[1])].add((i))
        pq_y[(from_xy[0]-to_xy[0],from_xy[1]-to_xy[1])].add((j+i+1))

#print(pq_x)
#print(pq_y)

result=10**9
for item in pq_x.keys():
    len_x=len(list(pq_x[item]))
    len_y=len(list(pq_y[item]))
    min_xy=min(len_x,len_y)+1
    temp=max(n-1-min_xy)

    result=min(result,temp)

print(result)

Submission status: Runtime Error

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

#pq=[[0]*n for _ in range(n)]

#初期値が0の辞書
from collections import defaultdict
pq_x = defaultdict(lambda: set([])) 
pq_y = defaultdict(lambda: set([])) 

for i,from_xy in enumerate(zahyou):
    for j,to_xy in enumerate(zahyou[i+1:]):
        #print(i,j+i+1)
        pq_x[(from_xy[0]-to_xy[0],from_xy[1]-to_xy[1])].add((i))
        pq_y[(from_xy[0]-to_xy[0],from_xy[1]-to_xy[1])].add((j+i+1))

print(pq_x)
print(pq_y)

result=10**9
for item in pq_x.keys():
    len_x=len(list(pq_x[item]))
    len_y=len(list(pq_y[item]))
    min_xy=min(len_x,len_y)+1
    temp=max(n-1-min_xy)

    result=min(result,temp)

print(result)

Submission status: Runtime Error

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

d = {}
for i in range(N):
    tmp = set()
    for j in range(N):
        if i == j:
            continue
        dx = xy[i][0] - xy[j][0]
        dy = xy[i][1] - xy[j][1]

        if (dx, dy) in tmp:
            continue
        if (dx, dy) not in d:
            d[(dx, dy)] = 1
        else:
            d[(dx, dy)] += 1
        tmp.add((dx, dy))

d = sorted(d.items(), key=lambda x: x[1], reverse=True)
cnt = d[0][1]
print(N - cnt)

Submission status: Runtime Error

Solution code:
import copy
import math

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

def dfs(parent, p, q):
    tosee.remove(parent)
    group[-1].append(parent)
    for el in tosee:
        x, y = el
        if x + p == parent[0] and y + q == parent[1] or \
                x - p == parent[0] and y - q == parent[1]:
            dfs(el,p,q)

m = math.inf
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]

        group = []
        tosee = copy.copy(xy)
        while tosee:
            el = tosee[0]
            group.append([])
            dfs(el,p,q)
            # print(tosee)
        temp = len(group)
        m = min(temp, m)
        # print(p, q, group)
print(m)

Submission status: Runtime Error

Solution code:
n = int(input())
xy = sorted([tuple(map(int,input().split())) for i in range(n)])
dif = []
for i in range(n-1):
    dif.append(tuple([xy[i+1][0]-xy[i][0],xy[i+1][1]-xy[i][1]]))
from collections import Counter
c = Counter(dif)
print(n-c[list(c)[0]])

Submission status: Runtime Error

Solution code:
from operator import itemgetter
from collections import defaultdict
n = int(input())
xy = sorted([list(map(int, input().split())) for i in range(n)], key = itemgetter(0,1))
a = defaultdict(int)
for key,(x1,y1) in enumerate(xy):
  for x2,y2 in xy[key+1:]:
    p,q = x2-x1, y2-y1
    if p != 0 or q != 0:
      a[(p,q)] += 1
ans = n - max(a.values())
print(ans)

Submission status: Runtime Error

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
print(dif)
print(n - max([dif[i] for i in dif.keys()]))

Submission status: Runtime Error

Solution code:
n = int(input())
data = []
for i in range(n):
    data.append(list(map(int, input().split())))
dif = dict()
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
print(n - max([dif[i] for i in dif.keys()]))

Submission status: Runtime Error

Solution code:
N = int(input())
crd = []

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

dic = dict()

for i in range(N - 1):
    for j in range(i + 1, N):
        dx = abs(crd[i][0] - crd[j][0])
        dy = abs(crd[i][1] - crd[j][1])
        if str(dx) + "_" + str(dy) in dic:
            dic[str(dx) + "_" + str(dy)] += 1
        else:
            dic[str(dx) + "_" + str(dy)] = 1

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

Submission status: Runtime Error

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

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

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

Submission status: Runtime Error

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

nodes.sort(reverse=True)
ans = 0
while nodes:
    ans += 1
    x, y = nodes.pop()
    for i, j in nodes[::-1]:
        if x-i != 0 and y-j != 0:
            vect = (i-x, j-y)
            break
    p, q = vect
    rm_list = []
    for i, j in nodes:
        if i-x == 0 or j-y == 0:
            continue
        if (i-x) % p == 0 and (j-y) % q == 0:
            rm_list.append((i, j))
    for item in rm_list:
        nodes.remove(item)
print(ans)

Submission status: Runtime Error

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

    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: Runtime Error

Solution code:
n = int(input())
li = []
for i in range(n):
    x, y = map(int, input().split())
    li.append([x, y])
ans = []
li = sorted(li, key=lambda x: x[0])
if n == 1:
    print(1)
else:
    for i in range(n - 1):
        for j in range(i + 1, n):
            ans.append((li[j][0] - li[i][0], li[j][1] - li[i][1]))
import collections
m = max(collections.Counter(ans).values())
print(n - m)

Submission status: Runtime Error

Solution code:
n=int(input())
li=[]
for i in range(n):
    x,y=map(int,input().split())
    li.append([x,y])
ans=[]
li=sorted(li, key=lambda x: x[0])
if n==1:
  print(1)
else:
  for i in range(n-1):
    for j in range(i+1,n):
        ans.append((li[j][0]-li[i][0],li[j][1]-li[i][1]))
import collections
m=max(collections.Counter(ans).values())
print(n-m)

Submission status: Runtime Error

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

#es=10**10

dc={}

for cb in it.combinations(x,2):
    d=cb[0]-cb[1]
    try:
        d=tuple(d)
        dc[d]+=1
    except:
        dc[d]=1
    continue
""" 
    dc[d[0],d[1]]+=1
    count=0
    
    for cb2 in it.combinations(x, 2):
        d2=cb2[0]-cb2[1]
        if np.all(d==d2):
            count+=1
    
    res=min(res,N-count) """

#print(dc)    
print(N-max(dc.values()))

Submission status: Runtime Error

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

#es=10**10

dc={}

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

    dc[d[0],d[1]]+=1
    count=0
    
    for cb2 in it.combinations(x, 2):
        d2=cb2[0]-cb2[1]
        if np.all(d==d2):
            count+=1
    
    res=min(res,N-count)

#print(dc)    
print(N-max(dc.values()))

Submission status: Runtime Error

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
print(N-max(cnt.values()))

Submission status: Runtime Error

Solution code:
import itertools
from collections import defaultdict

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

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: Runtime Error

Solution code:
from collections import defaultdict


def solve():
    N = int(input())
    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: Runtime Error

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

p_q_cand = []
for p in P:
    for q in P:
        if p == q:
            continue
        diff_p = p[0]-q[0]
        diff_q = p[1]-q[1]
        p_q_cand.append((abs(diff_p), abs(diff_q)))

C = Counter(p_q_cand)
p, q = C.most_common()[0][0]
ans = 0
used = set()
for a, b in sorted(P):
    if (a-p, b-q) not in used:
        ans += 1
    used.add((a, b))
print(ans)

Submission status: Runtime Error

Solution code:
n=int(input())
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: Runtime Error

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

#
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: Runtime Error

Solution code:
from collections import Counter
n= int(input())
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: Runtime Error

Solution code:
from collections import Counter
n= int(input())
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] = [abs(xy[j][0]-a),abs(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//2)
else:
  l,f = c.most_common()[1]
  print(n-f//2)

Submission status: Runtime Error

Solution code:
def main():
    N = int(input())
    A = [[int(i) for i in input().split()] for j in range(N)]
    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: Runtime Error

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

max_frenquency = max(dic.values())

print(N-max_frenquency)

Submission status: Runtime Error

Solution code:
def main():
    import sys
    input=sys.stdin.readline   
    sys.setrecursionlimit(100000000)

    n=int(input())
    point=[tuple(map(int,input().split())) for _ in range(n)]
    dic={i:j for i,j in zip(point,range(n))}
    

    ans=10**9
    for i in range(n-1):
        for j in range(i+1,n):
            p=point[j][0]-point[i][0]
            q=point[j][1]-point[i][1]
            cnt=0
            visited=[True]*n

            def dfs(x,y,p,q):
                if (x+p,y+q) in dic:
                    idx=dic[(x+p,y+q)]
                    if visited[idx]:
                        visited[idx]=False
                        dfs(x+p,y+q,p,q)
                if (x-p,y-q) in dic:
                    idx=dic[(x-p,y-q)]
                    if visited[idx]:
                        visited[idx]=False
                        dfs(x-p,y-q,p,q)

            for k in range(n):
                if visited[k]:
                    cnt+=1
                    dfs(point[k][0],point[k][1],p,q)      

            ans=min(ans,cnt)  
    print(cnt)

if __name__=='__main__':
    main()

Submission status: Runtime Error

Solution code:
N=int(input())
A=[list(map(int,input().split())) for i in range(N)]
B={}
for a,b in A:
  for c,d in A:
    if a>c:
      e=a-c
      f=b-d
    else:
      e=c-a
      f=d-b
    if e!=0 or f!=0:
      if (e,f) in B:
        B[(e,f)]+=1
      else:
        B[(e,f)]=1
        
a=max(B.values())
print(N-a//2)

Submission status: Runtime Error

Solution code:
from collections import Counter
N=int(input())
XY=[tuple(map(int, input().split())) for _ in range(N)]
PQ=[(x1-x2,y1-y2) for x1,y1 in XY for x2,y2 in XY if x1!=x2 or y1!=y2]
C=Counter(PQ)
print(N-C.most_common(1)[0][1])

Submission status: Runtime Error

Solution code:
import itertools
import collections

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

count = collections.defaultdict(int)
for i in itertools.combinations(x_y, 2):
    count[(i[0][0]-i[1][0], i[0][1]-i[1][1])] += 1
    count[(i[1][0]-i[0][0], i[1][1]-i[0][1])] += 1

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

Submission status: Runtime Error

Solution code:
from collections import Counter
N = int(input())
X = []
for i in range(N):
    x,y = map(int,input().split())
    X.append((x,y))
kouho = []
for i in range(N):
    for j in range(N):
        if i==j:continue
        kouho.append((X[i][0]-X[j][0],X[i][1]-X[j][1]))
C = Counter(kouho)
print(N-max(C.values()))

Submission status: Runtime Error

Solution code:
from collections import defaultdict
N = int(input())
X, Y = [], []
for _ in range(N):
    x, y = map(int, input().split())
    X.append(x)
    Y.append(y)
d = defaultdict(int)
for i in range(N):
    for j in range(N):
        if i == j:
            continue
        p = X[i] - X[j]
        q = Y[i] - Y[j]
        d[(p, q)] += 1
print(N - max(d.values()))

Submission status: Runtime Error

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
n = int(readline())
lst1 = [list(map(int,readline().split())) for i in range(n)]

cost = 1

#同じベクトルでつなげる要素を最大化する。全点対象にベクトルを求め、多数決。
dic1 = dict()

for i in range(n-1):
    for j in range(i+1,n):
        x,y = lst1[i][0] - lst1[j][0] , lst1[i][1] - lst1[j][1]
        if (x,y) in dic1:
            dic1[(x,y)] += 1
        else:
            dic1[(x,y)] = 1

#線分は頂点-1個。そのうち同ベクトル数が免除される。
cost += n-1
cost -= max(dic1.values())

print(cost)

Submission status: Runtime Error

Solution code:
n = int(input())
l = []
for i in range(n):
    tmp = list(map(int,input().split()))
    l.append(tmp)

from collections import defaultdict
d = defaultdict(int)

for i in range(len(l)):
    for j in range(len(l)):
        difx = l[i][0] - l[j][0]
        dify = l[i][1] - l[j][1]
        if difx!=0 or dify!=0:
            dif = str(difx) + "_" + str(dify)
            d[dif] += 1

p_q = max((v,k) for (k,v) in d.items())[1]
p,q = p_q.split("_")

ans=0
for i in range(len(l)):
    found=False
    for j in range(len(l)):
        difx = l[i][0] - l[j][0]
        dify = l[i][1] - l[j][1]
        if difx==int(p) and dify==int(q):
            found=True
            break
    if not found:
        ans+=1
print(ans)

Submission status: Runtime Error

Solution code:
from collections import Counter
n = int(input())
XY = tuple(tuple(map(int, input().split())) for _ in range(n))
L = []
for i in range(n-1):
  for j in range(i+1, n):
    x1, y1 = XY[i]
    x2, y2 = XY[j]
    L.append((x1-x2, y1-y2))
    L.append((x2-x1, y2-y1))
C = Counter(L)
ans = n - C.most_common()[0][1]
print(ans)

Submission status: Runtime Error

Solution code:
from collections import Counter
n=int(input())
b=[tuple(map(int,input().split())) for _ in range(n)]
r=[(x[0]-y[0],x[1]-y[1]) for x in b for y in b if x!=y]
c=Counter(r).most_commom(1)
print(n-c[0][1] if c else n)

Submission status: Runtime Error

Solution code:
from collections import Counter

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

pq = []

for x, y in A:
    for i, j in A:
        if x == i and y == j:
            continue
        pq.append(str(i-x)+str(j-y))

ans = Counter(pq).most_common()

print(N - ans[0][1])

Submission status: Runtime Error

Solution code:
import collections

N = int(input())
xy = [list(map(int,input().split())) for i in range(N)]
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]))
#print(pq)
pqc = collections.Counter(pq)
x = pqc.most_common()[0][1]
print(N-x)

Submission status: Runtime Error

Solution code:



"""
・あるボールから（p,q）の移動で別のボールに移れるならコストが０、そうでなければ１
　→あるボールの位置(x,y) + (p,q) の位置にボールがあるかどうか、全てのボールについて確認する。なければコスト＋１
・p,qの選び方は、全ボールの間隔を試すと行けそう(N <= 50 なので間に合いそう)

"""



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

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 = N
for p,q in pq:
    cost = 0
    for x,y in xy:
        if  (x+p, y+q) not in xy:
            cost += 1

    ans = min(ans, cost)

print(cost)

Submission status: Runtime Error

Solution code:



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

"""
・あるボールから（p,q）の移動で別のボールに移れるならコストが０、そうでなければ１
　→あるボールの位置(x,y) + (p,q) の位置にボールがあるかどうか、全てのボールについて確認する。なければコスト＋１
・p,qの選び方は、全ボールの間隔を試すと行けそう(N <= 50 なので間に合いそう)

"""


pq = []
for i in range(N):
    for j in range(N):
        if i != j:
            # 同じ間隔（同じp,qのパターン）が起こりうるのでdictで管理するほうがいいかも
            pq.append((xy[i][0] - xy[j][0], xy[i][1] - xy[j][1]))

set_xy = set(xy)
ans = N
for p,q in pq:
    cost = 0
    for x,y in xy:
        if  (x+p, y+q) not in set_xy:
            cost += 1

    ans = min(ans, cost)

print(cost)

Submission status: Runtime Error

Solution code:
from collections import Counter
from itertools import permutations
n=int(input())
A=[list(map(int,input().split())) for i in range(n)]
B=[(a[0]-b[0],a[1]-b[1]) for a,b in permutations(A,2)]
most=max(Counter(B).values())
print(n-most if n!=1 else 1)

Submission status: Runtime Error

Solution code:
from collections import Counter
n=int(input())
A=[list(map(int,input().split())) for i in range(n)]
Per=[(a[0]-b[0],a[1]-b[1]) for a in A for b in A if a!=b]
print(n-Counter(Per).most_common(1)[0][1])

Submission status: Runtime Error

Solution code:
def main():
    from collections import Counter, namedtuple

    pt = namedtuple('pt', 'x y')

    def delta(a: pt, b: pt) -> pt:
        x = a.x - b.x
        y = a.y - b.y
        if x < 0:
            x = -x
            y = -y
        return pt(x=x, y=y)

    n = int(input())
    ps = [pt(*map(int, input().split())) for _ in range(n)]

    c = Counter(
        delta(a, b)
        for i, a in enumerate(ps)
        for j, b in enumerate(ps)
        if i < j
    )

    ma = max(c.values())

    print(n - ma)


if __name__ == '__main__':
    main()