Problem:


Score : 300 points

Problem Statement

There are N balls in a two-dimensional plane. The i-th ball is at coordinates (x_i, y_i).

We will collect all of these balls, by choosing two integers p and q such that p \neq 0 or q \neq 0 and then repeating the following operation:

Choose a ball remaining in the plane and collect it. Let (a, b) be the coordinates of this ball. If we collected a ball at coordinates (a - p, b - q) in the previous operation, the cost of this operation is 0. Otherwise, including when this is the first time to do this operation, the cost of this operation is 1.

Find the minimum total cost required to collect all the balls when we optimally choose p and q.

Constraints

1 \leq N \leq 50

|x_i|, |y_i| \leq 10^9

If i \neq j, x_i \neq x_j or y_i \neq y_j.

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
x_1 y_1
:
x_N y_N

Output

Print the minimum total cost required to collect all the balls.

Sample Input 1

2
1 1
2 2

Sample Output 1

1

If we choose p = 1, q = 1, we can collect all the balls at a cost of 1 by collecting them in the order (1, 1), (2, 2).

Sample Input 2

3
1 4
4 6
7 8

Sample Output 2

1

If we choose p = -3, q = -2, we can collect all the balls at a cost of 1 by collecting them in the order (7, 8), (4, 6), (1, 4).

Sample Input 3

4
1 1
1 2
2 1
2 2

Sample Output 3

2



Sample input:
2
1 1
2 2


Sample output:
1

Submission status: Runtime Error

Solution code:
from collections import Counter, deque

data = []
N = int(input())
for i in range(N):
	data.extend([list(map(int, input().split(' ')))])
x = []

for e_set in data:
    for sub_set in data:
        x.append((e_set[0] - sub_set[0], e_set[1] - sub_set[1]))

val = Counter(x)
commons = val.most_common()[1][1]
ans = N - commons
if ans == 0:
  print(1)
else:
  print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
l = []
l2 = []

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

for i in range(len(l)):
    for j in range(i+1, len(l)):
        dif1 = l[i][0] - l[j][0]
        dif2 = l[i][1] - l[j][1]
        l2.append(str(dif1) + ' ' + str(dif2))


cnt = l2.count(max(l2, key=l2.count))

print(n - cnt)

Submission status: Runtime Error

Solution code:
from collections import Counter
n=int(input())
xy = sorted([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)]).keys()
B = Counter([xy[i+1][1]-xy[i][1] for i in range(0,len(xy)-1)]).keys()
A = [i for i in range(-1*max(A),max(A)+1)] if max(A)>=0 else  [i for i in range(max(A),-1*max(A)+1)]
B = [i for i in range(-1*max(B),max(B)+1)] if max(B)>=0 else  [i for i in range(max(B),-1*max(B)+1)]
final_ans=10**9
for a in A:
	if a==0:
		continue
	for b in B:
		if b==0:
			continue
		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]
		tmp_ans = min(ans,tmp)
		final_ans = min(final_ans,tmp_ans)

print(final_ans if final_ans!=0 else final_ans+1)

Submission status: Runtime Error

Solution code:
from collections import Counter


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

vector = [0] * ((N * (N - 1)) // 2)
cnt = 0
for i in range(N):
    for j in range(i + 1, N):
        x = ball[i][0] - ball[j][0]
        y = ball[i][1] - ball[j][1]
        if x < 0:
            x, y = -x, -y
        elif x == 0:
            if y < 0:
                y = -y
        vector[cnt] = x * (10 ** 10) + y
        cnt += 1
C = Counter(vector)
print(N - C.most_common()[0][1])

Submission status: Runtime Error

Solution code:
a = 2
print "1"

Submission status: Runtime Error

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


for i in range(n):
    for j in range(i+1,n):
        l.append([p[j][0]-p[i][0],p[j][1]-p[i][1]])

m=0
for i in range(len(l)):
    cnt=0
    tmp=0
    for j in range(len(l)):
        if l[i][0]==0:
            tmp=l[i][1]:
            if l[i][0]==l[j][0] and l[i][1]==l[j][1] and i!=j and tmp==l[j][1] or l[i][0]==-l[j][0] and l[i][1]==-l[j][1] and i!=jand tmp==l[j][1]:
                cnt+=1
        elif l[i][1]==0:
            tmp=l[i][0]:
            if l[i][0]==l[j][0] and l[i][1]==l[j][1] and i!=j and tmp==l[j][0] or l[i][0]==-l[j][0] and l[i][1]==-l[j][1] and i!=jand tmp==l[j][0]:
                cnt+=1
        elif l[i][0]==l[j][0] and l[i][1]==l[j][1] and i!=j or l[i][0]==-l[j][0] and l[i][1]==-l[j][1] and i!=j:
                cnt+=1
        if cnt>m:
            m=cnt
        
ans=n
if m!=0:
    ans=n-m-1
if n==2:
    ans=1
print(ans)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
from operator import sub

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(map(sub, balls[i], balls[j]))] += 1
    try:
        mmax = max(d.values())
        mmax = int(N - mmax)
    except:
        print(100)
    print(str(mmax))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import numpy as np

N = int(input())
list_coord = list()
for i in range(N):
    list_coord.append([int(i) for i in input().split()])
arr_coord = np.array(list_coord)

arr_pat = np.array([])
for i in range(N):
    for j in range(N):
        if i > j:
            arr_pat = np.append(arr_pat, (arr_coord[i] - arr_coord[j]))

arr_pat = arr_pat.reshape(int(len(arr_pat)/2), 2)

arr_pat_uni, arr_pat_cnt = np.unique(arr_pat, axis=0, return_counts=True)

print(N-np.max(arr_pat_cnt))

Submission status: Runtime Error

Solution code:
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()

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

n = ni()
li = []
li2 = []
for i in range(n):
    x, y = na()
    li.append([x,y])
    li2.append((i,x*x+y*y))
li2.sort(key=lambda x:(x[1],x[0]))
#print(li2)
ct = 1
dif = []
li3 = []
for i in range(n-1):
    mae = li[li2[i][0]]
    li3.append(mae)
    tugi = li[li2[i+1][0]]
    dx = tugi[0] - mae[0]
    dy = tugi[1] - mae[1]
    #print(dx,dy)
    dif.append([dx, dy])
li3.append(li[li2[n-1][0]])
ddd = get_unique_list(dif)
#print(li3)
#print(ddd)
cl = []
for d in ddd:
    ct = 1
    for i in range(n-1):
        if [d[0]+li3[i][0], d[1]+li3[i][1]] not in li3:
            ct += 1
    cl.append(ct)
print(min(cl))

Submission status: Runtime Error

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

N = [int(i) for i in input().split()][0]

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

salist=[]
for i in range(1,len(balls),1):
  sax = balls[i][0]-balls[i-1][0]
  say = balls[i][1]-balls[i-1][1]
  salist.append([sax,say])
  
balls.reverse()
costs=[]
for i,sa in enumerate(reversed(salist)):
  cost=1
  for i in range(0,len(balls)-1,1):
    if balls[i+1][0]!=balls[i][0]-sa[0] and balls[i+1][1]!=balls[i][1]-sa[1]:
      cost+=1
  costs.append(cost)

print(min(costs))

Submission status: Runtime Error

Solution code:
N = int(input())
xlist = []
ylist = []
pqlist = []
pqcount = {}
for i in range(N):
  x, y = map(int, input().split(" "))
  xlist.append(x)
  ylist.append(y)

for i in range(N-1):
  for j in range(i+1, N):
    p = xlist[i] - xlist[j]
    q = ylist[i] - ylist[j]
    tuple_pq = (p, q,)
    if not (tuple_pq in pqlist):
      pqlist.append(tuple_pq)
      pqcount[tuple_pq] = 1
    else:
      pqcount[tuple_pq] += 1

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

Submission status: Runtime Error

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

xy.sort()

ans = 0
while len(xy) > 2:
  rem_list = [[] for _ in range(N)]
  rem_cnt = 0
  rem_num = 0
  for i in range(1, N):
    p, q = xy[i][0] - xy[0][0], xy[i][1] - xy[0][1]
    cnt = 0
    for j in range(1, N):
      if p == 0 and xy[j][0] == xy[0][0] or q == 0 and xy[j][1] == xy[0][1]:
        cnt += 1
        rem_list[i].append(xy[j])
      elif p * q != 0 and (xy[j][0] - xy[0][0]) * p * (xy[j][1] - xy[0][1]) * q > 0 and (xy[j][0] - xy[0][0]) % p == 0 and (xy[j][1] - xy[0][1]) % q == 0:
        cnt += 1
        rem_list[i].append(xy[j])
    if rem_cnt < cnt:
      rem_cnt = cnt
      rem_num = i
  for r in rem_list[rem_num]:
    xy.remove(r)
  del xy[0]
  ans += 1

if len(xy) > 0:
  ans += 1
print(ans)

Submission status: Runtime Error

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

sys.setrecursionlimit(100000000)

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のペアを計算
all_dists = defaultdict(list)
for each_pair in combinations(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
    if each_p * each_q == 0:
        each_p = abs(each_p)
        each_q = abs(each_q)
    each_pq = (each_p, each_q)
    all_dists[each_pq].append([each_pair[0][2], each_pair[1][2]])

# 適当にスタート，探索を行う
count_list = []
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_list.append(num_distinct_components)

print(max(min(count_list), 1))

Submission status: Runtime Error

Solution code:
n=int(input())
r=[]
a=[]
for i in range(n):
  b,c=(int(j) for j in input().split())
  for k in range(i):
    d=abs(a[k][0]-b)
    e=abs(a[k][1]-c)
    r.append([d,e])
  a.append([b,c])
r.sort()
p=r[0]
x=1
z=1
t=0
q=[]
for i in range(len(r)-1):
  if r[i]==r[i+1]:
    x=x+1
  else:
    if x>z:
      p=r[i]
    x=1
for i in range(n):
  if a[i] not in q:
    t=t+1
  q.append([a[i][0]+p[0],a[i][1]+p[1]])
  q.append([a[i][0]-p[0],a[i][1]-p[1]])
print(t)

Submission status: Runtime Error

Solution code:
from collections import Counter
N = int(input())
l = [[int(arr) for arr in input().split()] for i in range(N)]
l.sort()
tmp = [[b - a for a, b in zip(l[j],l[k])] for j in range(N-1) for k in range(j+1,N)]
c = Counter(map(tuple, tmp))
m = c.most_common(1)[0][1]
print(N-m)

Submission status: Runtime Error

Solution code:
import collections
 
n = int(input())
l = []
l1 = []
for i in range(n):
  x, y = map(int,input().split())
  l.append((x, y))
l.sort(reverse=True)
for i in range(len(l)-1):
  a = l[i][0] - l[i+1][0]
  b = l[i][1] - l[i+1][1]
  l1.append((a,b))
c = collections.Counter(l1)
values, counts = zip(*c.most_common())
for i, j in zip(values, counts):
  if i[0] != 0 or i[1] != 0:
    num = n-j
    break
  else:
    num = n
print(num)

Submission status: Runtime Error

Solution code:
N = int(input())
xlist = []
ylist = []
pqlist = []
pqcount = {}
for i in range(N):
  x, y = map(int, input().split(" "))
  xlist.append(x)
  ylist.append(y)

for i in range(N):
  for j in range(i+1, N):
    p = xlist[i] - xlist[j]
    q = ylist[i] - ylist[j]
    tuple_pq = (p, q,)
    if not (tuple_pq in pqlist):
      pqlist.append(tuple_pq)
      pqcount[tuple_pq] = 1
    else:
      pqcount[tuple_pq] += 1

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

Submission status: Runtime Error

Solution code:
import numpy as np

N = int(input())
list_coord = list()
for i in range(N):
	list_coord.append([int(i) for i in input().split()])
arr_coord = np.array(list_coord)

arr_pat = np.array([])
for i in range(N):
	for j in range(N):
		if i > j:
			arr_pat = np.append(arr_pat, (arr_coord[i] - arr_coord[j]))

arr_pat = arr_pat.reshape(int(len(arr_pat)/2), 2)

arr_pat_uni, arr_pat_cnt = np.unique(arr_pat, axis=0, return_counts=True)

print(int(N-np.max(arr_pat_cnt)))

Submission status: Runtime Error

Solution code:
import collections

n = int(input())
l = []
l1 = []
for i in range(n):
  x, y = map(int,input().split())
  l.append((x, y))
l.sort(reverse=True)
for i in range(len(l)-1):
  a = l[i][0] - l[i+1][0]
  b = l[i][1] - l[i+1][1]
  l1.append((a,b))
c = collections.Counter(l1)
print(c.most_common()) 
values, counts = zip(*c.most_common())
for i, j in zip(values, counts):
  if i[0] != 0 or i[1] != 0:
    num = n-j
    break
  else:
    num = n
print(num)

Submission status: Runtime Error

Solution code:
import numpy as np

N = int(input())
list_coord = list()
for i in range(N):
  list_coord.append([int(i) for i in input().split()])
arr_coord = np.array(list_coord)

arr_pat = np.array([])
for i in range(N):
  for j in range(N):
    if i > j:
      arr_pat = np.append(arr_pat, (arr_coord[i] - arr_coord[j]))

arr_pat = arr_pat.reshape(int(len(arr_pat)/2), 2)

arr_pat_uni, arr_pat_cnt = np.unique(arr_pat, axis=0, return_counts=True)

print(int(N-np.max(arr_pat_cnt)))

Submission status: Runtime Error

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

sabun = []
for i in range(N):
    for j in range(N):
        if i == j:
            continue
        else:
            p = xy[i][0] - xy[j][0]
            q = xy[i][1] - xy[j][1]
            sabun.append([p,q])
count = [sabun.count(i)+sabun.count([-i[0],-i[1]]) for i in sabun]
print(int(N-(max(count))/2))

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.keys():
            d[key] = 0
        d[key] += 1
    pos.append(a)
    
print(N[0]-max(d.values()))

Submission status: Runtime Error

Solution code:
from collections import Counter
n = int(input())
s = [list(map(int,input().split())) for i in range(n)]
c = []
for i in range(n):
    for j in range(i+1,n):
        x = s[j][0] - s[i][0]
        y = s[j][1] - s[i][1]
        c.append(str(x) + " " + str(y))

r = Counter(c)
q = list(r.values())
q1 = max(q)
print(n-q1)

Submission status: Runtime Error

Solution code:
from collections import Counter

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

dc_c = []
dc_c = []
dc_ans = []
for i in range(n-1):
    ii = 0
    d = [[-1]*2 for i in range(n-1)]
    for j in range(i,n):
        if i != j:
            d[ii][0] = abs(x[i]-x[j])
            d[ii][1] = abs(y[i]-y[j])
            ii += 1
    dc = Counter(map(tuple, d))
    dc_ans = Counter(dc_ans) + dc
dc_ans = dc_ans.most_common()
if dc_ans[0][0] == (-1, -1):
    print(n-dc_ans[1][1])
else:
    print(n-dc_ans[0][1])

Submission status: Runtime Error

Solution code:
import fractions
from heapq import *

if __name__ == "__main__":
  N = int(input())
  A = list(map(int, input().split()))
  A.sort()
  
  print(sum(A[(len(A)) // 2:]) - sum(A[0:(len(A)) // 2]))

  for i in range(N - 1):
    a, b = heappop(A), heappop(A)
    heappush(A, a - b)
    print(b, a)

Submission status: Runtime Error

Solution code:
import collections
import copy
N = int(input())

cost = 0
diff_list = []
x_y_list = []

if N == 1:
    print(1)

for n in range(N):
    x, y = map(int, input().split())
    x_y_list.append((x, y))
    cost += 1

x_y_list_copy = copy.copy(x_y_list)

for n in range(N):
    x_y = x_y_list.pop()
    x = x_y[0]
    y = x_y[1]
    for tmp_x, tmp_y in x_y_list:
        diff_list.append((x - tmp_x, y - tmp_y))

for n in range(N):
    x_y = x_y_list_copy.pop(0)
    x = x_y[0]
    y = x_y[1]
    for tmp_x, tmp_y in x_y_list_copy:
        diff_list.append((x - tmp_x, y - tmp_y))

counter = collections.Counter(diff_list)
print(cost - max(counter.values()))

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
from sys import stdin

N=int(input())
xlist=[]
ylist=[]
dict = {}
for i in range(N):
  x, y = map(int, stdin.readline().rstrip().split())
  xlist.append(x)
  ylist.append(y)

for i in range(N):
  for j in range(N):
    if i != j:
      tupleStr=str(xlist[i] - xlist[j])+","+str(ylist[i] - ylist[j])
      if tupleStr in dict:
        dict[tupleStr]+=1
      else:
        dict[tupleStr]=1

maxNum = max(dict.values())
maxNum=2
print(N-maxNum)

Submission status: Runtime Error

Solution code:
n = int(input())
list = []
submap = {}
scmap = {}
for i in range(n):
    a, b = map(int, input().split())
    list = list + [(a,b)]
    for (x, y) in list:
        if (a-x, b-y) != (0, 0):
            if (a-x, b-y) in submap.keys():
                submap[(a-x, b-y)] = submap[(a-x, b-y)] + 1
            else:
                submap[(a-x, b-y)] = 1
(k, l) = max(submap, key=submap.get)

c = 0
while len(list) > 0:
    (x, y) = list[0]
    c = c + 1
    list.remove((x, y))
    while (x + k, y + l) in list:
        list.remove((x + k, y + l))
        (x, y) = (x + k, y + l)
print(c)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
from operator import sub

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(map(sub, balls[i], balls[j]))] += 1
    try:
        mmax = max(d.values())
        mmax = int(N - mmax)
    except:
        print(100)
    print(N)
    print(mmax)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
n=int(input())
o=[]
for i in range(n):
    x,y=map(int,input().split())
    o.append([x,y])
p1=[]
q1=[]
for i in range(1,n):
    p1+=[o[i][0]-o[i-1][0]]
    q1+=[o[i][1]-o[i-1][1]]
p=abs(min(map(int,p1)))
q=abs(min(map(int,q1)))
ans=0
a=0
for i in range(n):
    for u in range(n):
        if i==u:
            break
        pd=o[i][0]-o[u][0]
        qd=o[i][1]-o[u][1]
        if pd==p and qd==q:
            a+=1
print(n-a)

Submission status: Runtime Error

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

def gcd(x,y):
	if x<y:
		x,y = y,x
	if y == 0:
		return x
	return gcd(y,x%y)

def main():
	n = int(input())
	xy = []
	for _ in range(n):
		xy +=[list(map(int,input().split()))]
	xy.sort(key=lambda x:(x[0],x[1]))
	dic = {}
	for i in range(n):
		for j in range(i+1,n):
			x,y = xy[i][0] - xy[j][0], xy[i][1] - xy[j][1]
			if x*y == 0:
				temp = f"{x}.{y}"
			else:
				g = gcd(abs(x),abs(y))
				k = "" if x*y > 0 else "-"
				x = abs(x)//g
				y = abs(y)//g
				temp = f"{x}.{k}{y}"
			if temp in dic:
				dic[temp] = dic[temp]+1
			else:
				dic[temp] = 1
	ans = 100
	# print(dic, xy)
	for d in dic:
		p,q = map(int,d.split("."))
		nlst = xy
		tans = 0
		lenn = n
		while lenn != 0:
			tans += 1
			f = nlst[0]
			nnlst = []
			# print("print f ", f)
			for i in range(1,lenn):
				if p == 0:
					if ((nlst[i][1] - f[1]) % q != 0)or (nlst[i][0] != f[0]):
						nnlst += [nlst[i]]
					else:
						lenn -= 1
				elif q == 0:
					if ((nlst[i][0] - f[0]) % p != 0) or (nlst[i][1] != f[1]):
						nnlst += [nlst[i]]
					else:
						lenn -= 1
				else:
					# print(f"{abs(nlst[i][1] - f[1]) % q} {abs(nlst[i][0] - f[0]) % p}")
					if (((nlst[i][1] - f[1]) % q) != 0) or (((nlst[i][0] - f[0]) % p) != 0):
						nnlst +=[nlst[i]]
					else:
						if (nlst[i][1]-f[1]) == 0 or ((nlst[i][0]-f[0])==0):
							nnlst += [nlst[i]]
						else:	lenn -= 1
			lenn -= 1
			# print(nnlst)
			nlst = nnlst
		# print(f"{d},{tans}")
		ans = min(tans,ans)
	print(ans)
	return

main()

Submission status: Runtime Error

Solution code:
import itertools

N = int(input())
balls = []

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

ans = 100
for pat in list(itertools.permutations(balls)):
    dic = {}
    l = list(pat)
    px = l[0][0]
    py = l[0][1]
    t_max = 0
    for i in range(1,len(l)):
        dx = l[i][0] - px
        dy = l[i][1] - py
        px = l[i][0]
        py = l[i][1]
        if (dx,dy) not in dic.keys():
            dic[(dx,dy)] = 1
        else:
            dic[(dx,dy)] += 1
            if (t_max < dic[(dx,dy)]):
                t_max = dic[(dx,dy)]
        kitai = + N - i
        if ans < (N - kitai):
            break
    d_max = max(dic.values())
    cost = N - d_max
    if (cost < ans):
        ans = cost

print(ans)

Submission status: Runtime Error

Solution code:
# 2
import sys
sys.setrecursionlimit(10000)
args = sys.stdin.readlines()
N = int(args[0])
xy_list = [[int(y) for y in x.split(' ')] for x in args[1:]]

from collections import Counter, defaultdict

delta_dict = defaultdict(int)

for i in range(N):
    for j in range(N):
        if i != j:
            delta_dict[(xy_list[i][0] - xy_list[j][0], xy_list[i][1] - xy_list[j][1])] += 1

print(N - Counter(delta_dict).most_common()[0][1])

Submission status: Runtime Error

Solution code:
from collections import Counter
n=int(input())
lst=[]
for i in range(n):
  X,Y=map(int,input().split())
  lst.append([X,Y])
lst_2=sorted(lst,key=lambda x: x[0])
lst_3=sorted(lst,key=lambda x: x[1])
z=[]
if n==1:
  print(1)
else:
  for j in range(n):
    for k in range(j+1,n):
      z.append((lst_2[j][0]-lst_2[k][0],lst_2[j][1]-lst_2[k][1]))
u=[]
if n==1:
  print(1)
else:
  for j in range(n):
    for k in range(j+1,n):
      u.append((lst_3[j][0]-lst_3[k][0],lst_3[j][1]-lst_3[k][1]))
Z=Counter(z)
U=Counter(u)
m=max(Z.most_common()[0][1],U.most_common()[0][1])
print(n-m)

Submission status: Runtime Error

Solution code:
import collections

import math

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


def katamuki(balla, ballb):
    xa, ya = balla
    xb, yb = ballb
    x, y = (xa - xb), (ya - yb)
    dir = math.sqrt(y ** 2 + x ** 2)
    if x == 0:
        return 1.0, dir
    if y == 0:
        return 0.0, dir
    if y / x == -1.0:
        return 1.0, dir
    return y / x, dir


a = []
for i in range(0, n - 1):
    for j in range(i + 1, n):
        a.append(katamuki(balls[i], balls[j]))

counts = collections.Counter(a)
print(n - max(counts.values()))

Submission status: Runtime Error

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

sys.setrecursionlimit(100000)

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のペアを計算
all_dists = defaultdict(list)
for each_pair in combinations(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
    each_pq = (each_p, each_q)
    all_dists[each_pq].append([each_pair[0][2], each_pair[1][2]])

# 適当にスタート，探索を行う
count_list = []
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_list.append(num_distinct_components)

print(max(min(count_list), 1))

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

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

xy.sort()
xy = xy[::-1]
aaa = []
for i in range(len(xy)-1):
    for j in range(i+1, len(xy)):
        a, b = xy[i]
        c, d = xy[j]
        aaa.append(str(a-c)+str(b-d))

# import itertools
#
# # itertools.permutations(xy, 2)
#
# aaa = []
# for i in list(itertools.combinations(xy, 2)):
#     a, b, c, d = sum(i, [])
#     aaa.append([str(a-c)+str(b-d)])
#     # print(a,b,c,d)
# # print(aaa)
# aaa = sum(aaa, [])
# print(aaa)
import collections
bbb = collections.Counter(aaa)
# print(bbb.most_common())
print(n-bbb.most_common()[0][1])

Submission status: Runtime Error

Solution code:
n = int(input())
if n = 1:
  print(1)
  exit()
xy = []
for _ in range(n):
  x, y = map(int, input().split())
  xy.append([x, y])

vecs = {}
for i in range(n):
  for j in range(i+1, n):
    if xy[i][0] < xy[j][0]:
      vec = (xy[j][0] - xy[i][0], xy[j][1] - xy[i][1])
    elif xy[i][0] > xy[j][0]:
      vec = (xy[i][0] - xy[j][0], xy[i][1] - xy[j][1])
    else:
      vec = (0, abs(xy[j][1] - xy[i][1]))
    
    if vec in vecs:
      vecs[vec] += 1
    else:
      vecs[vec] = 1

vec_max = max(list(vecs.values()))
print(n - vec_max)

Submission status: Runtime Error

Solution code:
from sys import stdin

N=int(input())
xlist=[]
ylist=[]
dict = {}
for i in range(N):
  x, y = map(int, stdin.readline().rstrip().split())
  xlist.append(x)
  ylist.append(y)

for i in range(N):
  for j in range(N):
    if i != j:
      tupleStr=str(xlist[i] - xlist[j])+","+str(ylist[i] - ylist[j])
      if tupleStr in dict:
        dict[tupleStr]+=1
      else:
        dict[tupleStr]=1

maxNum = max(dict.values())
print(N-maxNum)

Submission status: Runtime Error

Solution code:
import itertools

N = int(input())
balls = []

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

ans = 100
for pat in list(itertools.permutations(balls)):
    dic = {}
    l = list(pat)
    px = l[0][0]
    py = l[0][1]
    t_max = 0
    for i in range(1,len(l)):
        dx = l[i][0] - px
        dy = l[i][1] - py
        px = l[i][0]
        py = l[i][1]
        if (dx,dy) not in dic.keys():
            dic[(dx,dy)] = 1
        else:
            dic[(dx,dy)] += 1
            if (t_max < dic[(dx,dy)]):
                t_max = dic[(dx,dy)]
        kitai = + N - i
        if ans < (N - kitai):
            break
    d_max = max(dic.values())
    cost = N - d_max
    if (cost < ans):
        ans = cost

print(ans)

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)
            tmp = (dx // c, dy // c)
            acc.setdefault(tmp, set()).add(j)
    return N - max([len(s) for s in acc.values()])


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 = int(input())
xy = [[int(x) for x in input().split()] for i in range(N)]
xy = sorted(xy)
ans = 1
if N <= 2:
  print(ans)
else:
  list_xypq = [[xy[0][0],xy[0][1],xy[1][0]-xy[0][0],xy[1][1]-xy[0][1]]]
  for i in range(2,N):
    x = int(xy[i][0])
    y = int(xy[i][1])
    for j in range(len(list_xypq)):
      x_tmp = int(list_xypq[j][0])
      y_tmp = int(list_xypq[j][1])
      p_tmp = int(list_xypq[j][2])
      q_tmp = int(list_xypq[j][3])
      if p_tmp == 10e10 and q_tmp == 10e10:
        list_xypq[j][2] = x-x_tmp
        list_xypq[j][3] = y-y_tmp
        break
      if p_tmp == 0 and q_tmp != 0:
        if x-x_tmp == 0 and (y-y_tmp)%q_tmp == 0:
          break
      elif p_tmp != 0 and q_tmp != 0:
        if (x-x_tmp)%p_tmp == 0 and y-y_tmp == 0:
          break
      elif  p_tmp == 0 and q_tmp == 0:
        if x-x_tmp == 0 and y-y_tmp == 0:
          break
      elif (x-x_tmp)%p_tmp == 0 and (y-y_tmp)%q_tmp == 0:
        break
    else:
      list_xypq.append([x,y,10e10,10e10])
      ans += 1
  print(ans)

Submission status: Runtime Error

Solution code:
from sys import stdin
from math import atan2, degrees
n = int(stdin.readline())
o = list(map(int, stdin.readline().split()))

ang = set()
add = ang.add
cnt = [0] * 100000000

for i in range(n-1):
    tmp = list(map(int, stdin.readline().split()))
    if tmp[0]-o[0]: r = degrees(atan2(tmp[1]-o[1],  tmp[0]-o[0]))
    else: r = (tmp[1]-o[1]) ** 0.5

    cnt[int(r * 1000000)] += 1
    o = tmp

print(1+sum(cnt)-max(cnt))

Submission status: Runtime Error

Solution code:
n = int(input())
xy = []
renso = {}

for i in range(n):
    xin,yin = map(int,input().split())
    xy.append((xin,yin))

xy.sort()

for i in range(n):
    for j in range(i,n):
        if( i==j ):
            continue
        dx = xy[i][0]-xy[j][0]
        dy = xy[i][1]-xy[j][1]
        if renso.get((dx,dy))==None:
            renso[(dx,dy)]=1
        else:
            renso[(dx,dy)]=renso[(dx,dy)]+1

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