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 sys
from itertools import combinations
from collections import defaultdict


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


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 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
    gcd = gcd_func(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(max(min(count_list), 1))

Submission status: Runtime Error

Solution code:
import math
N = int(input())
sheet = []
for i in range(N):
  line = input().split()
  sheet += [(int(line[0]), int(line[1]))]
 
dic = {}
for i in range(N):
  start = sheet[i]
  for j in range(i+1, N):
    vec = [(sheet[j][0]-start[0]), (sheet[j][1]-start[1])]
    size = math.gcd(vec[0],vec[1])
    vec[0] = vec[0]//size
    vec[1] = vec[1]//size
    vec = tuple(vec)
    if vec not in dic.keys():
      dic[vec] = set([j])
    else:
      dic[vec].add(j)
m = 0
for s in dic.values():
  if len(s)>m:
    m = len(s)
print(N-m)

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
    diff = (data[j][0] - data[i][0], data[j][1] - data[i][1])
    if diff in d:
      d[diff] += 1
    else:
      d[diff] = 1

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

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())
    except:
        print(100)
    print(int(N)-int(mmax))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

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

ans = 10**9
for i in check:
    b = []
    for j in range(n):
        b.append([xy[j][0]-i[0],xy[j][1]-i[1]])
    c = n
    for j in range(n):
        if b[j] in xy:
            c -= 1
    if c < ans:
        ans = c
print(c)

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]
    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
    d_max = max(dic.values())
    cost = N - d_max
    if (cost < ans):
        ans = cost

print(ans)

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)
ans = len(sxy2)+1-max(c.values())
print(ans) if ans != 0 else print(1)

Submission status: Runtime Error

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

vector = []

for i in range(N):
    first_point = ball_location[i]
    
    for next_point in ball_location[0:i] + ball_location[i+1:]:
        p = next_point[0] - first_point[0]
        q = next_point[1] - first_point[1]
        vector.append(str(p) + "," + str(q))
        
print(N - collections.Counter(vector).most_common()[0][1])

Submission status: Runtime Error

Solution code:
# B - Picking Up

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

dis  = []
for i in range(n):
    for j in range(n):
        if i != j:
            dis.append([ball[i][0] - ball[j][0], ball[i][1] - ball[j][1]])
cnt = []
print(dis)
for i in range(n):
    cnt.append(dis.count(dis[i]))
print(n - max(cnt))

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 == 0 and q_tmp == 0:
        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,0,0])
      ans += 1
      continue
    break
  print(ans)

Submission status: Runtime Error

Solution code:
import statistics
import copy
import collections
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=collections.Counter(xx).most_common()[0][0]
    Y=collections.Counter(xx).most_common()[0][0]
    if X==0 and Y==0:
        XX=copy.copy(xx)
        XX.remove(0)
        X=collections.Counter(xx).most_common()[0][0]
        YY=copy.copy(yy)
        YY.remove(0)
        Y=collections.Counter(xx).most_common()[0][0]
        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=collections.Counter(xx).most_common()[0][0]
    Y=collections.Counter(yy).most_common()[0][0]
    if X==0 and Y==0:
        XX=copy.copy(xx)
        XX.remove(0)
        X=collections.Counter(xx).most_common()[0][0]
        YY=copy.copy(yy)
        YY.remove(0)
        Y=collections.Counter(xx).most_common()[0][0]
        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 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())
    except:
        print(100)
    print(N-mmax)


if __name__ == '__main__':
    main()

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)
if max(ans) == 1:
    print(n)
else:
    print(n - max(ans))

Submission status: Runtime Error

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

L_sort = sorted(L)
L_dict = {}
for i in range(n-1):
    tmp0 = L_sort[i+1][0] - L_sort[i][0]
    tmp1 = L_sort[i+1][1] - L_sort[i][1]
    if (tmp0, tmp1) in L_dict:
        L_dict[(tmp0, tmp1)] += 1
    else:
        L_dict[(tmp0, tmp1)] = 1
ans = n - max(L_dict.values())
print(ans)

Submission status: Runtime Error

Solution code:
from sys import stdin

def solve(N, xys):
    diff = []
    diff_count = [0]*50
    idx = 0
    for i in range(N-1):
        for j in range(i+1,N):
            tmp_a = [xys[i][0] - xys[j][0], xys[i][1] - xys[j][1]]
            tmp_b = [xys[j][0] - xys[i][0], xys[j][1] - xys[i][1]]
            if tmp_a in diff or tmp_b in diff:
                diff_count[diff.index(tmp_a)] += 1
            else:
                diff.append(tmp_a)
                diff_count[idx] += 1
                idx += 1
    return N - max(diff_count)

if __name__ == '__main__':
    N = int(stdin.readline().rstrip())
    xys = []
    for i in range(N):
        xys.append([int(x) for x in stdin.readline().rstrip().split()])
    print(solve(N, xys))

Submission status: Runtime Error

Solution code:
N = int(input())
XY = []
for n in range(N):
    XY.append([int(i) for i in input().split()])
cnt = {}
for n in range(N):
    for nn in range(n+1,N): 
        dist = [XY[n][0]-XY[nn][0],XY[n][1]-XY[nn][1]]
        if str(dist) in cnt:
            cnt[str(dist)] += 1
        else:
            cnt[str(dist)] = 1
print(N - max(cnt.values()))

Submission status: Runtime Error

Solution code:
from itertools import combinations
import sys

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

X_Y = [0] * N

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

N = int(input())    

combo = list(combinations(X_Y, 2))
diff = [0] * (len(combo))

for i, item in enumerate(combo):
    x_dif = item[0][0] - item[1][0]
    y_dif = item[0][1] - item[1][1]
    diff[i] = [x_dif, y_dif]

count_list = [0] * len(diff)
for k, d in enumerate(diff):
    p = d[0]
    q = d[1]
    count = 0
    for i in range(0, len(X_Y) - 1):
        if (X_Y[i][0] == X_Y[i + 1][0] + p) and X_Y[i][1] == X_Y[i + 1][1] + q:
            count += 0
        else:
            count += 1
    count_list[k] = count
print(min(count_list) + 1)

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:
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-i):
        if i == j+i:
            continue
        else:
            p = xy[i][0] - xy[j+i][0]
            q = xy[i][1] - xy[j+i][1]
            # print(p,q)
            sabun.append([p,q])
count = [sabun.count(i) for i in sabun]
print(N-max(count))

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
    if xl[i][1]-xl[0][1] != 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+1):
    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:
N = int(input())
xylist = [[0, 0]]*N
for i in range(N):
  xy = list(map(int, input().split()))
  xylist[i] = xy

dl = {}
for i in range(N):
  for j in range(i+1, N):
    dx = str(xylist[j][0] - xylist[i][0])
    dy = str(xylist[j][1] - xylist[i][1])
    l = dx + "|" + dy
    if dx == "0" and dy == "0":
      continue
    if l in dl:
      dl[l] = dl[l] + 1
    else:
      dl[l] = 1

print(N - max(dl.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

if N==1:
  print(1)
else:
  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:
from statistics import mode

N=int(input())
x=[0]*N
y=[0]*N
a=[]
b=[]
c=1
for i in range(N):
  x[i], y[i]=map(int, input().split())
  
for n in range(1,N):
  a.append(x[n]-x[n-1])
  b.append(y[n]-y[n-1])

for n2 in range(N-1):
  if a[n2]!=mode(a) or b[n2]!=mode(b):
    c=c+1
print(c)

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))
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 and i[1] != 0:
    num = n-j
    break
  else:
    num = n
print(num)

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

    max_num = max(num)
    if max_num == 1:
        return 0
    else:
        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:
n = int(input())
li,diff= [],[]
for i in range(n):
    a=(input().split())
    a=[int(x) for x in a]
    li.append(a)

for i in range(len(li)-1):
    diff.append([])
    diff[i].append(li[i+1][0]-li[i][0])
    diff[i].append(li[i+1][1]-li[i][1])


b = []
for i in range(len(diff)):
    b.append(diff.count(diff[i]))

for i in range(b.count(max(b))):
    b.remove(max(b))
print(len(b)+1)

Submission status: Runtime Error

Solution code:
import numpy as np
from operator import itemgetter

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

st_xy1 = sorted(xy, key=itemgetter(0))
st_xy = sorted(st_xy1, key=itemgetter(1))

s = np.array(st_xy)

L = list(map(list,np.diff(s.transpose()).transpose()))

ans = []
for LL in list(map(list, set(map(tuple, L)))):
    ans.append(L.count(LL))
print(n - max(ans))

Submission status: Runtime Error

Solution code:
N = int(input())
xy = []
for i in range(N):
    xy.append(list(map(int,input().split())))
    
count = {}
for i in range(N-1):
    for j in range(i + 1, N):
        diff = [xy[j][0] - xy[i][0], xy[j][1] - xy[i][1]]
        if str(diff) in count:
            count[str(diff)] += 1
        else:
            count[str(diff)] = 1
            
print(str(N - max(count.values())))

Submission status: Runtime Error

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

distlist=[]
distnum=[]

for i in range(n):
    for j in range(n):
        vec=[xy[i][0]-xy[j][0], xy[i][1]-xy[j][1]]
        if(i==j):
             continue
        flag=0
        for k in range(len(distlist)):
            if(distlist[k][0]==vec[0] and distlist[k][1]==vec[1]):
                distnum[k] += 1
                flag=1
                break
        if(flag==0):
            distlist.append(vec)
            distnum.append(1)

print(n-max(distnum))

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_list = []
for pat in list(itertools.permutations(balls)):
    dic = {}
    l = list(pat)
    px = l[0][0]
    py = l[0][1]
    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
    d_max = max(dic.values())
    ans_list.append(N - d_max)

print(min(ans_list))

Submission status: Runtime Error

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

dl = {}
for i in range(N):
  for j in range(i+1, N):
    dx = str(xylist[j][0] - xylist[i][0])
    dy = str(xylist[j][1] - xylist[i][1])
    l = dx + "|" + dy
    if l in dl:
      dl[l] = dl[l] + 1
    else:
      dl[l] = 1

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

Submission status: Runtime Error

Solution code:

import collections
N=int(input())

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

x=[]
y=[]

for X,Y in XY:
    x.append(X)
    y.append(Y)
    
l1=[]
c=0
for i in range(N):
    for j in range(i+1,N):
        a=x[i]-x[j]
        b=y[i]-y[j]
        if a<=0 and b>=0:
            a=-a
            b=-b
        elif a<=0 and b<=0:
            a=-a
            b=-b
        l1.append(str(a)+str(b))
c = collections.Counter(l1)      
values, counts = zip(*c.most_common())    
print(N-max(counts))

Submission status: Runtime Error

Solution code:
n = int(input())

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

balls.sort()  
sorted(balls, key=lambda x: x[1])

hyo={}

for i in range(n):
  for j in range(i+1,n):
    difx=balls[j][0]-balls[i][0]
    dify=balls[j][1]-balls[i][1]
    if (difx,dify) in hyo.keys():
      hyo[(difx,dify)] +=1
    else:
      hyo[(difx,dify)] =1

#print(hyo)
p,q=max(hyo,key=hyo.get)

chk=[1]*n

for i in range(n-1,-1,-1):
  x=balls[i][0]-p
  y=balls[i][1]-q
  if [x,y] in balls:
    chk[i]=0
#print(balls)
#print(chk)
print(sum(chk))

Submission status: Runtime Error

Solution code:
n = int(input())
#print("n=",n)
xy_s = [[int(v) for v in input().split()] for _ in range(n)]
v = {}
for i in range(n):
  for j in range(n):
    if i == j:
      continue
    dx = xy_s[i][0] - xy_s[j][0]
    dy = xy_s[i][1] - xy_s[j][1]
    pq = (dx, dy)
    if pq in v:
      v[pq] += 1
    else:
      v[pq] = 1
    
    #v.append([xy_s[i][0] - xy_s[j][0] , xy_s[i][1] - xy_s[j][1]])
#print(v)
counts = v.values()
m = max(counts)
ans = n - m
#print("n={}, m={}, ans={}".format(n, m, ans))
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
            try:
                d[tuple(map(sub, balls[i], balls[j]))] += 1
            except:
                print(100)
    print(N-max(d.values()))


if __name__ == '__main__':
    main()

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+1):
    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 itertools

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

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

ans_list = []
for pat in list(itertools.permutations(balls)):
    dic = {}
    l = list(pat)
    px = l[0][0]
    py = l[0][1]
    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 (0>dx):
            dx *= -1
            dy *= -1
        if (dx,dy) not in dic.keys():
            dic[(dx,dy)] = 1
        else:
            dic[(dx,dy)] += 1
    d_max = max(dic.values())
    ans_list.append(N - d_max)

print(min(ans_list))

Submission status: Runtime Error

Solution code:
n = int(input())
cnt = dict()
xy = [tuple(map(int, input().split())) for _ in range(n)]
if n == 1:
    print(1)
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:
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

if N==1:
  return 1

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:
import collections
N = int(input())
e = [[int(i) for i in input().split()] for i in range(N)]
x = 0
y = 0
tupleArray = []
for i in range(N-1):
    for j in range(i+1, N):
        x = e[i][0] - e[j][0]
        y = e[i][1] - e[j][1]
        t1 = (x, y)
        tupleArray.append(t1)
c = collections.Counter(tupleArray)
print(N - c.most_common()[0][1])

Submission status: Runtime Error

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


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


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 = gcd_func(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:
import copy
n=int(input())
l=[list(map(int,input().split())) for i in range(n)]
ans=[]
for i in range(n):
  x1=l[i][0]
  y1=l[i][1]
  for j in range(n):
    if i!=j:
      x2=l[j][0]
      y2=l[j][1]
      if (x1-x2)!=0:
        p=(y1-y2)/(x1-x2)
        L=[]
        for k in range(n):
          L.append(round(l[k][1]-l[k][0]*p,9))
        ans.append(len(set(L)))
      else:
        L=[]
        for k in range(n):
          L.append(l[k][0])
        ans.append(len(set(L)))
print(min(ans))

Submission status: Runtime Error

Solution code:
# 何本の数直線上にあるかを求める　1<=ans<=n-1
n=int(input())
xy=[list(map(int,input().split())) for _ in range(n)]
# xy.sort(key=lambda x:x[0])
# print(xy)
diff=[]
for i in range(n):
    for j in range(i):
        diff.append((xy[i][0]-xy[j][0],xy[i][1]-xy[j][1]))

ans=[]
# print(set(diff))
for p,q in set(diff):
    qxHIKUpy=[]
    for i in range(n):
        qxHIKUpy.append(q*xy[i][0]-p*xy[i][1])
    ans.append(len(set(qxHIKUpy)))
# print(ans)
print(min(ans))

Submission status: Runtime Error

Solution code:
from itertools import combinations
n=int(input())
xs = []
for _ in range(n):
    x,y=map(int,input().split())
    xs.append((x,y))

def func(c):
    p,q=(xs[c[0]][0]-xs[c[1]][0],xs[c[0]][1]-xs[c[1]][1])
    ys=[(x,y) for x,y in xs if (x-p,y-q) not in xs]
    return len(ys)

c = combinations(range(n),2)
print(min(map(func, c)))

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)

for i in range(1,N):
        pqans=cpq.most_common(i)[0][0]
        if pqans != '0x0':
                redsc=cpq.most_common(i)[0][1]
                break


print(N-redsc)

Submission status: Runtime Error

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

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

x=[]
y=[]

for X,Y in XY:
    x.append(X)
    y.append(Y)
    
l1=[]
c=0
for i in range(N):
    for j in range(i+1,N):
        a=x[i]-x[j]
        b=y[i]-y[j]
        if a<0 and b>0:
            a=-a
            b=-b
        elif a<0 and b<0:
            a=-a
            b=-b
        l1.append(str(a)+str(b))
c = collections.Counter(l1)      
values, counts = zip(*c.most_common())    
print(N-max(counts))

Submission status: Runtime Error

Solution code:

N = int(input())
xy = []
for i in range(N):
    xy.append(list(map(int,input().split())))
    
count = {}
for i in range(N-1):
    for j in range(1, N):
        diff = [xy[j][0] - xy[i][0], xy[j][1] - xy[i][1]]
        if str(diff) in count:
            count[str(diff)] += 1
        else:
            count[str(diff)] = 1
            
print(str(N - max(count.values())))