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

tilt_map = {}

for i in range(N):
    for j in range(i+1, N):
        a = xy[i]
        b = xy[j]
        tilt_x = a[0] - b[0]
        tilt_y = a[1] - b[1]
        key = str(tilt_x) + ":" + str(tilt_y)
        if key in tilt_map:
            tilt_map[key] += 1
        else:
            tilt_map[key] = 1


most_key = sorted(tilt_map.items(), key=lambda x: x[1], reverse=True)[0][0]

idx = most_key.index(":")
m_dx = int(most_key[:idx])
m_dy = int(most_key[idx+1:])

if m_dx == 0:
    if m_dy < 0:
        m_dy *= -1
    xy.sort(key=lambda x: x[1])
else:
    if m_dx < 0:
        m_dx *= -1
        m_dy *= -1
    xy.sort(key=lambda x:x[0])

pos = xy.pop(0)
cost = 1

while len(xy) > 0:
    next_x = pos[0] + m_dx
    next_y = pos[1] + m_dy
    for _xy in xy[::]:
        if _xy[0] == next_x and _xy[1] == next_y:
            xy.remove([next_x, next_y])
            pos = [next_x, next_y]
            break
    else:
        pos = xy.pop(0)
        cost += 1
print(cost)

Submission status: Runtime Error

Solution code:
from statistics import mode

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

x.sort(key=lambda x:(x[0],x[1]))
tx = []
ty = []
for i in range(n-1):
    tx.append(x[i+1][0] - x[i][0])
    ty.append(x[i+1][1] - x[i][1])
    
ttx = mode(tx)
tty = mode(ty)
fs = min(n - tx.count(ttx), n - ty.count(tty))

x.sort(key=lambda x:(x[1],x[0]))
tx = []
ty = []
for i in range(n-1):
    tx.append(x[i+1][0] - x[i][0])
    ty.append(x[i+1][1] - x[i][1])
    
ttx = mode(tx)
tty = mode(ty)
lt = min(n - tx.count(ttx), n - ty.count(tty))

print(min(fs, lt))

Submission status: Runtime Error

Solution code:
#!/usr/bin/env pypy
from __future__ import division, print_function

import os
import sys
from __builtin__ import xrange as range
from cStringIO import StringIO
from future_builtins import ascii, filter, hex, map, oct, zip
from io import IOBase

import __pypy__


def gcd(x, y):
    """greatest common divisor of x and y"""
    while y:
        x, y = y, x % y
    return x


def get_2dline(p1, p2):
    if p1 == p2:
        return (0, 0, 0)
    _p1, _p2 = min(p1, p2), max(p1, p2)
    a, b, c = _p2[1] - _p1[1], _p1[0] - _p2[0], _p1[1] * _p2[0] - _p1[0] * _p2[1]
    g = gcd(gcd(a, b), c)
    return (a // g, b // g, c // g)


def main():
    n = int(input())
    points = []
    for _ in range(n):
        points.append(tuple(map(int, input().split())))

    line_set = set()
    for i in range(n):
        for j in range(n):
            a, b, c = get_2dline(points[i], points[j])
            g = gcd(a, b)
            line_set.add((a // g, b // g))
    line_set.discard((0, 0))

    res = 10**9
    for p, q in line_set:
        counter = set()
        for x, y in points:
            counter.add(p * x + q * y)
        res = min(res, len(counter))
    print(res)


# region fastio

BUFSIZE = 8192


class FastI(IOBase):
    def __init__(self, file):
        self._fd = file.fileno()
        self._buffer = StringIO()
        self.newlines = 0

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count("\n") + (not b)
            ptr = self._buffer.tell()
            self._buffer.seek(0, 2), self._buffer.write(b), self._buffer.seek(ptr)
        self.newlines -= 1
        return self._buffer.readline()


class FastO(IOBase):
    def __init__(self, file):
        self._fd = file.fileno()
        self._buffer = __pypy__.builders.StringBuilder()
        self.write = lambda s: self._buffer.append(s)

    def flush(self):
        os.write(self._fd, self._buffer.build())
        self._buffer = __pypy__.builders.StringBuilder()


def print(*args, **kwargs):
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


sys.stdin, sys.stdout = FastI(sys.stdin), FastO(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from collections import defaultdict
from sys import stdin

def main():
    N = int(input())
    XY = [tuple(map(int, input().split())) for _ in [0] * N]

    XY.sort()
    cnt = defaultdict(int)
    x1, y1 = XY[0]
    for x2, y2 in XY[1:]:
        x = x2 - x1
        y = y2 - y1
        cnt[(x, y)] += 1
        x1, y1 = x2, y2
    print(N - max(cnt.values()))

input = lambda: stdin.readline()
main()

Submission status: Runtime Error

Solution code:
from collections import Counter as c
N = int(input())
XY = [tuple(map(int, input().split())) for _ in range(N)]
XY.sort(key=lambda xy: xy[0])

inclination = []
for i in range(1, N):
    inclination.append((XY[i][0] - XY[i-1][0], XY[i][1] - XY[i-1][1]))

ans = N - sorted(list(c(inclination).items()), key=lambda x: x[1])[-1][1]
print(ans)

Submission status: Runtime Error

Solution code:
"""
map(int,input().split())

X = input().split()
x = []
for i in range(0,len(X)):
    x.append(X[i])

"""
def search(l, x):
    if x in l:
        return l.index(x)
    else:
        return -1

N = int(input())

ball = []

for n in range(N):
    x,y = map(int,input().split(" "))
    ball.append((x,y))

#最適p,q計算
pqList = []
pqCount = []
for i in range(0,N):
    for j in range(0,N):
        if i != j:
           i_x = ball[i][0]
           i_y = ball[i][1]
           j_x = ball[j][0]
           j_y = ball[j][1]
           s = search(pqList,(abs(i_x-j_x),abs(i_y-j_y)))
           if s != -1 :
               pqCount[s] += 1
           else:
               pqList.append((abs(i_x-j_x),abs(i_y-j_y)))
               pqCount.append(1)

print(int(N - (max(pqCount)/2)))

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Jun 15 20:54:29 2019

@author: Yamazaki Kenichi
"""

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

a = set()
for j in range(N):
    for i in range(j + 1,N):
        if (A[i][1] - A[j][1]) == 0 or (A[i][0] - A[j][0]) == 0:
            continue
        a1 = (A[i][1] - A[j][1]) / (A[i][0] - A[j][0])
        a.add(a1)

ans = []
for c in a:
    T = [A[0]]
    for i in range(N):
        flg = True
        for t in T:
            if A[i][1] - t[1] == c * (A[i][0] - t[0]):
                flg = False
                break
        if flg:
            T.append(A[i])
    ans.append(len(T))
print(min(ans))

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
import collections
def solve():
  n = int(input())
  queue = []
  queue2 = []
  for i in range(n):
   x,y = (int(i) for i in input().split())
   queue.append((x,y))
  for i in range(n):
    for j in range(n):
      if i!=j:
        x1,y1 = queue[i]
        x2,y2 = queue[j]
        p = x2-x1
        q = y2-y1
        queue2.append((p,q))
  #print(queue2)
  c = collections.Counter(queue2)
  ans = n
  
  print(ans-c.most_common()[0][1])
solve()

Submission status: Runtime Error

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

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

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

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

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

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

def main():

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

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

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

	for i, val in enumerate(xy):
		if i == 0:
			x,y = val
			xm = x
			ym = y
			continue
		x, y = val
		p = x - xm
		q = y - ym
		if (p,q) in gess:
			gess[(p, q)] += 1
		else:
			gess[(p, q)] = 1
		xm = x
		ym = y

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

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

	#print(xy)

	for i, val in enumerate(xy):
		if i == 0:
			x,y = val
			xm = x
			ym = y
			continue
		x, y = val
		p = x - xm
		q = y - ym
		if (p,q) in gess2:
			gess2[(p, q)] += 1
		else:
			gess2[(p, q)] = 1
		xm = x
		ym = y

	#print(gess2)

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

	tmp = max(nai, nai2)

	print(N-tmp)



if __name__ == "__main__":
	main()

Submission status: Runtime Error

Solution code:
import collections
N = int(input())
x_list = []
y_list = []

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

p_list = [x_list[i] - x_list[i+1] for i in range(N-1)]
q_list = [y_list[i] - y_list[i+1] for i in range(N-1)]

pq_list = sorted([(p_list[i],q_list[i]) for i in range(N-1)])

pq_qty = collections.Counter(pq_list).most_common()[0][1]

print(N-pq_qty)

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):
    for j in range(N-(i+1)):
        dx = balls[i][0] - balls[j][0]
        dy = balls[i][1] - 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())
x_1, y_1 = map(int, input().split(" "))
x_2, y_2 = map(int, input().split(" "))
p, q = (x_2 - x_1), (y_2 - y_1)
cost = 1
before_x, before_y = x_2, y_2
for i in range(2, N):
  x, y = map(int, input().split(" "))
  if (x - p != before_x) | (y - q != before_y):
    cost += 1
  before_x, before_y = x, y
  
print(cost)

Submission status: Runtime Error

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

cost = 0
diff_list = []

past_x, past_y = map(int, input().split())
cost += 1

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

counter = collections.Counter(diff_list)

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
from copy import *
from collections import*
n=int(input())
p=[list(map(int,input().split()))for i in range(n)]
l=[]
for i in range(n):
    q=deepcopy(p)
    a,b=q.pop(i)
#    print(a,q)
    l.extend([(s-a,t-b)for s,t in q])
print(n-(Counter(l).most_common()[0][1]+1)+1)

Submission status: Runtime Error

Solution code:
N = int(input())

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

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

Submission status: Runtime Error

Solution code:
#

import itertools
from collections import Counter
from collections import defaultdict
import bisect
from heapq import heappush, heappop

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

    xy.sort(key=lambda p: (p[0], p[1]))
    # print(xy)

    cand = defaultdict(lambda :0)
    ans = 0
    for i in range(N-1):
        for j in range(1, N):
            p = xy[j][0] - xy[i][0]
            q = xy[j][1] - xy[i][1]
            key = '{},{}'.format(p, q)
            cand[key] += 1
    counter = Counter(cand)
    pq_count = counter.most_common()[0][1]
    # print(counter.most_common()[0])
    print(N - pq_count)




if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from collections import Counter
import math
N = int(input())
x,y = map(int, input().split())
dis_list = [[x,y]]
for i in range(N-1):
	x , y = map(int,input().split())
	for j in range(len(dis_list)):
		x = abs(x- dis_list[j][0])
		y = abs(y-dis_list[j][1])
		dis_list.append([x,y])
dis_list = dis_list[1:1+N*(N-1)//2]
counter = Counter(map(tuple, dis_list))
print(N-counter.most_common()[0][1])

Submission status: Runtime Error

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

res = []
for pi in range(N):
  for pj in range(N-pi):
    for qi in range(N):
      for qj in range(N-qi):
#コストの和の最小値を求める
#これ以上進めない点が何個あるか数えれば良い
        p = x[pi] - x[pj]
        q = y[qi] - y[qj]
        count = 0
        for item in xy:
          if [item[0]+p,item[1]+q] not in xy:
            count += 1
        if count != 0: res.append(count)

print(min(res))

Submission status: Runtime Error

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

zm = []
XY.sort(key=lambda x:x[0])
XY.sort(key=lambda x:x[1])
for i in range(N - 1):
    a = XY[i][0] - XY[i + 1][0]
    b = XY[i][1] - XY[i + 1][1]
    zm.append((a, b))
from collections import Counter
print(N - Counter(zm).most_common(1)[0][1])

Submission status: Runtime Error

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

Submission status: Runtime Error

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

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

Submission status: Runtime Error

Solution code:
N = int(input())
List=[list(map(int,input().split())) for i in range(N)]
A = []
b =[]
for i in range(N):
    for j in range(i):
        if List[i][0] > List[j][0]:
            a = [List[i][0]-List[j][0],List[i][1]-List[j][1]]
        elif List[i][0] < List[j][0]:
            a = [List[j][0]-List[i][0],List[j][1]-List[i][1]]
        else:
            if List[i][1] > List[j][1]:
                a = [List[i][0]-List[j][0],List[i][1]-List[j][1]]
            elif List[i][1] < List[j][1]:
                a = [List[j][0]-List[i][0],List[j][1]-List[i][1]]
        b.append(A.count(a))
        A.append(a)
print(N-max(b)-1)

Submission status: Runtime Error

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

diffs = {}

for i in range(N):
    for j in range(i+1,N):
        diff = (pos[j][0] - pos[i][0], pos[j][1] - pos[i][1])
        if diff not in diffs:
            diffs[diff] = 0
        diffs[diff] += 1

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

Submission status: Runtime Error

Solution code:
n = int(input())
xy = []
diff = []
for _ in range(n):
  tmp = list(map(int,input().split()))
  xy.append(tmp)
for i in range(n):
  for j in range(n):
    if j != i:
      tmpd = [ xy[j][0] - xy[i][0] , xy[j][1] - xy[i][1] ]
      flag = 0
      for mxy in diff:
        if mxy[1:] == tmpd:
            flag = 1
            mxy[0] += 1
            break
      if flag == 0:
        diff.append([0]+tmpd)
diff.sort()
diff.reverse()
print(n-diff[0][0]-1)

Submission status: Runtime Error

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

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

PQ = {}
for i in range(1, len(XY)):
    pq = XY[i][0] - XY[i-1][0], XY[i][1] - XY[i-1][1]
    if pq in PQ.keys():
        PQ[pq] += 1
    else:
        PQ[pq] = 1
pq = max(PQ, key=lambda x: PQ[x])
print(N - PQ[pq])

Submission status: Runtime Error

Solution code:
import functools as ft
import logging
import unittest
from collections import (
    namedtuple,
)
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)
    ]

    ans = []
    for p, q in pq:
        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])

    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())
XY = [list(map(int, input().split())) for _ in range(N)]

XY.sort(key=lambda x: x[0])

PQ = {}

for i in range(N):
    x0, y0 = XY[i]
    for j in range(N):
        if i == j:
            continue
        x1, y1 = XY[j]
        p, q = x0 - x1, y0 - y1
        key = str(p) + ',' + str(q)
        if key in PQ:
            PQ[key] += 1
        else:
            PQ[key] = 1
ansL = PQ.values()
print(N - max(list(ansL)))

Submission status: Runtime Error

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

t = {}
for i, pi in enumerate(p):
    for j, pj in enumerate(p):
        if i==j : continue
        
        dx, dy = pi[0] - pj[0], pi[1] - pj[1]
        if (dx, dy) in t:
            t[(dx, dy)] += 1
        else:
            t[(dx, dy)] = 1

print(N-max([t[k] for k in t]))

Submission status: Runtime Error

Solution code:
import numpy as np
N = int(input())
x_y = []
for i in range(N):
	x_y.append(list(map(int,input().split())))
ans_1 = []	
ans_2 = []

for i in range(N):
	first_ = x_y[i]
	for j in range(N - 1 - i):
		second_ = x_y[i+j+1]
		dif = [abs(first_[0] - second_[0]),abs(first_[1] - second_[1])]
		if dif not in ans_1:
			ans_1.append(dif)
			ans_2.append(1)
		else:
			ans_2[ans_1.index(dif)] += 1
			
print(N - max(ans_2))

Submission status: Runtime Error

Solution code:
import collections
N = int(input())
x_list = []
y_list = []

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

p_list = [x_list[i] - x_list[i+1] for i in range(N-1)]
q_list = [y_list[i] - y_list[i+1] for i in range(N-1)]

pq_list = [(p_list[i],q_list[i]) for i in range(N-1)]

pq_qty = collections.Counter(pq_list).most_common()[0][1]

print(N-pq_qty)

Submission status: Runtime Error

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

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

Submission status: Runtime Error

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

zm = []
XY.sort(key=lambda x:x[0])
XY.sort(key=lambda x:x[1])
for i in range(N - 1):
    a = XY[i][0] - XY[i + 1][0]
    b = XY[i][1] - XY[i + 1][1]
    zm.append((a, b))
print(zm)
from collections import Counter
print(N - Counter(zm).most_common(1)[0][1])

Submission status: Runtime Error

Solution code:
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque, OrderedDict
from copy import deepcopy
from fractions import gcd
from functools import lru_cache, reduce
from math import ceil, floor
from sys import setrecursionlimit

import heapq as hq
import itertools as its
import operator as op


# globals
inf = float('inf')
N = 0


def set_inputs():
    global N
    return


def main():
    setrecursionlimit(100000)
    set_inputs()
    # ----------MAIN----------
    n = get_int()
    X, Y = get_data(n, [int, int])
    vecs = Counter()
    for i in range(n):
        for j in range(i+1, n):
            if X[i] > X[j] or (X[i] == X[j] and Y[i] > Y[j]):
                vecs[(X[i]-X[j], Y[i]-Y[j])] += 1
            else:
                vecs[(X[j]-X[i], Y[j]-Y[i])] += 1
    print(n-vecs.most_common()[0][1])
    return


def get_int():
    return int(input())


def get_float():
    return float(input())


def get_str():
    return input().strip()


def get_li():
    return [int(i) for i in input().split()]


def get_lf():
    return [float(f) for f in input().split()]


def get_lc():
    return list(input().strip())


def get_data(n, types, sep=None):
    if len(types) == 1:
        return [types[0](input().strip()) for _ in range(n)]
    return list(zip(*(
        [t(x) for t, x in zip(types, input().strip().split(sep=sep))]
        for _ in range(n)
    )))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
N = int(input())
xy = [list(map(int, input().split())) for _ in range(N)]
xy.sort(key = lambda x:x[0])
d = {}
for i in range(N):
    for j in range(N):
        if i == j:
            continue
        tmp = (xy[i][0] - xy[j][0], xy[i][1] - xy[j][1])
        if not tmp in d:
            d[tmp] = 0
        d[tmp] += 1
        #print(xy[i][0] - xy[j][0], xy[i][1] - xy[j][1])
    #print()
d = sorted(d.items(), key = lambda x:-x[1])
print(N - d[0][1])

Submission status: Runtime Error

Solution code:
# div2019-2B - Picking Up
import collections
import sys
input = sys.stdin.readline

n = int(input())
arr = sorted([list(map(int, input().rstrip().split())) for _ in range(n)])
dic_x, dic_y = {}, {}
for i in range(1, n):
    x = arr[i][0] - arr[i - 1][0]
    y = arr[i][1] - arr[i - 1][1]
    if x in dic_x:
        dic_x[x] += 1
    else:
        dic_x[x] = 1
    if y in dic_y:
        dic_y[y] += 1
    else:
        dic_y[y] = 1

p = collections.Counter(dic_x).most_common()[0][0]
q = collections.Counter(dic_y).most_common()[0][0]
ans = 1
for i in range(1, n):
    if (arr[i - 1][0], arr[i - 1][1]) != (arr[i][0] - p, arr[i][1] - q):
        ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
from collections import Counter
n = int(input())
a = [list(map(int,input().split())) for _ in range(n)]
b = sorted(a)
c = sorted(a, key=lambda x:x[1])
bd = []
cd = []
for i in range(n-1):
    b0 = b[i+1][0] - b[i][0]
    b1 = b[i+1][1] - b[i][1]
    bd.append((b0, b1))
    
    c0 = c[i+1][0] - c[i][0]
    c1 = c[i+1][1] - c[i][1]
    cd.append((c0, c1))
    
cbd = Counter(bd)
ccd = Counter(cd)
print(n-max(cbd.most_common()[0][1], ccd.most_common()[0][1]))

Submission status: Runtime Error

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

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

Submission status: Runtime Error

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

sys.setrecursionlimit(10000000)

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

Submission status: Runtime Error

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

dif=[]
for i in range(n):
    for k in range(i+1,n):
        dif.append([xy[i][0]-xy[k][0],xy[i][1]-xy[k][1]])
        dif.append([xy[k][0]-xy[i][0],xy[k][1]-xy[i][1]])
for i in range(len(dif)):
    dif[i]=str(dif[i])
c=collections.Counter(dif)
ans=list(c.values())
ans.sort(reverse=True)
print(n-ans[0])

Submission status: Runtime Error

Solution code:
import itertools


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

  if n == 1:
    print(1)
    return

  raise NotImplementedError()
  for i, j in itertools.combinations(range(len(p)), 2):
    d = (p[j][0] - p[i][0], p[j][1] - p[i][1])

    if d not in c:
      c[d] = 1
    else:
      c[d] += 1

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


if __name__ == '__main__':
  main()

Submission status: Runtime Error

Solution code:
n=int(input())
x=[[0,0] for i in range(n)]
for i in range(n):
    x[i][0],x[i][1]=map(int,input().split())
li=[]
c=[]
for i in range(n):
    for j in range(i+1,n):
        t=[x[i][0]-x[j][0],x[i][1]-x[j][1]]
        if t in li:
            p=li.index(t)
            c[p]+=1
        else:
            li+=[t]
            c+=[1]
m=max(c)
print(n-m)

Submission status: Runtime Error

Solution code:
import sys
N=int(input())
# N=50

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

#空のリストを用意
e = set()  #部分最小木
av = set()  #部分最小木に含まれる頂点
pv = set(p)  #その他の頂点

used = {}
for pp in p:
    used[pp] = 1
used[p[0]] += 1

#始点は任意
av.add(p[0])
pv.remove(p[0])

costs = 0
while 1:
    #比較のための初期値として十分大きい数を用意
    shortestlen = sys.float_info.max
    #部分最小木に追加する辺を為す2点の初期化
    kav = None  #部分最小木に含まれる頂点からの候補
    kpv = None  #その他の頂点からの候補
    for v1 in av:
        for v2 in pv:
            #重みの計算（ここでは距離）
            dist = 1 if (v1[0]==v2[0] or v1[1] == v2[1]) else 0
            # dist = math.sqrt(  (v1[0]-v2[0])**2 + ( v1[1]-v2[1] )**2 )
            if shortestlen > dist and used[v1] > 0:
                shortestlen = dist
                #候補の更新
                kav = v1
                kpv = v2
    if shortestlen >= 0:
        #部分最小木に追加
        costs += shortestlen
        e.add((kav , kpv))
        used[kav] -= 1
    #確定した頂点を移す
    av.add(kpv)
    pv.remove(kpv)
    #全頂点に対する判定を終えたら終了
    if len(pv) == 0:
        break

print(costs+1)
# print(e)