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
from sys import stdin

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

    if N == 1:
        print(1)
        return

    XY.sort()
    cnt = defaultdict(int)
    for i in range(N):
        x1, y1 = XY[i]
        for j in range(i + 1, N):
            x2, y2 = XY[j]
            p = x2 - x1
            q = y2 - y1
            cnt[(p, q)] += 1
    print(N - max(cnt.values()))

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

Submission status: Accepted

Solution code:
N = int(input())

xy = []
xyvec = {}

for i in range(N):
  x, y = map(int, input().split())
  for _x, _y in xy:
    if (x - _x, y - _y) in xyvec:
      xyvec[(x - _x, y - _y)].append(((_x, _y), (x, y)))
      xyvec[(_x - x, _y - y)].append(((x, y), (_x, _y)))
    else :
      xyvec[(x - _x, y - _y)] = [((_x, _y), (x, y))]
      xyvec[(_x - x, _y - y)] = [((x, y), (_x, _y))]

  xy.append((x, y))

result = N
for key in xyvec:
  temp_result = N - len(xyvec[key])
  if result > temp_result :
    result = temp_result

print(result)

Submission status: Accepted

Solution code:
from collections import Counter
n = int(input())
a = sorted(tuple(map(int, input().split())) for _ in range(n))
c = Counter((y[0] - x[0], y[1] - x[1]) for i, x in enumerate(a) for y in a[:i])
print(n - max(c.values(), default=0))

Submission status: Accepted

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


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

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

PQ=set()

for i in range(N-1):
    x1,y1=B[i]
    for j in range(i+1,N):
        x2,y2=B[j]

        u,v=x2-x1,y2-y1

        PQ.add((u,v))

def find(x):#find(a)=find(b)のとき同じグループ
    while Group[x] != x:
        x=Group[x]
    return x

def Union(x,y):  # xとyが同じグループになるよう更新
    if find(x) != find(y):
        Group[find(y)]=Group[find(x)]=min(find(y),find(x))
ANS=50

for p,q in PQ:

    Group=[i for i in range(N)]#グループ分け.Group[i]=jのときiとjは同じグループ

    for i in range(N-1):
        for j in range(i+1,N):
            if B[i][0]+p==B[j][0] and B[i][1]+q==B[j][1]:
                Union(i,j)
            if B[i][0]-p==B[j][0] and B[i][1]-q==B[j][1]:
                Union(i,j)

    G2=[find(i) for i in range(N)]
    ANS=min(ANS,len(set(G2)))

print(ANS)

Submission status: Accepted

Solution code:
n = int(input())

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

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

balls.sort()  
sorted(balls, key=lambda x: x[1])

hyo={}

for i in range(n):
  for j in range(i+1,n):
    difx=balls[j][0]-balls[i][0]
    dify=balls[j][1]-balls[i][1]
    if (difx,dify) in hyo.keys():
      hyo[(difx,dify)] +=1
    else:
      hyo[(difx,dify)] =1

#print(hyo)
p,q=max(hyo,key=hyo.get)

chk=[1]*n

for i in range(n-1,-1,-1):
  x=balls[i][0]-p
  y=balls[i][1]-q
  if [x,y] in balls:
    chk[i]=0
#print(balls)
#print(chk)
print(sum(chk))

Submission status: Accepted

Solution code:
from itertools import combinations
n=int(input())
if n == 1:
    print(1)
else:
    xs = []
    for _ in range(n):
        x,y=map(int,input().split())
        xs.append((x,y))
    
    def func(c):
        p,q=(xs[c[0]][0]-xs[c[1]][0],xs[c[0]][1]-xs[c[1]][1])
        ys=[(x,y) for x,y in xs if (x-p,y-q) not in xs]
        return len(ys)
    
    c = combinations(range(n),2)
    print(min(map(func, c)))

Submission status: Accepted

Solution code:
###############################################################################

from sys import stdout
from bisect import bisect_left as binl
from copy import copy, deepcopy
from collections import defaultdict
import math


mod = 1


def intin():
    input_tuple = input().split()
    if len(input_tuple) <= 1:
        return int(input_tuple[0])
    return tuple(map(int, input_tuple))


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


def intinl(count):
    return [intin() for _ in range(count)]


def modadd(x, y):
    global mod
    return (x + y) % mod


def modmlt(x, y):
    global mod
    return (x * y) % mod


def mod_inv(x):
    # available only when mod is prime
    global mod
    return pow(x, mod - 2, mod)


def gcm(x, y):
    while y != 0:
        z = x % y
        x = y
        y = z
    return x


def combination(x, y):
    assert(x >= y)

    ret = math.factorial(x)
    ret = ret // (math.factorial(x - y) * math.factorial(y))

    return ret


def get_divisors(x):
    retlist = []
    for i in range(1, int(x**0.5) + 3):
        if x % i == 0:
            retlist.append(i)
            retlist.append(x // i)
    return retlist


def get_factors(x):
    retlist = []
    for i in range(2, int(x**0.5) + 3):
        while x % i == 0:
            retlist.append(i)
            x = x // i
    retlist.append(x)
    return retlist


def make_linklist(xylist):
    linklist = {}
    for a, b in xylist:
        linklist.setdefault(a, [])
        linklist.setdefault(b, [])
        linklist[a].append(b)
        linklist[b].append(a)
    return linklist


def calc_longest_distance(linklist, v=1):
    distance_list = {}
    distance_count = 0
    distance = 0
    vlist_previous = []
    vlist = [v]
    nodecount = len(linklist)

    while distance_count < nodecount:
        vlist_next = []
        for v in vlist:
            distance_list[v] = distance
            distance_count += 1
            vlist_next.extend(linklist[v])
        distance += 1
        vlist_to_del = vlist_previous
        vlist_previous = vlist
        vlist = list(set(vlist_next) - set(vlist_to_del))

    max_distance = -1
    max_v = None
    for v, distance in distance_list.items():
        if distance > max_distance:
            max_distance = distance
            max_v = v

    return (max_distance, max_v)


def calc_tree_diameter(linklist, v=1):
    _, u = calc_longest_distance(linklist, v)
    distance, _ = calc_longest_distance(linklist, u)
    return distance


class UnionFind:

    def __init__(self, n):
        self.parent = [i for i in range(n)]

    def root(self, i):
        if self.parent[i] == i:
            return i
        self.parent[i] = self.root(self.parent[i])
        return self.parent[i]

    def unite(self, i, j):
        rooti = self.root(i)
        rootj = self.root(j)
        if rooti == rootj:
            return
        if rooti < rootj:
            self.parent[rootj] = rooti
        else:
            self.parent[rooti] = rootj

    def same(self, i, j):
        return self.root(i) == self.root(j)


###############################################################################


def main():
    n = intin()
    xylist = intinl(n)

    pqtoij = defaultdict(list)

    for i in range(n):
        for j in range(i + 1, n):
            x1, y1 = xylist[i]
            x2, y2 = xylist[j]

            if x1 - x2 > 0:
                p = x1 - x2
                q = y1 - y2
            if x1 - x2 < 0:
                p = -(x1 - x2)
                q = -(y1 - y2)
            if x1 - x2 == 0:
                if y1 - y2 > 0:
                    p = x1 - x2
                    q = y1 - y2
                if y1 - y2 < 0:
                    p = -(x1 - x2)
                    q = -(y1 - y2)

            pqtoij[(p, q)].append((i, j))

    maxcount = 0

    for (p, q), ijlist in pqtoij.items():
        checked = []
        count = 0
        for i, j in ijlist:
            if (i, j) in checked:
                continue
            count += 1
            checked.append((i, j))
        maxcount = max(maxcount, count)

    print(n - maxcount)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
cnt = dict()
xy = [tuple(map(int, input().split())) for _ in range(n)]
if n == 1:
    print(1)
    exit()
for x1, y1 in xy:
    for x2, y2 in xy:
        if x1 == x2 and y1 == y2:
            continue
        dx = x1 - x2
        dy = y1 - y2
        if (dx, dy) not in cnt:
            cnt[(dx, dy)] = 1
        else:
            cnt[(dx,dy)] += 1
print(n - max(cnt.values()))

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
import itertools
from collections import Counter

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

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

for first, second in list(itertools.permutations(point, 2)):
    fx, fy = first
    sx, sy = second
    ans[(sx-fx, sy-fy)] += 1

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

Submission status: Accepted

Solution code:
from sys import setrecursionlimit
setrecursionlimit(10 ** 8)

n = int(input())
X, Y = zip(*[[int(i) for i in input().split()] for j in range(n)])

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

used = [False] * n
D = {(X[i], Y[i]): i for i in range(n)}

def dfs(i, p, q):
    if used[i]:
        return
    used[i] = True
    if (X[i] + p, Y[i] + q) in D:
        dfs(D[X[i] + p, Y[i] + q], p, q)
    if (X[i] - p, Y[i] - q) in D:
        dfs(D[X[i] - p, Y[i] - q], p, q)

ans = int(1e12)

for i in range(n):
    for j in range(i + 1, n):
        p = X[i] - X[j]
        q = Y[i] - Y[j]
        used = [False] * n
        cnt = 0
        for k in range(n):
            if used[k]:
                continue
            cnt += 1
            dfs(k, p, q)

        ans = min(ans, cnt)

print(ans)

Submission status: Accepted

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

import copy

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

result = float('inf')


for i in range(N):
    if N == 1:
        result = 1
        break
    for j in range(N-i-1):
        p = List[i+j+1][0] - List[i][0]
        q = List[i+j+1][1] - List[i][1]
        tmp_list = copy.deepcopy(List)
        cost = 0
        
        for k in range(N):
            if [tmp_list[0][0] + p, tmp_list[0][1] + q] in List:
                tmp_cost = 0
            else:
                tmp_cost = 1
            cost += tmp_cost
            del tmp_list[0]
        if result > cost:
            result = cost
                    
print(result)

Submission status: Accepted

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import numpy as np

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

N = int(input())
xy = [[] for i in range(N)]
for i in range(N):
    xy[i] = [int(i) for i in input().split()]

xy = np.array(xy)

count_dic = {}
for i in range(N):
    for j in range(i+1,N):
        diff = xy[i] - xy[j]
        p,q = diff
        if p == 0 and q == 0:
            pass
        else:
            p = int(p)
            q = int(q)
            pq = str(p)+str(q)
            pq2 = str(-p)+str(-q)
            if pq in count_dic:
                count_dic[pq] += 1
            else:
                count_dic[pq] = 1
            if pq2 in count_dic:
                count_dic[pq2] += 1
            else:
                count_dic[pq2] = 1
# print(count_dic)
ans = 1
for k,v in sorted(count_dic.items(), key = lambda x:-x[1]):
    ans = N - v
    break
print(max(1,ans))

Submission status: Accepted

Solution code:
N = int(input())

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

    vec = []
    for i in range(N):
        for j in range(i+1,N,1):
            vec.append([point[i][0]-point[j][0],point[i][1]-point[j][1]])

    N2 = len(vec)
    check = [0 for i in range(N2)]

    for i in range(N2):
        for j in range(N2):
            minus = [-vec[j][0],-vec[j][1]]
            if vec[i] == vec[j] or vec[i] == minus:
                check[i] += 1

    print(N-max(check))

Submission status: Accepted

Solution code:
from collections import Counter
n = int(input())
a = [list(map(int,input().split())) for _ in range(n)]

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

b = sorted(a)
sb = []
for i in range(n-1):
    for j in range(i+1, n):
        sb.append((b[i][0] - b[j][0], b[i][1] - b[j][1]))
        
c = Counter(sb)
print(n-c.most_common()[0][1])

Submission status: Accepted

Solution code:
import numpy as np

n = int(input())

cnt_max = 0

if n in [1, 2]:
    output = 1
else:

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

    xy = np.array(xy)
    temp2 = []
    for i in range(n):
        temp1 = list(zip(xy[:, 0] - xy[i, 0], xy[:, 1] - xy[i, 1]))
        temp1.pop(i)
        temp2.append(temp1)
    cnt = 0
    for i in range(n):
        for j in range(n - 1):
            cnt = 0
            for k in range(n):
                # print(i, j, k)
                if temp2[i][j] in temp2[k]:
                    cnt += 1
        if cnt_max < cnt:
            cnt_max = cnt

    output = n - cnt_max

print(output)

Submission status: Accepted

Solution code:
from itertools import combinations


def main():
    N = int(input())
    x = []
    y = []
    for _ in range(N):
        x_n, y_n = map(int, input().split())
        x.append(x_n)
        y.append(y_n)
    if N == 1:
        print(1)
        return
    comb = list(combinations([i for i in range(N)], 2))
    dic = {}
    for c in comb:
        i, j = c[0], c[1]
        dx = x[j] - x[i]
        dy = y[j] - y[i]
        if not (dx, dy) in dic.keys():
            dic[(dx, dy)] = 0
        if not (-dx, -dy) in dic.keys():
            dic[(-dx, -dy)] = 0
        dic[(dx, dy)] += 1
        dic[(-dx, -dy)] += 1
    dic_sorted = sorted(dic.items(), key=lambda x:x[1])[::-1]
    print(N - dic_sorted[0][1])
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
B = []
for I in range(N):
    x,y = map(int,input().split())
    B.append([x,y])
B.sort()
minmin = N
for i in range(1,N):
    for j in range(N-i):
        d = [B[j+i][0]-B[j][0],B[j+i][1]-B[j][1]]
        A = [a for a in B]
        L = 1
        st = A.pop(0)
        while len(A)>0:
            next = [st[0]+d[0],st[1]+d[1]]
            if next in A:
                st = next
                A.remove(next)
            else:
                L += 1
                st = A.pop(0)
        if L < minmin:
            minmin = L
print(minmin)

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())


def count_cost(xy: list, p: int, q: int):
    n = len(xy)
    cnt = n

    for xi, yi in xy:
        if [xi+p, yi+q] in xy:
            cnt -= 1

    return cnt


n = ni()
xy = [list(li()) for _ in range(n)]

ans = n
for i in range(n):
    for j in range(i+1, n):
        xi, yi = xy[i]
        xj, yj = xy[j]

        p, q = xj - xi, yj - yi

        ans = min(ans, count_cost(xy, p, q))

print(ans)

Submission status: Accepted

Solution code:
import itertools
from collections import Counter
import sys
N=int(input())
balls=[]

for i in range(N):
    x,y=[int(j) for j in input().split(" ")]
    balls.append((x,y))

pqs=[]
if N==1:
    print(1)
    sys.exit()
for i in itertools.permutations(balls,2):
    p=i[1][0]-i[0][0]
    q=i[1][1]-i[0][1]
    pqs.append((p,q))

c=Counter(pqs)
c=dict(c)
c=sorted(c.items(),key=lambda w:w[1],reverse=True)
print(N-c[0][1])

Submission status: Accepted

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

xy = sorted(xy)
cnt = {}
if n == 1:
  ans = 1
else:
  for i in range(n-1):
    for j in range(i+1,n):
      if i == j:
        continue
      else:
        dx = xy[j][0] - xy[i][0]
        dy = xy[j][1] - xy[i][1]
        k = ','.join([str(dx), str(dy)])
        if k in cnt.keys():
          cnt[k] += 1
        else:
          cnt[k] = 1
  ans = n - max(cnt.values())
print(ans)

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline

N = int(readline())

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

diff_list = {}

for x1, y1 in XY:
    for x2, y2 in XY:
        if x1 == x2 and y1 == y2:
            continue
        diffx = x2 - x1
        diffy = y2 - y1
        diff = (diffx, diffy)
        if not (diff in diff_list): diff_list[diff] = 0
        diff_list[diff] += 1

values = diff_list.values()
if len(values) > 0:
    m = max(values)
    ans = N - m
else:
    ans = 1

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Apr 20 20:47:47 2019

@author: Owner
"""

import numpy as np
import sys
import collections
import scipy.misc
import math
from operator import itemgetter
import itertools
import copy
import bisect

#素因数を並べる
def prime_decomposition(n):
  i = 2
  table = []
  while i * i <= n:
    while n % i == 0:
      n /= i
      table.append(int(i))
    i += 1
  if n > 1:
    table.append(int(n))
  return table   
# 桁数を吐く
def digit(i):
    if i > 0:
        return digit(i//10) + [i%10]
    else:
        return []
    
def getNearestValueIndex(list, num):
    """
    概要: リストからある値に最も近い値のインデックスを取得する関数
    @param list: データ配列
    @param num: 対象値
    @return 対象値に最も近い値
    """

    # リスト要素と対象値の差分を計算し最小値のインデックスを取得
    idx = np.abs(np.asarray(list) - num).argmin()
    return idx

def find_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default

class UnionFind(object):
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
        self.size = [1 for _ in range(n)]

    def find(self, x):
        """
        x が属するグループを探索
        """
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def union(self, x, y):
        """
        x と y のグループを結合
        """
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x
            self.size[x] += self.size[y]

    def is_same(self, x, y):
        """
        x と y が同じグループか否か
        """
        return self.find(x) == self.find(y)

    def get_size(self, x):
        """
        x が属するグループの要素数
        """
        x = self.find(x)
        return self.size[x]
    

"""
N, X = map(int, input().split())

x = list(map(int, input().split()))

P = [0]*N
Y = [0]*N
for n in range(N):
    P[n], Y[n] = map(int, input().split())

# 多次元配列の宣言（あとでintにすること。）（タプルにすること。）
dp = np.zeros((N+1, 4,4,4))
    
all(nstr.count(c) for c in '753')

# 複数配列を並び替え
ABT = zip(A, B, totAB)
result = 0
# itemgetterには何番目の配列をキーにしたいか渡します
sorted(ABT,key=itemgetter(2))
A, B, totAB = zip(*ABT)
A.sort(reverse=True)

# 2進数のbit判定
(x >> i) & 1

# dp最小化問題
dp = [np.inf]*N
for n in range(N):
    if n == 0:
        dp[n] = 0
    else:
        for k in range(1,K+1):
            if n-k >= 0:
                dp[n] = min(dp[n], dp[n-k] + abs(h[n]-h[n-k]))
            else:
                break
# 累積和
add = 1 # 問題によって決まる
res = 0
sums = [0]*(len(nums)+1)
for i in range(len(nums)):
    sums[i+1] = sums[i] + nums[i]
for i in range(0, len(nums), 2):
    left = i
    right = min(i+add, len(nums))
    tmp = sums[right] - sums[left]
    res = max(tmp, res)

#２分探索
li, ri = bisect.bisect_left(p_ac, l[i]-1), bisect.bisect_right(p_ac, r[i]-1)    

#ソート関数
org_list = [3, 1, 4, 5, 2]
new_list = sorted(org_list)
print(org_list)
print(new_list)
# [3, 1, 4, 5, 2]
# [1, 2, 3, 4, 5]

#Distance Transformation
    for h in range(0,H):
        for w in range(0,W):
            if h == 0 and w == 0:
                pass
            elif h == 0:
                D[H-h-1][W-w-1]= min(D[H-h-1][W-w-1], D[H-h-1][W-w]+1)
            elif w == 0:   
                D[H-h-1][W-w-1]= min(D[H-h-1][W-w-1], D[H-h][W-w-1]+1)
            else:
                D[H-h-1][W-w-1]= min(D[H-h-1][W-w-1], D[H-h][W-w-1]+1, D[H-h-1][W-w]+1, D[H-h][W-w]+2)
            d_max = max(D[H-h-1][W-w-1], d_max)

"""



N=int(input())
ab = [(0, 0)]*N
a = [0]*N
b = [0]*N
for n in range(N):
    ab[n] = tuple(map(int, input().split()))
    a[n] = ab[n][0]
    b[n] = ab[n][1]
    
def main(): 
    if N == 1:
        return print(1)
    XY = list(itertools.permutations(ab, 2))
    pq = []
    for xy in XY:
        pq.append((xy[0][0]-xy[1][0],xy[0][1]-xy[1][1]))
    c_pq=collections.Counter(pq)
    print(N-c_pq.most_common()[0][1])
                
                
                
            
            
                

    
if __name__ == '__main__':
    main()

Submission status: Accepted

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

def readInts():
  return [int(s) for s in input().split(" ")]

def cost(N, points, pointToIndex, p, q):
  s = 0

  visited = [False for _ in range(N)]
  for i in range(N):
    if visited[i]: continue

    s += 1
    visited[i] = True

    k = 1
    while (points[i][0] + p * k <= points[-1][0]) and (points[i][1] + q * k <= points[-1][1] or points[i][1] + q * k >= points[-1][1]):
      np = (points[i][0] + p * k, points[i][1] + q * k)
      if np in pointToIndex and not visited[pointToIndex[np]]:
        visited[pointToIndex[np]] = True
        k += 1
      else:
        break

  return s

def main():
  N = readInts()[0]
  points = [tuple(readInts()) for _ in range(N)]
  points.sort()

  ans = N

  pointToIndex = {}
  for i, point in enumerate(points):
    pointToIndex[point] = i

  for i in range(N-1):
    for j in range(i+1, N):
      p = points[j][0] - points[i][0]
      q = points[j][1] - points[i][1]
      ans = min(ans, cost(N, points, pointToIndex, p, q))

  print(ans)

if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
from collections import (
    Counter,
)


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


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

    if len(xy) == 1:
        print(1)
        return

    (_, count), = Counter(
        (x1 - x2, y1 - y2)
        for (x1, y1) in xy
        for (x2, y2) in xy
        if not (x1 == x2 and y1 == y2)
    ).most_common(1)

    print(len(xy) - count)


if __name__ == '__main__':
    _main()

Submission status: Accepted

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

def search(i,j):
    p = xy[i][0]-xy[j][0]
    q = xy[i][1]-xy[j][1]
    res = N
    for k in range(N):
        for l in range(N):
            if xy[k][0]-xy[l][0]==p and xy[k][1]-xy[l][1]==q:
                res -= 1
    return res

ans = N
for i in range(N):
    for j in range(N):
        if i!=j:
            ans = min(ans,search(i,j))
print(ans)

Submission status: Accepted

Solution code:

n = int(input())

points = []

defer = []

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

points.sort()

for i in range(n):
  for j in range(i+1, n):
    defer.append((points[j][0] - points[i][0], points[j][1] - points[i][1]))

maxi = 0

for d in set(defer):
  maxi = max(defer.count(d), maxi)

print(n - maxi)

Submission status: Accepted

Solution code:
from collections import Counter


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

    if N == 1:
        print(1)
        return

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

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

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

        i = 1
        while True:
            n = (x + i * dx, y + i * dy)
            i += 1
            if n in pointset:
                visited.add(n)
            else:
                break
        i = 1
        while True:
            n = (x - i * dx, y - i * dy)
            i += 1
            if n in pointset:
                visited.add(n)
            else:
                break

    print(cost)


main()

Submission status: Accepted

Solution code:
import sys
n = int(input())
arr = sorted(list(map(lambda x: tuple(map(int, x.split())), sys.stdin.readlines())))
# print(arr)

candidate = set()
for i in range(n):
  for j in range(i+1, n):
    candidate.add((arr[j][0] - arr[i][0], arr[j][1] - arr[i][1]))
    
# print(candidate)

ans = n
for can in candidate:
  li = arr.copy()
  count = 0
  while (len(li) > 0) and (count < ans):
    count += 1
    p = li.pop(-1)
    p = (p[0] - can[0], p[1] - can[1])
    #print(li)
    pos = set(li)
    while p in pos:
      pos.remove(p)
      li.remove(p)
      p = (p[0] - can[0], p[1] - can[1])
      #print(li, "p", p)
  ans = count
print(ans)

Submission status: Accepted

Solution code:

from copy import deepcopy
from itertools import combinations
N = int(input())
if N==1:
    print(1)
    exit()
XY = [list(map(int, input().split())) for _ in range(N)]
ans = float("inf")
for (x1, y1), (x2, y2) in combinations(XY, 2):
    p, q = (x2-x1), (y2-y1)
    XY_ = deepcopy(XY)

    #XY_.sort()
    XY_.sort(key=lambda v: (v[0]*q - v[1]*p, v[0], v[1]))
    an = 0
    xp, yp = float("inf"), float("inf")
    for x, y in XY_:
        if xp+p==x and yp+q==y:
            pass
        else:
            an += 1
        xp, yp = x, y
    # if ans > an:
    #     print(p, q)
    ans = min(ans, an)
    for x, y in XY_:
        if xp-p==x and yp-q==y:
            pass
        else:
            an += 1
        xp, yp = x, y
    #if ans > an:

    ans = min(ans, an)
print(ans)

Submission status: Accepted

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

vec_counts = {0: 0}
for x1, y1 in zip(x_list, y_list):
    for x2, y2 in zip(x_list, y_list):
        v = x1 - x2, y1 - y2
        if v != (0, 0):
            if v in vec_counts:
                vec_counts[v] += 1
            else:
                vec_counts[v] = 1

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import itertools
import numpy as np
n = int(input())
points = np.array([list(map(int,input().split())) for _ in range(n)])

if n == 1:
    print(1)
else:
    # print(points)
    vectors_count = {}
    for vec1,vec2 in itertools.permutations(points,2):
        relative_vec = vec1 - vec2
        str_vec = (str(relative_vec))
        # print(type(relative_vec))
        if str_vec in vectors_count:
            vectors_count[str_vec] += 1
        else:
            vectors_count[str_vec] = 1

    # print(vectors_count)
    # # print(max(vectors_count.values()))
    max_vec = max(vectors_count.values())
    ans = n - max_vec
    print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
n = int(input())
coor = []
for i in range(n):
  x,y = map(int, input().split())
  coor.append([x,y])
  
if n == 1:
  print(1)
  exit()

dif = []
for i in range(n):
  for j in range(n):
    if i != j:
      dif.append((coor[i][0] - coor[j][0], coor[i][1] - coor[j][1]))
      
S = Counter(dif)
way = max(S.values())
print(n-way)

Submission status: Accepted

Solution code:

N = int(input())

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


vectors = []

x1, x2, y1, y2, xd, yd = 0, 0, 0, 0, 0, 0
for i in range(N):
    for j in range(i+1, N):
        x1, y1 = xy[i]
        x2, y2 = xy[j]

        vectors.append((x1-x2, y1-y2))
        vectors.append((x2-x1, y2-y1))

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

frequencies_dic = {}
M = len(vectors)
for i in range(M):
    x, y = vectors[i]
    if (x, y) not in frequencies_dic:
        frequencies_dic[(x,y)] = 1
    else:
        frequencies_dic[(x,y)] += 1
if N == 1:
    print(1)
else:
    zeros = max(list(frequencies_dic.values()))
    ans = N - zeros
    print(ans)

Submission status: Accepted

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

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

from itertools import permutations
from collections import Counter
l = [((A[0]-B[0]),(A[1]-B[1])) for A,B in permutations(XY,2)]
c = Counter(l)
print(N - c.most_common()[0][1] )

Submission status: Accepted

Solution code:
N=int(input())

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

XY.sort()

d={}

if N==1:
    print(1)
else:
    for i in range(N-1):
        for j in range(i+1,N):
            if str(XY[j][0]-XY[i][0])+' '+str(XY[j][1]-XY[i][1]) in d:
                d[str(XY[j][0]-XY[i][0])+' '+str(XY[j][1]-XY[i][1])]+=1
            else:
                d[str(XY[j][0]-XY[i][0])+' '+str(XY[j][1]-XY[i][1])]=1
            
    print(N-max(d.values()))

Submission status: Accepted

Solution code:
N=int(input())
xy=list(list(map(int,input().split())) for _ in range(N))
L=[]
c=1
for i in range(N):
    for j in range(N):
        if i!=j:
            L.append(([xy[j][0]-xy[i][0],xy[j][1]-xy[i][1]]))
for l in L:
    c=max(c,L.count(l))
print(N-c if N!=1 else 1)