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 Counter

N = int(input())
XY = [list(map(int, input().split())) for _ in range(N)]
XY.sort()
diff = []
for i in range(N):
    xi, yi = XY[i]
    for j in range(i+1, N):
        xj, yj = XY[j]
        diff.append((xj-xi, yj-yi))
c = Counter(diff)
print(N-max(c.values()) if c else N)

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n = inp()
a = [inpl() for i in range(n)]
a.sort(key=lambda x:x[1])
a.sort()
z = []
# pprint.pprint(a)
for i in range(n):
    for j in range(i,n):
        if i == j:
            continue
        z.append((a[i][0]-a[j][0], a[i][1]-a[j][1]))
c = Counter(z)
# pprint.pprint(c)
if n == 1:
    print(1)
else:
    print(n-c.most_common()[0][1])
# print(n-c.most_common()[0][1])

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
N=int(input())

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

dis=[[0]*(N) for i in range(N-1)]
#print(dis)

for i in range(N-1):
    for j in range(i+1,N):
        if l[i][0]-l[j][0]>0:
            dis[i][j]=[(l[i][0]-l[j][0]),(l[i][1]-l[j][1])]
        elif l[i][0]-l[j][0]<0:
            dis[i][j]=[-(l[i][0]-l[j][0]),-(l[i][1]-l[j][1])]
        else:
            dis[i][j]=[(l[i][0]-l[j][0]),abs(l[i][1]-l[j][1])]

temp=0
for i in range(N-1):
    for item in dis[i]:
        if item!=0:
            temp=max(sum(x.count(item) for x in dis),temp)

#print(l)
#print(dis)
print(N-temp)

Submission status: Accepted

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

N = int(input())
b = [list(map(int, input().split())) for _ in range(N)]
b.sort(key = lambda x: (x[0], x[1]))
vis = set()
viss = set()
res = 0
def dfs(n, p, q):
  global vis
  global viss
  res = 0
  vis.add(n)
  viss.add(n)
  for k in range(N):
    if k in vis: continue
    if k in viss: continue
    if (b[k][0] == b[n][0] + p) and (b[k][1] == b[n][1] + q):
      res = max(res, dfs(k, p, q))
  vis.discard(n)
  return res + 1
for i in range(N):
  for j in range(N):
    vis = set()
    viss = set()
    p = b[j][0] - b[i][0]
    q = b[j][1] - b[i][1]
    temp = 0
    for n in range(N):
      if n in viss: continue
      t = dfs(n, p, q)
      if t > 1:
        temp += t - 1
    res = max(temp, res)
    #print(temp, p, q)
print(N - res)

Submission status: Accepted

Solution code:
def main():
    n=int(input())
    xy = sorted([list(map(int, input().split())) for _ in range(n)])
    xy.sort()
    ans=n
    for i in range(n):
        [x1,y1]=xy[i]
        for j in range(n-1):
            [x2,y2]=xy[j]
            if i!=j:
                [p,q]=[x1-x2,y1-y2]
                cnt=0
                for k in range(n-1):
                    for l in range(k+1,n):
                        [x,y]=[ xy[k][0]-xy[l][0],xy[k][1]-xy[l][1] ]
                        if [x,y]==[p,q] or [x,y]==[-p,-q]:
                            cnt+=1
                ans=min(ans,n-cnt)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n = int(input())
x = []
y = []
for _ in range(n):
    line = list(map(int, input().split()))
    x.append(line[0])
    y.append(line[1])
if n >= 2:
    slope = []
    for i in range(n):
        for j in range(i+1, n):
            X = x[j] - x[i]
            Y = y[j] - y[i]
            if X != 0:
                if X < 0:
                    X = -X
                    Y = -Y
            slope.append([X, Y])
            if X == 0:
                slope.append([X, -Y])
    cnt = []
    for i in slope:
        cnt.append(slope.count(i))
    print(n - max(cnt))
else:
    print(1)

Submission status: Accepted

Solution code:
n = int(input())
x = []
y = []
for _ in range(n):
    line = list(map(int, input().split()))
    x.append(line[0])
    y.append(line[1])
if n >= 2:
    slope = []
    for i in range(n):
        for j in range(n):
            if i != j:
                X = x[j] - x[i]
                Y = y[j] - y[i]
                slope.append([X, Y])
    cnt = []
    for i in slope:
        cnt.append(slope.count(i))
    print(n - max(cnt))
else:
    print(1)

Submission status: Accepted

Solution code:
n=int(input())
l=[]
for i in range(n):
    l.append(list(map(int,input().split())))
ans=n
for i in range(n):
    for j in range(n):
        if i<j:
            p=l[i][0]-l[j][0]
            q=l[i][1]-l[j][1]
            kai=n
            for x in range(n):
                for y in range(n):
                    if l[x][0]-l[y][0]==p and l[x][1]-l[y][1]==q:
                        kai-=1
            ans=min(ans,kai)
print(ans)

Submission status: Accepted

Solution code:
import itertools
N = int(input())
X = [list(map(int,input().split())) for _ in range(N)]
if N==1:
    cmin = 1
else:
    cmin = 100
    for y in itertools.combinations(X,2):
        x1,y1 = y[0]
        x2,y2 = y[1]
        p = x2-x1
        q = y2-y1
        cnt0 = 0
        cnt1 = 0
        for i in range(N):
            x,y = X[i]
            if [x+p,y+q] in X:
                cnt0 += 1
            if [x-p,y-q] in X:
                cnt1 += 1
        cnt = max(cnt0,cnt1)
        cmin = min(cmin,N-cnt)
print(cmin)

Submission status: Accepted

Solution code:
from itertools import combinations
from collections import Counter

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

cXY = combinations(XY, 2)

edge = []
for a, b in cXY:
  edge.append((a[0]-b[0], a[1]-b[1]))
  edge.append((-a[0]+b[0], -a[1]+b[1]))

ce = Counter(edge)

if N == 1:
  ans = 1
else:
  dup = max(ce.values())
  ans = N - dup
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from operator import itemgetter
sys.setrecursionlimit(10000000)
from collections import Counter

def main():
    n = int(input().strip())
    p = []
    for i in range(n):
        x, y = map(int, input().strip().split())
        p.append((x, y))
    vtable = [0] * n**2
    for i in range(n):
        for j in range(n):
            vtable[i * n + j] = (p[i][0] - p[j][0], p[i][1] - p[j][1])
    c = sorted(Counter(vtable).values(), reverse=True)
    if len(c) == 1:
        print(1)
    else:
        print(n - c[1])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from fractions import gcd
from datetime import date, timedelta
from heapq import*
import math
from collections import defaultdict, Counter, deque
import sys
from bisect import *
import itertools
import copy
sys.setrecursionlimit(10 ** 7)
MOD = 10 ** 9 + 7


def main():
    n = int(input())
    xy = [list(map(int, input().split())) for i in range(n)]
    
    d = defaultdict(int)
    for i in range(n):
        for j in range(n):
            if i == j:
                continue
            aaa = xy[i][0] - xy[j][0]
            bbb = xy[i][1] - xy[j][1]
            d[(aaa,bbb)]+=1
            
    t = 0
    for v in d.values():
        t = max(v , t)
    print(n - t)

    






    


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from fractions import gcd
from datetime import date, timedelta
from heapq import*
import math
from collections import defaultdict, Counter, deque
import sys
from bisect import *
import itertools
import copy
sys.setrecursionlimit(10 ** 7)
MOD = 10 ** 9 + 7


def main():
    n = int(input())
    xy = [list(map(int, input().split())) for i in range(n)]
    
    d = defaultdict(int)
    for i in range(n):
        for j in range(n):
            if i == j:
                continue
            aaa = xy[i][0] - xy[j][0]
            bbb = xy[i][1] - xy[j][1]
            # if aaa > 0 and bbb >0:
            #     g = gcd(aaa, bbb)
            #     aaa //= g
            #     bbb //= g
            # else:
            #     if aaa > 0:
            #         aaa = 1
            #     else:
            #         bbb = 1

            d[(aaa,bbb)]+=1
            #d[(bbb,aaa)]+=1
    t = 0
    for v in d.values():
        t = max(v , t)
    print(n - t)

    






    


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n=int(input())
xy=[tuple(map(int,input().split())) for _ in range(n)]
pq=[]
for i in range(n):
    for j in range(n):
        if i==j:
            continue
        sx,sy=xy[i]
        gx,gy=xy[j]
        pq.append((gx-sx,gy-sy))



ans=n
for p,q in pq:
    now=0
    for x,y in xy:
        if (x+p,y+q) not in xy:
            now+=1
    ans=min(ans,now)

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
xy=[tuple(map(int,input().split())) for _ in range(n)]
pq=[]
for i in range(n):
    for j in range(n):
        if i==j:
            continue
        sx,sy=xy[i]
        gx,gy=xy[j]
        pq.append((gx-sx,gy-sy))


se=set(xy)

ans=n
for p,q in pq:
    now=0
    for x,y in xy:
        if (x+p,y+q) not in se:
            now+=1
    ans=min(ans,now)

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
n = int(input())
xy = [tuple(map(int, input().split())) for _ in range(n)]
v = []
for i in range(n):
    for j in range(n):
        if i == j: continue
        x, y = xy[j]
        px, py = xy[i]
        v.append((x-px, y-py))
num = Counter(v).most_common(1)[0][1] if v else 0
print(n - num)

Submission status: Accepted

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

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

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

print(N-Counter(map(lambda x:x[0]*10**10+x[1],pq)).most_common()[0][1])

Submission status: Accepted

Solution code:
from operator import itemgetter

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

XY.sort(key=itemgetter(1))
XY.sort(key=itemgetter(0))

ans = N
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]
        cost1 = N
        cost2 = N
        for x, y in XY:
            if [x+p, y+q] in XY:
                cost1 -= 1
            if [x-p, y-q] in XY:
                cost2 -= 1
        ans = min([ans, cost1, cost2])
print(ans)

Submission status: Accepted

Solution code:
class UnionFind :
    def __init__(self, size) :
        """
        Parameters
        ---
        size : int
            頂点数
        """
        self.parent = list(range(size))
        self.height = [0] * size
        self.size = [1] * size
        self.component = size

    def root(self, index) :
        """
        親のインデックスの取得

        Parameters
        ---
        index : int
            取得する頂点のインデックス

        Returns
        ---
        rootIndex : int
            指定した頂点の根のインデックス
        """
        if self.parent[index] == index :  # 根の場合
            return index
        rootIndex = self.root(self.parent[index])  # 葉の場合親の根を取得
        self.parent[index] = rootIndex  # 親の付け直し
        return rootIndex

    def union(self, index1, index2) :  # 結合
        """
        木の結合

        Parameters
        ---
        index1 : int
        index2 : int
            結合する頂点のインデックス
        """
        root1 = self.root(index1)
        root2 = self.root(index2)

        if root1 == root2 :  # 連結されている場合
            return

        self.component -= 1  # 連結成分を減らす

        if self.height[root1] < self.height[root2] :
            self.parent[root1] = root2  # root2に結合
            self.size[root2] += self.size[root1]
        else :
            self.parent[root2] = root1  # root1に結合
            self.size[root1] += self.size[root2]
            if self.height[root1] == self.height[root2] :
                self.height[root1] += 1
        return

    def isSameRoot(self, index1, index2) :
        """
        同じ木に属するかを判定する

        Parameters
        ---
        index1 : int
        index2 : int

        Returns
        ---
        boolean
        """
        return self.root(index1) == self.root(index2)

    def sizeOfSameRoot(self, index) :
        """
        指定した頂点の属する木の大きさを取得する
        """
        return self.size[self.root(index)]

    def getComponent(self) :
        """
        連結成分数を取得する
        """
        return self.component

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

ans = float('inf')
for x, y in XY:
    for u, v in XY:
        p = x - u
        q = y - v

        tree = UnionFind(N)
        for i, (a, b) in enumerate(XY):
            for j, (c, d) in enumerate(XY):
                if a - c == p and b - d == q:
                    tree.union(i, j)

        ans = min(ans, tree.getComponent())

print(ans)

Submission status: Accepted

Solution code:
N=int(input())

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

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

c={}
for i in range(N):
    for j in range(N):
        if i!=j:
            p=P[j][0]-P[i][0]
            q=P[j][1]-P[i][1]
            temp=str(p)+"_"+str(q)
            if temp in c:
                c[temp]+=1
            else:
                c[temp]=1
c_num=[]
for j in c:
    c_num.append(c[j])

print(N-max(c_num))

Submission status: Accepted

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

def main():
    N = int(input())
    xy = sorted([list(map(int, input().split())) for i in range(N)], key=lambda x: (x[0], x[1]))
    
    dic = {}
    max_ = 0
    for i in range(N):
        for j in range(N):
            if i == j:
                continue
            p = xy[i][0] - xy[j][0]
            q = xy[i][1] - xy[j][1]
            if (p, q) in dic:
                dic[(p, q)] += 1
            else:
                dic[(p, q)] = 1
            max_ = max(max_, dic[(p, q)])
    
    print(N - max_)

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

if N == 1:
    print(1)
else:
    memo = {}

    for i in range(N-1):
        for j in range(i+1,N):
            dx = x[j] - x[i]
            dy = y[j] - y[i]
            if (dx,dy) in memo:
                memo[(dx,dy)] += 1
            elif (-dx,-dy) in memo:
                memo[(-dx,-dy)] += 1
            else:
               memo[(dx,dy)] = 1
            #print(memo)

    M = max(memo.values())

    print(N-M)

Submission status: Accepted

Solution code:
#%%
import collections

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

l = []
for i in range(n):
    for j in range(n):
        tmp = str(x[i]-x[j]) + ' ' + str(y[i]-y[j])
        l.append(tmp)

c = collections.Counter(l)
a = list(c.values())
#print(a)
a.sort(reverse=True)


if n == 1:
    print(1)
else:
    print(n-a[1])

Submission status: Accepted

Solution code:
n=int(input())
lists=[]
if n>=2:
    for i in range(n):
        a,b=map(int,input().split())
        lists.append([a,b])
    diflist=[]
    for i in range(n):
        for j in range(n):
            if i!=j:
                add=(lists[i][0]-lists[j][0],lists[i][1]-lists[j][1])
                diflist.append(add)
            else:
                continue
    import collections
    dic=collections.Counter(diflist)
    value=dic.values()
    a=max(value)
    print(n-a)
else:
    print(1)

Submission status: Accepted

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


def main():
    n = int(input())
    xs = [0 for _ in range(n)]
    ys = [0 for _ in range(n)]
    d = dict()

    # KeyInsight (◯：気がつけた，△：解説を読んでなんとなく理解，×：理解できず):
    # ◯ 任意の二点について，ベクトルを計算
    # △ 同じベクトルの頻度を計算する
    # △ 頻度の最大値が減らせるコストの最大値
    # See:
    # https://www.youtube.com/watch?v=TbobvdA6AlE
    # https://atcoder.jp/contests/diverta2019-2/submissions/5920106
    for i in range(n):
        xi, yi = map(int, input().split())
        xs[i] = xi
        ys[i] = yi

    for j in range(n):
        for k in range(n):
            if j == k:
                continue

            c = xs[j] - xs[k], ys[j] - ys[k]

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

    ans = n

    for di in d.values():
        ans = min(ans, n - di)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main(): 
    from collections import defaultdict
    n = int(input())
    di = [list(map(int, input().split(' '))) for _ in range(n)]
    #result = {0:0}
    md = defaultdict(int)
    md[0] = 0
    for i in range(n):
        for j in range(n):
            if i == j:
                continue
            else:
                p = di[i][0] - di[j][0]
                q = di[i][1] - di[j][1]
                #result[(p,q)] = result.get((p,q), 0)+1
                md[(p,q)] += 1
    #print(result)
    #print(n - max(result.values()))
    #print(md)
    print(n - max(md.values()))
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict
n = int(input())
di = [list(map(int, input().split(' '))) for _ in range(n)]
#result = {0:0}
md = defaultdict(int)
md[0] = 0
for i in range(n):
    for j in range(n):
        if i == j:
            continue
        else:
            p = di[i][0] - di[j][0]
            q = di[i][1] - di[j][1]
            #result[(p,q)] = result.get((p,q), 0)+1
            md[(p,q)] += 1
#print(result)
#print(n - max(result.values()))
#print(md)
print(n - max(md.values()))

Submission status: Accepted

Solution code:
#from collections import defaultdict
n = int(input())
di = [list(map(int, input().split(' '))) for _ in range(n)]
result = {0:0}
#md = defaultdict(int)
for i in range(n):
    for j in range(n):
        if i == j:
            continue
        else:
            p = di[i][0] - di[j][0]
            q = di[i][1] - di[j][1]
            result[(p,q)] = result.get((p,q), 0)+1
            #md[(p,q)] += 1
#print(result)
print(n - max(result.values()))
#print(md)
#print(n - max(md.values()))

Submission status: Accepted

Solution code:
import collections

N = int(input())
arr = [list(map(int,input().split())) for _ in range(N)]
if N==1:
  print(1)
else:
  arr = sorted(arr,key=lambda x:(x[0],x[1]))
  diff_arr = []
  for j in range(N):
    for k in range(1,N-j):
      diff_arr.append(str(arr[j+k][0]-arr[j][0])+'_'+str(arr[j+k][1]-arr[j][1]))
  c = collections.Counter(diff_arr)
  print(N-max(c.values()))

Submission status: Accepted

Solution code:
from collections import defaultdict
n = int(input())
p = [[int(i) for i in input().split()] for i in range(n)]
x,ans = defaultdict(int),0
for i in range(n):
    for j in range(i+1,n):
        a,b = p[i][0]-p[j][0],p[i][1]-p[j][1]
        x[(a,b)]+=1
        x[(-a,-b)]+=1
for i in x.values(): ans = max(ans,i)
print(n-ans)

Submission status: Accepted

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

ans = dict()

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

for i in range(n):
    for j in range(n):
        if (i == j):
            continue
        p = xy[j][0] - xy[i][0]
        q = xy[j][1] - xy[i][1]
        if ans.get((p, q)) == None:
            ans[(p, q)] = 1
        else:
            ans[(p, q)] += 1
# print(ans)
print(n-max(ans.values()))

Submission status: Accepted

Solution code:
from itertools import combinations
from collections import Counter

n = int(input())
xy_array = [[int(x) for x in input().split()] for y in range(n)]
comb_xy = combinations(xy_array, 2)
ans = float("INF")
res_x = 0
res_y = 0

vector = []
for i, j in comb_xy:
    xx = j[0] - i[0]
    yy = j[1] - i[1]
    vector.append((xx, yy))
    xx = i[0] - j[0]
    yy = i[1] - j[1]
    vector.append((xx, yy))

if n == 1:
    print(1)
    exit()
print(n - max(Counter(vector).values()))

Submission status: Accepted

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

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

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

d = defaultdict(int)

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

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

Submission status: Accepted

Solution code:
from operator import itemgetter
from collections import defaultdict

big = 10**10
N = int(input())
pt = [[int(x) for x in input().split()] for _ in range(N)]
pt.sort(key = itemgetter(1))
pt.sort(key = itemgetter(0))
di = defaultdict(int)
for i,p0 in enumerate(pt):
    for j,p1 in enumerate(pt):
        if(i>=j):continue
        p,q = p0[0]-p1[0],p0[1]-p1[1]
        di[p*big+q] += 1
maxd = 0
for i in di:
    if(i==0):continue
    maxd = max(di[i],maxd)
print(N-maxd)

Submission status: Accepted

Solution code:
from collections import Counter
n = int(input())
a = []
ans = []
if n == 1:
    print(1)
    exit()
for _ in range(n):
    x, y = map(int, input().split())
    a.append([x, y])
a.sort()
for i in range(n):
    for j in range(i + 1, n):
        p = a[i][0] - a[j][0]
        q = a[i][1] - a[j][1]
        ans.append(str(p) + " " + str(q))
print(n - max(Counter(ans).values()))

Submission status: Accepted

Solution code:
import itertools
import collections
import sys
N=int(input())
if N==1:
    print(1)
    sys.exit()
X=[0]*N
Y=[0]*N
for i in range(N):
    X[i],Y[i]=[int(x) for x in input().split()]
p=[]
for c in list(itertools.permutations(zip(X,Y), 2)):
    p.append(str(c[1][0]-c[0][0]) + ',' +str(c[1][1]-c[0][1]))
    #print(c,c[1][0]-c[0][0],c[1][1]-c[0][1])
#print(p)
print(N - collections.Counter(p).most_common()[0][1])

Submission status: Accepted

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

ans = N
for i in range(N):
  for j in range(N):
    if i != j:
      p = XY[i][0] - XY[j][0]
      q = XY[i][1] - XY[j][1]
      tmp = 0
      for k in range(N):
        for l in range(N):
          if k != l and p == XY[k][0] - XY[l][0] and q == XY[k][1] - XY[l][1]:
            tmp +=1
      ans = min(ans, N-tmp)
print(ans)

Submission status: Accepted

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

cd = defaultdict(int)
C = [list(map(int, input().split())) for _ in range(N)]

for i in range(N):
    for j in range(N):
        if i == j:
            continue
        cd[(C[i][0]-C[j][0],C[i][1]-C[j][1])] += 1

if N == 1:
    print(1)
else:
    print(N-max(cd.values()))

Submission status: Accepted

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

for i in range(n):
    for j in range(n):
        if i==j:
            continue
        if ((xy[i][0]-xy[j][0]),(xy[i][1]-xy[j][1])) in diff:
            diff[((xy[i][0]-xy[j][0]), (xy[i][1]-xy[j][1]))]+=1
        else:
            diff[((xy[i][0] - xy[j][0]), (xy[i][1] - xy[j][1]))] = 1

print(n-max(diff.values()) if n!=1 else 1)

Submission status: Accepted

Solution code:
def main():

    N = int(input())
    if N == 1: return 1
    if N == 2: return 1

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

    pq = []
    for i in range(N-1):
        x0, y0 = ball[i]
        for j in range(i+1, N):
            x1, y1 = ball[j]
            pq.append([x1-x0, y1-y0])
    # print(pq)

    min_count = N
    for p, q in pq:
        count = 0
        visited = set()
        for b in ball:
            if b not in visited:
                count += 1
                z, w = b[0], b[1]
                while (z, w) in ball:
                    visited.add((z, w))
                    z += p
                    w += q
            # print(visited, count)
        min_count = min(min_count, count)

    return min_count

if __name__ == '__main__':
    print(main())

Submission status: Accepted

Solution code:
import math
N = int(input())
s_dict = {}
cood_list=[]
ans = 0
for i in range(N):
    a,b = map(int,input().split())
    for j in range(len(cood_list)):
        p = a - cood_list[j][0]
        q = b - cood_list[j][1]
        if 0 > p:
            p = -p
            q = -q
        elif p == 0:
            q = abs(q)
        s = str(p)+","+str(q)
        if s not in s_dict:
            s_dict[s] = 1
        else:
            s_dict[s] += 1
    cood = [a,b]
    cood_list.append(cood)
if N != 1:
    print(N-max(s_dict.values()))
else:
    print(1)

Submission status: Accepted

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

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

for i in range(n):
    for j in range(i+1, n):
        if (xy[j][0] - xy[i][0], xy[j][1] - xy[i][1]) not in dict_xy:
            dict_xy[xy[j][0] - xy[i][0], xy[j][1] - xy[i][1]] = 1
        else:
            dict_xy[xy[j][0] - xy[i][0], xy[j][1] - xy[i][1]] += 1

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

Submission status: Accepted

Solution code:
from collections import Counter
n=int(input())
L=[]
for _ in range(n):
   x,y=map(int,input().split())
   L.append((x,y))
D=[]
if n==1:print(1)
else:
   for i in range(n):
      for j in range(i+1,n):
          D.append((L[i][0]-L[j][0],L[i][1]-L[j][1]))
          D.append((L[j][0]-L[i][0],L[j][1]-L[i][1]))
   C=Counter(D)
   print(n-C.most_common()[0][1])

Submission status: Accepted

Solution code:
from itertools import combinations


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


pq_list = [(a - c, b - d) for (a, b), (c, d) in list(combinations(ball, 2))]
max_cnt = 0
for p, q in pq_list:
    cnt = 0
    for x, y in ball:
        if [x+p, y+q] in ball:
            cnt += 1
    max_cnt = max(cnt, max_cnt)
print(n - max_cnt)

Submission status: Accepted

Solution code:
def solve(n, x, y):
    S = set()
    for i in range(n):
        for j in range(n):
            if i != j:
                p, q = x[i]-x[j], y[i]-y[j]
                S.add((p, q))
    P = set([(x[i], y[i])for i in range(n)])
    best = n
    for p, q in S:
        total = n
        for i in range(n):
            u, v = x[i] + p, y[i] + q
            if (u, v) in P:
                total -= 1
        best = min(best, total)
    return best

n = int(input())
x = [-1] * n
y = [-1] * n
for i in range(n):
    x[i], y[i] = map(int, input().split())
print(solve(n, x, y))

Submission status: Accepted

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

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7

n = int(input())
xy = [list(map(int,input().split())) for _ in range(n)]
ans = float('inf')
if n == 1:
    print(1)
    quit()
for i in range(n):
    for j in range(n):
        if i == j:
            continue
        p,q = xy[j][0] - xy[i][0],xy[j][1] - xy[i][1]
        cost = n
        for k in range(n):
            for l in range(n):
                a,b = xy[k][0] - xy[l][0],xy[k][1] - xy[l][1]
                #print('p',p,'q',q,'a',a,'b',b,'cost',cost)
                if p == a and q == b:
                    cost -= 1
        ans = min(cost,ans)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
inputs = [[int(i) for i in input().split()] for _ in range(N)]

ans = 1
rates = {0: 0}
for i in range(N):
    for j in range(N):
        if i == j:
            continue
        vector = (inputs[i][0] - inputs[j][0], inputs[i][1] - inputs[j][1])
        rates[vector] = rates.get(vector, 0) + 1

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

Submission status: Accepted

Solution code:
import sys
s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in ss]
ss2nnn = lambda ss: [s2nn(s) for s in ss]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline().rstrip() for _ in range(n)]
ii2sss = lambda n: [list(sys.stdin.readline().rstrip()) for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

from collections import defaultdict  # 初期化済み辞書

def main():
    N = i2n()
    XY = ii2nnn(N)
    # n <= 50 なので、xy[i] → xy[j] の全ての組み合わせについて、距離を全探索できちゃう
    # 距離 dx, dy をkeyに、その距離の i, j ペアの数をvalueとしてカウント
    d = defaultdict(lambda: 0)
    for i in range(N):
        xi, yi = XY[i]
        for j in range(N):
            if i == j:
                continue
            xj, yj = XY[j]
            dxy = (xj - xi, yj - yi)
            d[dxy] += 1
    # 基本はコストN
    # max(value) だけコストを減らせる
    n = N
    dv = d.values()
    if dv:
        n -= max(d.values())
    print(n)

main()

Submission status: Accepted

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

def main():
    n = int(input())
    arr = sorted(tuple(map(int, input().split())) for _ in range(n))
    cnt = {}
    for i in range(n):
        for j in range(i + 1, n):
            dif = (arr[j][0] - arr[i][0], arr[j][1] - arr[i][1])
            cnt.setdefault(dif, 0)
            cnt[dif] += 1
    print(n - max(cnt.values(), default=0))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# diverta2019-2B - Picking Up
def main():
    n = int(input())
    arr = sorted(tuple(map(int, input().split())) for _ in range(n))
    cnt = {}
    for i in range(n):
        for j in range(i + 1, n):
            dif = (arr[j][0] - arr[i][0], arr[j][1] - arr[i][1])
            cnt.setdefault(dif, 0)
            cnt[dif] += 1
    print(n - max(cnt.values(), default=0))


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

dist = []
for i in range(N):
    for j in range(N):
        if i == j:
            continue
        dx = x[i] - x[j]
        dy = y[i] - y[j]
        dist.append([dx, dy])

res = N
for p, q in dist:
    cnt = 0
    for i in range(N):
        for j in range(N):
            if i == j:
                continue
            if p == x[i] - x[j] and q == y[i] - y[j]:
                cnt += 1
    res = min(res, N - cnt)

print(res)