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())
l = [list(map(int,input().split())) for i in range(n)]
if n == 1:
    print(1)
    exit()
d = defaultdict(int)
for i in range(n):
    for j in range(n):
        if i== j:
            continue
        a,b = l[i]
        c,e = l[j]
        d[(a-c,b-e)] += 1
ans = n
m = max(d.values())
for i,j in d.items():
    if j != m:
        continue

    x,y = i
    if x==0 and y == 0:
        continue
    count = 0
    for c,d in l:
        if [c+x,d+y] in l:
            count += 1
    ans = min(ans,n-count)
print(ans)

Submission status: Accepted

Solution code:
import bisect
import copy
import heapq
import math
import sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(5000000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

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

# dic={}
# for i in range(n):
#     x,y=xy[i]
#     dic[(x,y)]=1
if n==1:
    print(1)
    quit()
cnt=0
sadic=defaultdict(int)
for i in range(n):
    x,y=xy[i]
    for j in range(n):
        if i==j:
            continue
        x2,y2=xy[j]
        p,q=x-x2,y-y2
        sadic[(p,q)]+=1
# print(sadic)
print(n-max(sadic.values()))

Submission status: Accepted

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

from collections import Counter

def main():
    N = int(input())
    S = [tuple(map(int,input().split())) for _ in range(N)]

    if N == 1:
        print(1)
    else:
        cnt = []
        for i in range(N-1):
            xi, yi = S[i]
            for j in range(i+1,N):
                xj, yj = S[j]
                cnt.append((xi-xj, yi-yj))
                cnt.append((xj-xi, yj-yi))
        A = Counter(cnt)
        ll = max(A.values())
        print(N-ll)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
def main():
    N = int(input())
    C = [list(map(int, input().split())) for i in range(N)]
    ans = N
    for a,b in C:
        for x, y in C:
            if a == x and b == y:
                continue
            p, q = a -x , b - y
            CNT = 0
            for u, v in C:
                for s, t in C:
                    if u == s and v == t:
                        continue
                    if u-s == p and v-t == q:
                        CNT += 1
            ans = min(ans, N-CNT)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
x = [0] * n
y = [0] * n

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

table = {}

for i in range(n - 1):
    for j in range(i + 1, n):
        dx = x[i] - x[j]
        dy = y[i] - y[j]
        if (dx, dy) not in table:
            table[(dx, dy)] = 1
            table[(-dx, -dy)] = 1
        else:
            table[(dx, dy)] += 1
            table[(-dx, -dy)] += 1

m = 0

for key, value in table.items():
    m = max(m, value)

print(n - m)

Submission status: Accepted

Solution code:
N, *XY = map(int, open(0).read().split())
X = XY[::2]
Y = XY[1::2]
ans = N
for i in range(N):
    for j in range(N):
        if i == j:
            continue
        p = X[i] - X[j]
        q = Y[i] - Y[j]
        cnt = 0
        for k in range(N):
            for l in range(N):
                if k == l:
                    continue
                if X[k] - X[l] == p and Y[k] - Y[l] == q:
                    cnt += 1
        ans = min(ans, N - cnt)
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AtoZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)


#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1:
    arr.append([temp, 1])
  if arr==[]:
    arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  divisors.sort()
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n:
    return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############
N = I()
data = ILL(N)

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

kouho = []
for i in range(N):
  for j in range(i+1,N):
    a,b = data[i]
    c,d = data[j]
    kouho.append((c-a,d-b))
MIN = INF
for x,y in kouho:
  ans = N
  for i in range(N):
    for j in range(i+1,N):
      a,b = data[i]
      c,d = data[j]
      if (a+x == c and b+y == d) or (c+x == a and d+y == b):
        ans -= 1
  MIN = min(MIN,ans)
print(MIN)

Submission status: Accepted

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

ans = 0

for i in range(N-1):
  x1,y1 = xy[i]
  for j in range(i+1,N):
    x2,y2 = xy[j]
    p = x2-x1
    q = y2-y1
    cost = 0
    for x,y in xy:
      if [x-p,y-q] in xy:
        cost += 1
    ans = max(ans,cost)
    
print(N-ans)

Submission status: Accepted

Solution code:
n = int(input())
s = [list(map(int, input().split())) for _ in range(n)]
t = []
for i in range(n):
    for j in range(n):
        if not i == j:
            t.append([s[i][0] - s[j][0], s[i][1] - s[j][1]])
ans = n
for i in range(pow(n, 2) - n):
    cnt = 0
    for j in range(pow(n, 2) - n):
        if t[i][0] == t[j][0] and t[i][1] == t[j][1]:
            cnt += 1
    ans = min(ans, n - cnt)
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
n=int(input())
if n==1:
  print(1)
  exit()
xy=[tuple(map(int,input().split())) for _ in range(n)]

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

#most_common(): (要素、出現回数)という形のタプルを出現回数順に並べたリストを返す
print(n-Counter(l).most_common()[0][1])

Submission status: Accepted

Solution code:
from collections import defaultdict

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

if n == 1:
    print(1)
    exit()
for i in range(n):
    for j in range(n):
        if i != j:
            data[x[j] - x[i], y[j] - y[i]] += 1

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

Submission status: Accepted

Solution code:
import sys
N = int(sys.stdin.readline().rstrip())

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

zahyo = []
for _ in range(N):
    x, y = map(int, sys.stdin.readline().rstrip().split())
    zahyo.append((x, y))
zahyo.sort()

p_q = set()
for i in range(N - 1):
    for j in range(i + 1, N):
        p = zahyo[j][0] - zahyo[i][0]
        q = zahyo[j][1] - zahyo[i][1]
        p_q.add((p, q))

ans = float("inf")
for p, q in p_q:
    used = set()
    ans_tmp = 0
    for i in range(N):
        if i not in used:
            x_base = zahyo[i][0]
            y_base = zahyo[i][1]
            ans_tmp += 1
            for j, (x, y) in enumerate(zahyo[i + 1:], 1):
                if x - x_base == p and y - y_base == q:
                    used.add(i + j)
                    x_base = x
                    y_base = y
    ans = min(ans_tmp, ans)
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
inf = float('inf')
ninf = -float('inf')
'''
#Pythonを用いる場合
#numpy 1.18.0, scipy 1.4.1, scikit-learn 0.22, numba 0.47.0, networkx 2.4
 
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix
'''
 
#整数input
def ii(): return int(sys.stdin.readline().rstrip()) #int(input())
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) #list(map(int,input().split()))
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]
#文字列input
def ss(): return sys.stdin.readline().rstrip() #input()
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss()) #list(input().split())
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？

n=ii()

arr=[list(mii()) for _ in range(n)]

chk={}

for i in arr:
    for j in arr:
        if i!=j:
            p=i[0]-j[0]
            q=i[1]-j[1]

            if str(p)+","+str(q) in chk:
                chk[str(p)+","+str(q)]+=1
            else:
                chk[str(p)+","+str(q)]=1

places="w"
num=0

for i,j in chk.items():
    if j>num:
        num=j
        places=i

print(n-num)

Submission status: Accepted

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

dic = {}
tmp = 0

for i in range(N):
  for j in range(N):
    if i == j:
      continue
    p = XYs[j][0] - XYs[i][0]
    q = XYs[j][1] - XYs[i][1]

    if "{}_{}".format(p,q) not in dic:
      dic["{}_{}".format(p,q)] = 1
    else:
      dic["{}_{}".format(p,q)] += 1
      
for k in dic:
  if tmp < dic[k]:
    tmp = dic[k]

print(N-tmp)

Submission status: Accepted

Solution code:
import fractions
n = int(input())
z = [list(map(int,input().split())) for _ in range(n)]
if n == 1:
	print(1)
else:
	a = []
	ans = 10**18
	for i in range(n):
		for j in range(i+1, n):
			a.append((z[i][0]-z[j][0], z[i][1]-z[j][1]))
	for i, j in a:
		tmpans = n
		for k, l in z:
			if [k-i, l-j] in z:
				tmpans -= 1
		ans = min(ans, tmpans)
	print(ans)

Submission status: Accepted

Solution code:
n = int(input())
ans = n
L = [list(map(int, input().split())) for _ in range(n)]
pq = []
for i in range(n):
    for j in range(i+1, n):
        pq.append([L[j][0] - L[i][0], L[j][1] - L[i][1]])
for p, q in pq:
    cost = n
    for x, y in L:
        if [x-p, y-q] in L:
            cost -=1
    ans = min(ans, cost)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
if n == 1:
    print(1)
else:
    buf = []
    for i in range(n):
        x,y = map(int,input().split())
        buf.append([x,y])
    
    buf.sort()
    
    ans = 1e9
    for i in range(n):
        for j in range(i+1,n):
            p,q = buf[j][0]-buf[i][0],buf[j][1]-buf[i][1]
    
            ind = 0
            used = set()
            tcost = 0
            befx = 0
            befy = 0
            flag = False
            while True:
                befx,befy = buf[ind][0],buf[ind][1]
                tcost += 1
                for l in range(n):
                    if l not in used:
                        tx,ty = buf[l][0],buf[l][1]
                        if tx-befx == p and ty-befy == q:
                            befx = tx
                            befy = ty
                            used.add(l)
                while True:
                    ind += 1
                    if ind == n:
                        flag = True
                        break
                    if ind in used:
                        continue
                    else:
                        break
                if flag:
                    break
            if ans > tcost:
                # print(used)
                # print(p,q,tcost)
                ans = tcost
    
    print(ans)

Submission status: Accepted

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

v={}
for i in range(N):
    for j in range(N):
        if i==j:
            continue
        vect=[x[i][0]-x[j][0],x[i][1]-x[j][1]]
        vs=str(vect[0])+","+str(vect[1])
        if vs in v:
            v[vs]+=1
        else:
            v[vs]=1

VM=0
for m in v:
    VM=max(VM,v[m])
print(N-VM)

Submission status: Accepted

Solution code:
from collections import defaultdict
import numpy as np
import sys

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

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

memo = defaultdict(int)

for i in xy:
    for j in xy:
        if np.all(i == j):
            continue
        else:
            tmp = j - i
            if tmp[0] < 0:
                tmp *= -1
            elif tmp[0] == 0 and tmp[1] < 0:
                tmp *= -1
            memo[str(tmp)] += 1

print(n - max(memo.values()) // 2)

Submission status: Accepted

Solution code:
from collections import Counter
n=int(input())
if n==1:
  print(1)
  exit()
xy=[tuple(map(int,input().split())) for _ in range(n)]
xy.sort()
l=[]
for i in range(n-1):
  for j in range(i+1,n):
    l.append((xy[j][0]-xy[i][0],xy[j][1]-xy[i][1]))
print(n-Counter(l).most_common()[0][1])

Submission status: Accepted

Solution code:
N = int(input())

points = [list(map(int, input().split())) for _ in range(N)]
vec_dic = {}

max_same = 0
for i in range(N):
    x1,y1 = points[i]
    for j in range(N):
        if i == j:
            continue
        x2,y2 = points[j]
        d_x = x2 - x1
        d_y = y2 - y1
        if d_x in vec_dic.keys():
            if d_y in vec_dic[d_x].keys():
                vec_dic[d_x][d_y] += 1
                max_same = max(max_same, vec_dic[d_x][d_y])
            else:
                vec_dic[d_x][d_y] = 1
                max_same = max(max_same,1)
        else:
            vec_dic[d_x] = {d_y: 1}
            max_same = max(max_same, 1)
print(N-max_same)

Submission status: Accepted

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

ans = 1000
for i in range(n):
    for j in range(n):
        if i == j:
            continue
        temp = 0
        x0, y0 = ball[i]
        x1, y1 = ball[j]
        p, q = x1-x0, y1-y0
        used = [False]*(n)
        for k in range(n):
            if not used[k]:
                temp += 1
                x0, y0 = ball[k]
                used[k] = True

                x, y = x0, y0
                while True:
                    f = 0
                    for l in range(n):
                        if used[l]:
                            continue
                        if x + p == ball[l][0] and y + q == ball[l][1]:
                            used[l] = True
                            x += p
                            y += q
                            f = 1
                    if f == 0:
                        break

                x, y = x0, y0
                while True:
                    f = 0
                    for l in range(n):
                        if used[l]:
                            continue
                        if x - p == ball[l][0] and y - q == ball[l][1]:
                            used[l] = True
                            x -= p
                            y -= q
                            f = 1
                    if f == 0:
                        break

        ans = min(ans, temp)

if n == 1:
    print(1)
else:
    print(ans)

Submission status: Accepted

Solution code:
n = int(input())
grid = []
if n == 1:
    print(1)
    exit()
for _ in range(n):
    x,y = map(int,input().split())
    grid.append((x,y))
S = set(grid)
ans = float("inf")
for i in range(n-1):
    for j in range(i+1,n):
        cnt = 0
        p = grid[i][0]-grid[j][0]
        q = grid[i][1]-grid[j][1]
        for k in range(n):
            if (grid[k][0]-p,grid[k][1]-q) in S:
                cnt += 1
        else:
            ans = min(n-cnt,ans)
print(ans)

Submission status: Accepted

Solution code:
import sys,os
from collections import defaultdict, deque
from math import ceil, floor
if sys.version_info[1] >= 5:
    from math import gcd
else:
    from fractions import gcd
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in os.environ else lambda *x: 0
def main(given=sys.stdin.readline):
    input = lambda: given().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    MOD = 10**9+7

    
    N = II()
    coordinates = []
    diffs = defaultdict(int)
    for i in range(N):
        coordinates.append(LMIIS())
    coordinates.sort()
    for i in range(N):
        x1,y1 = coordinates[i]
        for j in range(i+1,N):
            x2,y2 = coordinates[j]
            diffs[(x1-x2,y1-y2)] += 1
    
    max_diff = ()
    max_count = 0

    for k,v in diffs.items():
        if max_count < v:
            max_count = v
            max_diff = k
    print(N-max_count)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import collections

N = int(input())

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

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

x_y.sort(key=lambda x: (x[0], x[1]))
pq_cand = []
for i in range(N):
    for j in range(i + 1, N):
        pq_cand.append((x_y[j][0] - x_y[i][0], x_y[j][1] - x_y[i][1]))

pqc = collections.Counter(pq_cand)
_, x = max(pqc.items(), key=lambda x: x[1])
print(N - 1 - x + 1)

Submission status: Accepted

Solution code:
import sys
import collections

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(tin())
mod=1000000007

#+++++

def main():
	n = int(input())
	dd=[]
	for _ in range(n):
		b , c = tin()
		dd.append([b,c])
	#s = input()
	dist_dict=collections.defaultdict(lambda :0)
	for i,(xa, ya) in enumerate(dd):
		for xb, yb in dd:#[i+1:]:
			if xa==xb and ya == yb:
				continue
			dist_dict[str(xa-xb)+'_'+str(ya-yb)]+=1
			dist_dict[str(xb-xa)+'_'+str(yb-ya)]+=1
	rr=0
	for k in dist_dict:
		rr=max(rr,dist_dict[k])
		#print(k,dist_dict[k])
	return n-int(rr//2)
		
	
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Accepted

Solution code:
from itertools import combinations
from collections import Counter


def main():
    n = int(input())
    if n == 1:
        print(1)
        exit()

    XY = [list(map(int, input().split())) for _ in range(n)]
    d = []
    for A, B in combinations(XY, 2):
        x1, y1 = A[0], A[1]
        x2, y2 = B[0], B[1]
        p, q = x2 - x1, y2 - y1
        d.append((p, q))
        d.append((-p, -q))
    # print(d)
    # print(Counter(d))

    C = Counter(d)
    ans = 0
    for v in C.values():
        ans = max(ans, v)
    print(n - ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

maxi=0
for i in range(N-1):
  for j in range(i+1,N):
    if (x[j]-x[i],y[j]-y[i]) not in d:
      d[ (x[j]-x[i],y[j]-y[i]) ] =1
      d[ (x[i]-x[j],y[i]-y[j]) ] =1
    else:
      d[ (x[j]-x[i],y[j]-y[i]) ] +=1
      d[ (x[i]-x[j],y[i]-y[j]) ] +=1
#print(d)      

for p in d:
  maxi=max(maxi,d[p])
ans= (N-1-maxi)+1
print(ans)

Submission status: Accepted

Solution code:
def solve():
    N = int(input())
    x = []
    y = [] 

    if N == 1:
        print("1")
        return

    ans = float('inf')
    for i in range(N):
        input_x, input_y = map(int,input().split())
        x.append(input_x)
        y.append(input_y)

    for i in range(N):
        for j in range(N):
            if i == j:
                continue
            p = x[i] - x[j]
            q = y[i] - y[j]

            sub = 0
            for i2 in range(N):
                for j2 in range(N):
                    if i2 == j2:
                        continue

                    if x[i2] - x[j2] == p and y[i2] - y[j2] == q:
                        sub += 1
            ans = min(ans, N-sub)
    
    print(ans)

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

if n == 1:
    print(1)
    exit()
    
D = {}
for i in range(n):
    for j in range(n):
        if i == j:
            continue
        a = XY[i][0]
        b = XY[i][1]
        c = XY[j][0]
        d = XY[j][1]
        p = c-a
        q = d-b
        if (p, q) in D:
            D[(p, q)] += 1
        else:
            D[(p,q)] = 1

D = list(D.items())
D.sort(key = lambda x: -x[1])
print(n-D[0][1])

Submission status: Accepted

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

if N!=1:
    pqs = []
    for i in range(N):
        for j in range(i+1,N):
            X1 = XY[i][0]
            Y1 = XY[i][1]
            X2 = XY[j][0]
            Y2 = XY[j][1]
            pqs.append(str(X1-X2)+","+str(Y1-Y2))
            pqs.append(str(X2-X1)+","+str(Y2-Y1))

    from collections import Counter
    C = dict(Counter(pqs))
    out = N - max(C.values())
    print(out)
else:
    print(1)

Submission status: Accepted

Solution code:
# input()
# int(input())
# map(int, input().split())
# list(map(int, input().split()))
# list(map(int, list(input()))) # スペースがない数字リストを読み込み
import math
import sys
import bisect
import heapq  # 優先度付きキュー(最小値取り出し)
from collections import deque
inf = 10**18
mod = 10**9+7

n = int(input())
xy = [list(map(int, input().split())) for i in range(n)]
xsub = 0
dicx = {}
xy.sort(reverse=True)
for i in range(n-1):
    for j in range(i+1,n):
        prex,prey = xy[i]
        x, y = xy[j]
        tmpx = x - prex
        tmpy = y - prey
        if (tmpx, tmpy) in dicx:
            dicx[(tmpx, tmpy)] += 1
        else:
            dicx[(tmpx, tmpy)] = 1
for _,num in dicx.items():
    xsub = max(num, xsub)
print(n-xsub)

Submission status: Accepted

Solution code:
n=int(input())
l=[]
if n==1:
    print(1)
    exit()
else:
    for i in range(n):
        x,y=map(int,input().split())
        l.append((x,y))
    x={}
    for i in l:
        for j in l:
            if i!=j:
                t=(i[0]-j[0],i[1]-j[1])
                if t in x:
                    x[t]+=1
                else:
                    x[t]=1
    print(n-max(x.values()))

Submission status: Accepted

Solution code:
from collections import defaultdict as dd
from itertools import combinations
from sys import exit
n = int(input())
if n == 1:
    print(1)
    exit()

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

Vector = dd(lambda: 0)
for point1, point2 in combinations(Points, 2):
    if point1[0] > point2[0]:
        x_v = point1[0] - point2[0]
        y_v = point1[1] - point2[1]
    elif point1[0] == point2[0] and point1[1] >= point2[1]:
        x_v = point1[0] - point2[0]
        y_v = point1[1] - point2[1]
    else:
        x_v = point2[0] - point1[0]
        y_v = point2[1] - point1[1]
    Vector[(x_v, y_v)] += 1
#print(Vector)

print(max(n - max(Vector.values()), 1))

Submission status: Accepted

Solution code:
n=int(input())

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

stdin = sys.stdin
inf = 1 << 60
mod = 1000000007

sys.setrecursionlimit(10**7)

ni = lambda: int(ns())
nin = lambda y: [ni() for _ in range(y)]
na = lambda: list(map(int, stdin.readline().split()))
nan = lambda y: [na() for _ in range(y)]
nf = lambda: float(ns())
nfn = lambda y: [nf() for _ in range(y)]
nfa = lambda: list(map(float, stdin.readline().split()))
nfan = lambda y: [nfa() for _ in range(y)]
ns = lambda: stdin.readline().rstrip()
nsn = lambda y: [ns() for _ in range(y)]
ncl = lambda y: [list(ns()) for _ in range(y)]
nas = lambda: stdin.readline().split()

from collections import defaultdict

n = ni()
xy = nan(n)

dic = defaultdict(int)
for i in range(n):
    cx, cy = xy[i]
    cx += 10 ** 9
    cy += 10 ** 9
    for j in range(n):
        if i == j:
            continue
        nx, ny = xy[j]
        nx += 10 ** 9
        ny += 10 ** 9
        dic[(nx - cx, ny - cy)] += 1

m = 0
for k, v in dic.items():
    m = max(v, m)

ans = n - m
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import Counter
from math import ceil
def input():
    return sys.stdin.readline()[:-1]
def gcd(a,b):
    if b == 0:
        return a
    return gcd(b,a%b)
def main():
    N = int(input())
    P = []
    for _ in range(N):
        P.append(list(map(int,input().split())))
    P = sorted(P)
    K = []
    if N == 1:
        print(1)
        exit(0)
    for k in range(N-1):
        for l in range(k+1,N):
            a, b, c, d = P[k][0], P[k][1], P[l][0], P[l][1]
            e = c-a
            f = d-b
            K.append((e,f))
    C = Counter(K).most_common()
    S = set([])
    temp = 0
    for k in range(N-1):
        for l in range(k+1,N):
            a, b, c, d = P[k][0], P[k][1], P[l][0], P[l][1]
            e = c-a
            f = d-b
            if e == C[0][0][0] and f == C[0][0][1]:
                if k not in S or l not in S:
                    S.add(k)
                    S.add(l)
                    temp += 1
    print(N-temp)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.buffer.readline
    N = int(input())
    XY = [[int(i) for i in input().split()] for j in range(N)]
    XY.sort()
    from collections import Counter
    c = Counter()
    for i in range(N-1):
        for j in range(i+1, N):
            p = XY[j][0] - XY[i][0]
            q = XY[j][1] - XY[i][1]
            c[(p, q)] += 1
    ans = N - (c.most_common()[0][1] if c else 0)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
N=int(input())
point=[list(map(int,input().split())) for _ in range(N)]
ans=float("inf")
for i in range(N):
    for j in range(i+1,N):
        x1,y1=point[i]
        x2,y2=point[j]
        vec=[x1-x2,y1-y2]
        tree=[[] for _ in range(N)]
        col=[-1]*N
        for k in range(N):
            for l in range(k+1,N):
                xa, ya = point[k]
                xb, yb = point[l]
                if ((vec[0]==xa-xb)and(vec[1]==ya-yb))or((-vec[0]==xa-xb)and(-vec[1]==ya-yb)):
                    tree[k-1].append(l-1)
                    tree[l-1].append(k-1)
        for k in range(N):
            d=deque()
            if col[k]==-1:
                d.append(k)
            while len(d)>0:
                v=d.popleft()
                col[v]=k
                for l in tree[v]:
                    if col[l]==-1:
                        d.append(l)
        #print(col)
        #print(set(col))
        ans=min(ans,len(set(col)))
if N==1:
    print(1)
else:
    print(ans)