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:
n=int(input())
pts=[list(map(int,input().split())) for _ in range(n)]

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

ans=100

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

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

        p=x1-x2
        q=y1-y2

        visit=[0]*n
        
        cur=0
        for k in range(n):
            if visit[k]==1:
                continue
            cur+=1
            x3,y3=pts[k]
            cx=x3
            cy=y3
            while my_index(pts,[cx,cy])>=0:
                visit[my_index(pts,[cx,cy])]=1
                cx+=p
                cy+=q
            cx=x3
            cy=y3
            while my_index(pts,[cx,cy])>=0:
                visit[my_index(pts,[cx,cy])]=1
                cx-=p
                cy-=q
        
        ans=min(ans,cur)
    
print(ans)

Submission status: Accepted

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


def read():
    N = int(input().strip())
    XY = []
    for i in range(N):
        x, y = map(int, input().strip().split())
        XY.append((x, y))
    return N, XY


def solve(N, XY):
    if N == 1:
        return 1

    min_cost = 1000000
    for j in range(N):
        for i in range(j):
            rdict = defaultdict(list)
            x0, y0 = XY[i]
            x1, y1 = XY[j]
            p, q = x1 - x0, y1 - y0
            for k in range(N):
                x, y = XY[k]
                rdict[q * x - p * y].append((x, y))
            cost = 0
            for v in rdict.values():
                vs = list(sorted(v))
                x0, y0 = vs[0]
                for x1, y1 in vs:
                    if x1 - x0 != p or y1 - y0 != q:
                        cost += 1
                    x0, y0 = x1, y1
            min_cost = min(min_cost, cost)
    return min_cost


if __name__ == '__main__':
    inputs = read()
    print(solve(*inputs))

Submission status: Accepted

Solution code:
from collections import *

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

if N==1:
    print(1)
    exit()
    
cnt = defaultdict(int)

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

M = max(list(cnt.values()))
print(N-M)

Submission status: Accepted

Solution code:
N = int(input())
graph = []
for _ in range(N):
    x, y = map(int, input().split())
    graph.append([x, y])
if N == 1:
    print(1)
    exit()
ans = float('inf')
for i in range(N):
    for j in range(N):
        if i == j:
            continue
        p = graph[i][0] - graph[j][0]
        q = graph[i][1] - graph[j][1]
        vec_cnt = 0
        for k in range(N):
            for l in range(N):
                if p == graph[k][0] - graph[l][0] and q == graph[k][1] - graph[l][1]:
                    vec_cnt += 1
        ans = min(ans, N - vec_cnt)
print(ans)

Submission status: Accepted

Solution code:
from collections import *
n=int(input())
x=[0]*n
y=[0]*n
for i in range(n):
  x[i],y[i]=map(int,input().split())
a=[]
for i in range(n):
  for j in range(n):
    if i==j:continue
    a+=[(x[i]-x[j],y[i]-y[j])]
c=list(Counter(a).values())
print(n-max(c) if c else n)

Submission status: Accepted

Solution code:
import collections
n = int(input())
balls = []
for _ in range(n):
    x, y = map(int, input().split())
    balls.append([x, y])
# print(balls)
delta = []
for i in range(n):
    for j in range(n):
        if i == j:
            continue
        dx = balls[j][0] - balls[i][0]
        dy = balls[j][1] - balls[i][1]
        delta.append((dx, dy))

c_delta = collections.Counter(delta)
# print(c_delta)
if len(c_delta):
    print(n-c_delta.most_common()[0][1])
else:
    print(1)

Submission status: Accepted

Solution code:
from collections import defaultdict
n = int(input())
balls = []
diffs = [[None] * n for _ in range(n)]
for _ in range(n):
    x, y = [int(i) - 1 for i in input().split()]
    balls.append((x, y))

d = defaultdict(int)

# 各ボールの差分を計算する
for i in range(n):
    for j in range(n):
        ax, ay = balls[i]
        bx, by = balls[j]
        diffs[i][j] = (bx - ax, by - ay)
        if bx - ax != 0 or by - ay != 0:  # p≠0 または q≠0
            d[(bx - ax, by - ay)] += 1

_max = 0

for k, v in d.items():
    _max = max(_max, v)

print(n - _max)

Submission status: Accepted

Solution code:
from decimal import Decimal

N = int(input())

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

cnt ={}

for i in range(N):
    xi = xy[i][0]
    yi = xy[i][1]

    for j in range(i+1,N):
        xj = xy[j][0]
        yj = xy[j][1]

        x_dif =xi-xj
        y_dif = yi-yj
        if x_dif<0:
            x_dif = -x_dif
            y_dif = -y_dif
        elif x_dif == 0:
            y_dif = abs(y_dif)

        if (x_dif,y_dif)  in cnt.keys():
            cnt[x_dif,y_dif] += 1
        else:
            cnt[x_dif, y_dif] =1

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

Submission status: Accepted

Solution code:
class Union_Find():
    def __init__(self,N):
        """0,1,...,n-1を要素として初期化する.

        n:要素数
        """
        self.n=N
        self.parents=[-1]*N
        self.rank=[0]*N

    def find(self, x):
        """要素xの属している族を調べる.

        x:要素
        """
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        """要素x,yを同一視する.

        x,y:要素
        """
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.rank[x]>self.rank[y]:
            self.parents[x] += self.parents[y]
            self.parents[y] = x
        else:
            self.parents[y] += self.parents[x]
            self.parents[x] = y

            if self.rank[x]==self.rank[y]:
                self.rank[y]+=1

    def size(self, x):
        """要素xの属している要素の数.

        x:要素
        """
        return -self.parents[self.find(x)]

    def same(self, x, y):
        """要素x,yは同一視されているか?

        x,y:要素
        """
        return self.find(x) == self.find(y)

    def members(self, x):
        """要素xが属している族の要素.
        ※族の要素の個数が欲しいときはsizeを使うこと!!

        x:要素
        """
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        """族の名前のリスト
        """
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        """族の個数
        """
        return len(self.roots())

    def all_group_members(self):
        """全ての族の出力
        """
        return {r: self.members(r) for r in self.roots()}

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

#================================================
N=int(input())
P=[0]*N

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

M=float("inf")
for i in range(N):
    for j in range(N):
        p=P[j][0]-P[i][0]
        q=P[j][1]-P[i][1]

        U=Union_Find(N)
        for k in range(N):
            for l in range(N):
                if P[l]==(P[k][0]+p,P[k][1]+q):
                    U.union(k,l)

        M=min(M,U.group_count())
print(M)

Submission status: Accepted

Solution code:
import sys
import collections

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    N = int(input())
    XY = [[int(x) for x in input().split()] for _ in range(N)]

    c = collections.Counter()

    if N == 1:
        print(1)
        return

    for i in range(N):
        for j in range(N):
            if i == j:
                continue
            xi, yi = XY[i]
            xj, yj = XY[j]
            c[(xi - xj, yi - yj)] += 1

    print(N - c.most_common()[0][1])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict
n=int(input())
c=[]
for _ in range(n): c.append(list(map(int,input().split())))
dic=defaultdict(int)
for i in range(n):
    for j in range(n):
        if i==j: continue
        dic[(c[i][0]-c[j][0],c[i][1]-c[j][1])]+=1
if dict(dic): print(n-max(dic.values()))
else: print(1)

Submission status: Accepted

Solution code:
ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
import collections
import math
import itertools
import heapq as hq
n = ni()
if n==1:
    print(1)
    exit()
xy = []
for i in range(n):
    xy.append(tma())
co = collections.Counter()

for i in range(n):
    for j in range(n):
        if i==j:
            continue
        x1,y1 = xy[i]
        x2,y2 = xy[j]
        co[(x2-x1,y2-y1)] +=1

ans = 10**9
for num in co.values():
    ans = min(ans,n-num)
print(ans)

Submission status: Accepted

Solution code:
from collections import *
(n,),*p=[[*map(int,i.split())] for i in open(0)]
d=defaultdict(int)
for x, y in p:
    for a, b in p:
        d[(x-a, y-b)]+=(x,y)!=(a,b)
print(n-max(d.values()))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict

(n, ), *p = [[*map(int, i.split())] for i in open(0)]
d = defaultdict(int)
for i in range(n):
    for j in range(n):
            d[(p[i][0] - p[j][0], p[i][1] - p[j][1])] += i!=j
print(n - max(d.values()))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict

(n, ), *p = [[*map(int, i.split())] for i in open(0)]
d = defaultdict(int)
for i in range(n):
    for j in range(n):
        if i != j:
            d[(p[i][0] - p[j][0], p[i][1] - p[j][1])] += 1
print(n*(n<2) or n - max(d.values()))

Submission status: Accepted

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
from collections import Counter
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())

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

A = sorted(A)

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

freq = 0
for v in d.values():
    freq = max(freq, v)
print(N - freq)

Submission status: Accepted

Solution code:
import itertools

def main():
    N = int(input())
    z = []
    ans = 51
    for i in range(N):
        z.append(tuple(map(int, input().split())))
    z.sort(key=lambda x: x[1])
    z.sort(key=lambda x: x[0], reverse=True)
    if len(z) == 1:
        print(1)
        return
    for i, j in itertools.combinations(range(N), 2):
        p = z[i][0] - z[j][0]
        q = z[i][1] - z[j][1]
        ans = min(ans, solve(N, z, p, q))
    print(ans)

def solve(N, z, p, q):
    passlist = set()
    cnt = 0
    for i in range(N):
        if z[i] in passlist:
            continue
        x, y = z[i][0], z[i][1]
        for j in range(N):
            s, t = x-p, y-q
            if (s, t) not in z:
                cnt += 1
                break
            passlist.add((s, t))
            x, y = s, t
    return cnt

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from itertools import combinations


def main():
    N = int(input())
    points = [list(map(int, input().split())) for _ in range(N)]
    ans = N
    for i, j in combinations(range(N), 2):
        p1, p2 = points[i], points[j]
        if p1 == p2:
            continue
        dx, dy = p1[0] - p2[0], p1[1] - p2[1]
        cost = N
        for k, l in combinations(range(N), 2):
            p3, p4 = points[k], points[l]
            if (p3[0] + dx == p4[0] and p3[1] + dy == p4[1]) or \
                    (p4[0] + dx == p3[0] and p4[1] + dy == p3[1]):
                cost -= 1
        ans = min(ans, cost)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
(n,),*xy = [list(map(int, s.split())) for s in open(0)]

from collections import Counter
from itertools import combinations
from sys import exit

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

c = Counter()

for (xa,ya),(xb,yb) in combinations(xy,2):
    c[(xa-xb, ya-yb)] += 1
    c[(xb-xa, yb-ya)] += 1

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

Submission status: Accepted

Solution code:

from collections import defaultdict

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

X.sort()
ctr = defaultdict(int)
for i in range(N - 1):
    for j in range(i + 1, N):
        p = X[i][0] - X[j][0]
        q = X[i][1] - X[j][1]
        ctr[(p, q)] += 1
        ctr[(-p, -q)] += 1

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

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict

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

sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


def main():
    N = int(readline())
    if N==1:
        print(1)
        sys.exit()
    XY = list(list(map(int, readline().split())) for _ in range(N))
    d = defaultdict(int)
    for i in range(N-1):
        x1, y1 = XY[i]
        for j in range(i+1,N):
            x2, y2 = XY[j]
            x = x2-x1
            y = y2-y1
            d[x,y] += 1
            d[-x,-y] += 1
    print(N-max(d.values()))



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())  
  
dic = {}
for i in range(n):
  for j in range(n):
    if i!=j:
      x = X[i]-X[j]
      y = Y[i]-Y[j]
      dic[(x,y)] = dic.get((x,y),0) + 1

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

Submission status: Accepted

Solution code:
import sys,math,collections,itertools
input = sys.stdin.readline

N=int(input())
xy = []

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

for _ in range(N):
    xy.append(list(map(int,input().split())))

rxy = []
for i in range(N):
    for j in range(N):
        if i==j:
            continue
        rxy.append((xy[i][0]-xy[j][0],xy[i][1]-xy[j][1]))
cr = collections.Counter(rxy)
print(N-max(cr.values()))

Submission status: Accepted

Solution code:
def main():
    import sys

    def input(): return sys.stdin.readline().rstrip()

    n = int(input())
    x, y = [0]*n, [0]*n
    for i in range(n):
        x[i], y[i] = map(int, input().split())
    from collections import defaultdict
    xy = defaultdict(int)
    for i in range(n):
        for j in range(n):
            if i == j: continue
            xy[(x[i]-x[j], y[i]-y[j])] += 1
    if xy == {}:
        print(1)
        return
    p, q = max(xy, key=lambda x: xy[x])
    ans = n
    for i in range(n):
        for j in range(n):
            if i == j: continue
            if x[i]-x[j] == p and y[i]-y[j] == q:
                ans -= 1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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


def main():
    from itertools import combinations
    n = int(readline())
    mat = [list(map(int, readline().split())) for _ in range(n)]

    if n == 1:
        return print(1)

    ans = INF
    for com in combinations(range(n), r=2):
        first, second = com
        dx = mat[first][0] - mat[second][0]
        dy = mat[first][1] - mat[second][1]
        uf = UnionFind(n)
        for i in range(n):
            cx, cy = mat[i]
            for j in range(n):
                nx, ny = mat[j]
                if (cx - nx == dx and cy - ny == dy) or (-cx + nx == dx and - cy + ny == dy):
                    uf.union(i, j)
        ans = min(ans, uf.group_count())

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
(n,), *z = [[*map(int, o.split())] for o in open(0)]
if n == 1:
    print(1)
    exit()
from itertools import*
from collections import*
print(n - Counter((z[i][0] - z[j][0], z[i][1] - z[j][1]) for i, j in permutations(range(n), 2)).most_common()[0][1])

Submission status: Accepted

Solution code:
(n,),*a=[[*map(int,i.split())]for i in open(0)]
d={0:0}
for i,j in a:
    for x,y in a:
        if i!=x or j!=y:
            d[(i-x,j-y)]=d.get((i-x,j-y),0)+1
print(n-max(d.values()))

Submission status: Accepted

Solution code:
(n,),*a=[[*map(int,i.split())]for i in open(0)]
d={}
for i,j in a:
    for x,y in a:
        if i!=x or j!=y:
            d[(i-x,j-y)]=d.get((i-x,j-y),0)+1
print(n-max(list(d.values())+[0]))

Submission status: Accepted

Solution code:
from itertools import permutations
n = int(input())
point_ls = [0] * n
for i in range(n):
    point_ls[i] = list(map(int, input().split()))
ind_ls = [i for i in range(n)]
diff_ls = []
for start, end in permutations(ind_ls, 2):
    diff = [0] * 2
    diff[0] = point_ls[end][0] - point_ls[start][0]
    diff[1] = point_ls[end][1] - point_ls[start][1]
    diff_ls.append(diff)
ans = 0
for diff in diff_ls:
    same = 0
    for diff2 in diff_ls:
        if diff == diff2:
            same += 1
    ans = max(ans, same)
print(n-ans)

Submission status: Accepted

Solution code:
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    N = I()
    xy = [LI() for _ in range(N)]

    if N == 1:
        print(1)
    else:
        interval = []
        for i in range(N):
            for j in range(N):
                if i != j:
                    interval.append((xy[i][0] - xy[j][0], xy[i][1] - xy[j][1]))

        cnt = collections.Counter(interval)
        nocost = max(cnt.values())
        ans = N - nocost
        print(ans)

if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
from collections import Counter
N = int(input())
X = []
for _ in range(N):
  X.append(list(map(int, input().split())))
  
if N == 1:
  print(1)
  exit(0)
A = []
for i in range(N):
  for j in range(N):
    if i==j:
      continue
    A.append((X[i][0]-X[j][0], X[i][1]-X[j][1]))
    
C = Counter(A)
print(N - C.most_common()[0][1])

Submission status: Accepted

Solution code:
N = int(input())
INF = int(1e13)
A = [list(map(int, input().split())) for _ in range(N)]
X = [[[0, 0] for __ in range(N)] for _ in range(N)]
for i in range(N):
  for j in range(N):
    X[i][j] = [A[i][0]-A[j][0], A[i][1] - A[j][1]]
for i in range(N):
  X[i][i][0], X[i][i][1] = INF + 2*i, INF + 2*i+1
D = {}
for i in range(N):
  for j in range(N):
    if X[i][j][0]*(10*INF)+X[i][j][1] in D:
      D[X[i][j][0]*(10*INF)+X[i][j][1]] += 1
    else:
      D[X[i][j][0]*(10*INF)+X[i][j][1]] = 1
if N == 1:
  print(1)
else:
  print(N-max(D[i] for i in D))

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
from math import sqrt
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

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

        if x == y:
            return

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

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

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

    # これ追加
    def count_group(self):
        return len({self.find(x) for x in range(N)})

N = getN()
que = [getList() for i in range(N)]
if N == 1:
    print(1)
    exit()

dis = []
# [p, q]の通りは50C2通りある
for i in range(N):
    for j in range(i + 1, N):
        dis.append([que[i][0] - que[j][0], que[i][1] - que[j][1]])

ans = float('inf')
for p, q in dis:
    U = UnionFind(N)
    for i in range(N):
        for j in range(i + 1, N):
            if (que[i][0] + p == que[j][0] and que[i][1] + q == que[j][1]) or (que[i][0] - p == que[j][0] and que[i][1] - q == que[j][1]):
                U.union(i, j)
    ans = min(ans, U.count_group())
print(ans)

Submission status: Accepted

Solution code:
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

n = INT()
x = [LIST() for i in range(n)]
 
a = []
for i in range(n):
    for j in range(n):
        if i != j:
            a.append((x[j][0]-x[i][0], x[j][1]-x[i][1]))
 
a.sort()
count = 1
reg = 1

for i in range(1, len(a)):
    if a[i][:] == a[i-1][:]:
        count += 1
        reg = max(reg, count)
    else:
        count = 1

if n == 1:
    ans = n
else:
    ans = n - reg

print(ans)

Submission status: Accepted

Solution code:
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

n = INT()
x = [LIST() for i in range(n)]
reg = 0

for i in range(n):
    for j in range(n):
        if i != j:
            p = x[j][0] - x[i][0]
            q = x[j][1] - x[i][1]
            count = 0
            for k in range(n):
                for l in range(n):
                    if x[l][0] - x[k][0] == p  and x[l][1] - x[k][1] ==  q:
                        count += 1
            reg = max(reg, count)

ans = n - reg
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
n = int(input())
points = [tuple(map(int, input().split())) for _ in range(n)]

cnt = defaultdict(int)
cnt[(0, 0)] = 0
for i in range(n):
    for j in range(n):
        if i == j:
            continue
        cnt[(points[i][0] - points[j][0], points[i][1] - points[j][1])] += 1

# print(cnt)
ans = n - max(cnt.values())
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
from itertools import combinations

input = sys.stdin.readline


def main():
    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)
        sys.exit()

    vector = defaultdict(int)
    for a, b in combinations(range(N), 2):
        dx = x[a] - x[b]
        dy = y[a] - y[b]
        if dx == 0:
            vector[(0, abs(dy))] += 1
        elif dx > 0:
            vector[(dx, dy)] += 1
        else:
            vector[(-dx, -dy)] += 1

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# ベクトルを固定して全探索まではわかる 実装がわからん
# いやべつに順番は関係ないのか？ 「残っているボールを 1つ選んで回収する。」

n = int(input())
if n == 1:
    print(1)  # 「ただし、1つ目に選んだボールについては必ずコスト 1かかる。」
    exit()
points = []
for _ in range(n):
    points.append(list(map(int, input().split())))

ans = 10**18
for p in range(n):
    for q in range(n):
        if p == q:
            continue
        vector = [points[p][0] - points[q][0], points[p][1] - points[q][1]]
        tmp = 0
        for i in range(n):
            for j in range(n):
                if i == j:
                    continue
                if points[i][0] - points[j][0] == vector[
                        0] and points[i][1] - points[j][1] == vector[1]:
                    tmp += 1

        ans = min(ans, n - tmp)

print(ans)

Submission status: Accepted

Solution code:
n=int(input())

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

ball_xy = []
for _ in range(n):
    x, y = (int(x) for x in input().split())
    ball_xy.append([x, y])

distance = {}

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

cost_0 = max(distance.values())

print(n-cost_0)

Submission status: Accepted

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

a = {}
for i in range(n):
    for j in range(n):
        if i == j:
            continue
        v = x[j] - x[i], y[j] - y[i]
        if v not in a:
            a[v] = 1
        else:
            a[v] += 1
ans = n
# print("a =", a)
if len(a.values()) > 0:
    ans -= max(a.values())
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
if n==1:
    print(1)
    exit()
x=[]
for i in range(n):
    a,b=map(int,input().split())
    x.append([a,b])
x.sort()
ans=float("inf")
for i in range(n-1):
    for j in range(i+1,n):
        p,q=x[j][0]-x[i][0],x[j][1]-x[i][1]
        cnt=0
        flg=[False for i in range(n)]
        for k in range(n):
            if flg[k]==False:
                flg[k]=True
                cnt+=1
                fl=True
                xx,yy=x[k][0],x[k][1]
                while fl:
                    nx,ny=xx+p,yy+q
                    if [nx,ny] in x:
                        a=x.index([nx,ny])
                        flg[a]=True
                        xx,yy=nx,ny
                    else:
                        fl=False
        if cnt<ans:
            ans=cnt
print(ans)

Submission status: Accepted

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

res = 0
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 ii in range(N):
            for jj in range(N):
                pp = x[jj] - p
                qq = y[jj] - q
                if ii == jj:
                    continue
                if pp == x[ii] and qq == y[ii]:
                    cnt += 1
            res = max(res, cnt)

print(N - res)

Submission status: Accepted

Solution code:
from collections import Counter
n = int(input())
XY = [list(map(int,input().split())) for _ in range(n)]
dXY = Counter([])
for i in range(n):
    for j in range(n):
        if i!=j:
            dXY += Counter([str(XY[i][0]-XY[j][0])+'_'+str(XY[i][1]-XY[j][1])])
if n==1:
    print(1)
else:
    print(n-dXY.most_common()[0][1])