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 itertools import combinations
N = int(input())
d = [list(map(int, input().split())) for _ in range(N)]

dd = dict()
t = 0

for n ,m in combinations(d, 2):
    if n[0] == m[0]:
        t += 1
    else:
        a = (m[1]-n[1])/(m[0]-n[0])
        if a in dd:
            dd[a] += 1
        else:
            dd.setdefault(a, 1)

print(N-max(t, *dd.values()))

Submission status: Runtime Error

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n = inp()
a = [inpl() for _ in range(n)]
c = []
for i,(x,y) in enumerate(a):
    for j,(z,w) in enumerate(a):
        if i == j: continue
        c.append(((x-z), (y-w)))
h = Counter(c)
print(n-max(h.values()))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))
# 受け渡されたすべての要素からsubだけ引く.リストを*をつけて展開しておくこと


def a_int(): return int(read())


def ints(): return list(map(int, read().split()))


def read_col(H):
    '''H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


def read_tuple(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_matrix(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    # return [list(map(int, read().split())) for _ in range(H)] # 内包表記はpypyでは遅いため


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter, xor, add
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  # , insort_left, insort_right
from functools import reduce
from math import gcd


def lcm(a, b):
    # 最小公倍数
    g = gcd(a, b)
    return a // g * b


# https://atcoder.jp/contests/diverta2019-2/tasks/diverta2019_2_b
N = a_int()
XY = read_tuple(N)
# q,pは何通りありえる？N**2//2通りぐらい
# p,qを決定したらあとは直線に乗っているか確かめれば良い
# 点に当たるたびにO(N)かけて調べれば良い
# 以下のO(n**4)のプログラムが可能
# for q,p全通り
#     while ある点を選択
#        その点の+p+qを見てボールを消す
#     コストをmin
# と思ったけど、ただ単純にp,qで拾えるボールの個数を数えればいいかも

PQcandi = []
for po1, po2 in combinations(XY, r=2):
    dx = po1[0] - po2[0]
    dy = po1[1] - po2[1]
    if dx < 0:
        dx *= -1
        dy *= -1
    elif dx == 0:
        dy = abs(dy)

    PQcandi.append((dx, dy))

print(N - max(Counter(PQcandi).values()))


# def del_ball(p, q, XYtmp):
#     ret = []
#     # x軸にソートしてあるので左から拾っていく
#     x, y = XYtmp[0]
#     for xxyy in XYtmp[1:]:
#         if xxyy == (x + p, y + q):
#             x += p
#             y += q
#         else:
#             ret.append(xxyy)

#     return ret


# from copy import deepcopy
# ans = INF
# for p, q in PQcandi:
#     XYtmp = deepcopy(XY)
#     anstmp = 0
#     while XYtmp:
#         anstmp += 1
#         XYtmp = del_ball(p, q, XYtmp)
#     # print(p, q, anstmp)
#     ans = min(ans, anstmp)
# print(ans)

Submission status: Runtime Error

Solution code:
n=int(input())
xy=[lnii() for i in range(n)]
xy.sort(key=lambda x:x[0])

ans=n

pq=[]
for i in range(n-1):
  for j in range(i+1,n):
    t_p=xy[j][0]-xy[i][0]
    t_q=xy[j][1]-xy[i][1]
    pq.append([t_p,t_q])

for p,q in pq:
  cnt=0
#  for x,y in xy:
#    if [x+p,y+q] in xy:
#      cnt+=1
  for i in range(n):
    for j in range(n):
      if i==j:
        continue
      x1,y1=xy[i]
      x2,y2=xy[j]
      if (x2-x1)==p and (y2-y1)==q:
        cnt+=1
  ans=min(ans,n-cnt)
print(ans)

Submission status: Runtime Error

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N = int(input())
XY = []
for _ in range(N):
    x, y = mapint()
    XY.append((x, y))

from collections import defaultdict, Counter
dic = []
for i in range(N):
    x1, y1 = XY[i]
    for j in range(N):
        if i==j:
            continue
        x2, y2 = XY[j]
        dx, dy = x2-x1, y2-y1
        if dx==0 and dy==0:
            continue
        dic.append((dx, dy))
c = Counter(dic)
(x, y), cnt = c.most_common()[0]
print(N-cnt)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
dic = defaultdict(int) #初期化する関数。

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

for i in range(N):
  for j in range(i+1,N):
    p = X[i][0] - X[j][0]
    q = X[i][1] - X[j][1]
    if p <0:
      p = -p;q=-q
    dic[(p,q)] +=1

path = max(dic.values())
ans = N-path
#print(dic)
print(ans)

Submission status: Runtime Error

Solution code:
from itertools import combinations
N = int(input())
X = [list(map(int,input().split())) for _ in range(N)]
C = {}
for z in combinations(X,2):
    x1,x2 = z
    a = x1[0]-x2[0]
    b = x1[1]-x2[1]
    if a>=0 and b>=0:
        if (a,b) not in C:
            C[(a,b)] = 0
        C[(a,b)] += 1
    elif a>=0 and b<0:
        if (a,b) not in C:
            C[(a,b)] = 0
        C[(a,b)] += 1
    elif a<0 and b>=0:
        if (-a,-b) not in C:
            C[(-a,-b)] = 0
        C[(-a,-b)] += 1
    elif a<0 and b<0:
        if (-a,-b) not in C:
            C[(-a,-b)] = 0
        C[(-a,-b)] += 1
C = sorted(list(C.items()),key=lambda x:x[1],reverse=True)
k = C[0][1]
print(N-k)

Submission status: Runtime Error

Solution code:
from collections import defaultdict

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

d = defaultdict(int)
for i in range(n):
    for j in range(n):
        if i== j:
            continue
        a,b = l[i]
        c,e = l[j]
        d[(a-c,b-e)] += 1
ans = n
m = max(d.values())
for i,j in d.items():
    if j != m:
        continue

    x,y = i
    if x==0 and y == 0:
        continue
    count = 0
    for c,d in l:
        if [c+x,d+y] in l:
            count += 1
    ans = min(ans,n-count)
print(ans)

Submission status: Runtime Error

Solution code:
import bisect
import copy
import heapq
import math
import sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(5000000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

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

# dic={}
# for i in range(n):
#     x,y=xy[i]
#     dic[(x,y)]=1

cnt=0
sadic=defaultdict(int)
for i in range(n):
    x,y=xy[i]
    for j in range(n):
        if i==j:
            continue
        x2,y2=xy[j]
        p,q=x-x2,y-y2
        sadic[(p,q)]+=1
# print(sadic)
print(n-max(sadic.values()))

Submission status: Runtime Error

Solution code:
from collections import defaultdict

n = int(input())
x, y = [0] * n, [0] * n
data = defaultdict(int)
for i in range(n):
    x[i], y[i] = map(int, input().split())

for i in range(n):
    for j in range(n):
        if i != j:
            data[x[j] - x[i], y[j] - y[i]] += 1

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

Submission status: Runtime Error

Solution code:
from collections import defaultdict

n = int(input())
x, y = [0] * n, [0] * n
data = defaultdict(int)
for i in range(n):
    x[i], y[i] = map(int, input().split())

for i in range(n):
    for j in range(i + 1, n):
        data[x[j] - x[i], y[j] - y[i]] += 1

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

Submission status: Runtime Error

Solution code:
from collections import defaultdict
import numpy as np

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

x = xy[xy.argsort(axis=0)[:, 0]]
y = xy[xy.argsort(axis=0)[:, 1]]

x = [list(x) for x in np.diff(x, axis=0)]
y = [list(y) for y in np.diff(y, axis=0)]


memo_x = defaultdict(int)
memo_y = defaultdict(int)

for i, j in zip(x, y):
    memo_x[str(i)] += 1
    memo_y[str(j)] += 1

print(n - max(max(memo_x.values()), max(memo_x.values())))

Submission status: Runtime Error

Solution code:
from collections import Counter
n=int(input())
xy=[tuple(map(int,input().split())) for _ in range(n)]
xy.sort()
l=[]
for i in range(n-1):
  for j in range(i+1,n):
    l.append((xy[j][0]-xy[i][0],xy[j][1]-xy[i][1]))
print(n-Counter(l).most_common()[0][1])

Submission status: Runtime Error

Solution code:
import collections

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

x_y.sort(key=lambda x: (x[0], x[1]))
pq_cand = []
for i in range(N):
    for j in range(i + 1, N):
        pq_cand.append((x_y[j][0] - x_y[i][0], x_y[j][1] - x_y[i][1]))

pqc = collections.Counter(pq_cand)
_, x = max(pqc.items(), key=lambda x: x[1])
print(N - 1 - x + 1)

Submission status: Runtime Error

Solution code:
import collections

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

pq_cand = []
for i in range(N):
    for j in range(i + 1, N):
        pq_cand.append((x[j] - x[i], y[j] - y[i]))

pqc = collections.Counter(pq_cand)
_, x = max(pqc.items(), key=lambda x: x[1])
print(N - x)

Submission status: Runtime Error

Solution code:
import collections
n = int(input())
ans = 1
dic = collections.defaultdict(list)
ls = []
for i in range(n):
    [x,y] = [int(j) for j in input().split()]
    if x not in ls:
        ls.append(x)
    dic[x].append(y)

ls.sort()
for key in dic.keys():
    dic[key].sort()

diffs = []

dic_ans = collections.defaultdict(int)
count = 0

for i in range(len(ls)):
    xs = ls[i]
    for j in range(len(dic[xs])):
        #同じxの中
        if j != len(dic[xs])-1:
            diff_x = 0
            diff_y = dic[xs][j+1] - dic[xs][j]
        #xが違う場合
        else:
            #最後でない場合
            if i != len(ls)-1:
                diff_x = ls[i+1] - xs
                diff_y = dic[ls[i+1]][0] - dic[xs][j]
        #if i != len(ls)-1:
        if [diff_x,diff_y] in diffs:
            dic_ans[diffs.index([diff_x,diff_y])] += 1
        else:
            diffs.append([diff_x,diff_y])
            dic_ans[len(diffs)-1] += 1
dic_ans[diffs.index([diff_x,diff_y])] -= 1

print(n - max(dic_ans.values()))
#print(dic_ans)
#print(diffs)

Submission status: Runtime Error

Solution code:
def gcd(a,b):
    if a%b==0:
        return b
    return gcd(b,a%b)

N=int(input())
v=[list(map(int,input().split())) for _ in range(N)]
d={}

for i in range(1,N):
    for j in range(i):
        if i!=j:
            x=v[i][0]-v[j][0]
            y=v[i][1]-v[j][1]
            if x<0:
                x*=-1
                y*=-1
            if x!=0 and y!=0:
                g=gcd(x,abs(y))
            elif x==0 and y!=0:
                g=y
            else:
                g=x
            x//=g
            y//=g
            V=str(x)+","+str(y)
            if V in d:
                d[V]+=1
            else:
                d[V]=1
M=0
for D in d:
    M=max(M,d[D])
for D in d:
    if d[D]==M:
        ans=N-d[D]
        break
if ans==0:
    ans+=1
print(ans)

Submission status: Runtime Error

Solution code:
from math import gcd

N=int(input())
v=[list(map(int,input().split())) for _ in range(N)]
d={}

for i in range(1,N):
    for j in range(i):
        if i!=j:
            x=v[i][0]-v[j][0]
            y=v[i][1]-v[j][1]
            if x<0:
                x*=-1
                y*=-1
            g=gcd(x,abs(y))
            x//=g
            y//=g
            V=str(x)+","+str(y)
            if V in d:
                d[V]+=1
            else:
                d[V]=1
M=0
for D in d:
    M=max(M,d[D])
for D in d:
    if d[D]==M:
        ans=N-d[D]
        break
if ans==0:
    ans+=1
print(ans)

Submission status: Runtime Error

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

D = {}
for i in range(n):
    for j in range(n):
        if i == j:
            continue
        a = XY[i][0]
        b = XY[i][1]
        c = XY[j][0]
        d = XY[j][1]
        p = c-a
        q = d-b
        if (p, q) in D:
            D[(p, q)] += 1
        else:
            D[(p,q)] = 1

D = list(D.items())
D.sort(key = lambda x: -x[1])
print(n-D[0][1])

Submission status: Runtime Error

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

pqs = []
for i in range(N):
    for j in range(i+1,N):
        X1 = XY[i][0]
        Y1 = XY[i][1]
        X2 = XY[j][0]
        Y2 = XY[j][1]
        pqs.append(str(X1-X2)+","+str(Y1-Y2))
        pqs.append(str(X2-X1)+","+str(Y2-Y1))

from collections import Counter
C = dict(Counter(pqs))
out = N - max(C.values())
print(out)

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))
x={}
for i in l:
    for j in l:
        if i!=j:
            t=(i[0]-j[0],i[1]-j[1])
            if t in x:
                x[t]+=1
            else:
                x[t]=1
print(n-max(x.values()))

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))
x={}
for i in l:
    for j in l:
        if i!=j:
            t=(i[0]-j[0],i[1]-j[1])
            if t in x:
                x[t]+=1
            else:
                x[t]=1
print(max(x.values()))

Submission status: Runtime Error

Solution code:
from collections import defaultdict as dd
from itertools import combinations
from sys import exit
n = int(input())
if n == 1:
    print(1)

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

Vector = dd(lambda: 0)
for point1, point2 in combinations(Points, 2):
    if point1[0] >= point2[0]:
        x_v = point1[0] - point2[0]
        y_v = point1[1] - point2[1]
    else:
        x_v = point2[0] - point1[0]
        y_v = point2[1] - point1[1]
    Vector[(x_v, y_v)] += 1

print(max(n - max(Vector.values()), 1))

Submission status: Runtime Error

Solution code:
from collections import defaultdict as dd
from itertools import combinations
n = int(input())
Points = []
for i in range(n):
    Points.append(list(map(int, input().split())))

Vector = dd(lambda: 0)
for point1, point2 in combinations(Points, 2):
    if point1[0] >= point2[0]:
        x_v = point1[0] - point2[0]
        y_v = point1[1] - point2[1]
    else:
        x_v = point2[0] - point1[0]
        y_v = point2[1] - point1[1]
    Vector[(x_v, y_v)] += 1

print(max(n - max(Vector.values()), 0))

Submission status: Runtime Error

Solution code:
from collections import defaultdict as dd
from itertools import combinations
n = int(input())
Points = []
for i in range(n):
    Points.append(list(map(int, input().split())))

Vector = dd(lambda: 0)
for point1, point2 in combinations(Points, 2):
    if point1[0] >= point2[0]:
        x_v = point1[0] - point2[0]
        y_v = point1[1] - point2[1]
    else:
        x_v = point2[0] - point1[0]
        y_v = point2[1] - point1[1]
    Vector[(x_v, y_v)] += 1

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

Submission status: Runtime Error

Solution code:
from collections import Counter
N = int(input())
xylist = sorted([tuple(map(int, input().split())) for _ in range(N)])
def calc(xy1, xy2):
  return (xy1[0]-xy2[0], xy1[1]-xy2[1])

sbn = Counter([calc(xylist[i+1], xylist[i]) for i in range(N-1)]).most_common()
print(1 + N-1 - sbn[0][1])

Submission status: Runtime Error

Solution code:
def main():
    import sys
    input = sys.stdin.buffer.readline
    N = int(input())
    XY = [[int(i) for i in input().split()] for j in range(N)]
    XY.sort()
    from collections import Counter
    c = Counter()
    for i in range(N-1):
        for j in range(i+1, N):
            p = XY[j][0] - XY[i][0]
            q = XY[j][1] - XY[i][1]
            c[(p, q)] += 1
    ans = N - c.most_common()[0][1]
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
from collections import Counter
from math import ceil
def input():
    return sys.stdin.readline()[:-1]
def gcd(a,b):
    if b == 0:
        return a
    return gcd(b,a%b)
def main():
    N = int(input())
    P = []
    for _ in range(N):
        P.append(list(map(int,input().split())))
    K = []
    for k in range(N-1):
        for l in range(k+1,N):
            a, b, c, d = P[k][0], P[k][1], P[l][0], P[l][1]
            if [a,b] != [c,d]:
                e = c-a
                f = d-b
                while gcd(e,f) != 1:
                    t = gcd(e,f)
                    e //= t
                    f //= t
                K.append((e,f))
    C = Counter(K).most_common()
    print(max(1,N-C[0][1]))

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from itertools import combinations
from collections import Counter

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

delta = []
for i, j in combinations(list(range(N)), 2):
    if xy[i][0] < xy[j][0]:
        p0 = xy[i][:]
        p1 = xy[j][:]
    else:
        p0 = xy[j][:]
        p1 = xy[i][:]
    delta.append((p1[0] - p0[0], p1[1] - p0[1]))
cnt = Counter(delta)

dlt = cnt.most_common()[0][0]

visited =set()
c = 0

for i in range(N):
    if xy[i] in visited:continue
    c += 1
    temp = [[xy[i], c]]
    while temp:
        q = temp.pop()
        for n in [1, -1]:
            x1, y1 = q[0][0] + n * dlt[0], q[0][1] + n * dlt[1]
            if not (x1, y1) in visited and (x1, y1) in xy:
                temp.append([(x1, y1), q[1]])
                visited.add((x1, y1))

print(c)

Submission status: Runtime Error

Solution code:
4
1 1
1 2
2 1
2 2

Submission status: Runtime Error

Solution code:
import collections
import itertools

def Z(): return int(input())
def ZZ(): return [int(_) for _ in input().split()]

def main():
    N = Z()
    P = [ZZ() for _ in range(N)]
    d = collections.defaultdict(int)
    output = 0
    for i, j in itertools.combinations(range(N), 2):
        dx, dy = P[i][0] - P[j][0], P[i][1] - P[j][1]
        if dx < 0: dx, dy = -dx, -dy
        d[(dx, dy)] += 1
    output += (N - max(d.values()))
    print(output)

    return

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
n = int(input())
xy = []
for _ in range(n):
    x, y = map(int, input().split())
    xy.append((x, y))
dxdy = {}
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]
        if dx<0:
            dx, dy = -dx, -dy
        if (dx, dy) in dxdy:
            dxdy[(dx, dy)] += 1
        else:
            dxdy[(dx, dy)] = 1
print(n-max(dxdy.values()))

Submission status: Runtime Error

Solution code:
from collections import Counter

N = int(input())
M = [tuple(map(int, input().split())) for _ in range(N)]
Map = []
for i in range(N):
    x1, y1 = M[i]
    for j in range(i + 1, N):
        x2, y2 = M[j]
        Map.append((x2 - x1, y2 - y1))
MapC = Counter(Map)
print(N - MapC.most_common(1)[0][1])

Submission status: Runtime Error

Solution code:
n = int(input())
xy = [list(map(int, input().split())) for _ in range(n)]
array = []
for i in range(n-1):
    for j in range(i+1, n):
        x1, y1 = xy[i]
        x2, y2 = xy[j]
        array.append((x2-x1, y2-y1))
from collections import Counter, deque
c = sorted(list(Counter(array).items()), reverse=True, key=lambda x:x[1])[0][0]
array = [[] for _ in range(n)]
for i in range(n-1):
    for j in range(i+1, n):
        x1, y1 = xy[i]
        x2, y2 = xy[j]
        if (x2-x1, y2-y1) == c:
            array[i].append(j)
            array[j].append(i)
flag = [True] * n
result = n
for i in range(n):
    if flag[i]:
        data = [i]
        d = deque([])
        for j in array[i]:
            data.append(j)
            d.append(j)
            flag[j] = False
        while len(d) > 0:
            j = d.pop()
            if j not in data:
                data.append(j)
                d.append(j)
                flag[j] = False
        result -= len(data)-1
print(result)

Submission status: Runtime Error

Solution code:
from collections import defaultdict

def diverta192_b():
    N = int(input())
    P = [tuple(map(int, input().split())) for _ in range(N)]
    dcnt = defaultdict(int)
    for i in range(N):
        xi, yi = P[i]
        for j in range(i):
            xj, yj = P[j]
            dx1, dy1 = xi-xj, yi-yj
            dx2, dy2 = xj-xi, yj-yi
            dcnt[(dx1,dy1)] += 1
            dcnt[(dx2,dy2)] += 1
    most = sorted(dcnt.values(), reverse=True)[0]
    ans = N - most
    print(ans)

diverta192_b()

Submission status: Runtime Error

Solution code:
from collections import defaultdict

def diverta192_b():
    N = int(input())
    P = [tuple(map(int, input().split())) for _ in range(N)]
    dcnt = defaultdict(int)
    for i in range(N):
        xi, yi = P[i]
        for j in range(i):
            xj, yj = P[j]
            if xi > xj: dx, dy = xi-xj, yi-yj
            else: dx, dy = xj-xi, yj-yi
            dcnt[(dx,dy)] += 1
    most = sorted(dcnt.values(), reverse=True)[0]
    ans = N - most
    print(ans)

diverta192_b()

Submission status: Runtime Error

Solution code:
def diverta192_b():
    N = int(input())
    P = [tuple(map(int, input().split())) for _ in range(N)]
    dcnt = defaultdict(int)
    for i in range(N):
        xi, yi = P[i]
        for j in range(i):
            xj, yj = P[j]
            if xi > xj: dx, dy = xi-xj, yi-yj
            else: dx, dy = xj-xi, yj-yi
            dcnt[(dx,dy)] += 1
    most = sorted(dcnt.values(), reverse=True)[0]
    ans = N - most
    print(ans)

diverta192_b()

Submission status: Runtime Error

Solution code:
n = int(input())
dat = []
for i in range(n):
    a,b = map(int, input().split())
    dat.append([a,b])
dat2 = []
for i in range(n):
    x1, y1 = dat[i]
    for j in range(i+1, n):
        x2, y2 = dat[j]
        dat2.append( (x1-x2, y1-y2) )
import collections
c = collections.Counter(dat2)
#print(c)
print(n - c.most_common(1)[0][1])

Submission status: Runtime Error

Solution code:
n=int(input())
L=[]
for _ in range(n):
    l=list(map(int,input().split()))
    L.append(l)
pq=[]
ans=[]
for i in range(n-1):
    for j in range(i+1,n):
        x=L[i][0]-L[j][0]
        y=L[i][1]-L[j][1]
        if [x,y] in pq:
            ans[pq.index([x,y])] += 1
        elif [-x,-y] in pq:
            ans[pq.index([-x,-y])] += 1
        else:
            pq.append([x,y])
            ans.append(1)

print(n-max(ans))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

n = int(input())

x = [0]*n
y = [0]*n
for i in range(n):
    xx,yy= map(int, input().split())
    x[i] = xx-1
    y[i] = yy-1

from collections import defaultdict
d = defaultdict(lambda:0)

for i in range(n):
    for j in range(n):
        if i==j:continue

        p = x[j]-x[i]
        q = y[j]-y[i]

        d[p*10**9+q] +=1

dv = d.values()
mad =max(dv)

print(n-mad)

Submission status: Runtime Error

Solution code:
from collections import defaultdict

n=int(input())
x=[]
y=[]
for i in range(n):
    xx,yy=list(map(int,input().split()))
    x.append(xx)
    y.append(yy)

dif=defaultdict(int)

for i in range(n):
    for j in range(n):
        if i==j:continue
        p=x[j]-x[i]
        q=y[j]-y[i]
        dif[(p,q)]+=1

dif=sorted(dif.items(),key=lambda x:x[1],reverse=True)
ans=n-dif[0][1]

print(ans)

Submission status: Runtime Error

Solution code:
import sys
from collections import defaultdict

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


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


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

    cnt = defaultdict(int)
    for i in range(N):
        for j in range(N):
            if i == j:
                continue

            dx = X[j] - X[i]
            dy = Y[j] - Y[i]
            cnt[(dx, dy)] += 1

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


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
ans=float("INF")
n=int(input())
l=[list(map(int,input().split())) for i in range(n)]
if n==1:print(1);exit()
for i in range(n):
    for j in range(n):
        if i==j:continue
        p,q=l[i][0]-l[j][0],l[i][1]-l[j][1]
        ret=0
        pre=sorted(l,reverse=1,key=lambda x:p*x[0]+q*x[1])
        while pre:
            ret+=1
            x,y=pre.pop()
            while  [x+p,y+q] in pre:
                pre.remove([x+p,y+q])
                x,y=[x+p,y+q]
        ans=min(ans,ret)
print(ans)ans=float("INF")
n=int(input())
l=[list(map(int,input().split())) for i in range(n)]
if n==1:print(1);exit()
for i in range(n):
    for j in range(n):
        if i==j:continue
        p,q=l[i][0]-l[j][0],l[i][1]-l[j][1]
        ret=0
        pre=sorted(l,reverse=1,key=lambda x:p*x[0]+q*x[1])
        while pre:
            ret+=1
            x,y=pre.pop()
            while  [x+p,y+q] in pre:
                pre.remove([x+p,y+q])
                x,y=[x+p,y+q]
        ans=min(ans,ret)
print(ans)ans=float("INF")
n=int(input())
l=[list(map(int,input().split())) for i in range(n)]
if n==1:print(1);exit()
for i in range(n):
    for j in range(n):
        if i==j:continue
        p,q=l[i][0]-l[j][0],l[i][1]-l[j][1]
        ret=0
        pre=sorted(l,reverse=1,key=lambda x:p*x[0]+q*x[1])
        while pre:
            ret+=1
            x,y=pre.pop()
            while  [x+p,y+q] in pre:
                pre.remove([x+p,y+q])
                x,y=[x+p,y+q]
        ans=min(ans,ret)
print(ans)

Submission status: Runtime Error

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
from itertools import combinations
from collections import Counter
def main():
    n=int(input())
    if n==1:
        print(1)
    XY=[tuple(map(int,input().split())) for i in range(n)]
    lis=list(combinations(XY,2))
    PQ=[]
    for l in lis:
        if l[0][0]<l[1][0]:
            PQ.append((l[1][0]-l[0][0],l[1][1]-l[0][1]))
        else:
            PQ.append((l[0][0]-l[1][0],l[0][1]-l[1][1])) 
    x=Counter(PQ).most_common(1)[0][1]
    print(n-x)

if __name__=='__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
from itertools import combinations
from collections import Counter
def main():
    n=int(input())
    XY=[tuple(map(int,input().split())) for i in range(n)]
    lis=list(combinations(XY,2))
    PQ=[]
    for l in lis:
        if l[0][0]<l[1][0]:
            PQ.append((l[1][0]-l[0][0],l[1][1]-l[0][1]))
        else:
            PQ.append((l[0][0]-l[1][0],l[0][1]-l[1][1])) 
    x=Counter(PQ).most_common(1)[0][1]
    print(n-x)

if __name__=='__main__':
    main()

Submission status: Runtime Error

Solution code:
from collections import Counter

N = int(input())
XY = []
for i in range(0, N):
    XY.append(list(map(int, input().split())))
XY.sort(key=lambda x: x[0])
YX = sorted(XY, key=lambda x: x[1])
A, B = Counter(), Counter()
for i in range(1, N):
    diff = (XY[i][0]-XY[i-1][0], XY[i][1]-XY[i-1][1])
    A[diff] += 1
for i in range(1, N):
    diff = (YX[i][0]-YX[i-1][0], YX[i][1]-YX[i-1][1])
    B[diff] += 1
PQ = max(max(A.items(), key=lambda x: x[1]), max(
    B.items(), key=lambda x: x[1]))[0]
ans1, ans2 = 1, 1
for i in range(1, N):
    if not((XY[i][0]-PQ[0] == XY[i-1][0])and(XY[i][1]-PQ[1] == XY[i-1][1])):
        ans1 += 1
for i in range(1, N):
    if not((YX[i][0]-PQ[0] == YX[i-1][0])and(YX[i][1]-PQ[1] == YX[i-1][1])):
        ans2 += 1
print(min(ans1, ans2))

Submission status: Runtime Error

Solution code:
n = int(input())
pos = []
diff = []
for _ in range(n):
  x,y = map(int,input().split())
  for px,py in pos:
    diff.append((x-px, y-py))
    diff.append((px-x, py-y))
  pos.append((x,y))
from collections import Counter
diff = Counter(diff).most_common()
x,y = diff[0][0]
count = diff[0][1]
if x== y == 0:
  x,y = diff[1][0]
  count = diff[1][1]
print(n-count)

Submission status: Runtime Error

Solution code:
n = int(input())
d = dict()
p = []
for i in range(n):
    x,y = map(int,input().split())
    for j in p:
        if str(x-j[0])+" "+str(y-j[1]) in d:
            d[str(x-j[0])+" "+str(y-j[1])] += 1
        else:
            d[str(x-j[0])+" "+str(y-j[1])] = 1
        if str(j[0]-x)+" "+str(j[1]-y) in d:
            d[str(j[0]-x)+" "+str(j[1]-y)] += 1
        else:
            d[str(j[0]-x)+" "+str(j[1]-y)] = 1
    p.append([x,y])

ans = max(d.values())
print(n-ans)

Submission status: Runtime Error

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

for i in range(n):
    for j in range(i+1,n):
        diffx = xys[i][0] - xys[j][0]
        diffy = xys[i][1] - xys[j][1]
        if diffx == 0:
            vec.append([12345678901234,i,j])
        else:
            vec.append([diffy/diffx,i,j])
vec.sort()
cnt =1
cntMax = 0
val=-1
for i in range(1,len(vec)):
    if vec[i][0] != vec[i-1][0]:
        if cnt > cntMax:
            val = vec[i-1][0]
            cntMax = cnt
        cnt = 1
    else:
        cnt += 1
if cnt > cntMax:
    val = vec[-1][0]
    cntMax = max(cntMax,cnt)

check = [1]*(n+1)
check[0]=0

for i in range(len(vec)):
    if vec[i][0] == val:
        check[vec[i][2]] = 0
print(sum(check))

Submission status: Runtime Error

Solution code:
from collections import Counter

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

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

ans = N
diff = []

for i in range(N-1):
    for j in range(i+1, N):
        diff.append((xy[j][0]-xy[i][0], xy[j][1]-xy[i][1]))

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