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:
#!/usr/bin/env python3
import sys
import itertools

def solve(N: int, x: "List[int]", y: "List[int]"):
    PL = list(zip(x,y))

    mincost = float('inf')
    for seq in itertools.permutations(PL):
        cost = 1
        p = seq[1][0] - seq[0][0]
        q = seq[1][1] - seq[0][1]
        #print(seq)
        for i in range(1,len(seq)):
            p2 = seq[i][0] - seq[i-1][0] 
            q2 = seq[i][1] - seq[i-1][1] 
            #print(p,p2,q,q2)
            if p != p2 or  q != q2:
                cost += 1
        mincost = min(mincost,cost)

    print(mincost)
            


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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))
    solve(N, x, y)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:

N = int(input())

xy = []
for i in range(N):
    xi, yi = map(int, input().split())
    xy.append((xi, yi))

t = 10**9
vectors = []

x1, x2, y1, y2, xd, yd = 0, 0, 0, 0, 0, 0
for i in range(N):
    for j in range(i+1, N):
        x1, y1 = xy[i]
        x2, y2 = xy[j]
        if x1 > x2:
            xd = x1 - x2
        elif x2 > x1:
            xd = x2 - x1
        else:
            continue
        if y1 > y2:
            yd = y1 - y2
        elif y2 > y1:
            yd = y2 - y1
        else:
            continue

        vectors.append((xd, yd))

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

frequencies_dic = {}
M = len(vectors)
for i in range(M):
    x, y = vectors[i]
    if (x, y) not in frequencies_dic:
        frequencies_dic[(x,y)] = 1
    else:
        frequencies_dic[(x,y)] += 1

zeros = max(list(frequencies_dic.values()))
ans = N - zeros
print(ans)

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 = []
    for i in range(N):
        if C[c][0] != 0:
            tmp.append(round(arr[i][1] - arr[i][0]/C[c][0]*C[c][1],15))
        else:
            tmp.append(round(arr[i][0] - arr[i][1]/C[c][1]*C[c][0],15))
    tmp = list(set(tmp))
    S[c] = len(tmp)

print(min(S))

Submission status: Runtime Error

Solution code:
N = int(input())

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

z = []
for i,j in zip(x,x[1:]):
  y.append((j[0]-i[0],j[1]-i[1]))

print(len(set(y)))

Submission status: Runtime Error

Solution code:
N = int(input())
hoge = []
s = []
for _ in range(N):
	a, b = map(int, input().split())
	hoge.append([a,b])

import itertools
#print(list(itertools.combinations(hoge,2)))
#print(list(itertools.combinations(hoge,2))[0])
for i in range(len(list(itertools.combinations(hoge,2)))):
	s.append(str([list(itertools.combinations(hoge,2))[i][1][0] - list(itertools.combinations(hoge,2))[i][0][0],\
       list(itertools.combinations(hoge,2))[i][1][1] - list(itertools.combinations(hoge,2))[i][0][1]]))
#print(s)
import collections
c = collections.Counter(s)
print(N - c.most_common()[0][1])

Submission status: Runtime Error

Solution code:
from sys import stdin
from collections import Counter

input = stdin.readline

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

l = []
append = l.append
for i in range(n):
  for j in range(n):
    if not i == j:
      append((xy[j][0]-xy[i][0], xy[j][1]-xy[i][1]))
c = Counter(l)
print(n-c.most_common()[0][1])

Submission status: Runtime Error

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

kouho_list = []

for i, AB in enumerate(AB_list):
    for j,ab in enumerate(AB_list[i+1:]):
        kouho_list.append((AB[0]-ab[0] ,AB[1]-ab[1]))

from collections import Counter
kouho_counter = Counter(kouho_list).most_common()
#print(kouho_counter)
result = len(AB_list) - kouho_counter[0][1]

'''
候補は49 + 48 + 47 + ...
この候補の中で、一番えらばれているものをp,qとして設定する
その後、ループを回して、実際にコストを計算する

'''



#print(AB_list)
print(result)

Submission status: Runtime Error

Solution code:
from collections import Counter

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

for i, a in enumerate(points):
    for j in range(N):
        if j == i:
            continue
        b = points[j]
        dx = b[0] - a[0]
        dy = b[1] - a[1]
        counter[(dx, dy)] += 1

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

for p in points:
    if p in visited:
        continue
    x, y = p
    visited.add(p)
    if (x + dx, y + dy) in visited or (x - dx, y - dy) in visited:
        continue
    cost += 1

print(cost)

Submission status: Runtime Error

Solution code:
import functools as ft
import logging
import unittest
from collections import (
    namedtuple,
    Counter,
)
from heapq import (
    heappush,
    heappop,
)

debug = logging.getLogger(__name__).debug


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


@ft.total_ordering
class PrioritizedItem(namedtuple('PrioritizedItem', 'priority, value')):
    def __lt__(self, other):
        return self.priority < other.priority


def a_star(succ, cost, heuristic, start):
    cost_dict = {start: (heuristic(start), 0)}
    prev_dict = {}
    close = set()
    q = [PrioritizedItem(cost_dict[start], start)]

    while q:
        cost_u, u = heappop(q)
        if u not in close and cost_u <= cost_dict[u]:
            close.add(u)

            yield u, prev_dict, cost_dict

            for v in succ(u):
                cost_uv = cost(u, v)
                heuristic_v = heuristic(v)

                cost_v_old = cost_dict.get(v)
                cost_v_new = (
                    cost_u[1] + cost_uv + heuristic_v,
                    cost_u[1] + cost_uv,
                )
                if cost_v_old is None or cost_v_new < cost_v_old:
                    cost_dict[v] = cost_v_new
                    prev_dict[v] = u
                    heappush(q, PrioritizedItem(cost_v_new, v))
                    try:
                        close.remove(v)
                    except KeyError:
                        pass


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

    pq = [
        (x1 - x2, y1 - y2)
        for (x1, y1) in xy
        for (x2, y2) in xy
        if not (x1 == x2 and y1 == y2)
    ]
    pq_counter = Counter(pq)

    ans = []
    for p, q in sorted(pq_counter, key=pq_counter.get)[::-1]:
        ans.append(len(xy) - pq_counter[p, q])

    print(min(ans))


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:
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 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:
from collections import Counter





if __name__ == "__main__":
    #入力取得
    N = int(input())

    p = []


    results = [[] for i in range(N)]

    for row in results:
        for i in range(N):
            row.append('')

    tmp = []



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


    for i in range(len(p)):
        for j in range(i+1, len(p)):

            if p[i][0] == p[j][0]:
                r = N*N
            else:
                r = (p[i][1]-p[j][1])/(p[i][0]-p[j][0])

            results[i][j] = r

            tmp.append(r)



    counter = Counter(tmp)
    max_r = counter.most_common()[0][0]
    # print(max_r)

    results2 = [0]*N


    for i in range(len(results)):
        for j in range(i+1,len(results)):
            if results[i][j] == max_r:
                results2[i] += 1




    tmp_ans = N - (max(results2) + 1)
    if tmp_ans == 0:
        print(1)
    else:
        print(tmp_ans)

Submission status: Runtime Error

Solution code:
import collections
N = int(input())
ball = [tuple(map(int, input().split())) for _ in range(N)]
ball.sort(key=lambda x:(x[0], x[1]))
diff = [tuple((ball[i][0] - ball[i-1][0], ball[i][1] - ball[i-1][1])) for i in range(1,N)]
c = collections.Counter(diff)
ans = c.most_common()[0][1]
print(N - ans)

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 = []
    for i in range(N):
        if C[c][0] != 0:
            tmp.append(round(arr[i][1] - arr[i][0]/C[c][0]*C[c][1],10))
        else:
            tmp.append(round(arr[i][0] - arr[i][1]/C[c][1]*C[c][0],10))
    tmp = list(set(tmp))
    S[c] = len(tmp)

print(min(S))

Submission status: Runtime Error

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

B = sorted(L, key=lambda x: x[1], reverse=True)  
B = sorted(B, key=lambda x: x[0])

dic_x = {}
dic_y = {}
for i in range(N-1):
    if B[i+1][0] - B[i][0] in dic_x:
        dic_x[B[i+1][0] - B[i][0]] += 1
        
    else:
        dic_x[B[i+1][0] - B[i][0]] = 1
        
        
    if B[i+1][1] - B[i][1] in dic_y:
        dic_y[B[i+1][1] - B[i][1]] += 1
        
    else:
        dic_y[B[i+1][1] - B[i][1]] = 1
        
        
tmp_x = max(dic_x.items(), key=lambda x:x[1])[0]
tmp_y = max(dic_y.items(), key=lambda x:x[1])[0]
ans_1 = 0
for i in range(N-1):
    if B[i][0] + tmp_x == B[i+1][0] and B[i][1] + tmp_y == B[i+1][1]:
        pass
    else:
        ans_1 += 1

B = sorted(L, key=lambda x: x[0], reverse=True)      
B = sorted(B, key=lambda x: x[1])

dic_x = {}
dic_y = {}
for i in range(N-1):
    if B[i+1][0] - B[i][0] in dic_x:
        dic_x[B[i+1][0] - B[i][0]] += 1
        
    else:
        dic_x[B[i+1][0] - B[i][0]] = 1
        
        
    if B[i+1][1] - B[i][1] in dic_y:
        dic_y[B[i+1][1] - B[i][1]] += 1
        
    else:
        dic_y[B[i+1][1] - B[i][1]] = 1
        
        
tmp_x = max(dic_x.items(), key=lambda x:x[1])[0]
tmp_y = max(dic_y.items(), key=lambda x:x[1])[0]
ans_2 = 0
for i in range(N-1):
    if B[i][0] + tmp_x == B[i+1][0] and B[i][1] + tmp_y == B[i+1][1]:
        pass
    else:
        ans_2 += 1
        
print(min(ans_1, ans_2)+1)

Submission status: Runtime Error

Solution code:
import itertools
import collections

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

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

relative_coord_list = []
for coord_comb in list(itertools.combinations(coord_list,2)):
    relative_coord = [abs(coord_comb[0][0] - coord_comb[1][0]), abs(coord_comb[1][0] - coord_comb[1][1])]
    relative_coord_list.append(relative_coord)

#print(str(relative_coord_list))

coord_collections = collections.Counter(tuple(x) for x in relative_coord_list)

target_tupple = coord_collections.most_common()[0]
result = N - target_tupple[1]

print(str(result))

Submission status: Runtime Error

Solution code:
from collections import defaultdict
from itertools import combinations
def solve():
    n = int(input())
    XY = [list(map(int, input().split())) for _ in range(n)]
    m = defaultdict(int)
    for i, j in combinations(range(n), 2):
        m[(XY[i][0] - XY[j][0], XY[i][1] - XY[j][1])] += 1
        m[(XY[j][0] - XY[i][0], XY[j][1] - XY[i][1])] += 1
    print(n - max(m.items(), key=lambda x: x[1])[1])
solve()

Submission status: Runtime Error

Solution code:
N=int(input())
x=['']*N
y=['']*N
dic={}
for i in range(N):
    x[i],y[i]=map(int,input().split())

for i in range(N):
    for j in range(N):
        if i==j:
            pass
        else:
            p=y[j]-y[i]
            q=x[j]-x[i]
            if (p,q) in dic.keys():
                dic[(p,q)] += 1
            else:
                dic[(p,q)] = 1

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

Submission status: Runtime Error

Solution code:
from collections import Counter
n=int(input())
balls=[]
distance=[]
for i in range(n):
  balls.append(list(map(int,input().split())))
for i in range(n-1):
  for j in range(i+1,n):
    distance.append(str(balls[i][0]-balls[j][0])+" "+str(balls[i][1]-balls[j][1]))
d=Counter(distance)
print(n-d.most_common()[0][1])

Submission status: Runtime Error

Solution code:
from collections import defaultdict
N = int(input())
Xs = []
Ys = []
za = []

for i in range(N):
    x,y = list(map(int, input().split(" ")))
    Xs.append(x)
    Ys.append(y)
    za.append((x,y))

za.sort(key=lambda x:x[0])
dix = defaultdict(lambda :0)
diy = defaultdict(lambda :0)
for i,z in enumerate(za[1:]):
    x = z[0]
    before = za[i][0]
    tempx = x -before
    y = z[1]
    before = za[i][1]
    tempy =  y -before
    diy[(tempx,tempy)] += 1

ymax = max(diy.values())
cand = [N - ymax]


za.sort(key=lambda x:x[1])
dix = defaultdict(lambda :0)
diy = defaultdict(lambda :0)
for i,z in enumerate(za[1:]):
    x = z[0]
    before = za[i][0]
    tempx = x -before
    y = z[1]
    before = za[i][1]
    tempy =  y -before
    diy[(tempx,tempy)] += 1

ymax = max(diy.values())
cand.append(N - ymax)


print(min(cand))

Submission status: Runtime Error

Solution code:
N = int(input())
xy = []
for i in range(N):
    x,y = map(int,input().split())
    xy.append([x,y])
dists = set()
for i in range(N):
    for j in range(i+1,N):
        dists.add( (abs(xy[i][0]-xy[j][0]),abs(xy[i][1]-xy[j][1])) )
ans = []
for pq in dists:
    tmp = 1
    i = 0
    while i < N-1:
        if [xy[i][0]+pq[0],xy[i][1]+pq[1]] != xy[i+1]: tmp += 1
        i += 1

    ans.append(tmp)

print(min(ans))

Submission status: Runtime Error

Solution code:
import numpy as np
n = int(input())
if n == 1:
    print(1)

points = np.zeros((n, 2), dtype=np.int)
for i in range(n):
    x, y = [int(x) for x in input().split()]
    points[i, 0] = x
    points[i, 1] = y

diffs = {}
for i in range(n):
    for j in range(n):
        if i != j:
            diff = (points[i, 0] - points[j, 0], points[i, 1] - points[j, 1])
            if diff in diffs:
                diffs[diff] += 1
            else:
                diffs[diff] = 1

count = sorted(diffs.items(), key=lambda kv: kv[1])[-1][1]
print(n-count)

Submission status: Runtime Error

Solution code:
N = int(input())
ary = []
# d = []
d2 = []
for _ in range(N):
  ball = list(map(int, input().split()))
  ary.append(ball)

for i in range(N-1):
    x = ary[i][0] - ary[i+1][0]
    y = ary[i][1] - ary[i+1][1]
    # d.append(x)
    # d.append(y)
    tmp = str(x) + str(y)
    d2.append(tmp)
    # d = []
# print(ary)
# print(d2)

max = d2.count(d2[0])
for i in range(1,N-1):
    if max < d2.count(d2[i]):
        max = d2.count(d2[i])

print(len(d2) - max + 1)

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)

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)):
    Duplicate.append(Data.count(Data[k]))
    # print(Data[k])

# print(Duplicate)

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

Submission status: Runtime Error

Solution code:

N = int(input())

#x_max, y_max = 0, 0

xy = []
for i in range(N):
    xi, yi = map(int, input().split())
    xy.append((xi, yi))

t = 10**9
vectors = []

x1, x2, y1, y2, xd, yd = 0, 0, 0, 0, 0, 0
for i in range(N):
    for j in range(i+1, N):
        x1, y1 = xy[i]
        x2, y2 = xy[j]
        if x1 > x2:
            xd = x1 - x2
        elif x2 > x1:
            xd = x2 - x1
        else:
            continue
        if y1 > y2:
            yd = y1 - y2
        elif y2 > y1:
            yd = y2 - y1
        else:
            continue

        vectors.append((xd, yd))

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

frequencies_dic = {}
M = len(vectors)
for i in range(M):
    x, y = vectors[i]
    if (x, y) not in frequencies_dic:
        frequencies_dic[(x,y)] = 1
    else:
        frequencies_dic[(x,y)] += 1

ans = max(list(frequencies_dic.values()))
print(ans)

Submission status: Runtime Error

Solution code:
import functools as ft
import logging
import unittest
from collections import (
    namedtuple,
    Counter,
)
from heapq import (
    heappush,
    heappop,
)

debug = logging.getLogger(__name__).debug


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


@ft.total_ordering
class PrioritizedItem(namedtuple('PrioritizedItem', 'priority, value')):
    def __lt__(self, other):
        return self.priority < other.priority


def a_star(succ, cost, heuristic, start):
    cost_dict = {start: (heuristic(start), 0)}
    prev_dict = {}
    close = set()
    q = [PrioritizedItem(cost_dict[start], start)]

    while q:
        cost_u, u = heappop(q)
        if u not in close and cost_u <= cost_dict[u]:
            close.add(u)

            yield u, prev_dict, cost_dict

            for v in succ(u):
                cost_uv = cost(u, v)
                heuristic_v = heuristic(v)

                cost_v_old = cost_dict.get(v)
                cost_v_new = (
                    cost_u[1] + cost_uv + heuristic_v,
                    cost_u[1] + cost_uv,
                )
                if cost_v_old is None or cost_v_new < cost_v_old:
                    cost_dict[v] = cost_v_new
                    prev_dict[v] = u
                    heappush(q, PrioritizedItem(cost_v_new, v))
                    try:
                        close.remove(v)
                    except KeyError:
                        pass


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

    pq = [
        (x1 - x2, y1 - y2)
        for (x1, y1) in xy
        for (x2, y2) in xy
        if not (x1 == x2 and y1 == y2)
    ]
    pq_counter = Counter(pq)

    ans = []
    for p, q in sorted(pq_counter, key=pq_counter.get)[::-1]:
        result = a_star(
            succ=lambda u: [u + (xy_,) for xy_ in xy],
            cost=lambda u, v: int(
                v[-1][0] - u[-1][0] != p
                or v[-1][1] - u[-1][1] != q
            ),
            heuristic=lambda u: 0,
            start=((float('inf'),) * 2,),
        )
        tail, prev_dict, cost_dict = (None,) * 3
        for tail, prev_dict, cost_dict in result:
            if len(tail) > len(xy):
                break
        ans.append(cost_dict[tail][0])
        debug([len(xy), pq_counter[p, q], ans[-1]])
        if len(xy) - pq_counter[p, q] == ans[-1]:
            break

    print(min(ans))


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:
n = int(input())
a = sorted([list(map(int, input().split())) for _ in range(n)])
d = {}
ret = float('inf')
for i in range(n - 1):
    for j in range(i + 1, n):
        p, q = a[j][0] - a[i][0], a[j][1] - a[i][1]
        if p == 0 and q == 0:
            continue
        key = (p, q)
        d.setdefault(key, 0)
        d[key] += 1
print(n - max(d.values()))

Submission status: Runtime Error

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

L_sort = sorted(L, key=lambda x:(x[0]+x[1]))
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
if max(L_dict.values()) == 1:
    print(n)
else:
    ans = n - max(L_dict.values())
    print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
pos = [list(map(int, input().split())) for _ in range(n)]
d = {}
for x, y in pos:
  for nx, ny in pos:
    dx = nx - x
    dy = ny - y
    key = (dx, dy)
    if key == (0, 0):
      continue
    if key in d:
      d[key] += 1
    else:
      d[key] = 1
print(n - max([d[key] for key in d]))

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

cnt = 0
for i in itertools.permutations(xy):
  data = []
  for j in range(N):
    if j == 0:
      rex,rey = i[j]
    else:
      x,y = i[j]
      if y-rey == 0:
        data.append(MAX_INT)
      else:
        data.append((x-rex)/(y-rey))
      rex,rey = i[j]
  else:
    d = collections.Counter(data)
    cnt = max(cnt,d.most_common()[0][1])
print(N-cnt)

Submission status: Runtime Error

Solution code:
import numpy as np
n = int(input())
points = np.zeros((n, 2), dtype=np.int)
for i in range(n):
    x, y = [int(x) for x in input().split()]
    points[i, 0] = x
    points[i, 1] = y

diffs = {}
for i in range(n):
    for j in range(n):
        if i != j:
            diff = (points[i, 0] - points[j, 0], points[i, 1] - points[j, 1])
            if diff in diffs:
                diffs[diff] += 1
            else:
                diffs[diff] = 1

count = sorted(diffs.items(), key=lambda kv: kv[1])[-1][1]
print(n-count)

Submission status: Runtime Error

Solution code:
import collections

n = input()
N = int(n)

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

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

clist = collections.Counter(diff)
count = clist.most_common()[0][1]
result = N - count
print(result)

Submission status: Runtime Error

Solution code:
from fractions import Fraction
N = int(input())
l = []

d = {}
x = [0] * N
y = [0] * N
for i in range(N):
    x[i], y[i] = map(int, input().split())

for i in range(N):
    for j in range(i + 1, N):
        dx = x[i] - x[j]
        dy = y[i] - y[j]
        if dx == 0:
            frac = "-0"
        else:
            frac = Fraction(dy, dx)
        frac = str(frac)
        if frac not in d:
            d[frac] = 1
        else:
            d[frac] += 1


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

Submission status: Runtime Error

Solution code:
from collections import defaultdict
from itertools import combinations
def solve():
    n = int(input())
    XY = [list(map(int, input().split())) for _ in range(n)]
    m = defaultdict(int)
    for i, j in combinations(range(n), 2):
        m[(XY[i][0] - XY[j][0], XY[i][1] - XY[j][1])] += 1
    print(n - max(m.items(), key=lambda x: x[1])[1])
solve()

Submission status: Runtime Error

Solution code:
from collections import Counter



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

for i, a in enumerate(points):
    for j in range(N):
        if j == i:
            continue
        b = points[j]
        dx = b[0] - a[0]
        dy = b[1] - a[1]
        vecs[(i, j)] = (dx, dy)
        counter[(dx, dy)] += 1

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

for i, p in enumerate(points):
    if i in visited:
        continue
    x, y = p
    if (x + dx, y + dy) in visited or (x - dx, y - dy) in visited:
        continue
    cost += 1
    visited.add(p)

print(cost)

Submission status: Runtime Error

Solution code:
from collections import Counter
str = input()
N = int(str.split()[0])

x = []
y = []
t = []
for i in range(N) :
	str = input()
	sStr = str.split()
	x.append(int(sStr[0]))
	y.append(int(sStr[1]))
	t.append(i)
for i in range(N) :
	for j in range(i, N) :
		if (x[i] < x[j]) :
			x[i], x[j] = x[j], x[i]
			y[i], y[j] = y[j], y[i]
			t[i], t[j] = t[j], t[i]

for i in range(N) :
	for j in range(i, N) :
		if (x[i] == x[j]) :
			if (y[i] < y[j]) :
				x[i], x[j] = x[j], x[i]
				y[i], y[j] = y[j], y[i]
				t[i], t[j] = t[j], t[i]

a = []

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

c = Counter(a)
Ml = c.most_common(1)[0][0]

co = 1
for i in range(N - 1) :
	tuple = (x[i] - x[i+1], y[i] - y[i+1])
	if (tuple != Ml) :
		co = co + 1

print(co)

Submission status: Runtime Error

Solution code:
import statistics
import copy
n=int(input())
x=[0]*n
xx=[0]*(n-1)
yy=[0]*(n-1)
for i in range(n):
    x[i]=list(map(int,input().split()))
x.sort(key=lambda x:x[1])
x.sort(key=lambda x:x[0])
for i in range(n-1):
    xx[i]=x[i+1][0]-x[i][0]
    yy[i]=x[i+1][1]-x[i][1]
X=statistics.mode(xx)
Y=statistics.mode(yy)
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
    print(min(max(cntx0,cnty),max(cntx,cnty0)))    
else:
    cntx=n-1-xx.count(X)+1
    cnty=n-1-yy.count(Y)+1
    print(max(cntx,cnty))

Submission status: Runtime Error

Solution code:
import sys
import collections

def input():
    return sys.stdin.readline()[:-1]

def main():
    n = int(input())
    x = [list(map(int, input().split())) for _ in range(n)]

    dist = [(x[j][0] - x[i][0], x[j][1] - x[i][1]) for j in range(n) for i in range(n)]
    c = collections.Counter(dist)
    ans = c.most_common()
    print(n - ans[1][1])

if __name__ == '__main__':
    main()

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

dic = {}
for i in range(N):
    px = balls[i][0]
    py = balls[i][1]
    for j in range(N-(i+1)):
        dx = balls[j][0] - px
        dy = balls[j][1] - py
        px = balls[j][0]
        py = balls[j][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())
print(N - d_max)

Submission status: Runtime Error

Solution code:
N = int(input())
xy = [list(map(int, input().split())) for _ in range(N)]
xy.sort()
deff_xy = []
memo = {}
for i in range(N-1):
    x = str(xy[i+1][0]-xy[i][0])
    y = str(xy[i+1][1]-xy[i][1])
    deff_xy = ('').join([x, y])
    if deff_xy in memo:
        memo[deff_xy] += 1
    else:
        memo[deff_xy] = 1
print(N-max(memo.values()))

Submission status: Runtime Error

Solution code:
import numpy
import sys

input = sys.stdin.readline

n = int(input())

arr = numpy.zeros((1000000000, 1000000000), dtype=numpy.bool)

for _ in range(n):
    x, y = map(int, input().split())
    arr[x-1][y-1] = True

cost = 0

x = 0
y = n-1
tansaku_kaisu = 1
for index in range(2 * n - 1):
    if index == 0:
        if arr[y][x] == True:
            cost += 1
        tansaku_kaisu += 1
    elif index == 2 * n - 1 - 1:
        if arr[y][x] == True:
            cost += 1
    else:
        for _ in range(tansaku_kaisu):
            if arr[y][x] == True:
                cost += 1
                if _ != 0 and arr[y-1][x-1] == True:
                    cost -= 1

        if 0 <= index <= n - 1:
            tansaku_kaisu += 1
        else:
            tansaku_kaisu -= 1

print(cost + 1)

Submission status: Runtime Error

Solution code:
from collections import Counter
n = int(input())
diffs = []
xi, yi = map(int, input().split())
for _ in range(n - 1):
    xn, yn = map(int, input().split())
    diffs.append((xi - xn, yi - yn))
    xi, yi = xn, yn

c = Counter(diffs)
cv = c.most_common(1)
(p, q), val = c.most_common(1)[0]
print(n - val)

Submission status: Runtime Error

Solution code:
from itertools import combinations
N = int(input())

X_Y = [0] * N

for i in range(N):
    X_Y[i] = tuple(map(int, input().split()))
    
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)