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 sys import stdin
import collections

def main():
  N = int(input())
  
  xlist=[]
  ylist=[]
  for i in range(N):
    x, y = map(int, stdin.readline().rstrip().split())
    xlist.append(x)
    ylist.append(y)
    
  tupleList=[]
  for i in range(N):
    for j in range(N):
      if i < j:
        tupleList.append((xlist[i] - xlist[j], ylist[i] - ylist[j]))
        
  c = collections.Counter(tupleList)
  print(N-c[max(c)])   

main()

Submission status: Runtime Error

Solution code:
from collections import Counter
def solve(N, XY):
    XY = sorted(XY)
    cnt = Counter()
    d = []
    for x0, y0 in XY:
        for x1, y1 in XY:
            if x0 == x1 and y0 == y1:
                continue
            d.append((x0 - x1, y0 - y1))
    m = Counter(d).most_common()[0]
    return len(XY) - m[1]

def main():
    N = int(input())

    XY = []
    for i in range(N):
        XY.append(tuple([int(x) for x in input().split()]))

    print(solve(N, XY))

main()

Submission status: Runtime Error

Solution code:
import itertools

N=input()
XY=[ map(int, raw_input().split())  for _ in range(N) ]
XY.sort(key=lambda x:(x[0],x[1]) )

D={}

C=list( itertools.combinations( range(1,N+1), 2) )

for b1, b2 in C:
	x1=XY[b1-1][0]
	y1=XY[b1-1][1]
	x2=XY[b2-1][0]
	y2=XY[b2-1][1]

	dx=x2-x1
	dy= y2-y1
	if (dx,dy) not in D:
		D[(dx,dy)]=1
	else:
		D[(dx,dy)]+=1

print N-max( D.values() )

Submission status: Runtime Error

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

cost = []
for i in range(n-1):
  p = pos[i+1][0] - pos[i][0]
  q = pos[i+1][1] - pos[i][1]
  move = [p,q]
  cost.append(move)
  
best = max(cost, key=cost.count)

for i in range(n-1):
  if cost[i] != best:
    count += 1
print(count)

Submission status: Runtime Error

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

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

ans = inf
for i in range(N - 1):
    xi, yi = xy[i]
    for j in range(i + 1, N):
        xj, yj = xy[j]
        #
        p = xj - xi
        q = yj - yi
        terms = set([])
        for n, (xn, yn) in enumerate(xy):
            mp = q * xn -  p * yn
            mod = xn % p if p > 0 else yn % q
            terms.add((mp, mod))
        # print("#", p, q, terms)
        ans_tmp = len(terms)
        #
        if ans > ans_tmp: ans = ans_tmp

print(ans)

Submission status: Runtime Error

Solution code:
from collections import Counter
n=int(input())
xy = [list(map(int,input().split())) for i in range(n)]
a = Counter([xy[i+1][0]-xy[i][0] for i in range(0,len(xy)-1)]).most_common()[0][0]
b = Counter([xy[i+1][1]-xy[i][1] for i in range(0,len(xy)-1)]).most_common()[0][0]

ans=0
tmp0,tmp1 = xy[0]
for i in range(1,len(xy)):
	ans += 0 if tmp0 == xy[i][0]-a  and tmp1 == xy[i][1]-b else 1
	tmp0=xy[i][0]
	tmp1=xy[i][1]
tmp = ans
ans=0
for i in range(len(xy)-1,-1,-1):
	ans += 0 if tmp0 == xy[i][0]-a and tmp1 == xy[i][1]-b else 1
	tmp0=xy[i][0]
	tmp1=xy[i][1]

print(min(ans,tmp)+1)

Submission status: Runtime Error

Solution code:
from pprint import pprint
from collections import defaultdict
import numpy as np

def main():
    N = int(input())
    balls = [tuple(map(int,input().split())) for _ in range(N)]
    d = defaultdict(int)
    for i in range(N):
        for j in range(N):
            if i == j:
                continue
            d[tuple(np.subtract(balls[i],balls[j]))] += 1
    print(N-max(d.values()))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:


def gcd_core(a, b):
    if b == 0:
        return a
    else:
        return gcd_core(b, a % b)


def gcd(arr):
    g = gcd_core(arr[0], arr[1])
    for i in range(2, len(arr)):
        g = gcd_core(g, arr[i])
    return g



n = int(input())
b1 = []

for i in range(n):
    b1.append(list(map(int,input().split())))

b2 = b1.copy()
b3 = b1.copy()
b4 = b1.copy()
b5 = b1.copy()
b6 = b1.copy()
b7 = b1.copy()
b8 = b1.copy()



b1.sort(key=lambda x:(x[0],x[1]))
b2.sort(key=lambda x:(x[1],x[0]))
b3.sort(key=lambda x:(x[0],-x[1]))
b4.sort(key=lambda x:(x[1],-x[0]))
b5.sort(key=lambda x:(-x[0],x[1]))
b6.sort(key=lambda x:(-x[1],x[0]))
b7.sort(key=lambda x:(-x[0],x[1]))
b8.sort(key=lambda x:(-x[1],x[0]))
# print(b1)
# print(b2)

costs = []

l1_x = {}
l1_y = {}

bef_x = b1[0][0]
bef_y = b1[0][1]
for i in range(1,n):
    diff_x = b1[i][0]-bef_x
    diff_y = b1[i][1]-bef_y
    bef_x = b1[i][0]
    bef_y = b1[i][1]

    if not diff_x in l1_x:
        l1_x[diff_x] = 1
    else:
        l1_x[diff_x]+=1

    if not diff_y in l1_y:
        l1_y[diff_y] = 1
    else:
        l1_y[diff_y]+=1

x_step = max(l1_x,key = l1_x.get)
y_step = max(l1_y,key = l1_y.get)


cost1 = 1
bef_x = b1[0][0]
bef_y = b1[0][1]
for i in range(1,n):
    diff_x = b1[i][0]-bef_x
    diff_y = b1[i][1]-bef_y
    bef_x = b1[i][0]
    bef_y = b1[i][1]

    if diff_x != x_step or diff_y != y_step:
        cost1 += 1

costs.append(cost1)
#*****************************************************
l1_x = {}
l1_y = {}

bef_x = b2[0][0]
bef_y = b2[0][1]
for i in range(1, n):
    diff_x = b2[i][0] - bef_x
    diff_y = b2[i][1] - bef_y
    bef_x = b2[i][0]
    bef_y = b2[i][1]

    if not diff_x in l1_x:
        l1_x[diff_x] = 1
    else:
        l1_x[diff_x] += 1

    if not diff_y in l1_y:
        l1_y[diff_y] = 1
    else:
        l1_y[diff_y] += 1

x_step = max(l1_x, key = l1_x.get)
y_step = max(l1_y, key = l1_y.get)

cost2 = 1
bef_x = b2[0][0]
bef_y = b2[0][1]
for i in range(1, n):
    diff_x = b2[i][0] - bef_x
    diff_y = b2[i][1] - bef_y
    bef_x = b2[i][0]
    bef_y = b2[i][1]

    if diff_x != x_step or diff_y != y_step:
        cost2 += 1

costs.append(cost2)




l1_x = {}
l1_y = {}

bef_x = b3[0][0]
bef_y = b3[0][1]
for i in range(1,n):
    diff_x = b3[i][0]-bef_x
    diff_y = b3[i][1]-bef_y
    bef_x = b3[i][0]
    bef_y = b3[i][1]

    if not diff_x in l1_x:
        l1_x[diff_x] = 1
    else:
        l1_x[diff_x]+=1

    if not diff_y in l1_y:
        l1_y[diff_y] = 1
    else:
        l1_y[diff_y]+=1

x_step = max(l1_x,key = l1_x.get)
y_step = max(l1_y,key = l1_y.get)


cost1 = 1
bef_x = b3[0][0]
bef_y = b3[0][1]
for i in range(1,n):
    diff_x = b3[i][0]-bef_x
    diff_y = b3[i][1]-bef_y
    bef_x = b3[i][0]
    bef_y = b3[i][1]

    if diff_x != x_step or diff_y != y_step:
        cost1 += 1

costs.append(cost1)
#*****************************************************
l1_x = {}
l1_y = {}

bef_x = b4[0][0]
bef_y = b4[0][1]
for i in range(1, n):
    diff_x = b4[i][0] - bef_x
    diff_y = b4[i][1] - bef_y
    bef_x = b4[i][0]
    bef_y = b4[i][1]

    if not diff_x in l1_x:
        l1_x[diff_x] = 1
    else:
        l1_x[diff_x] += 1

    if not diff_y in l1_y:
        l1_y[diff_y] = 1
    else:
        l1_y[diff_y] += 1

x_step = max(l1_x, key = l1_x.get)
y_step = max(l1_y, key = l1_y.get)

cost2 = 1
bef_x = b4[0][0]
bef_y = b4[0][1]
for i in range(1, n):
    diff_x = b4[i][0] - bef_x
    diff_y = b4[i][1] - bef_y
    bef_x = b4[i][0]
    bef_y = b4[i][1]

    if diff_x != x_step or diff_y != y_step:
        cost2 += 1

costs.append(cost2)




l1_x = {}
l1_y = {}

bef_x = b5[0][0]
bef_y = b5[0][1]
for i in range(1,n):
    diff_x = b5[i][0]-bef_x
    diff_y = b5[i][1]-bef_y
    bef_x = b5[i][0]
    bef_y = b5[i][1]

    if not diff_x in l1_x:
        l1_x[diff_x] = 1
    else:
        l1_x[diff_x]+=1

    if not diff_y in l1_y:
        l1_y[diff_y] = 1
    else:
        l1_y[diff_y]+=1

x_step = max(l1_x,key = l1_x.get)
y_step = max(l1_y,key = l1_y.get)


cost1 = 1
bef_x = b5[0][0]
bef_y = b5[0][1]
for i in range(1,n):
    diff_x = b5[i][0]-bef_x
    diff_y = b5[i][1]-bef_y
    bef_x = b5[i][0]
    bef_y = b5[i][1]

    if diff_x != x_step or diff_y != y_step:
        cost1 += 1

costs.append(cost1)
#*****************************************************
l1_x = {}
l1_y = {}

bef_x = b6[0][0]
bef_y = b6[0][1]
for i in range(1, n):
    diff_x = b6[i][0] - bef_x
    diff_y = b6[i][1] - bef_y
    bef_x = b6[i][0]
    bef_y = b6[i][1]

    if not diff_x in l1_x:
        l1_x[diff_x] = 1
    else:
        l1_x[diff_x] += 1

    if not diff_y in l1_y:
        l1_y[diff_y] = 1
    else:
        l1_y[diff_y] += 1

x_step = max(l1_x, key = l1_x.get)
y_step = max(l1_y, key = l1_y.get)

cost2 = 1
bef_x = b6[0][0]
bef_y = b6[0][1]
for i in range(1, n):
    diff_x = b6[i][0] - bef_x
    diff_y = b6[i][1] - bef_y
    bef_x = b6[i][0]
    bef_y = b6[i][1]

    if diff_x != x_step or diff_y != y_step:
        cost2 += 1

costs.append(cost2)




l1_x = {}
l1_y = {}

bef_x = b7[0][0]
bef_y = b7[0][1]
for i in range(1,n):
    diff_x = b7[i][0]-bef_x
    diff_y = b7[i][1]-bef_y
    bef_x = b7[i][0]
    bef_y = b7[i][1]

    if not diff_x in l1_x:
        l1_x[diff_x] = 1
    else:
        l1_x[diff_x]+=1

    if not diff_y in l1_y:
        l1_y[diff_y] = 1
    else:
        l1_y[diff_y]+=1

x_step = max(l1_x,key = l1_x.get)
y_step = max(l1_y,key = l1_y.get)


cost1 = 1
bef_x = b7[0][0]
bef_y = b7[0][1]
for i in range(1,n):
    diff_x = b7[i][0]-bef_x
    diff_y = b7[i][1]-bef_y
    bef_x = b7[i][0]
    bef_y = b7[i][1]

    if diff_x != x_step or diff_y != y_step:
        cost1 += 1

costs.append(cost1)
#*****************************************************
l1_x = {}
l1_y = {}

bef_x = b8[0][0]
bef_y = b8[0][1]
for i in range(1, n):
    diff_x = b8[i][0] - bef_x
    diff_y = b8[i][1] - bef_y
    bef_x = b8[i][0]
    bef_y = b8[i][1]

    if not diff_x in l1_x:
        l1_x[diff_x] = 1
    else:
        l1_x[diff_x] += 1

    if not diff_y in l1_y:
        l1_y[diff_y] = 1
    else:
        l1_y[diff_y] += 1

x_step = max(l1_x, key = l1_x.get)
y_step = max(l1_y, key = l1_y.get)

cost2 = 1
bef_x = b8[0][0]
bef_y = b8[0][1]
for i in range(1, n):
    diff_x = b8[i][0] - bef_x
    diff_y = b8[i][1] - bef_y
    bef_x = b8[i][0]
    bef_y = b8[i][1]

    if diff_x != x_step or diff_y != y_step:
        cost2 += 1

costs.append(cost2)

print(min(costs))

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
n=int(input())
s=[]
d=[]
i=0
while i!=n:
    s=list(map(int,input().split()))
    d.append(s)
    i+=1
#print(d)
i=0
f=[]
s=[]
j=0
while i!=n:
    while j!=n:
        if i!=j:
            f.append(abs(d[i][0]-d[j][0]))
            f.append(abs(d[i][1] - d[j][1]))
            s.append(f)
            f=[]

        j += 1
    i+=1
    j=0


#print(s)
i=0
f=[]
while i!=len(s):
    f.append(s.count(s[i]))
    i+=1
#print(f)
print(int(n-max(f)/2))

Submission status: Runtime Error

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

cnt = 0
while len(xy) > 0:
  tmp = xy.pop(0)
  if len(xy) == 0:
    cnt += 1
    break
  p, q = xy[0][0] - tmp[0], xy[0][1] - tmp[1]
  for l in xy:
    if p == 0 and abs(l[1] - tmp[1]) % q == 0 or q == 0 and abs(l[0] - tmp[0]) % p == 0 or abs(l[0] - tmp[0]) % p == 0 and abs(l[1] - tmp[1]) % q == 0:
      xy.remove(l)
  cnt += 1
print(cnt)

Submission status: Runtime Error

Solution code:
from collections import Counter


def mathgcd(x, y):
    if y == 0:
        return x
    else:
        return mathgcd(y, x % y)


N = int(input())
points = [tuple(map(int, input().split())) for _ in range(N)]
vecs = {}
counter = Counter()

for i, p in enumerate(points):
    for j in range(i, N):
        if j == i:
            continue
        q = points[j]
        a = min(p, q)
        b = max(p, q)
        dx = b[0] - a[0]
        dy = b[1] - a[1]
        gcd = mathgcd(dx, dy)
        if gcd != 0:
            dx //= gcd
            dy //= gcd
        vecs[(i, j)] = (dx, dy)
        counter[(dx, dy)] += 1

vec, _ = counter.most_common()[0]
dx, dy = vec
visited = set()
cost = 0

for i, p in enumerate(points):
    if i in visited:
        continue
    cost += 1
    for j in range(i, N):
        if j == i:
            continue
        if vecs[(i, j)] == (dx, dy):
            visited.add(j)

print(cost)

Submission status: Runtime Error

Solution code:
n = int(input())
z = [list(map(int, input().split())) for _ in range(n)]
z.sort()
pq_pattern = []
pq_counter = [0]*(n-1)

for i in range(n-1):
    #print([z[i+1][0] - z[i][0], z[i+1][1] - z[i][1]])
    if [z[i+1][0] - z[i][0], z[i+1][1] - z[i][1]] in pq_pattern:
        pq_counter[pq_pattern.index([z[i+1][0] - z[i][0], z[i+1][1] - z[i][1]])] += 1
    else:
        pq_pattern.append([z[i+1][0] - z[i][0], z[i+1][1] - z[i][1]])
print(1+max(pq_counter))

Submission status: Runtime Error

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

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

    return num

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

z = most_frequent(l)
l = 1
for i in range(1,len(c)):
    if([c[i][0]-z[0],c[i][1]-z[1]] not in c):
        l+=1
print(l)

Submission status: Runtime Error

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

sys.setrecursionlimit(10000000000)

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

Submission status: Runtime Error

Solution code:
import collections 
N=int(input())
T=[list(map(int,input().split())) for _ in range(N)]
T.sort(reverse=True)
TMP=[]
if N==1:
    print(1)
else:
    for i in range(N-1):
        for b in range(i,N-1):
            TMP.append((T[i][0]-T[b+1][0],T[i][1]-T[b+1][1]))
c=collections.Counter(TMP)
print(N-c.most_common(n=1)[0][1])

Submission status: Runtime Error

Solution code:
import sys
import collections

n = int(input())
xy = []
for _ in range(n):
    xy.append([int(i) for i in input().split()])
xy.sort()

cost_list = []
for i in range(n):
    for j in range(i,n):
        if i == j:
            continue
        x_sub = xy[j][0] - xy[i][0]
        y_sub = xy[j][1] - xy[i][1]
        cost_list.append('{},{}'.format(x_sub, y_sub))

cost_dic = collections.Counter(cost_list)
#print(cost_dic)
zero_cost_num = max(cost_dic.values())
#print(zero_cost_num)
ans = n - zero_cost_num

print(ans)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
n = int(input())
xy = [list(map(int, input().split())) for _ in range(n)]
xy.sort()
d = defaultdict(int)
for i in range(n-1):
    x1, y1 = xy[i]
    x2, y2 = xy[i+1]
    d["%d:%d" % (x2-x1, y2-y1)] += 1

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

Submission status: Runtime Error

Solution code:
N=int(input())

X=[]
X.sort()
PQ=[]

for i in range(1,N):
  [p,q]=[X[i][0]-X[i-1][0],X[i][1]-X[i-1][1]]
  if [p,q] not in PQ:
    PQ.append([p,q])
print(len(PQ))

Submission status: Runtime Error

Solution code:
N = int(input())

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

#print(l)

subx = -99
suby = -99

subl = []
dic = {}

for i in range(1, N) :
    #subl.append([l[i][0] - l[i-1][0], l[i][1] - l[i-1][1]])
    k = 1000000001*(l[i][0] - l[i-1][0]) + l[i][1] - l[i-1][1]
    if k not in dic :
        dic[k] = 1
    else :
        dic[k] += 1

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

Submission status: Runtime Error

Solution code:
n = int(input())

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

diff = []
for i in range(n):
    for j in range(n):
        if i > j:
            diff.append(str(xy[i][0] - xy[j][0])+'and'+str(xy[i][1] - xy[j][1]))

ans = []
for i in set(diff):
    ans.append(diff.count(i))
    
print(n - max(ans))

Submission status: Runtime Error

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
Max = sys.maxsize
def l():
    return list(map(int,input().split()))
def m():
    return map(int,input().split())
def onem():
    return int(input())
def s(x):
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa == x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x):
    return " ".join(map(str,x))

n = onem()
a = []
for i in range(n):
    a.append(l())
aa = []
for i in range(n-1):
    for j in range(i,n):
        if not (a[i][0] - a[j][0] == 0 and a[i][1] - a[j][1] == 0):
            aa.append([a[i][0] - a[j][0],a[i][1] - a[j][1]])
            aa.append([a[j][0] - a[i][0],a[j][1] - a[i][1]])
aa.sort()
c = 1
cc = 1
lp = aa[0]
for i in range(1,len(aa)):
    if lp == aa[i]:
        c += 1
    else:
        if c >= cc:
            cc = c
        lp = aa[i]
        c = 1
if c >= cc:
    cc = c


print(n - cc )

Submission status: Runtime Error

Solution code:
N = int(input())

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

dis_dic = {}
for n in range(N):
    for m in range(N):
        if (n != m):
            distance_tuple = (position[n][0] - position[m]
                              [0], position[n][1] - position[m][1])

            if distance_tuple in dis_dic.keys():
                dis_dic[distance_tuple] += 1
            else:
                dis_dic[distance_tuple] = 1

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

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
ri = lambda: int(input())
#rl = lambda: [int(x) if x.isdecimal() else x for x in input().split()]
#rl = lambda: list(input().split()))
rl = lambda: map(int,input().split())
rr = lambda N: [list(l) for l in zip(*[rl() for _ in range(N)])]
YN = lambda b: print('YES') if b else print('NO')
yn = lambda b: print('Yes') if b else print('No')
OE = lambda x: print('Odd') if x%2 else print('Even')
INF = 10**18
MOD = 10**9+7

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

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

Submission status: Runtime Error

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

check = set()
ans = {}
bp = X[0][0]
bq = X[0][1]
for i in range(1,N):
    p = abs(bp-X[i][0])
    q = abs(bq-X[i][1])
    index = str(p)+str(q)
    if index in check:
        ans[index] += 1
    else:
        ans[index] = 1
        check.add(index)
    bp = X[i][0]
    bq = X[i][1]

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

Submission status: Runtime Error

Solution code:
from sys import stdin
n = int(stdin.readline().rstrip())
data = [[int(s) for s in stdin.readline().rstrip().split()] for _ in range(n)]
d = {}

for i in range(n):
  for j in range(i + 1, n):
    diff = (data[i][0] - data[j][0], data[i][1] - data[j][1])
    if diff in d:
      d[diff] += 1
    else:
      d[diff] = 1

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

Submission status: Runtime Error

Solution code:
N = int(input())

XY = []
for _ in range(N):
    x, y = map(int, input().split())
    XY.append((x,y))
    
import itertools
import collections
import sys

sys.setrecursionlimit(10000)

ans_list = []
for v in itertools.permutations(XY):
    count_list = []
    for (x0, y0), (x1,y1) in zip(v[1:], v[:-1]):
        count_list.append((x1-x0, y1-y0))
    ans_list.append(max(collections.Counter(count_list).values()))
    
ans = N-max(ans_list)
print(ans)

Submission status: Runtime Error

Solution code:
from collections import defaultdict

table = defaultdict(lambda: 0)

n = int(input())
xylist = []
for _ in range(n):
    x, y = map(int, input().split())
    xylist += [[x, y]]

xylist.sort()

for i in range(n):
    for j in range(0, i):
        x = xylist[i][0] - xylist[j][0]
        y = xylist[i][1] - xylist[j][1]
        table[x+y*10**10] += 1

max_v = max(table.values())
print(n-max_v)

Submission status: Runtime Error

Solution code:
from collections import Counter
N = int(input())
l = []
pql = []
for i in range(N):
        x, y = map(int, input().split())
        l.append((x,y))
for i in range(N-1):
        p = l[i+1][0] - l[i][0]
        q = l[i+1][1] - l[i][1]
        pql.append((p,q))
pq = Counter(pql)
cntl = pq.most_common(1)
cnt = cntl[0][1]
print(N - cnt)

Submission status: Runtime Error

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

                

d=[]
discount=[]
for i in range(n):
    for j in range(n):
        if i!=j:

            tmp=[x[i][0]-x[j][0],x[i][1]-x[j][1]]

            if tmp not in d:
                d.append(tmp)
                discount.append(1)
            else:
                discount[d.index(tmp)]+=1
                
print(n-max(discount))

Submission status: Runtime Error

Solution code:
from sys import stdin
from collections import Counter
N = int(stdin.readline().rstrip())
data = []
for _ in range(N):
    data.append([int(x) for x in stdin.readline().rstrip().split()])
diff = []
for i in range(1,N):
    diff.append((data[i][0]-data[i-1][0],data[i][1]-data[i-1][1]))
d=Counter(diff)
ans = N - max(d.values())
print(ans)

Submission status: Runtime Error

Solution code:
import math
from collections import Counter


N = int(input())
points = [tuple(map(int, input().split())) for _ in range(N)]
vecs = {}
counter = Counter()

for i, p in enumerate(points):
    for j in range(i, N):
        if j == i:
            continue
        q = points[j]
        a = min(p, q)
        b = max(p, q)
        dx = b[0] - a[0]
        dy = b[1] - a[1]
        gcd = math.gcd(dx, dy)
        if gcd != 0:
            dx //= gcd
            dy //= gcd
        vecs[(i, j)] = (dx, dy)
        counter[(dx, dy)] += 1

vec, _ = counter.most_common()[0]
dx, dy = vec
visited = set()
cost = 0

for i, p in enumerate(points):
    if i in visited:
        continue
    cost += 1
    for j in range(i, N):
        if j == i:
            continue
        if vecs[(i, j)] == (dx, dy):
            visited.add(j)

print(cost)

Submission status: Runtime Error

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

cost = N
from operator import itemgetter
XY.sort(key = itemgetter(0))
dic = {}

for i in range(N-1):
    xx,yy = XY[i]
    x,y = XY[i+1]
    temp = (x-xx,y-yy)
    if temp in dic:
        dic[temp] += 1
    else:
        dic[temp] = 1

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

Submission status: Runtime Error

Solution code:
N = int(input())

cost = 1
xy_set = []
for i in range(N):
    x, y = map(int, input().split())
    xy_set.append((x, y))
xy_set_sorted = sorted(xy_set, key=lambda a: a[0])

xy_sub_set = {}
for i in range(1, N):
    xs = xy_set_sorted[i][0] - xy_set_sorted[i-1][0]
    ys = xy_set_sorted[i][1] - xy_set_sorted[i - 1][1]
    if xy_sub_set.get((xs, ys)) is None:
        xy_sub_set[(xs, ys)] = 1
    else:
        xy_sub_set[(xs, ys)] += 1

xy_sub_set_sorted = sorted(xy_sub_set.items(), key=lambda a: a[1], reverse=True)
print(cost + (N-1) - xy_sub_set_sorted[0][1])

Submission status: Runtime Error

Solution code:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
 
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

import collections

n = ni()
balls = []
dis = []

for i in range(n):
    x,y = na()
    for b in balls:
        dis.append(str(abs(b[0]-x))+'_'+str(abs(b[1]-y)))
    balls.append([x,y])

c = collections.Counter(dis)
u = c.most_common()[0][1]

print(n-u)

Submission status: Runtime Error

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

sys.setrecursionlimit(100000)

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

Submission status: Runtime Error

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


# 点を一番通る直線を求める？何個被るかが答えになるかも<=わｋらｎ
zm = []
for i in range(N-1):
    a=XY[i][0] - XY[i+1][0]
    b=XY[i][1] - XY[i+1][1]
    zm.append((a,b))
from collections import Counter
print(N - Counter(zm).most_common(1)[0][1])

Submission status: Runtime Error

Solution code:
N = int(input())

prev_a, prev_b = map(int, input().split())
diffs = {}
for _ in range(N - 1):
  a, b = map(int, input().split())
  key = "{} {}".format(prev_a - a, prev_b - b)
  if key not in diffs:
    diffs[key] = 2
  else:
    diffs[key] += 1

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

Submission status: Runtime Error

Solution code:
import collections

n = input()
N = int(n)

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

diff = []
for xy in XY:
    for xy2 in XY:
        dx = xy[0] - xy2[0]
        dy = xy[1] - xy2[1]
        d = dx * 10 + dy
        if d != 0:
            diff.append(d)

clist = collections.Counter(diff)

result = N - clist.most_common()[0][1]
print(result)

Submission status: Runtime Error

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

xys.sort()
diffs = []
count = []
# 全探索して、一番共通項が多い差分から計算する
for i in range(N):
    for j in range(i+1,N):
        x1,y1 = xys[i]
        x2,y2 = xys[j]
        diff = (x1-x2, y1-y2)
        if diff not in diffs:
            diffs.append(diff)
            count.append(1)
        else:
            k = diffs.index(diff)
            count[k] += 1

print(N-max(count))

Submission status: Runtime Error

Solution code:
import sys,heapq
from collections import deque,defaultdict
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True  and False
def ddprint(x):
  if DBG:
    print(x)

n = inn()
a = []
for i in range(n):
    x,y = inm()
    a.append((x,y))

h = defaultdict(int)
for i in range(n-1):
    z = a[i]
    for j in range(i+1,n):
        u = a[j]
        p = z[0]-u[0]
        q = z[1]-u[1]
        if p<0:
            p = -p
            q = -q
        elif p==0 and q<0:
            q = -q
        h[(p,q)] += 1

ddprint(h)
mx = max(h.values())
print(n-mx)

Submission status: Runtime Error

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

case = []
for x,y in xy:
    for xx, yy in xy:
        if x == xx and y == yy:
            continue
        score = N
        xs = xx - x
        ys = yy - y
        for xxx,yyy in xy:
            if x == xxx and y == yyy:
                continue
            if (xxx - xs,yyy - ys) in xy:
                score -= 1
        case.append(score)
print(min(case))

Submission status: Runtime Error

Solution code:
n=int(input())
s=[]
d=[]
i=0
while i!=n:
    s=list(map(int,input().split()))
    d.append(s)
    i+=1
#print(d)
i=0
f=[]
s=[]
j=0
while i!=n:
    while j!=n:
        if i!=j:
            f.append(d[i][0]-d[j][0])
            f.append(d[i][1] - d[j][1])
            s.append(f)
            f=[]

        j += 1
    i+=1
    j=0


#print(s)
i=0
f=[]
while i!=len(s):
    f.append(s.count(s[i]))
    i+=1
#print(f)
print(n-max(f))

Submission status: Runtime Error

Solution code:
import itertools

n = int(input())
p = [tuple(map(int, input().split())) for _ in range(n)]
c = {}

for i, j in itertools.combinations(range(len(p)), 2):
  d = (p[j][0] - p[i][0], p[j][1] - p[i][1])
  
  if d not in c:
    c[d] = 1
  else:
    c[d] += 1  

print(len(p) - max(c.values()))

Submission status: Runtime Error

Solution code:
import statistics
n=int(input())
x=[0]*n
xx=[0]*(n-1)
yy=[0]*(n-1)
for i in range(n):
    x[i]=list(map(int,input().split()))
x.sort(key=lambda x:x[1])
x.sort(key=lambda x:x[0])
for i in range(n-1):
    xx[i]=x[i+1][0]-x[i][0]
    yy[i]=x[i+1][1]-x[i][1]
X=statistics.mode(xx)
Y=statistics.mode(yy)
cntx=n-1-xx.count(X)+1
cnty=n-1-yy.count(Y)+1
print(max(cntx,cnty))

Submission status: Runtime Error

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

xydist1 = {}
xylist = list(sorted(xylist, key=lambda x: x[0]))
for (x1, y1), (x2, y2) in zip(xylist, xylist[1:]):
  if (x2-x1, y2-y1) not in xydist1:
    xydist1[(x2-x1, y2-y1)] = 1
  else:
    xydist1[(x2-x1, y2-y1)] += 1

xydist2 = {}
xylist = list(sorted(xylist, key=lambda x: x[1]))
for (x1, y1), (x2, y2) in zip(xylist, xylist[1:]):
  if (x2-x1, y2-y1) not in xydist2:
    xydist2[(x2-x1, y2-y1)] = 1
  else:
    xydist2[(x2-x1, y2-y1)] += 1

max1 = max(xydist1.values())
max2 = max(xydist2.values())
print(n - max(max1, max2))

Submission status: Runtime Error

Solution code:
N = int(input())

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

ans_list = []
for v in itertools.permutations(XY):
    count_list = []
    for (x0, y0), (x1,y1) in zip(v[1:], v[:-1]):
        count_list.append((x1-x0, y1-y0))
    ans_list.append(max(collections.Counter(count_list).values()))
    
ans = N-max(ans_list)
print(ans)