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: Accepted

Solution code:
from collections import defaultdict
n = int(input())
li = []
for i in range(n):
    x, y = map(int, input().split())
    li.append((x, y))
dd = defaultdict(lambda:0)
for i in range(n):
    for j in range(n):
        if i != j:
            dd[(li[i][0]-li[j][0], li[i][1]-li[j][1])] += 1
m = 0
for k in dd:
    m = max(dd[k],m)
print(n-m)

Submission status: Accepted

Solution code:
from collections import defaultdict

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

cnt = defaultdict(int)
for xi, yi in xy:
    for xj, yj in xy:
        cnt[(xi - xj, yi - yj)] += 1
cnt[(0, 0)] = 0
ans = n - max(cnt.values())
print(ans)

Submission status: Accepted

Solution code:
import itertools
def main():
  N = int(input())
  posi = []
  for i in range(N):
    posi.append(list(map(int, input().split())))
  posi.sort()
  num = [i for i in range(N)]
  ans = 1000000000
  for pair in itertools.combinations(num,2):
    p = posi[pair[1]][0]-posi[pair[0]][0]
    q = posi[pair[1]][1]-posi[pair[0]][1]
    ch = [True]*N
    ans_temp = 0
    for i in range(N):
      if ch[i]:
        ans_temp += 1
        ch[i] = False
      now = posi[i]
      while [now[0] +  p, now[1] + q] in posi:
        ch[posi.index([now[0] +  p, now[1] + q])] = False
        now = [now[0] +  p, now[1] + q]
    ans = min(ans, ans_temp)
  if N == 1:
    ans = 1
  print(ans)
    
  
if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
from itertools import permutations
from collections import Counter

N,*xyf = map(int, open(0).read().split())
xy = [(xyf[i*2],xyf[i*2+1]) for i in range(N)]
if N == 1:
    print(1)
else:
    count = []
    for a, b in permutations(xy,2):
        count.append((b[0]-a[0],b[1]-a[1]))
    c = Counter(count)
    print(N-max(c.values()))

Submission status: Accepted

Solution code:
N = int(input())
lis = []
for i in range(N):
    lis.append(tuple(map(int, input().split())))
if N == 1:
    print(1)
    exit()

dic = {}
for i in range(N):
    for j in range(N):
        if i == j:
            continue
        val = (lis[i][0]-lis[j][0], lis[i][1]-lis[j][1])
        if val in dic:
            dic[val] += 1
        else:
            dic[val] = 1
#print(dic)
print(N-max(dic.values()))

Submission status: Accepted

Solution code:
n = int(input())

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


if n == 1:
    print(1)
else:
    diff = {}
    
    for i in range(n):
        for j in range(n):
            if i == j:
                continue
            vec = (balls[i][0]-balls[j][0], balls[i][1]-balls[j][1])
            if vec not in diff:
                diff[vec] = 1
            else:
                diff[vec] += 1
    
    print(n-max(diff.values()))

Submission status: Accepted

Solution code:
import sys
import itertools
from collections import defaultdict

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_nl = lambda: list(map(int, readline().split()))
in_na = lambda: map(int, read().split())
in_s = lambda: readline().rstrip().decode('utf-8')


def main():
    N = in_n()
    xy = [tuple(in_nn()) for _ in range(N)]

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

    comb = itertools.combinations(range(N), 2)
    d = defaultdict(int)

    for i, j in comb:
        x1, y1 = xy[i]
        x2, y2 = xy[j]
        xd = x2 - x1
        yd = y2 - y1
        d[(xd, yd)] += 1
        d[(-xd, -yd)] += 1

    ans = N - max(d.values())
    # print(d)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
#mod = 10 ** 9 + 7 
mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

N = INT()
xy = [LIST() for _ in range(N)]
xy.sort(key = lambda x:(x[0], x[1]))

delta = defaultdict(int)
if N == 1:
	print(1)
else:
	for x, y in combinations(xy, 2):
		delta[(y[0]-x[0], y[1]-x[1])] += 1

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

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


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

def sub(p,q):
    seen = [False]*n
    ans = 0
    for start in range(n):
        if seen[start]:
            continue
        ans += 1
        qq = [start]
        seen[start] = True
        while qq:
            u = qq.pop()
            for i,(x,y) in enumerate(xys):
                if seen[i]:
                    continue
#                 print(xys[u][1], y, p, q)
                if (xys[u][0]-x, xys[u][1]-y) == (p,q) or (xys[u][0]-x, xys[u][1]-y) == (-p,-q):
                    qq.append(i)
                    seen[i] = True
    return ans
ans = 10**10
for i in range(n):
    for j in range(n):
        p = xys[i][0]-xys[j][0]
        q = xys[i][1]-xys[j][1]
        val = sub(p,q)
        ans = min(ans, val)
print(ans)

Submission status: Accepted

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

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

cnt=0
for p,q in pq:
  t_cnt=0
  for x,y in xy:
    if [x+p,y+q] in xy:
      t_cnt+=1
  cnt=max(cnt,t_cnt)

print(n-cnt)

Submission status: Accepted

Solution code:
n = int(input())
xy = [list(map(int, input().split())) for i in range(n)]
cnt = 0
for i in range(n - 1):
    xi, yi = xy[i]
    for j in range(i + 1, n):
        xj, yj = xy[j]
        cost = 0
        for x, y in xy:
            cost += 1 if [x - xj + xi, y - yj + yi] in xy else 0
    cnt = max(cnt, cost)
print(n - cnt)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
#mod = 10 ** 9 + 7 
mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

N = INT()
xy = [LIST() for _ in range(N)]

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

xy.sort(key = lambda x: (x[0], x[1]))
diff = []

for s, t in combinations(xy, 2):
	st = str(t[0]-s[0]) + " " +str(t[1]-s[1])
	diff.append(st)

print(max(N - Counter(diff).most_common()[0][1], 1))

Submission status: Accepted

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

    d = [[(0,0)] * N for _ in range(N)]
    b = set()
    for i in range(N):
        for j in range(N):
            d[i][j] = (X[i][0] - X[j][0], X[i][1] - X[j][1])
            if not (X[i][0] - X[j][0] == 0 and X[i][1] - X[j][1] == 0):
                b.add((X[i][0] - X[j][0], X[i][1] - X[j][1]))
    
    cnt = 0
    for a in b:
        tmp = 0
        for i in range(N):
            tmp += d[i].count(a)

        cnt = max(cnt, tmp)
    
    print(1 + (N - 1 - cnt))
            


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
from typing import Any, Callable, Deque, Dict, List, Mapping, Optional, Sequence, Set, Tuple, TypeVar, Union
# import time
# import math, cmath
# import numpy as np
# import scipy.sparse.csgraph as cs            # csgraph_from_dense(ndarray, null_value=inf), bellman_ford(G, return_predecessors=True), dijkstra, floyd_warshall
# import random                                # random, uniform, randint, randrange, shuffle, sample
# import string                                # ascii_lowercase, ascii_uppercase, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from datetime import date, datetime          # date.today(), date(year,month,day) => date obj; datetime.now(), datetime(year,month,day,hour,second,microsecond) => datetime obj; subtraction => timedelta obj
# from datetime.datetime import strptime       # strptime('2019/01/01 10:05:20', '%Y/%m/%d/ %H:%M:%S') returns datetime obj
# from datetime import timedelta               # td.days, td.seconds, td.microseconds, td.total_seconds(). abs function is also available.
# from copy import copy, deepcopy              # use deepcopy to copy multi-dimentional matrix without reference
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import _heapify_max, _heappop_max, _siftdown_max
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from fractions import Fraction               # Fraction(a, b) => a / b ∈ Q. note: Fraction(0.1) do not returns Fraciton(1, 10). Fraction('0.1') returns Fraction(1, 10)



def main():
    Num = Union[int, float]
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79e+308
    # inf = 2 ** 63 - 1             # (for fast JIT compile in PyPy) 9.22e+18
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def isp():   return input().split()
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    # def _heappush_max(h, item): h.append(item); _siftdown_max(h, 0, len(h)-1)
    

    def calc_cost(p, q, points):
        selected = [False] * n
        cnt = 0
        for i in range(n):
            if not selected[i]:
                selected[i] = True
                cnt += 1
                x, y = points[i]
                while True:
                    if [x + p, y + q] in points:
                        selected[points.index([x + p, y + q])] = True
                        x, y = x + p, y + q
                    else:
                        break
                x, y = points[i]
                while True:
                    if [x - p, y - q] in points:
                        selected[points.index([x - p, y - q])] = True
                        x, y = x - p, y - q
                    else:
                        break
        return cnt
    
    
    n = ii()
    points = [lmi() for _ in range(n)]

    if n == 1:
        print(1)
    else:
        cost = inf
        for i in range(n):
            for j in range(n):
                if i != j:
                    p = points[i][0] - points[j][0]
                    q = points[i][1] - points[j][1]
                    cost = min(cost, calc_cost(p, q, points))
        print(cost)



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    ################
    class UnionFind():
        """
        parents : 親要素(findしない場合は根ではないことの注意)，根の場合は"-(要素数）"
        find(x):要素xの属するグループの根を返す
        size(x):要素xの属するグループの要素数を返す
        same(x,y):x,yが同じグループに属しているか返す
        members(x):要素xが属するグループに属する要素をリストで返す
        roots:全ての根の要素を返す
        group_count():グループの数を返す
        all_group_members():{根要素：[そのグループに含まれる要素のリスト]}の辞書を返す
        """
        def __init__(self, n):
            self.n = n
            self.parents = [-1] * n

        def find(self, x):
            #根を探す&つなぎかえる
            if self.parents[x] < 0:
                return x
            else:
                self.parents[x] = self.find(self.parents[x])
                return self.parents[x]

        def union(self, x, y):
            x = self.find(x)
            y = self.find(y)

            if x == y:
                return

            if self.parents[x] > self.parents[y]:
                x, y = y, x

            self.parents[x] += self.parents[y]
            self.parents[y] = x

        def size(self, x):
            return -self.parents[self.find(x)]

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

        def members(self, x):
            root = self.find(x)
            return [i for i in range(self.n) if self.find(i) == root]

        def roots(self):
            return [i for i, x in enumerate(self.parents) if x < 0]

        def group_count(self):
            return len(self.roots())

        def all_group_members(self):
            return {r: self.members(r) for r in self.roots()}

        def __str__(self):
            return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
    
################


    mod=10**9+7
    N=I()
    X=[0]*N
    Y=[0]*N
    for i in range(N):
        X[i],Y[i]=MI()
    
    ans=N
    
    for ii in range(N):
        for jj in range(N):
            p=X[ii]-X[jj]
            q=Y[ii]-Y[jj]
            uf=UnionFind(N)
    
            for j in range(N):
                for k in range(N):
                    if X[k]-X[j]==p and Y[k]-Y[j]==q:
                        uf.union(j,k)
            temp=uf.group_count()
            ans=min(ans,temp)
    print(ans)
        
        

main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
def main():
    N = int(input())
    if N == 1:print(1);exit();
    x = [None] * N
    y = [None] * N
    for i in range(N):
        x[i], y[i] = map(int, input().split())
    
    diff = []
    nums = []
    for i in range(N):
        for j in range(N):
            if i == j:
                continue
            if (x[j]-x[i],y[j]-y[i]) in diff:
                nums[diff.index((x[j]-x[i],y[j]-y[i]))] += 1
            else:
                diff.append((x[j]-x[i],y[j]-y[i]))
                nums.append(1)
    # print(diff)
    # print(nums)
    print(N-max(nums))

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n = inp()
a = [inpl() for _ in range(n)]
if n == 1:
    print(1)
    quit()
c = []
for i,(x,y) in enumerate(a):
    for j,(z,w) in enumerate(a):
        if i == j: continue
        c.append(((x-z), (y-w)))
h = Counter(c)
print(n-max(h.values()))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))
# 受け渡されたすべての要素からsubだけ引く.リストを*をつけて展開しておくこと


def a_int(): return int(read())


def ints(): return list(map(int, read().split()))


def read_col(H):
    '''H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


def read_tuple(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_matrix(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    # return [list(map(int, read().split())) for _ in range(H)] # 内包表記はpypyでは遅いため


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter, xor, add
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  # , insort_left, insort_right
from functools import reduce
from math import gcd


def lcm(a, b):
    # 最小公倍数
    g = gcd(a, b)
    return a // g * b


# https://atcoder.jp/contests/diverta2019-2/tasks/diverta2019_2_b
N = a_int()
XY = read_tuple(N)
XY.sort()
if N == 1:
    print(1)
    exit()
# q,pは何通りありえる？N**2//2通りぐらい
# p,qを決定したらあとは直線に乗っているか確かめれば良い
# 点に当たるたびにO(N)かけて調べれば良い
# 以下のO(n**4)のプログラムが可能
# for q,p全通り
#     while ある点を選択
#        その点の+p+qを見てボールを消す
#     コストをmin
# と思ったけど、ただ単純にp,qで拾えるボールの個数を数えればいいかも

PQcandi = []
for po1, po2 in combinations(XY, r=2):
    dx = po1[0] - po2[0]
    dy = po1[1] - po2[1]
    if dx < 0:
        dx *= -1
        dy *= -1
    elif dx == 0:
        dy = abs(dy)

    PQcandi.append((dx, dy))


def del_ball(p, q, XYtmp):
    ret = []
    # x軸にソートしてあるので左から拾っていく
    x, y = XYtmp[0]
    for xx, yy in XYtmp[1:]:
        if xx == x + p and yy == y + q:
            x += p
            y += q
        else:
            ret.append((xx, yy))

    return ret


from copy import deepcopy
ans = INF
for p, q in PQcandi:
    XYtmp = deepcopy(XY)
    anstmp = 0
    while XYtmp:
        anstmp += 1
        XYtmp = del_ball(p, q, XYtmp)
    # print(p, q, anstmp)
    ans = min(ans, anstmp)
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))

n=int(input())
xy=[lnii() for i in range(n)]
xy.sort(key=lambda x:x[0])

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

ans=n
for p,q in pq:
  cnt=0
  for x,y in xy:
    if [x+p,y+q] in xy:
      cnt+=1
  '''
  for i in range(n):
    for j in range(n):
      if i==j:
        continue
      x1,y1=xy[i]
      x2,y2=xy[j]
      if (x2-x1)==p and (y2-y1)==q:
        cnt+=1
  '''

  ans=min(ans,n-cnt)
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))
# 受け渡されたすべての要素からsubだけ引く.リストを*をつけて展開しておくこと


def a_int(): return int(read())


def ints(): return list(map(int, read().split()))


def read_col(H):
    '''H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


def read_tuple(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_matrix(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    # return [list(map(int, read().split())) for _ in range(H)] # 内包表記はpypyでは遅いため


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter, xor, add
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  # , insort_left, insort_right
from functools import reduce
from math import gcd


def lcm(a, b):
    # 最小公倍数
    g = gcd(a, b)
    return a // g * b


# https://atcoder.jp/contests/diverta2019-2/tasks/diverta2019_2_b
N = a_int()
XY = read_tuple(N)
if N == 1:
    print(1)
    exit()
# q,pは何通りありえる？N**2//2通りぐらい
# p,qを決定したらあとは直線に乗っているか確かめれば良い
# 点に当たるたびにO(N)かけて調べれば良い
# 以下のO(n**4)のプログラムが可能
# for q,p全通り
#     while ある点を選択
#        その点の+p+qを見てボールを消す
#     コストをmin
# と思ったけど、ただ単純にp,qで拾えるボールの個数を数えればいいかも

PQcandi = []
for po1, po2 in combinations(XY, r=2):
    dx = po1[0] - po2[0]
    dy = po1[1] - po2[1]
    if dx < 0:
        dx *= -1
        dy *= -1
    elif dx == 0:
        dy = abs(dy)

    PQcandi.append((dx, dy))

print(N - max(Counter(PQcandi).values()))


# def del_ball(p, q, XYtmp):
#     ret = []
#     # x軸にソートしてあるので左から拾っていく
#     x, y = XYtmp[0]
#     for xxyy in XYtmp[1:]:
#         if xxyy == (x + p, y + q):
#             x += p
#             y += q
#         else:
#             ret.append(xxyy)

#     return ret


# from copy import deepcopy
# ans = INF
# for p, q in PQcandi:
#     XYtmp = deepcopy(XY)
#     anstmp = 0
#     while XYtmp:
#         anstmp += 1
#         XYtmp = del_ball(p, q, XYtmp)
#     # print(p, q, anstmp)
#     ans = min(ans, anstmp)
# print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations
N = int(input())
X = [list(map(int,input().split())) for _ in range(N)]
if N==1:
    print(1)
else:
    C = {}
    for z in combinations(X,2):
        x1,x2 = z
        a = x1[0]-x2[0]
        b = x1[1]-x2[1]
        if a>=0 and b>=0:
            if (a,b) not in C:
                C[(a,b)] = 0
            C[(a,b)] += 1
        elif a>0 and b<0:
            if (a,b) not in C:
                C[(a,b)] = 0
            C[(a,b)] += 1
        elif a==0 and b<0:
            if (a,-b) not in C:
                C[(a,-b)] = 0
            C[(a,-b)] += 1
        elif a<0 and b>0:
            if (-a,-b) not in C:
                C[(-a,-b)] = 0
            C[(-a,-b)] += 1
        elif a<0 and b==0:
            if (-a,b) not in C:
                C[(-a,b)] = 0
            C[(-a,b)] += 1
        elif a<0 and b<0:
            if (-a,-b) not in C:
                C[(-a,-b)] = 0
            C[(-a,-b)] += 1
    C = sorted(list(C.items()),key=lambda x:x[1],reverse=True)
    k = C[0][1]
    print(N-k)

Submission status: Accepted

Solution code:
from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))

n=int(input())
xy=[lnii() for i in range(n)]
xy.sort(key=lambda x:x[0])

ans=n

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

for p,q in pq:
  cnt=0
#  for x,y in xy:
#    if [x+p,y+q] in xy:
#      cnt+=1
  for i in range(n):
    for j in range(n):
      if i==j:
        continue
      x1,y1=xy[i]
      x2,y2=xy[j]
      if (x2-x1)==p and (y2-y1)==q:
        cnt+=1
  ans=min(ans,n-cnt)
print(ans)

Submission status: Accepted

Solution code:
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def i(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10**9)
INF = 10**9
mod = 10**9+7

N = i()
S = [l() for _ in range(N)]
ans = 0
pq = []
for i in S:
    for j in S:
        if i == j:
            continue
        pq.append((i[0]-j[0],i[1]-j[1]))
for p,q in set(pq):
    cnt = 0
    for i in S:
        for j in S:
            if i == j:
                continue
            if (i[0]-j[0],i[1]-j[1]) == (p,q):
                cnt += 1
    ans = max(ans,cnt)
print(N-ans)

Submission status: Accepted

Solution code:
from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))

n=int(input())
xy=[lnii() for i in range(n)]
xy.sort(key=lambda x:x[0])

ans=n

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

for p,q in pq:
  cnt=0
  for x,y in xy:
    if [x+p,y+q] in xy:
        cnt+=1
  ans=min(ans,n-cnt)

print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))

n=int(input())
xy=[lnii() for i in range(n)]
xy.sort(key=lambda x:x[0])

ans=n

pq=[]
for i in range(n):
  for j in range(n):
    if i==j:
      continue
    t_p=xy[j][0]-xy[i][0]
    t_q=xy[j][1]-xy[i][1]
    pq.append([t_p,t_q])

for p,q in pq:
  cnt=0
  for x,y in xy:
    if [x+p,y+q] in xy:
        cnt+=1
  ans=min(ans,n-cnt)

print(ans)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N = int(input())
XY = []
for _ in range(N):
    x, y = mapint()
    XY.append((x, y))

from collections import defaultdict, Counter
dic = []
for i in range(N):
    x1, y1 = XY[i]
    for j in range(N):
        if i==j:
            continue
        x2, y2 = XY[j]
        dx, dy = x2-x1, y2-y1
        if dx==0 and dy==0:
            continue
        dic.append((dx, dy))
c = Counter(dic)
if len(c)==0:
    print(N)
else:
    (x, y), cnt = c.most_common()[0]
    print(N-cnt)

Submission status: Accepted

Solution code:
import math
import collections
import fractions
import itertools

def solve():
    n = int(input())
    xy = [[int(x) for x in input().split()] for _ in range(n)]
    vec = list()
    for xy1, xy2 in itertools.combinations(xy, 2):
        p = xy2[0] - xy1[0]
        q = xy2[1] - xy1[1]
        vec.append((p, q))
        vec.append((-p, -q))
    c = collections.Counter(vec)
    if n >= 2:
        ans = max(c.values())
        print(n - ans)
    else:
        print(1)
    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
n=int(input())
xy=[]
for i in range(n):
  x,y=map(int,input().split())
  xy.append((x,y))
pq=[]
for i in range(n):
  for j in range(n):
    if i==j:continue
    x1,y1=xy[i]
    x2,y2=xy[j]
    pq.append((x2-x1,y2-y1))
ans=n
for p,q in pq:
  t=0
  for x,y in xy:
    if (x+p,y+q) not in xy:
      t+=1
  ans=min(ans,t)
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
dic = defaultdict(int) #初期化する関数。

N = int(input())
if N == 1:
  print(1)
  exit()
X = []
for i in range(N):
  x,y = map(int,input().split())
  X.append([x,y])

for i in range(N):
  for j in range(i+1,N):
    p = X[i][0] - X[j][0]
    q = X[i][1] - X[j][1]
    if p <0:
      p = -p;q=-q
    if p == 0 and q < 0:
      q=-q
    dic[(p,q)] +=1

path = max(dic.values())
ans = N-path
#print(dic)
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
balls=[]
for i in range(n):
  x,y=map(int,input().split())
  balls.append([x,y])
minans=n
for i in range(0,n-1):
  for j in range(i+1,n):
    p=balls[j][0]-balls[i][0]
    q=balls[j][1]-balls[i][1]
    ballset=set()
    ans=0
    for k in range(n):
      x=balls[k][0]
      y=balls[k][1]
      ballset.add(x*(10**10)+y)
    while ballset:
      current=ballset.pop()
      ballset.add(current)
      y=current%(10**10)
      x=(current-y)//(10**10)
      while (x-p)*(10**10)+(y-q) in ballset:
        x-=p
        y-=q
      while x*(10**10)+y in ballset:
        ballset.remove(x*(10**10)+y)
        x+=p
        y+=q
      ans+=1
    minans=min(minans,ans)
print(minans)

Submission status: Accepted

Solution code:
N=int(input())
X=[list(map(int,input().split())) for i in range(N)]
def solve(p,q):
  global N,X
  r=0
  for i in range(N):
    for j in range(N):
      if X[i][0]+p==X[j][0] and X[i][1]+q==X[j][1]:
        r-=1
  return r

P=0
for i in range(N):
  for j in range(i+1,N):
    P=min(P,solve(X[j][0]-X[i][0],X[j][1]-X[i][1]))
print(N+P)