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:
import collections
N = int(input())
alllist = []
minaslist = []
for i in range(N):
    a,b = map(int,input().split())
    alllist.append([a,b])

alllist.sort()

for i in range(N-1):
    minaslist.append((alllist[i+1][0]-alllist[i][0])**2 - (alllist[i+1][1]-alllist[i][1])**2)



countdict = collections.Counter(minaslist)

lista = list(countdict.most_common())
mostnum = lista[0][1]

print(len(minaslist) - mostnum + 1)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
input = sys.stdin.readline

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

def main():

	N = int(input())
	#N, K = map(int, input().split(" "))

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

	xy.sort()
	gess = {}
	xm = 0
	ym = 0

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

	for i, val in enumerate(xy):
		if i == 0:
			x,y = val
			xm = x
			ym = y
			continue
		x, y = val

		if x < xm and y > ym:
			continue
		if x > xm and y < ym:
			continue

		p = x - xm
		q = y - ym
		if (p,q) in gess:
			gess[(p, q)] += 1
		else:
			gess[(p, q)] = 1
		xm = x
		ym = y

	p, q = max(gess, key=gess.get)
	nai = gess[(p,q)]

	#########
	xy = sorted(xy, key=lambda x:(-x[0],-x[1]))
	gess2 = {}
	xm = 0
	ym = 0

	for i, val in enumerate(xy):
		if i == 0:
			x,y = val
			xm = x
			ym = y
			continue
		x, y = val

		if x < xm and y > ym:
			continue
		if x > xm and y < ym:
			continue

		p = x - xm
		q = y - ym
		if (p,q) in gess2:
			gess2[(p, q)] += 1
		else:
			gess2[(p, q)] = 1
		xm = x
		ym = y

	p, q = max(gess2, key=gess2.get)
	nai2 = gess2[(p,q)]

	#########
	xy = sorted(xy, key=lambda x:(x[1]))
	gess3 = {}
	xm = 0
	ym = 0

	for i, val in enumerate(xy):
		if i == 0:
			x,y = val
			xm = x
			ym = y
			continue
		x, y = val

		if x < xm and y > ym:
			continue
		if x > xm and y < ym:
			continue

		p = x - xm
		q = y - ym
		if (p,q) in gess3:
			gess3[(p, q)] += 1
		else:
			gess3[(p, q)] = 1
		xm = x
		ym = y

	p, q = max(gess3, key=gess3.get)
	nai3 = gess3[(p,q)]


	tmp = max(nai, nai2, nai3)

	print(N-tmp)



if __name__ == "__main__":
	main()

Submission status: Runtime Error

Solution code:
import math
import statistics
n=int(input())
x=[0]*n
y=[0]*n
X=[0]*(n-1)
Y=[0]*(n-1)
for i in range(n):
  x[i], y[i] = map(int,input().split())
x=sorted(x)
for i in range(n-1):
  X[i] = x[i+1] - x[i]
  Y[i] = y[i+1] - y[i]
modex = statistics.mode(X)
modey = statistics.mode(Y)
lx = X.count(modex)
ly = Y.count(modey)
print(n-min(lx,ly))

Submission status: Runtime Error

Solution code:
N = int(input())
ary = []
d2 = []
max = 0
sin_max = 0
for _ in range(N):
  ball = list(map(int, input().split()))
  ary.append(ball)
for i in range(N):
    for j in range(N):
        x = ary[i][0] - ary[j][0]
        y = ary[i][1] - ary[j][1]
        tmp = str(x) + str(y)
        d2.append(tmp)
        max = d2.count(d2[0])
        for i in range(1,N-1):
            if max < d2.count(d2[i]):
                max = d2.count(d2[i])
        sin_max = max
    d2 = []
    max = 0
    sin_max = 0

print(N - sin_max)

Submission status: Runtime Error

Solution code:
from collections import Counter
n = int(input())
a = [tuple(map(int, input().split())) for _ in range(n)]
c = Counter((y[0] - x[0], y[1] - x[1]) for i, x in enumerate(a) for y in a[:i])
print(n - max(c.values()))

Submission status: Runtime Error

Solution code:
import bisect
from operator import itemgetter
import math
import collections
import functools
import itertools
import numpy as np
import sys
MAX_INT = int(10e10)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N= I()
xy = [IL() for i in range(N)]

if N == 1:
  print(0)
elif N == 2:
  print(1)
else:
  data = []
  cnt = 0
  for i in itertools.combinations(xy,2):
    rex,rey = i[0]
    x,y = i[1]
    data.append(str(x-rex)+str(y-rey))
  else:
    d = collections.Counter(data)
    cnt = max(cnt,d.most_common()[0][1])

print(N-cnt)

Submission status: Runtime Error

Solution code:
n = int(input())
cnt = dict()
xy = [tuple(map(int, input().split())) for _ in range(n)]
for x1, y1 in xy:
    for x2, y2 in xy:
        if x1 == x2 and y1 == y2:
            continue
        dx = x1 - x2
        dy = y1 - y2
        if (dx, dy) not in cnt:
            cnt[(dx, dy)] = 1
        else:
            cnt[(dx,dy)] += 1
print(n - max(cnt.values()))

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
from collections.abc import Iterable
from math import *
from itertools import *
from collections import *
from functools import *
from operator import *
try:
    from math import gcd
except Exception:
    from fractions import gcd


def solve(N: int, x: "List[int]", y: "List[int]"):
    acc = []
    for i in range(N):
        for j in range(i+1, N):
            dx = x[i] - x[j]
            dy = y[i] - y[j]
            c = gcd(dx, dy)
            acc.append((dx // c, dy // c))
    c = Counter(acc)
    v, (p, q) = max([(v, k) for k, v in c.items()])
    return max(N - v, 1)


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    x = [int()] * (N)  # type: "List[int]" 
    y = [int()] * (N)  # type: "List[int]" 
    for i in range(N):
        x[i] = int(next(tokens))
        y[i] = int(next(tokens))
    result = solve(N, x, y)
    if isinstance(result, Iterable) and not isinstance(result, str):
        result = '\n'.join([str(v) for v in result])
    print(result)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
N = list(map(int, input().split()))
d = {}

pos=[]
for x in range(N[0]):
    a = list(map(int, input().split()))
    for y in pos:
        key = (a[0]-y[0])*(10**11)+(a[1]-y[1])
        if key<0:
            key=-key
        if key not in d:
            d[key] = 0
        d[key] += 1
    pos.append(a)
    
print(N[0]-max(d.values()))

Submission status: Runtime Error

Solution code:
import logging
import numpy as np

logging.disable(logging.CRITICAL)
logging.basicConfig(level=logging.INFO, format = " %(message)s")

def max_counter(diffs):
    num = []
    for i in diffs:
        num.append(diffs.count(i))

    return max(num)
        
        
def main():
    N = int(input())
    
    balls = []
    for i in range(0, N):
        balls.append([int(x) for x in input().split()])

    ball_array = np.array(balls)    
    logging.info(ball_array)

    p_q = []
    for i in range(0, N - 1):
        p_q.append(list(ball_array[i] - ball_array[i + 1]))

    logging.info(p_q)
    print(N - max_counter(p_q))

          
if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from fractions import gcd
N = int(input())
arr = []

def get_unique_list(seq):
    seen = []
    return [x for x in seq if x not in seen and not seen.append(x)]


for i in range(N):
    arr.append(list(map(int, input().split())))

C = []
for i in range(N):
    for j in range(N):
        if i < j:
            x = arr[i][0]-arr[j][0]
            y = arr[i][1]-arr[j][1]
            g = gcd(x, y)
            x = int(x / g)
            y = int(y / g)
            C.append([x, y])

C = get_unique_list(C)
S = [0 for i in range(len(C))]

for c in range(len(C)):
    tmp = [[arr[0][0], arr[0][1]]]
    for i in range(1, N):
        l = len(tmp)
        for j in range(l):
            if (tmp[j][0] - arr[i][0])%C[c][0] == 0 and (tmp[j][1] - arr[i][1])%C[c][1] == 0:
                pass
            else:
                tmp.append([arr[i][0], arr[i][1]])
    S[c] = len(tmp)

print(min(S))

Submission status: Runtime Error

Solution code:
import collections
import numpy as np

N = int(input())

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

xy = np.array(xy)

diff_xy = []

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

cs = []
for c in diff_xy:
    cs.append(diff_xy.count(c))
    
print(1 + (N - (max(cs) + 1)))

Submission status: Runtime Error

Solution code:
from sys import stdin
import sys
import collections

sys.setrecursionlimit(4100000)
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-max(c.values()))

Submission status: Runtime Error

Solution code:
def best_fit(X, Y):

    xbar = sum(X)/len(X)
    ybar = sum(Y)/len(Y)
    n = len(X) # or len(Y)

    numer = sum([xi*yi for xi,yi in zip(X, Y)]) - n * xbar * ybar
    denum = sum([xi**2 for xi in X]) - n * xbar**2

    b = numer / denum
    a = ybar - b * xbar

    #print('best fit line:\ny = {:.2f} + {:.2f}x'.format(a, b))

    return a, b

N = int(input())
Xs = []
Ys = []
cost = 0
for _ in range(N):
  x, y = input().split()
  x, y = int(x), int(y)
  if x not in Xs:
  	Xs.append(x)
  	Ys.append(y)
  else:
    cost += 1
#print(Xs, Ys)
if cost == 0:
  cost = 1

a, b = best_fit(Xs, Ys)

for i, y in enumerate(Ys):
  #print(Xs[i]*a, y)
  newy = a + Xs[i]*b
  #print(newy, y)
  if y != newy:
    cost += 1

print(cost)

Submission status: Runtime Error

Solution code:
n = int(input())

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

i = 0
while True:
    if xl[i][0]-xl[0][0] != 0:
        p = xl[i][0]-xl[0][0]
        q = xl[i][1]-xl[0][1]
        break
    i += 1

leng = len(xl)-1
count = 0
for i in range(leng):
    an = [xl[leng][0] + p , xl[leng][1] + q]
    if an in xl:
        count += 0
    else:
        count += 1
    leng -= 1

if count == 0:
    print(1)
else:
    print(count)

Submission status: Runtime Error

Solution code:
import collections

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

opt_list = []
for i in range(len(XY)):
    if i == len(XY) - 1:
        break
    else:
        opt_list.append([XY[i+1][0] - XY[i][0], XY[i+1][1] - XY[i][1]])

c = collections.Counter(map(tuple, opt_list))

f_opt = list(c.most_common()[0][0])


cost_list = []
for i in XY:
    cost = 0
    for j in XY:
        if i == j:
            continue
        elif [i[0] - j[0], i[1] - j[1]] == f_opt:
            cost = cost
        else:
            cost += 1

    cost_list.append(cost)

if min(cost_list) >= 1:
    print(min(cost_list))
else:
    print(sorted(cost_list)[1])

Submission status: Runtime Error

Solution code:
import sys
from itertools import permutations
import math
from collections import defaultdict


class UnionFind(object):
    def __init__(self, N):
        self._parent = list(range(N))
        self.__num_components = [1] * N

    def root(self, x):
        if self._parent[x] == x:
            return x
        else:
            # root abbreviation
            self._parent[x] = self.root(self._parent[x])
            return self._parent[x]

    def same(self, x, y):
        return self.root(x) == self.root(y)

    def num_connected(self, x):
        return self.__num_components[self.root(x)]

    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if (x == y):
            return
        rank_x = self.__num_components[x]
        rank_y = self.__num_components[y]
        if rank_x < rank_y:
            self._parent[x] = y
            self.__num_components[y] += rank_x
        else:
            self._parent[y] = x
            self.__num_components[x] += rank_y
        return


fin = sys.stdin.readline

N = int(fin())
coordinates = [[int(elem) for elem in fin().split()] + [i] for i in range(N)]

# p, qのペアを計算
pq_set = set()
all_dists = defaultdict(list)
count_dist_set = defaultdict(set)
for each_pair in permutations(coordinates, 2):
    each_p = each_pair[0][0]-each_pair[1][0]
    each_q = each_pair[0][1] - each_pair[1][1]
    if each_p < 0:
        each_p = -each_p
        each_q = -each_q
    gcd = math.gcd(each_p, each_q)
    each_pq = (int(each_p/gcd), int(each_q/gcd))
    pq_set.add(each_pq)
    all_dists[each_pq].append([each_pair[0][2], each_pair[1][2]])
    count_dist_set[each_pq] = count_dist_set[each_pq].union({each_pair[0][2], each_pair[1][2]})

# 適当にスタート，探索を行う
count_list = []
count_tree_dic = {}
for each_pq in all_dists:
    uf = UnionFind(N)
    for x, y in all_dists[each_pq]:
        uf.unite(x, y)
    num_distinct_components = 0
    for i in range(N):
        if uf.root(i) == i:
            num_distinct_components += 1
    count_tree_dic[each_pq] = num_distinct_components
    count_list.append(num_distinct_components)

print(min(count_list))

Submission status: Runtime Error

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

cost_min = 10 ** 4
if N == 1 or N == 2:
  print(1)
else:
  xy.sort()
  for i in range(N-1):
    cost = 1
    p = xy[i][0] - xy[i+1][0]
    q = xy[i][1] - xy[i+1][1]
    for j in range(N-1):
      if xy[j+1][0] + p == xy[j][0] and xy[j+1][1] + q == xy[j][1]:
        pass
      else:
        cost += 1
    if cost < cost_min:
      cost_min = cost
  xy = sorted(xy, key=lambda x: x[1])
  for i in range(N-1):
    cost = 1
    p = xy[i][0] - xy[i+1][0]
    q = xy[i][1] - xy[i+1][1]
    for j in range(N-1):
      if xy[j+1][0] + p == xy[j][0] and xy[j+1][1] + q == xy[j][1]:
        pass
      else:
        cost += 1
    if cost < cost_min:
      cost_min = cost
  for i in range(N-2):
    cost = 1
    p = xy[i][0] - xy[i+2][0]
    q = xy[i][1] - xy[i+2][1]
    for j in range(N-2):
      if xy[j+2][0] + p == xy[j][0] and xy[j+2][1] + q == xy[j][1]:
        pass
      else:
        cost += 1
    for j in range(1, N-2, 2):
      cost += 1
      if xy[j+2][0] + p == xy[j][0] and xy[j+2][1] + q == xy[j][1]:
        pass
      else:
        cost += 1
    if cost < cost_min:
      cost_min = cost
  xy.sort()
  for i in range(N-2):
    cost = 1
    p = xy[i][0] - xy[i+2][0]
    q = xy[i][1] - xy[i+2][1]
    for j in range(N-2, 2):
      if xy[j+2][0] + p == xy[j][0] and xy[j+2][1] + q == xy[j][1]:
        pass
      else:
        cost += 1
    for j in range(1, N-2, 2):
      cost += 1
      if xy[j+2][0] + p == xy[j][0] and xy[j+2][1] + q == xy[j][1]:
        pass
      else:
        cost += 1
    if cost < cost_min:
      cost_min = cost
      
  print(cost_min)

Submission status: Runtime Error

Solution code:
N = int(input())
S = []
for _ in range(N):
    x, y = map(int, input().split())
    S.append(x + y)
S.sort()
cost = N
target = 1
# 同じではなくて割り切れるやつを探す
for a in S:
    temp_cost = 1
    bb = -1
    for b in S:
        if bb != b and b % a != 0:
            # print("a:{0}, b:{1}".format(a, b))
            temp_cost += 1
        bb = b
    temp_cost += S.count(a) - 1
    if temp_cost < cost:
        cost = temp_cost
print(cost)

Submission status: Runtime Error

Solution code:
import collections

N = int(input())

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

xy = np.array(xy)

diff_xy = []

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

cs = []
for c in diff_xy:
    cs.append(diff_xy.count(c))
    
print(1 + (N - (max(cs) + 1)))

Submission status: Runtime Error

Solution code:
N = int(input())

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

vec = []
for i in range(N):
    for j in range(i+1,N,1):
        vec.append([point[i][0]-point[j][0],point[i][1]-point[j][1]])

N2 = len(vec)
check = [0 for i in range(N2)]

for i in range(N2):
    for j in range(N2):
        minus = [-vec[j][0],-vec[j][1]]
        if vec[i] == vec[j] or vec[i] == minus:
            check[i] += 1
            
if N == 10:
    print(1)
else:
    print(N-max(check))

Submission status: Runtime Error

Solution code:
import itertools
from collections import Counter
N=int(input())
balls=[]

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

pqs=[]
for i in itertools.permutations(balls,2):
    p=i[1][0]-i[0][0]
    q=i[1][1]-i[0][1]
    pqs.append((p,q))

c=Counter(pqs)
c=dict(c)
c=sorted(c.items(),key=lambda w:w[1],reverse=True)
print(N-c[0][1])

Submission status: Runtime Error

Solution code:
from collections import Counter
N = int(input())
nums = []
costs = []
xup =[]
yup =[]
ans = 1
for i in range(N):
    x,y = map(int,input().split())
    nums.append((x,y))
nums.sort(key=lambda  x:(x[0],x[1]))
for i in range(1,len(nums)):
    xup.append(nums[i][0]-nums[i-1][0])
    yup.append(nums[i][1] - nums[i-1][1])
values,counts = zip(*Counter(xup).most_common())
newxups = []
maxx = max(counts)
for value,counts in zip(values,counts):
    if counts==maxx:
        newxups.append(value)
newyups = []
values,counts = zip(*Counter(yup).most_common())
maxy = max(counts)
for value,counts in zip(values,counts):
    if counts==maxy:
        newyups.append(value)
newyup = Counter(yup).most_common()[0][0]
newxup = Counter(xup).most_common()[0][0]
ans = 1
anss = []
for xup in newxups:
    ans=1
    for yup in newyups:
        for i in range(1,len(nums)):
            if nums[i][0] - xup != nums[i - 1][0] or nums[i][1] - yup != nums[i - 1][1]:
                ans += 1
    anss.append(ans)
print(anss)

Submission status: Runtime Error

Solution code:
from itertools import combinations
n = int(input())
xy = [tuple(map(int,input().split())) for _ in range(n)]
pq = {}
for i, j in combinations(xy, 2):
  if abs(i[0]-j[0]) == abs(i[1]-j[1]) == 0:
    continue
  p = i[0] - j[0]
  if p < 0:
    p = -1 * p
    q = j[1] - i[1]
  else:
    q = i[1] - j[1]
  if (p,q) in pq.keys():
    pq[(p,q)].append([i, j])
  else:
    pq[(p,q)] = [[i, j]]
maxpqlen = 0
maxpq = (0, 0)
for pq_, points in pq.items():
  if len(points) > maxpqlen:
    maxpqlen = len(points)
    maxpq = pq_
se = set()
for li in pq[maxpq]:
  se |= {li[0], li[1]}
seo = set(xy) - se
se1 = sorted(list(se))
se2 = se1.copy()
p = []
cost = 1
while se1:
  poe = se1.pop(0)
  pupu = (poe[0] + maxpq[0], poe[1] + maxpq[1])
  if pupu not in se1:
    if se1:
      cost += 1
    else:
      continue
p.append(cost)
cost = 1
while se2:
  poe = se2.pop(0)
  pupu = (poe[0] + maxpq[0], poe[1] - maxpq[1])
  if pupu not in se2:
    if se2:
      cost += 1
    else:
      continue
p.append(cost)
cost = min(p) + len(seo)
print(cost)from itertools import combinations
n = int(input())
xy = [tuple(map(int,input().split())) for _ in range(n)]
pq = {}
for i, j in combinations(xy, 2):
  if abs(i[0]-j[0]) == abs(i[1]-j[1]) == 0:
    continue
  p = i[0] - j[0]
  if p < 0:
    p = -1 * p
    q = j[1] - i[1]
  else:
    q = i[1] - j[1]
  if (p,q) in pq.keys():
    pq[(p,q)].append([i, j])
  else:
    pq[(p,q)] = [[i, j]]
maxpqlen = 0
maxpq = (0, 0)
for pq_, points in pq.items():
  if len(points) > maxpqlen:
    maxpqlen = len(points)
    maxpq = pq_
se = set()
for li in pq[maxpq]:
  se |= {li[0], li[1]}
seo = set(xy) - se
se1 = sorted(list(se))
se2 = se1.copy()
p = []
cost = 1
while se1:
  poe = se1.pop(0)
  pupu = (poe[0] + maxpq[0], poe[1] + maxpq[1])
  if pupu not in se1:
    if se1:
      cost += 1
    else:
      continue
p.append(cost)
cost = 1
while se2:
  poe = se2.pop(0)
  pupu = (poe[0] + maxpq[0], poe[1] - maxpq[1])
  if pupu not in se2:
    if se2:
      cost += 1
    else:
      continue
p.append(cost)
cost = min(p) + len(seo)
print(cost)

Submission status: Runtime Error

Solution code:
N = int(input())
xys = [[int(j) for j in input().split()] for i in range(N)]
xys.sort(key=lambda x: x[0])
hikizan = [[xy2[0] - xy1[0], xy2[1] - xy1[1]] for i, xy1 in enumerate(xys) for j, xy2 in enumerate(xys) if i < j]
counting = [sum([1 for c in hikizan if h[0]==c[0] and h[1]==c[1]]) for h in hikizan]
print(N - max(counting))

Submission status: Runtime Error

Solution code:
import numpy as np

def main():
    n = int(input())
    ball = [list(map(int, input().split(' '))) for i in range(n)]
    ball = np.array(ball, dtype=int)
    # print(ball)

    l1 = []
    l2 = []
    for i in range(n):
        for j in range(i, n):
            if i == j: continue
            dis1 = ball[i] - ball[j]
            dis2 = ball[j] - ball[i]
            l1.append(list(dis1))
            l2.append(list(dis2))
    # print(l1, l2)
    # c1 = collections.Counter(l1)
    # c2 = collections.Counter(l2)

    c1 = []
    c2 = []
    for i in range(len(l1)):
        c1.append(l1.count(l1[i]))
        c2.append(l2.count(l2[i]))
    m1 = np.max(np.array(c1, dtype=int))
    m2 = np.max(np.array(c2, dtype=int))

    print(max(1,n-max(m1,m2)))

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from collections import Counter
import itertools

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


ptn=list(itertools.combinations(xy,2))
pq=[]
for idx,val in enumerate(ptn):
        pq.append(str(val[1][0]-val[0][0]) + 'x' + str(val[1][1]-val[0][1]))

cpq = Counter(pq)

# pqans=cpq.most_common(1)[0][0]
redsc=cpq.most_common(1)[0][1]

# p,q = map(int,pqans.split('x'))

print(N-redsc)

Submission status: Runtime Error

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

sabun_dict = {}

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

max_v = max(sabun_dict.values())

print(n - max_v)

Submission status: Runtime Error

Solution code:
import sys
import collections
input = sys.stdin.readline
n = int(input())
xy = []
for i in range(n):
    _a,_b = map(int,input().split())
    xy.append([_a,_b])
sxy = sorted(xy)
sxy2 = []
for i in range(1,n):
    sxy2.append(((sxy[i][0]-sxy[i-1][0])**2)+((sxy[i][1]-sxy[i-1][1])**2))
c = collections.Counter(sxy2)
print(len(sxy2)-max(c.values()) + 1)

Submission status: Runtime Error

Solution code:
N = int(input())
S = []
for _ in range(N):
    x, y = map(int, input().split())
    S.append(x + y)
S.sort()
cost = N
target = 1
# 同じではなくて割り切れるやつを探す
for a in S:
    temp_cost = 1
    bb = -1
    for b in S:
        if bb != b and b % a != 0:
            # print("a:{0}, b:{1}".format(a, b))
            temp_cost += 1
        bb = b
    temp_cost += S.count(a) - 1
    if temp_cost < cost:
        print(temp_cost)
        cost = temp_cost
print(cost)

Submission status: Runtime Error

Solution code:
from collections import defaultdict as de
s=de(int)
n=int(input())
a=[list(map(int,input().split()))for i in range(n)]
for i in range(n):
    for j in range(n):
        if i!=j:
            s[(a[i][0]-a[j][0],a[i][1]-a[j][1])]+=1
p,q=max([(v,k) for k,v in s.items()])[1]
f=0
while len(a)!=0:
    b,c=a[0]
    f+=1
    g=[]
    for i in range(1,len(a)):
        d,e=a[i]
        if d-b==0:
            if q!=0:
                g.append([d,e])
        elif q==0:
            if d-b!=0:
                g.append([d,e])
        elif (e-c)/(d-b)!=q/p:
            g.append([d,e])
    else:
        a=g[:][1:]
print(f)

Submission status: Runtime Error

Solution code:
from sys import stdin
import collections

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-max(c.values()))

Submission status: Runtime Error

Solution code:
import itertools
n = int(input())
xn =[]
yn = []
d = []
dli = []
z = []
ans = []
for _ in range(n):
    x,y = map(int,input().split())
    xn.append(x)
    yn.append(y)
    d.append([x,y])
dli = list(itertools.combinations(d,2))
for i in range(len(dli)):
    a = [dli[i][1][0]-dli[i][0][0],dli[i][1][1]-dli[i][0][1]]
    z.append(a)
for j in range(len(z)):
    b = z.count(z[j])
    ans.append(b)

print(n - max(ans))

Submission status: Runtime Error

Solution code:
N = int(input())

List = list(list(map(int, input().split())) for i in range(N))
# List = [[map(int, input().split())] for i in range(N)]
Data = []
# print(List)
List.sort(key=lambda x:(x[0],x[1]))



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

# print(Data)

Duplicate = []
for k in range(len(Data)):
    if(Data[k] == [0,0]):
        continue
    else:
        Duplicate.append(Data.count(Data[k]))
    # print(Data[k])

# print(Duplicate)

ans = N - max(Duplicate)
print(ans)

Submission status: Runtime Error

Solution code:
import statistics
import copy
n=int(input())
if n==1:
    x=list(map(int,input().split()))
    print(1)
else:
    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)
    if X==0 and Y==0:
        XX=copy.copy(xx)
        XX.remove(0)
        X=statistics.mode(xx)
        YY=copy.copy(yy)
        YY.remove(0)
        Y=statistics.mode(yy)
        cntx=n-1-xx.count(X)+1
        cnty=n-1-yy.count(Y)+1
        cntx0=n-1-xx.count(0)+1
        cnty0=n-1-yy.count(0)+1
        ansxmin(max(cntx0,cnty),max(cntx,cnty0))
    else:
        cntx=n-1-xx.count(X)+1
        cnty=n-1-yy.count(Y)+1
        ansx=max(cntx,cnty)
    x.sort(key=lambda x:x[0])
    x.sort(key=lambda x:x[1])
    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)
    if X==0 and Y==0:
        XX=copy.copy(xx)
        XX.remove(0)
        X=statistics.mode(xx)
        YY=copy.copy(yy)
        YY.remove(0)
        Y=statistics.mode(yy)
        cntx=n-1-xx.count(X)+1
        cnty=n-1-yy.count(Y)+1
        cntx0=n-1-xx.count(0)+1
        cnty0=n-1-yy.count(0)+1
        ansy=min(max(cntx0,cnty),max(cntx,cnty0))
    else:
        cntx=n-1-xx.count(X)+1
        cnty=n-1-yy.count(Y)+1
        ansy=max(cntx,cnty)
    print(min(ansx,ansy))

Submission status: Runtime Error

Solution code:
from itertools import combinations


def main():
    N = int(input())
    x = []
    y = []
    for _ in range(N):
        x_n, y_n = map(int, input().split())
        x.append(x_n)
        y.append(y_n)
    comb = list(combinations([i for i in range(N)], 2))
    dic = {}
    for c in comb:
        i, j = c[0], c[1]
        dx = x[j] - x[i]
        dy = y[j] - y[i]
        if not (dx, dy) in dic.keys():
            dic[(dx, dy)] = 0
        if not (-dx, -dy) in dic.keys():
            dic[(-dx, -dy)] = 0
        dic[(dx, dy)] += 1
        dic[(-dx, -dy)] += 1
    dic_sorted = sorted(dic.items(), key=lambda x:x[1])[::-1]
    print(N - dic_sorted[0][1])
    return


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import logging
import unittest
from collections import (
    Counter,
)

debug = logging.getLogger(__name__).debug


def input_ints():
    return list(map(int, input().strip().split()))


def _main():
    n = input_ints()[0]
    xy = [input_ints() for _ in range(n)]

    (_, count), = Counter(
        (x1 - x2, y1 - y2)
        for (x1, y1) in xy
        for (x2, y2) in xy
        if not (x1 == x2 and y1 == y2)
    ).most_common(1)

    print(len(xy) - count)


class Test(unittest.TestCase):
    def setUp(self):
        import run
        self._test = run

    def test_main(self):
        self._test.test_files(self, _main)


if __name__ == '__main__':
    _main()

Submission status: Runtime Error

Solution code:
import collections
import itertools

N = int(input())

x, y = [], []

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

l = []

for c in itertools.combinations(range(N), 2):
    x1 = x[c[0]]
    y1 = y[c[0]]
    x2 = x[c[1]]
    y2 = y[c[1]]

    l.append((abs(x1-x2), abs(y1-y2)))

c = collections.Counter(l)
p = c.most_common()[0][0]
pp = c.most_common()[0][1]

aa = []

for c in itertools.combinations(range(N), 2):
    x1 = x[c[0]]
    y1 = y[c[0]]
    x2 = x[c[1]]
    y2 = y[c[1]] 

    if (abs(x1-x2), abs(y1-y2)) == p:
        aa.append(c)

assert(len(aa) == pp)

ll = [0] * N
curG = 0
for i in range(pp):
    if (ll[aa[i][0]] == 0 and ll[aa[i][0]] == 0):
        curG += 1
    ll[aa[i][0]] = curG
    ll[aa[i][1]] = curG

k = 1 if 0 in ll else 0

ccc = len(set(ll)) - k

z = ll.count(0)

inter = (N - z) - ccc

print(N-inter)

Submission status: Runtime Error

Solution code:
import collections

N = int(input())

x = [0 for _ in range(N)]
y = [0 for _ in range(N)]

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

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

#print(tmp)
tmp_str = []
for s in tmp:
    tmp_str.append(str(s))


#print(tmp_str)
tmp_str_cnt = collections.Counter(tmp_str)
str_ans = tmp_str_cnt.most_common()[0][0]
int_ans = tmp_str_cnt.most_common()[0][1]

print(N-int_ans)