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: Time Limit Exceeded

Solution code:
# 残っているボールを1つ選んで回収、(a, b)
# (a-p, b-q) コスト0

import itertools
import sys
sys.setrecursionlimit(100000) 

score = 1
p = 0
q = 0

n = int(input())
e = [[int(i) for i in input().split()] for i in range(n)]

if n == 1:
    print(1)
    exit()

arr = list(itertools.permutations(e))
for i, parent in enumerate(arr):
    if i == 0:
        for j, child in enumerate(parent):
            if j == 0:
                p = parent[j + 1][0] - child[0]
                q = parent[j + 1][1] - child[1]
                score = 1
                continue
            if not child[0] == parent[j-1][0] + p and not child[1] == parent[j - 1][1] + q:
                score += 1
    else:
        tmp_p = p
        tmp_q = q
        sc = score
        for j, child in enumerate(parent):
            if j == 0:
                p = parent[j + 1][0] - child[0]
                q = parent[j + 1][1] - child[1]
                score = 1
                continue
            if not child[0] == parent[j-1][0] + p and not child[1] == parent[j - 1][1] + q:
                score += 1
            if score > sc:
                p = tmp_p
                q = tmp_q
                score = sc
                continue

print(score)

Submission status: Time Limit Exceeded

Solution code:
import logging
import itertools
import numpy as np

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

def costs_counter(N, diffs):
    num = []
    for i in diffs:
        num.append(diffs.count(i))

    max_num = max(num)
    
    return N - max_num
        
def main():
    N = int(input())

    if N == 1:
        print(1)
    else:
        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)
        
        costs = []
        for seq in itertools.permutations(ball_array):
            p_q = []
            for i in range(0, N - 1):
                diff = list(seq[i] - seq[i + 1])
                if diff[0] != 0 or diff[1] != 0:
                    p_q.append(diff)

                logging.info(p_q)
            costs.append(costs_counter(N, p_q))

        logging.info(costs)
        print(min(costs))
          
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# coding: UTF-8
import sys
#sys.setrecursionlimit(n)
import heapq
import re
import bisect
import random
import math
import itertools
from collections import defaultdict, deque
from copy import deepcopy
from decimal import *

readl= lambda: list(map(int, sys.stdin.readline().split()))
readt= lambda: tuple(map(int, sys.stdin.readline().split()))
read = lambda: sys.stdin.readline().rstrip()
readi = lambda: int(read())
readmi = lambda: map(int, sys.stdin.readline().split())
readms = lambda: map(str, sys.stdin.readline().split())

n = readi()
a = []
b = []
if n == 1:
    print(1)
    exit()
for i in range(n):
    x, y = readmi()
    a.append([x,y])
    b.append([y,x])
a.sort()
b.sort()
aa = defaultdict(int)
bb = defaultdict(int)
cc = defaultdict(int)
dd = defaultdict(int)
old1 = 0
old2 = 0
flg = True
for i in range(n - 1):
    aa[(a[i + 1][0] - a[i][0], a[i + 1][1] - a[i][1])] += 1
    bb[(b[i + 1][0] - b[i][0], b[i + 1][1] - b[i][1])] += 1
    cc[(-a[i + 1][0] + a[i][0], -a[i + 1][1] + a[i][1])] += 1
    dd[(-b[i + 1][0] + b[i][0], -b[i + 1][1] + b[i][1])] += 1
aaa = sorted(aa.items(), key=lambda x:x[1], reverse=True)
bbb = sorted(bb.items(), key=lambda x:x[1], reverse=True)
ccc = sorted(cc.items(), key=lambda x:x[1], reverse=True)
ddd = sorted(dd.items(), key=lambda x:x[1], reverse=True)
kkk = max(aaa[0],bbb[0],ccc[0],ddd[0], key=lambda x:x[1])
ccount = []
def dfs(index,count,used,used_count,oldx,oldy):
    t_used = list(used)
    if used_count == n - 1:
        ccount.append(count)
        return
    for i in range(n):
        if t_used[i]:
            continue
        else:
            t_used[i] = True
            t = 0
            if a[i][0] - oldx == kkk[0][0] and a[i][1] - oldy == kkk[0][1]:
                t = 0
            else:
                t = 1
            dfs(i, count + t, t_used, used_count + 1, a[i][0], a[i][1])
for i in range(n):
    use = [False] * (n + 1)
    use[i] = True
    dfs(i, 1, use, 0, a[i][0], a[i][1])
print(min(ccount))

Submission status: Time Limit Exceeded

Solution code:
import collections
import itertools
n=int(input())
x=[]

for i in range(n):
    aa=list(input().split())
    x.append((int(aa[0]),int(aa[1])))
    
if n==1 or n==2:
    print(1)
else:
    bb=list(itertools.permutations(x))
    res=[]
    for j in range(len(bb)):
        cc=bb[j]
        z=[]
        for i in range(n-1):
            z.append((cc[i][0]-cc[i+1][0],cc[i][1]-cc[i+1][1]))
        c = collections.Counter(z)
        res.append(c.most_common()[0][1])
    print(n-max(res))

Submission status: Time Limit Exceeded

Solution code:
import collections
import itertools
n=int(input())
x=[]

for i in range(n):
    aa=list(input().split())
    x.append((int(aa[0]),int(aa[1])))
    
if n==1 or n==2:
    print(1)
else:
    

    bb=list(itertools.permutations(x))
    res=[]
    for j in range(len(bb)):
        cc=bb[j]
        z=[]
        for i in range(n-1):
            xxx=(cc[i][0]-cc[i+1][0],cc[i][1]-cc[i+1][1])
            z.append(xxx)
            c = collections.Counter(z)
            res.append(c.most_common()[0][1])
    print(n-max(res))

Submission status: Time Limit Exceeded

Solution code:
import itertools
costs = []
N = int(input())
x, y = [], []
# (x,y)の値を取得
for n in range(N):
    temp = list(map(int, input().split()))
    x.append(temp[0])
    y.append(temp[1])
# コスト計算
for n, perm in enumerate(itertools.permutations(zip(x,y), N)):
    sol = 0
    cost = 1
    for i in range(1, N):
        if i == 1:
            sol = [perm[i][0] - perm[i-1][0], perm[i][1] - perm[i-1][1]]
        else:
            if perm[i][0] - sol[0] == perm[i-1][0] and perm[i][1] - sol[1] == perm[i-1][1]:
                cost += 0
            else:
                cost += 1
    costs.append(cost)
print(min(costs))

Submission status: Time Limit Exceeded

Solution code:
import itertools
import numpy as np
costs = []
N = int(input())
x, y = [], []
# (x,y)の値を取得
for n in range(N):
    temp = list(map(int, input().split()))
    x.append(temp[0])
    y.append(temp[1])
# コスト計算
for n, perm in enumerate(itertools.permutations(zip(x,y), N)):
    sol = 0
    cost = 1
    for i in range(1, N):
        if i == 1:
            sol = [perm[i][0] - perm[i-1][0], perm[i][1] - perm[i-1][1]]
        else:
            if perm[i][0] - sol[0] == perm[i-1][0] and perm[i][1] - sol[1] == perm[i-1][1]:
                cost += 0
            else:
                cost += 1
    costs.append(cost)
print(np.min(costs))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
li_ = []

for i in range(N):
  a, b = map(int, input().split())
  li_.append([a, b])
li_.sort()    

li_1 = [x[0] for x in li_]
li_2 = [x[1] for x in li_]
a_ = max(li_1) - min(li_1)
b_ = max(li_2) - min(li_2)

def picking_up(p, q):
  li = [x for x in li_]
  cost = 0
  for i in range(N):
    if len(li) == 0:
      break
    cost += 1
    if len(li) == 0:
      break
    a, b = li[0][0], li[0][1]
    li.remove([a,b])
    while [a+p, b+q] in li:
        li.remove([a+p, b+q])
        a, b = a+p, b + q
  return cost


new_cost = 100
for p in range(a_+1):
    for q in range(b_+1):
        cost = picking_up(p, q)
        if cost < new_cost:
            new_cost = cost
           
print(new_cost)

Submission status: Time Limit Exceeded

Solution code:
import copy

n = int(input())
lst = [[0]*2 for i in range(n)]
for i in range(n):
    lst[i][0], lst[i][1] = map(int, input().split())

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

lst_copy = copy.deepcopy(lst)
saidai = 0
for i in range(n-1):
    for j in range(i+1, n):
        cnt = 0
        p = lst[j][0] - lst[i][0]
        q = lst[j][1] - lst[i][1]
        lst_copy = copy.deepcopy(lst)
        while lst_copy != []:
            lst_k = lst_copy.pop(0)
            xs, ys = lst_k[0], lst_k[1]
            length = len(lst_copy)
            delete_lst = []
            lst_copy_copy = copy.deepcopy(lst_copy)
            for l in range(length):
                xl, yl = lst_copy[l][0], lst_copy[l][1]
                if xl == xs + p and yl == ys + q:
                    xs = xs + p
                    ys = ys + q
                    cnt += 1
                    lst_copy_copy.remove([xl, yl])
            lst_copy = lst_copy_copy
        saidai = max(saidai, cnt)

print(n-saidai)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
import itertools

def solve(N: int, x: "List[int]", y: "List[int]"):
    if N == 1:
        print(1)
        return

    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
            if cost >= mincost:
                break
        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: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
from itertools import product
n = int(input())
xy = [list(map(int, input().split())) for _ in range(n)]

xy.sort(key=lambda x: (x[0], x[1]))
ps = set()
for i, j in product(range(n), range(n)):
    if i >= j:
        continue
    ps.add(xy[j][0] - xy[i][0])
qs = set()
for i, j in product(range(n), range(n)):
    if i >= j:
        continue
    qs.add(xy[j][1] - xy[i][1])

m = 0
for p, q in product(ps, qs):
    c = 0
    for i in range(n - 1):
        for j in range(i + 1, n):
            if xy[j][0] - xy[i][0] != p:
                continue
            if xy[j][1] - xy[i][1] != q:
                continue
            c += 1
            break
    m = max(m, c)

xy.sort(key=lambda x: (x[1], x[0]))
ps = set()
for i, j in product(range(n), range(n)):
    if i >= j:
        continue
    ps.add(xy[j][0] - xy[i][0])
qs = set()
for i, j in product(range(n), range(n)):
    if i >= j:
        continue
    qs.add(xy[j][1] - xy[i][1])

for p, q in product(ps, qs):
    c = 0
    for i in range(n - 1):
        for j in range(i + 1, n):
            if xy[j][0] - xy[i][0] != p:
                continue
            if xy[j][1] - xy[i][1] != q:
                continue
            c += 1
            break
    m = max(m, c)

print(n - m)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
x, y = (
    zip(*(map(int, input().split()) for _ in range(N))) if N else
    ((), ())
)

class UnionFindTree:
    def __init__(self, n):
        self.p = [i for i in range(n + 1)]
        self.r = [0 for _ in range(n + 1)]

    def find(self, x):
        if self.p[x] != x:
            self.p[x] = self.find(self.p[x])
        return self.p[x]

    def union(self, x, y):
        px = self.find(x)
        py = self.find(y)
        if px != py:
            if self.r[px] < self.r[py]:
                self.p[px] = py
            else:
                self.p[py] = px
                if self.r[px] == self.r[py]:
                    self.r[px] += 1

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


ans = 10**10

for i in range(N):
    for j in range(N):
        p, q = (x[i] - x[j], y[i] - y[j])
        uft = UnionFindTree(N)
        for u in range(N):
            for v in range(N):
                if (x[u] - x[v], y[u] - y[v]) == (p, q) or (x[u] - x[v], y[u] - y[v]) == (-p, -q):
                    uft.union(u, v)
        ans = min(ans, len({uft.find(z) for z in range(N)}))

print(ans)

Submission status: Accepted

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

  dic={}
  for i in range(n):
    for j in range(n):
      if i==j:
        continue
      dx,dy = l[j][0]-l[i][0],l[j][1]-l[i][1]
      if (dx,dy) not in dic:
        dic[dx,dy]=1
      else:
        dic[dx,dy]+=1

  dic=sorted(dic.items(),key=lambda x:x[1],reverse=True)
  print(n-dic[0][1])

Submission status: Accepted

Solution code:
import sys, math, re
from itertools import accumulate
sys.setrecursionlimit(10**9)

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

def mi():
    return map(int, input().split())

def ii():
    return int(input())

def i2(n):
    tmp = [list(mi()) for i in range(n)]
    return [list(i) for i in zip(*tmp)]

def main():
    N = ii()
    if N == 1:
        print(1)
        return
        
    x, y = i2(N)
    d = {}

    for i in range(N):
        for j in range(N):
            if i == j:
                continue

            pair = (x[i]-x[j], y[i]-y[j])
            if not pair in d:
                d[pair] = 0
            
            d[pair] += 1

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


if __name__ == "__main__":
    main()

Submission status: Accepted

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

a={}
for v in itertools.combinations(xy,2):
  z = list(v)
  z.sort()
  x = z[1][0]-z[0][0]
  y = z[1][1]-z[0][1]
  if (x,y) not in a:
    a[(x,y)] = 1
  else:
    a[(x,y)] += 1
if n == 1:
  print (1)
else:
  print (n-max(a.values()))

Submission status: Accepted

Solution code:
import itertools
n = int(input())
xy = []

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


a,b = [],[]
for v in itertools.combinations(xy,2):
  z = list(v)
  z.sort()
  x = z[1][0]-z[0][0]
  y = z[1][1]-z[0][1]
  a.append([x,y])
  if [x,y] in b:
    continue
  b.append([x,y])

c = 0
for i in b:
  c = max(c,a.count(i))
print (n-c)

Submission status: Accepted

Solution code:
n = int(input())
 
difs = {}
points = []
 
for i in range(n):
    x, y = list(map(int, input().split()))
 
    for j in range(len(points)):
        dif1 = (points[j][0] - x, points[j][1] - y)
        dif2 = (-dif1[0], -dif1[1])
 
        difs[dif1] = 1 if dif1 not in difs else difs[dif1] + 1
        difs[dif2] = 1 if dif2 not in difs else difs[dif2] + 1
 
    points.append((x, y))
 
if n == 1:
    print(1)
else:
    print(n-max(difs.values()))

Submission status: Accepted

Solution code:
n=int(input())
l=[]
for i in range(n):
    x,y=map(int,input().split())
    l.append([x,y])
l=sorted(l)
s=set()
for j in range(n-1):
    for k in range(j,n):
        s.add((l[k][0]-l[j][0],l[k][1]-l[j][1]))
s_l=sorted(list(s))
cnt=[0]*len(s_l)
dic={}
for i in range(len(s_l)):
    dic[s_l[i]]=i
for j in range(n-1):
    for k in range(j+1,n):
        cnt[dic[(l[k][0]-l[j][0],l[k][1]-l[j][1])]]+=1
if n==1:
    print(1)
    exit()
print(n-max(cnt))

Submission status: Accepted

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

d = dict()
for point in xy:
    d[str(point)] = 1


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

ans = N
que = deque()

for i in range(N):
    for j in range(i+1, N):
        p = xy[i][0] - xy[j][0]
        q = xy[i][1] - xy[j][1]

        ans_tmp = N

        for point in xy:
            add = [point[0] + p, point[1] + q]
            # sub = [point[0] - p, point[1] - q]
            if d.get(str(add)) == 1:
                ans_tmp -= 1
                d[str(add)] -= 1
                que.append(str(add))
            # if d.get(str(sub)) == 1:
            #     ans -= 1
            #     d[str(sub)] -= 1
        
        ans = min(ans, ans_tmp)
        
        while len(que):
            key = que.pop()
            d[key] += 1
        


print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import deque
input = sys.stdin.readline

def main():
  n = int(input())
  ball = [tuple(map(int, input().split())) for i in range(n)]

  ans = n
  for i in range(n):
    for j in range(n):
      p, q = ball[i][0] - ball[j][0], ball[i][1] - ball[j][1]
      par = [-1]*n
      node = [[] for i in range(n)]
      for s in range(n):
        for t in range(n):
          x, y = ball[s][0] - ball[t][0], ball[s][1] - ball[t][1]
          if x == p and y == q:
            node[s].append(t)
            node[t].append(s)
      already = [False]*n
      count = 0
      for k in range(n):
        if already[k]:
          continue
        count += 1
        already[k] = True
        not_yet = deque([k])
        while not_yet:
          key = not_yet.pop()
          for v in node[key]:
            if already[v]:
              continue
            already[v] = True
            not_yet.append(v)
      if ans > count:
        ans = count
  print(ans)

  
main()

Submission status: Accepted

Solution code:
n = int(input())
A = []
for _ in range(n):
  x, y = map(int, input().split())
  A.append((x, y))
maxc = 0
for i in range(n):
  for j in range(n):
    c = 0
    if i == j:
      continue
    dx = A[i][0] - A[j][0]
    dy = A[i][1] - A[j][1]
    for k in range(n):
      for l in range(n):
        if k == l:
          continue
        if A[k][0] + dx == A[l][0] and A[k][1] + dy == A[l][1]:
          c += 1
    if maxc < c:
      maxc = c
print(n-maxc)

Submission status: Accepted

Solution code:
n = int(input())

difs = {}
points = []

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

    for j in range(len(points)):
        dif1 = (points[j][0] - x, points[j][1] - y)
        dif2 = (-dif1[0], -dif1[1])

        difs[dif1] = 1 if dif1 not in difs else difs[dif1] + 1
        difs[dif2] = 1 if dif2 not in difs else difs[dif2] + 1

    points.append((x, y))

if n == 1:
    print(1)
else:
    print(n-max(difs.values()))

Submission status: Accepted

Solution code:
import sys
#import numpy as np
import math
#from fractions import Fraction
import itertools
from collections import deque
from collections import Counter
import heapq
from fractions  import gcd
#input=sys.stdin.readline
#import bisect
n=int(input())
l=[i for i in range(n)]
xy=[list(map(int,input().split()))  for _ in range(n)]
if n==1:
  print(1)
  exit()
comb=itertools.permutations(l,2)
dic={}
for c in comb:
    i,j=c
    xi,yi=xy[i]
    xj,yj=xy[j]
    p=xi-xj
    q=yi-yj
    if (p,q) not in dic:
        dic[(p,q)]=1
    else:
        dic[(p,q)]+=1
res=-1
ai=-1
for i in dic.keys():
    if res<dic[i]:
        ai=i
        res=dic[i]
print(n-dic[ai])

Submission status: Accepted

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

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

dis = {}

for i in range(N):
    for j in range(N):
        if i == j:
            continue
        X = XY[j][0]-XY[i][0]
        Y = XY[j][1]-XY[i][1]
        if (X,Y) in dis:
            dis[(X,Y)] += 1
        else:
            dis[(X,Y)] = 1
print(N-max(dis.values()))

Submission status: Accepted

Solution code:
N=int(input())
if N==1:
  print(1)
  exit()
L=list()
R=list()
for i in range(N):
  a,b=map(int,input().split())
  L.append([a,b])
k=dict()
for i in range(N-1):
  for j in range(i+1,N):
    a,b=L[i]
    c,d=L[j]
    R.append([a-c,b-d])
    n=str(a-c)+" "+str(b-d)
    if n in k:
      k[n]+=1
    else:
      k[n]=1
    R.append([c-a,d-b])
    n=str(c-a)+" "+str(d-b)
    if n in k:
      k[n]+=1
    else:
      k[n]=1
op=max(k.values())
print(N-op)

Submission status: Accepted

Solution code:
from collections import defaultdict
from typing import Counter

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

ans = 0

for i in range(N):
    for j in range(N):
        if i == j:
            continue
        a = XY[i][0]-XY[j][0]
        b = XY[i][1]-XY[j][1]
        cnt[a][b] += 1
        ans = max(cnt[a][b], ans)

print(N-ans)

Submission status: Accepted

Solution code:
import sys
from sys import exit
from collections import deque
from copy import deepcopy
from bisect import bisect_left, bisect_right, insort_left, insort_right
from heapq import heapify, heappop, heappush
from itertools import product, permutations, combinations, combinations_with_replacement
from functools import reduce
from math import gcd, sin, cos, tan, asin, acos, atan, degrees, radians

sys.setrecursionlimit(10**6)
INF = 10**20
eps = 1.0e-20
MOD = 10**9+7

def lcm(x,y):
    return x*y//gcd(x,y)
def lgcd(l):
    return reduce(gcd,l)
def llcm(l):
    return reduce(lcm,l)
def powmod(n,i,mod):
    return pow(n,mod-1+i,mod) if i<0 else pow(n,i,mod)
def div2(x):
    return x.bit_length()
def div10(x):
    return len(str(x))-(x==0)
def intput():
    return int(input())
def mint():
    return map(int,input().split())
def lint():
    return list(map(int,input().split()))
def ilint():
    return int(input()), list(map(int,input().split()))
def judge(x, l=['Yes', 'No']):
    print(l[0] if x else l[1])
def lprint(l, sep='\n'):
    for x in l:
        print(x, end=sep)
def ston(c, c0='a'):
    return ord(c)-ord(c0)
def ntos(x, c0='a'):
    return chr(x+ord(c0))
class counter(dict):
    def __init__(self, *args):
        super().__init__(args)
    def add(self,x,d=1):
        self.setdefault(x,0)
        self[x] += d
    def list(self):
        l = []
        for k in self:
            l.extend([k]*self[k])
        return l
class comb():
    def __init__(self, n, mod=None):
        self.l = [1]
        self.n = n
        self.mod = mod
    def get(self,k):
        l,n,mod = self.l, self.n, self.mod
        k = n-k if k>n//2 else k
        while len(l)<=k:
            i = len(l)
            l.append(l[i-1]*(n+1-i)//i if mod==None else (l[i-1]*(n+1-i)*powmod(i,-1,mod))%mod)
        return l[k]
def pf(x,mode='counter'):
    C = counter()
    p = 2
    while x>1:
        k = 0
        while x%p==0:
            x //= p
            k += 1
        if k>0:
            C.add(p,k)
        p = p+2-(p==2) if p*p<x else x
    if mode=='counter':
        return C
    S = set([1])
    for k in C:
        T = deepcopy(S)
        for x in T:
            for i in range(1,C[k]+1):
                S.add(x*(k**i))
    if mode=='set':
        return S
    if mode=='list':
        return sorted(list(S))

N=intput()
xy=[]
for _ in range(N):
    xy.append(lint())
xy.sort()
if N==1:
    print(1)
    exit()
C=counter()
for i in range(N):
    for j in range(i+1,N):
        C.add((xy[j][0]-xy[i][0],xy[j][1]-xy[i][1]))
print(N-max(list(C.values())))

Submission status: Accepted

Solution code:
N = int(input())
l=[]
if N==1:
   print(1)
   exit()
for i in range(N):
   a,b=map(int,input().split())
   l.append((a,b))
l2=[]
for i in range(N):
   for j in range(N):
      if i!=j:
         l2.append((l[i][0]-l[j][0],l[i][1]-l[j][1]))
from collections import Counter
l2=max(Counter(l2).values())
print(N-l2)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def MS(): return input().split()
def LS(): return list(input())
def LLS(rows_number): return [LS() for _ in range(rows_number)]
def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')
# from math import ceil, floor, log2
from collections import deque, defaultdict
# from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
# from heapq import heapify, heappop, heappush
# import numpy as np    # cumsum
# from bisect import bisect_left, bisect_right

def solve():
    N = II()
    X = [0] * N
    Y = [0] * N
    for i in range(N):
        x, y = MI()
        X[i], Y[i] = x, y

    dct = defaultdict(int)
    for i in range(N):
        for j in range(N):
            if i == j: continue
            xi, yi = X[i], Y[i]
            xj, yj = X[j], Y[j]

            dct[(xi-xj, yi-yj)] += 1
    # print(dct)
    mx = 0
    for d in dct.values():
        mx = max(mx, d)
    print(N - mx)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
N = int(input())

P = []

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

mp = {}

for i in range(N):
    for j in range(i+1,N):
        mp[(P[i][0]-P[j][0],P[i][1]-P[j][1])] = 0
        mp[(P[j][0]-P[i][0],P[j][1]-P[i][1])] = 0

for i in range(N):
    for j in range(i+1,N):
        mp[(P[i][0]-P[j][0],P[i][1]-P[j][1])] += 1
        mp[(P[j][0]-P[i][0],P[j][1]-P[i][1])] += 1

ans = N
for i in mp:
    ans = min(ans,N-mp[i])

print(ans)

Submission status: Accepted

Solution code:
n= int(input())
if n == 1:
  print(1)
  exit()
ab = [list(map(int,input().split())) for _ in range(n)]
pq = {}
for i in range(n-1):
  for j in range(i+1,n):
    a1,b1 = ab[i]
    a2,b2 = ab[j]
    p = a1-a2
    q = b1-b2
    if p<0 or p==0 and q<0:
      p = -p
      q = -q
    if (p,q) in pq:
      pq[(p,q)] += 1
    else:
      pq[(p,q)] = 1
print(n-max(pq.values()))

Submission status: Accepted

Solution code:
N = int(input())

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

from collections import defaultdict

if N == 1:
    print(1)
    exit(0)

cnt = defaultdict(int)
for pi in range(N):
    for pj in range(N):
        if pi == pj:
            continue
        # x
        dx = P[pi][0] - P[pj][0]

        # y
        dy = P[pi][1] - P[pj][1]

        cnt[(dx, dy)] += 1

ans = N-max(cnt.values())
print(ans)

Submission status: Accepted

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

c=[set() for i in range(n)]
for i in range(n):
  for j in range(n):
    c[i].add((p[i][0]-p[j][0],p[i][1]-p[j][1]))
mn=1 if n==1 else 100
for i in range(n):
  for j in range(i+1,n):
    cnt=0
    pq=(p[i][0]-p[j][0],p[i][1]-p[j][1])
    for k in range(n):
      if not(pq in c[k]):
        cnt+=1
    mn=min(mn,cnt)
print(mn)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# coding: utf-8

# In[9]:


N = int(input())
X = []; Y = []
for _ in range(N):
    x,y = map(int, input().split())
    X += [x]
    Y += [y]


# In[10]:


dic = {}
for i in range(N):
    for j in range(N):
        if i != j:
            x = X[i]-X[j]
            y = Y[i]-Y[j]
            dic[(x,y)] = dic.get((x,y),0) + 1
if N == 1:
    print(1)
else:
    print(N-max(dic.values()))


# In[ ]:

Submission status: Accepted

Solution code:
N = int(input())
S = list(tuple(map(int, input().split())) for _ in range(N))
A = []
if N == 1:
    print(1)
else:
    for i in range(N):
        for j in range(N):
            if i == j:
                continue
            a, b = S[i]
            c, d = S[j]
            for k in range(len(A)):
                e, f, g = A[k]
                if e == a-c and f == b-d:
                    A[k] = (e, f, g+1)
                    break
            else:
                A.append((a-c, b-d, 1))
    print(N-max(list(x[2] for x in A)))

Submission status: Accepted

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

count=[]
for x1,y1 in xy:
    for x2,y2 in xy:
        if x1==x2 and y1==y2:
            continue
        c=str(x1-x2)+':'+str(y1-y2)
        count.append(c)

from collections import*
C=Counter(count)
C['zentsu999']=0
print(N-max(C.values()))

Submission status: Accepted

Solution code:
import sys
import itertools

input = sys.stdin.readline


def main():
    N = int(input())
    balls = [tuple(map(int, input().split())) for _ in range(N)]
    comb = list(itertools.combinations(balls, 2))
    ans = 0
    for c in comb:
        a, b = c
        p = b[0] - a[0]
        q = b[1] - a[1]
        ans_i = 0
        for d in balls:
            e = (d[0] + p, d[1] + q)
            if e in balls:
                ans_i += 1
        ans = max(ans, ans_i)
    print(N - ans)


if __name__ == '__main__':
    main()