Problem:


Score : 300 points

Problem Statement

There are N balls in a two-dimensional plane. The i-th ball is at coordinates (x_i, y_i).

We will collect all of these balls, by choosing two integers p and q such that p \neq 0 or q \neq 0 and then repeating the following operation:

Choose a ball remaining in the plane and collect it. Let (a, b) be the coordinates of this ball. If we collected a ball at coordinates (a - p, b - q) in the previous operation, the cost of this operation is 0. Otherwise, including when this is the first time to do this operation, the cost of this operation is 1.

Find the minimum total cost required to collect all the balls when we optimally choose p and q.

Constraints

1 \leq N \leq 50

|x_i|, |y_i| \leq 10^9

If i \neq j, x_i \neq x_j or y_i \neq y_j.

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
x_1 y_1
:
x_N y_N

Output

Print the minimum total cost required to collect all the balls.

Sample Input 1

2
1 1
2 2

Sample Output 1

1

If we choose p = 1, q = 1, we can collect all the balls at a cost of 1 by collecting them in the order (1, 1), (2, 2).

Sample Input 2

3
1 4
4 6
7 8

Sample Output 2

1

If we choose p = -3, q = -2, we can collect all the balls at a cost of 1 by collecting them in the order (7, 8), (4, 6), (1, 4).

Sample Input 3

4
1 1
1 2
2 1
2 2

Sample Output 3

2



Sample input:
2
1 1
2 2


Sample output:
1

Submission status: Accepted

Solution code:
from collections import defaultdict

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

d = defaultdict(int)
for i, (xi, yi) in enumerate(xy):
  for j, (xj, yj) in enumerate(xy):
    p, q = xi - xj, yi - yj
    d[(p, q)] += 1

d.pop((0, 0))
ans = N
for k in d:
  ans = min(ans, N-d[k])

print(ans)

Submission status: Accepted

Solution code:
import collections
import itertools

def Z(): return int(input())
def ZZ(): return [int(_) for _ in input().split()]

def main():
    N = Z()
    P = [ZZ() for _ in range(N)]
    vecs = set()
    d = collections.defaultdict(int)
    output = 1
    if N == 1:
        print(output)
        return

    for i, j in itertools.combinations(range(N), 2):
        dx, dy = P[i][0] - P[j][0], P[i][1] - P[j][1]
        if dx < 0: dx, dy = -dx, -dy
        vecs.add((dx, dy))

    c = 0
    for v in list(vecs):
        cc = 0
        for i, j in itertools.combinations(range(N), 2):
            if (P[i][0] - P[j][0] == v[0] and P[i][1] - P[j][1] == v[1]) or (P[i][0] - P[j][0] == -v[0] and P[i][1] - P[j][1] == -v[1]):
                cc += 1
        c = max(c, cc)
    output = (N - c)
    print(output)
    return

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import combinations
from collections import Counter

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

if N != 1:
    delta = []
    for i, j in combinations(list(range(N)), 2):
        if xy[i][0] < xy[j][0]:
            p0 = xy[i][:]
            p1 = xy[j][:]
        else:
            p0 = xy[j][:]
            p1 = xy[i][:]
        delta.append((p1[0] - p0[0], p1[1] - p0[1]))
    cnt = Counter(delta)
    dlt = cnt.most_common()
    
def calc(dd):
    visited =set()
    c = 0
    for i in range(N):
        if xy[i] in visited:continue
        c += 1
        temp = [[xy[i], c]]
        while temp:
            q = temp.pop()
            for n in [1, -1]:
                x1, y1 = q[0][0] + n * dd[0], q[0][1] + n * dd[1]
                if not (x1, y1) in visited and (x1, y1) in xy:
                    temp.append([(x1, y1), q[1]])
                    visited.add((x1, y1))
    return c

if N == 1: print(1)
else:
    ans = []
    pre = dlt[0][1]
    for lst in dlt:
        ans.append(calc(lst[0]))
    print(min(ans))

Submission status: Accepted

Solution code:
import itertools
from collections import defaultdict

n = int(input())
xy = []
for _ in range(n):
    xy.append(list(map(int, input().split())))
    
dd = defaultdict(int)
for lst in itertools.combinations(xy, 2):
    dx = lst[0][0] - lst[1][0]
    dy = lst[0][1] - lst[1][1]
    dd[(dx, dy)] += 1
    dd[(-dx, -dy)] += 1
ans = 0
for i, j in dd.items():
    ans = max(ans, j)
print(n - ans)

Submission status: Accepted

Solution code:
n = int(input())
xy = []
for _ in range(n):
    x, y = map(int, input().split())
    xy.append((x, y))
dxdy = {}
if n==1:
    print(1)
    exit()
for i in range(n-1):
    for j in range(i+1, n):
        dx = xy[i][0] - xy[j][0]
        dy = xy[i][1] - xy[j][1]
        if dx<0:
            dx, dy = -dx, -dy
        elif dx==0:
            dx, dy = dx, abs(dy)
        if (dx, dy) in dxdy:
            dxdy[(dx, dy)] += 1
        else:
            dxdy[(dx, dy)] = 1
print(n-max(dxdy.values()))

Submission status: Accepted

Solution code:
from collections import Counter


N = int(input())
M = [tuple(map(int, input().split())) for _ in range(N)]
Map = []
if N == 1:
    print(1)
    exit()
for i in range(N):
    x1, y1 = M[i]
    for j in range(N):
        if i == j:
            continue
        x2, y2 = M[j]
        Map.append((x2 - x1, y2 - y1))
MapC = Counter(Map)
print(N - MapC.most_common(1)[0][1])

Submission status: Accepted

Solution code:
from itertools import combinations
from collections import defaultdict

n = int(input())

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

conter = defaultdict(int)
for com in combinations(range(n), 2):
    x1, y1 = xy[com[0]]
    x2, y2 = xy[com[1]]
    conter[(x2-x1, y2-y1)] += 1
    conter[(x1-x2, y1-y2)] += 1

ans = 0
for k, v in conter.items():
    ans = max(ans, v)

print(n - ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

def diverta192_b():
    N = int(input())
    P = [tuple(map(int, input().split())) for _ in range(N)]
    if len(P) == 1:
        print(1)  # 座標が1つだけ与えられる場合は即終了
        return

    dcnt = defaultdict(int)  # import忘れずに
    for i in range(N):
        xi, yi = P[i]
        for j in range(i):
            xj, yj = P[j]
            dcnt[(xi-xj, yi-yj)] += 1
            dcnt[(xj-xi, yj-yi)] += 1  # 逆向きもカウントする(都合よいほうを使う)
    most = sorted(dcnt.values(), reverse=True)[0]  # 最も多いカウントを取り出す
    ans = N - most
    print(ans)

diverta192_b()

Submission status: Accepted

Solution code:
from collections import defaultdict

def diverta192_b():
    N = int(input())
    P = [tuple(map(int, input().split())) for _ in range(N)]
    if len(P) == 1:
        print(1)
        return
    dcnt = defaultdict(int)
    for i in range(N):
        xi, yi = P[i]
        for j in range(i):
            xj, yj = P[j]
            dx1, dy1 = xi-xj, yi-yj
            dx2, dy2 = xj-xi, yj-yi
            dcnt[(dx1,dy1)] += 1
            dcnt[(dx2,dy2)] += 1
    most = sorted(dcnt.values(), reverse=True)[0]
    ans = N - most
    print(ans)

diverta192_b()

Submission status: Accepted

Solution code:
n = int(input())
dat = []
for i in range(n):
    a,b = map(int, input().split())
    dat.append([a,b])
dat2 = []
if n == 1:
    print(1)
else:
    for i in range(n):
        x1, y1 = dat[i]
        for j in range(n):
            if i == j:
                continue
            x2, y2 = dat[j]
            dat2.append( (x1-x2, y1-y2) )
    import collections
    c = collections.Counter(dat2)
    #print(c)
    ta, tb = c.most_common(1)[0][0]
    res = 0
    for i in range(n):
        canwarp = False
        x1, y1 = dat[i]
        for j in range(n):
            if i == j:
                continue
            x2, y2 = dat[j]
            if x1-x2 == ta and  y1-y2 == tb:
                canwarp = True
        if canwarp:
            continue
        else:
            res += 1
    print(res)

Submission status: Accepted

Solution code:
n=int(input())
L=[]
for _ in range(n):
    l=list(map(int,input().split()))
    L.append(l)
if n==1:
    print(1)
    exit()
pq=[]
ans=[]
for i in range(n-1):
    for j in range(i+1,n):
        x=L[i][0]-L[j][0]
        y=L[i][1]-L[j][1]
        if [x,y] in pq:
            ans[pq.index([x,y])] += 1
        elif [-x,-y] in pq:
            ans[pq.index([-x,-y])] += 1
        else:
            pq.append([x,y])
            ans.append(1)

print(n-max(ans))

Submission status: Accepted

Solution code:
import sys

# import re
import math
import collections
# import decimal
import bisect
# import itertools
import fractions
# import functools
import copy
import heapq
import decimal
# import statistics
import queue

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===


def main():
    n = ni()
    pos = []
    for i in range(n):
        x, y = ns()
        pos.append((x, y))

    res = dict()
    for i in range(n):
        for j in range(n):
            if i == j: continue
            tmp_key = (pos[j][0] - pos[i][0], pos[j][1] - pos[i][1])
            if tmp_key in res.keys():
                res[tmp_key].append((pos[i], pos[j]))
            else:
                res[tmp_key] = [(pos[i], pos[j])]

    ans = 0
    for k in res.keys():
        ans = max(ans, len(res[k]))

    print(n-ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
ball = [list(map(int,input().split())) for i in range(n)]
ans = 0
for x in range(n):
    for y in range(n):
        if x == y:
            continue
        else:
            p = ball[x][0] - ball[y][0]
            q = ball[x][1] - ball[y][1]
            cou = 0
            for i in range(n):
                for j in range(n):
                    if ball[i][0]-ball[j][0] == p and ball[i][1]-ball[j][1] == q:
                        cou += 1
            ans = max(ans,cou)
print(n-ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

n = int(input())

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

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

from collections import defaultdict
d = defaultdict(lambda:0)

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

        p = x[j]-x[i]
        q = y[j]-y[i]

        d[p*10**9+q] +=1

dv = d.values()
mad =max(dv)

print(n-mad)

Submission status: Accepted

Solution code:
from collections import defaultdict

n=int(input())
if n==1:
    print(1)
    exit()
x=[]
y=[]
for i in range(n):
    xx,yy=list(map(int,input().split()))
    x.append(xx)
    y.append(yy)

dif=defaultdict(int)

for i in range(n):
    for j in range(n):
        if i==j:continue
        p=x[j]-x[i]
        q=y[j]-y[i]
        dif[(p,q)]+=1

dif=sorted(dif.items(),key=lambda x:x[1],reverse=True)
ans=n-dif[0][1]

print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


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


def main():
    N = int(input())
    if N == 1:
        print(1)
        return

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

    cnt = defaultdict(int)
    for i in range(N):
        for j in range(N):
            if i == j:
                continue

            dx = X[j] - X[i]
            dy = Y[j] - Y[i]
            cnt[(dx, dy)] += 1

    cnt = sorted(cnt.items(), key=lambda x: x[1], reverse=True)
    ans = N - cnt[0][1]
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

for i in range(n):
    for j in range(n):
        if i==j:continue
        p,q=l[i][0]-l[j][0],l[i][1]-l[j][1]
        ret=0
        pre=sorted(l,reverse=1,key=lambda x:p*x[0]+q*x[1])
        while pre:
            ret+=1
            x,y=pre.pop()
            while  [x+p,y+q] in pre:
                pre.remove([x+p,y+q])
                x,y=[x+p,y+q]
        ans=min(ans,ret)
print(ans)

Submission status: Accepted

Solution code:
ans=float("INF")
n=int(input())
l=[list(map(int,input().split())) for i in range(n)]

for i in range(n):
    for j in range(n):

        p,q=l[i][0]-l[j][0],l[i][1]-l[j][1]
        ret=0
        pre=sorted(l,reverse=1,key=lambda x:p*x[0]+q*x[1])
        while pre:
            ret+=1
            x,y=pre.pop()
            while  [x+p,y+q] in pre:
                pre.remove([x+p,y+q])
                x,y=[x+p,y+q]
        ans=min(ans,ret)
print(ans)

Submission status: Accepted

Solution code:
ans=float("INF")
n=int(input())
l=[list(map(int,input().split())) for i in range(n)]
if n==1:print(1);exit()
for i in range(n):
    for j in range(n):
        if i==j:continue
        p,q=l[i][0]-l[j][0],l[i][1]-l[j][1]
        ret=0
        pre=sorted(l,reverse=1,key=lambda x:p*x[0]+q*x[1])
        while pre:
            ret+=1
            x,y=pre.pop()
            while  [x+p,y+q] in pre:
                pre.remove([x+p,y+q])
                x,y=[x+p,y+q]
        ans=min(ans,ret)
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
dots=[]
for i in range(n):
    x,y=map(int,input().split())
    dots.append((x,y))
dots=sorted(sorted(dots, key=lambda x:x[1]))
#print(dots)
from itertools import combinations

combs=combinations(dots,r=2)
tmp=0
for c in combs:
    c=sorted(c)
    dx=c[1][0]-c[0][0]
    dy=c[1][1]-c[0][1]
    cnt=0
    for i in range(n):
        subdot=(dots[i][0]+dx,dots[i][1]+dy)
        if subdot in dots:
            cnt+=1
    tmp=max(tmp,cnt)
print(n-tmp)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
from itertools import combinations
from collections import Counter
def main():
    n=int(input())
    if n==1:
        print(1)
        sys.exit()
    XY=[tuple(map(int,input().split())) for i in range(n)]
    XY.sort()
    PQ=[]
    for i in range(n-1):
        x1=XY[i]
        for j in range(i+1,n):
            x2=XY[j]
            PQ.append((x2[0]-x1[0],x2[1]-x1[1]))
    print(n-Counter(PQ).most_common(1)[0][1])

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
from itertools import combinations
from collections import Counter
def main():
    n=int(input())
    if n==1:
        print(1)
        sys.exit()
    XY=[tuple(map(int,input().split())) for i in range(n)]
    XY.sort()
    lis=list(combinations(XY,2))
    PQ=[]
    for l in lis:
        PQ.append((l[1][0]-l[0][0],l[1][1]-l[0][1]))
    x=Counter(PQ).most_common(1)[0][1]
    print(n-x)

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/diverta2019-2/tasks/diverta2019_2_b

n = int(input())
ball = []
s = set()
for _ in range(n):
    x, y = map(int, input().split())
    ball.append((x, y))
    s.add((x, y))

ans = n
for i in range(n):
    x, y = ball[i]
    for j in range(n):
        dx, dy = x - ball[j][0], y - ball[j][1]
        if dx == 0 and dy == 0:
            continue
        point = 0
        for k in range(n):
            a, b = ball[k][0] - dx, ball[k][1] - dy
            if (a, b) in s:
                point += 1
        ans = min(ans, n - point)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
if n== 1:
  print(1)
  exit()
pos = []
diff = []
for _ in range(n):
  x,y = map(int,input().split())
  for px,py in pos:
    diff.append((x-px, y-py))
    diff.append((px-x, py-y))
  pos.append((x,y))
from collections import Counter
diff = Counter(diff).most_common()
x,y = diff[0][0]
count = diff[0][1]
if x== y == 0:
  x,y = diff[1][0]
  count = diff[1][1]
print(n-count)

Submission status: Accepted

Solution code:
from collections import deque
n=int(input())
ans=10**18
xy=[list(map(int,input().split())) for _ in range(n)]
d=dict()
for i in range(n):
    a,b=xy[i]
    d[(a,b)]=i
def bfs(s,p,q,visited):
    queue=deque([s])
    visited[s]=1
    while queue:
        x=queue.popleft()
        a,b=xy[x]
        if (a+p,b+q) in d:
            idx=d[(a+p,b+q)]
            if visited[idx]==0:
                visited[idx]=1
                queue.append(idx)
        if (a-p,b-q) in d:
            idx=d[(a-p,b-q)]
            if visited[idx]==0:
                visited[idx]=1
                queue.append(idx)
for i in range(n-1):
    ai,bi=xy[i]
    for j in range(i+1,n):
        aj,bj=xy[j]
        p,q=ai-aj,bi-bj
        cnt=0
        visited=[0]*n
        for k in range(n):
            if visited[k]==0:
                bfs(k,p,q,visited)
                cnt+=1
        ans=min(ans,cnt)
if n==1:
    ans=1
print(ans)
#print(d)

Submission status: Accepted

Solution code:
n = int(input())
d = dict()
p = []
for i in range(n):
    x,y = map(int,input().split())
    for j in p:
        if str(x-j[0])+" "+str(y-j[1]) in d:
            d[str(x-j[0])+" "+str(y-j[1])] += 1
        else:
            d[str(x-j[0])+" "+str(y-j[1])] = 1
        if str(j[0]-x)+" "+str(j[1]-y) in d:
            d[str(j[0]-x)+" "+str(j[1]-y)] += 1
        else:
            d[str(j[0]-x)+" "+str(j[1]-y)] = 1
    p.append([x,y])

if len(d.values()) == 0:
    ans = 0
else:
    ans = max(d.values())
print(n-ans)

Submission status: Accepted

Solution code:
n=int(input())
xys=[list(map(int,input().split())) for _ in range(n)]
vec = []
pqs = []
for i in range(n):
    for j in range(i+1,n):
        pqs.append([(xys[i][0]-xys[j][0]),(xys[i][1]-xys[j][1])])
        pqs.append([-(xys[i][0]-xys[j][0]),-(xys[i][1]-xys[j][1])])
pqs.sort()
import collections

cnt = 1
cntMax = 0
for i in range(1,len(pqs)+1):
    if i == len(pqs):
        cntMax = max(cntMax,cnt)
    elif pqs[i] == pqs[i-1]:
        cnt += 1
    else:
        cntMax = max(cntMax,cnt)
        cnt = 1
print(n-cntMax)

Submission status: Accepted

Solution code:
n = int(input())
all_li = []
for _ in range(n):
    tmp = list(map(int,input().split()))
    all_li.append(tmp)
if len(all_li) == 1:
    print(1)
    exit()
lee = len(all_li)
vector_map = {}
for i in range(n):
    for j in range(n):
        if i == j:
            continue
        a = all_li[i][0]
        b = all_li[i][1]
        c = all_li[j][0]
        d = all_li[j][1]
        if (c-a,d-b) in vector_map:
            vector_map[(c-a,d-b)] += 1
        else:
            vector_map[(c-a,d-b)] = 1
m = max(vector_map.values())
print(n-m)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/diverta2019-2/tasks/diverta2019_2_b

n = int(input())
X, Y = [], []
for _ in range(n):
    xi, yi = map(int, input().split())
    X.append(xi)
    Y.append(yi)
# print(X)
# print(Y)

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

# PQをバラすとだめ？
posPQ = []
score = int(1e18)
for i in range(n):
    xi, yi = X[i], Y[i]
    for j in range(n):
        if i == j:
            continue
        xj, yj = X[j], Y[j]
        p = xj - xi
        q = yj - yi

        # posPQ.append((dx, dy))
        count = n
        for k in range(n):
            for l in range(n):
                if X[l] - X[k] == p and Y[l] - Y[k] == q:
                    count -= 1
        # print(p, q, count)
        score = min(score, count)
print(score)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 5 + 10)


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


def resolve():
    N = int(input())
    if N==1:
        print(1)
    else:
        X, Y = [0] * N, [0] * N
        for i in range(N):
            X[i], Y[i] = map(int, input().split())
        ans = 10 ** 10
        for i in range(N):
            for j in range(N):
                if i != j:
                    p = X[j] - X[i]
                    q = Y[j] - Y[i]
                else:
                    continue
                sub = 0
                for k in range(N):
                    for l in range(N):
                        if X[l] - X[k] == p and Y[l] - Y[k] == q:
                            sub += 1
                ans = min(ans, N - sub)
    
        print(ans)


resolve()

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n = int(input())
    XY = sorted([list(map(int, input().split())) for _ in range(n)])

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

    res = n
    for i in range(n):
        x1, y1 = XY[i]
        for j in range(n):
            if i == j:
                continue
            x2, y2 = XY[j]
            dx, dy = x2 - x1, y2 - y1

            cnt = 0
            for k in range(n):
                x3, y3 = XY[k]
                for l in range(n):
                    if k == l:
                        continue
                    x4, y4 = XY[l]
                    if dx == x4 - x3 and dy == y4 - y3:
                        cnt += 1

            res = min(res, n - cnt)

    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
def main():
    import sys
    from collections import defaultdict
    input = sys.stdin.readline
    N = int(input())
    if N == 1:
        print(1)
        exit()
    XY = [0] * N
    for i, (x, y) in enumerate([[int(x) for x in input().strip().split()] for _ in range(N)]):
        XY[i] = (x, y)
    XY.sort(key=lambda x:(x[0], x[1]))

    dic = defaultdict(int)
    for d in range(1, N):
        for i in range(N-d):
            dic[(XY[i+d][0]-XY[i][0], XY[i+d][1]-XY[i][1])] += 1
            dic[(XY[i][0]-XY[i+d][0], XY[i][1]-XY[i+d][1])] += 1

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import Counter

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

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

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

ans = N
diff = []

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

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

Submission status: Accepted

Solution code:
from collections import defaultdict
n=int(input())
xy=[list(map(int,input().split())) for _ in range(n)]
if n==1:
  print(1)
  exit()
d=defaultdict(lambda:0)
for i in range(n-1):
  for j in range(i+1,n):
    dx=xy[i][0]-xy[j][0]
    dy=xy[i][1]-xy[j][1]
    d[(dx,dy)]+=1
    d[(-dx,-dy)]+=1
print(n-max(d.values()))
#for k,v in d.items():
#  print(k,v)

Submission status: Accepted

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

ans = N

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

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
from itertools import permutations
n=int(input())
if n==1:print(1);exit()
XY=[list(map(int,input().split())) for _ in range(n)]
A=[(X[0]-Y[0],X[1]-Y[1]) for X,Y in permutations(XY,2)]
print(n-max(Counter(A).values()))

Submission status: Accepted

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

D={}
for i in range(N-1):
    t1=L[i]
    L2=L[i+1:]
    for t2 in L2:
        x1,y1=t1
        x2,y2=t2
        d1=(x2-x1,y2-y1)
        d2=(x1-x2,y1-y2)
        if d1 in D:
            D[(x2-x1,y2-y1)]+=1
        else:
            D[(x2-x1,y2-y1)]=1
        if d2 in D:
            D[(x1-x2,y1-y2)]+=1
        else:
            D[(x1-x2,y1-y2)]=1

print(max(N-max(D.values()),0))

Submission status: Accepted

Solution code:
n=int(input())
if n==1:
    print(1)
    exit()
    
x=[0]*n
y=[0]*n

for i in range(n):
    x[i],y[i]=map(int,input().split())
dis=[]
for i in range(n):
    for j in range(n):
        if i==j:
            continue
        dis.append((x[j]-x[i],y[j]-y[i]))
        
from collections import Counter
c=Counter(dis).most_common()[0]
print(n-c[1])

Submission status: Accepted

Solution code:
import collections

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

div = []
for i in range(N):
    for j in range(N):
        if(i == j):
            continue
        div.append(tuple((X[i][0]-X[j][0], X[i][1]-X[j][1])))
        
c = collections.Counter(div)
c_s = sorted(c.items(), key=lambda x:x[1], reverse=True)

if(N == 1):
    print(1)
else:
    print(N-c_s[0][1])

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from collections import defaultdict

n = int(readline())
xy = [tuple(map(int, readline().split())) for _ in range(n)]
dict = defaultdict(int)
dict[0] = 0
for i, check in enumerate(xy):
    for dxy in xy[i + 1:]:
        y, x = check[0], check[1]
        dy, dx = dxy[0], dxy[1]
        dict[(y - dy, x - dx)] += 1
        dict[(dy - y, dx - x)] += 1
print(n - max(dict.values()))

Submission status: Accepted

Solution code:
N=int(input())
s=[list(map(int, input().split())) for i in range(N)]
d={}
for i in range(N-1):
    for j in range(i+1,N):
        a=s[i]
        b=s[j]
        t=(a[0]-b[0],a[1]-b[1])
        if t in d:
            d[t]+=1
        else:
            d[t]=1
        t=(b[0]-a[0],b[1]-a[1])
        if t in d:
            d[t]+=1
        else:
            d[t]=1
m=0
for i in d.values():
    if i>m:
        m=i
print(N-m)

Submission status: Accepted

Solution code:
n = int(input())
INF = 114514191981036436433-4
xy = []
for i in range(n):
    x,y = map(int,input().split())
    xy.append((x,y))
    
a = n
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]
        ans = n
        
        for k in range(n):
            for l in range(n):
                xx,yy = xy[k][0] - xy[l][0] , xy[k][1] - xy[l][1]
                if xx == p and yy == q:
                    ans -= 1
                    
        a = min(a,ans)
        
print(a)

Submission status: Accepted

Solution code:
import sys
import math  # noqa
import bisect  # noqa
import queue  # noqa


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


def main():
    N = int(input())

    if N == 1:
        return print(1)

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

    cnt = {}
    for i in range(N):
        for j in range(N):
            if i == j:
                continue
            rx = X[i] - X[j]
            ry = Y[i] - Y[j]
            if (rx, ry) not in cnt:
                cnt[(rx, ry)] = 1
            else:
                cnt[(rx, ry)] += 1
            if (-rx, -ry) not in cnt:
                cnt[(-rx, -ry)] = 1
            else:
                cnt[(-rx, -ry)] += 1

    cnt = [[v, k] for k, v in cnt.items()]
    cnt.sort(reverse=True)
    res = N - cnt[0][0] // 2
    print(res)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

    d = {}
    for i in range(N):
        tmp = set()
        for j in range(N):
            if i == j:
                continue
            dx = xy[i][0] - xy[j][0]
            dy = xy[i][1] - xy[j][1]

            if (dx, dy) in tmp:
                continue
            if (dx, dy) not in d:
                d[(dx, dy)] = 1
            else:
                d[(dx, dy)] += 1
            tmp.add((dx, dy))

    d = sorted(d.items(), key=lambda x: x[1], reverse=True)
    cnt = d[0][1]
    print(N - cnt)

main()

Submission status: Accepted

Solution code:
import sys


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


sys.setrecursionlimit(10 ** 9)


def main():
    N = int(input())
    XY = [list(map(int, input().split())) for _ in range(N)]
    P = []
    Q = []
    if N == 1:
        print(1)
        return
    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]
            P.append(p)
            Q.append(q)
    ans = float("inf")

    for p, q in zip(P, Q):
        a = N
        for i in range(N):
            x, y = XY[i][0], XY[i][1]
            if [x + p, y + q] in XY:
                a -= 1
        if a < ans:
            ans = a
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import Counter

if __name__ == "__main__":
    n = int(input())
    pos = list()
    for i in range(n):
        pos.append(list(map(int, input().split())))

    # まず1個のボールを最初選びそこから次のボールを選んだときの距離をp,qとして
    # それぞれの組み合わせの最汎値を求める
    dist = list()
    for i in range(n):
        for j in range(n):
            if i != j:
                tmp = (pos[j][0] - pos[i][0], pos[j][1]-pos[i][1])
                dist.append(tmp)

    # most_comon(n)とすると、最も出現回数が多い順からn要素を抽出する
    pq = Counter(dist).most_common(1)

    print(n - pq[0][1] if n != 1 else 1)

Submission status: Accepted

Solution code:
from collections import defaultdict
N = int(input())
d = defaultdict(int)
XY = sorted([list(map(int,input().split())) for _ in range(N)])
for i in range(N):
  for j in range(i):
    d[(XY[i][0] - XY[j][0], XY[i][1] - XY[j][1])] += 1
print(N - max(d.values(), default=0))

Submission status: Accepted

Solution code:
n = int(input())
xy = sorted([tuple(map(int,input().split())) for i in range(n)])
if n==1:
    print(1)
    exit()
dif = []
for i in range(n):
    for j in range(i+1,n):
        dif.append(tuple([xy[j][0]-xy[i][0],xy[j][1]-xy[i][1]]))
from collections import Counter
c = Counter(dif)
print(n-max(c.values()))

Submission status: Accepted

Solution code:
import copy
import math

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

def dfs(parent, p, q):
    seen[parent] = True
    for child in range(N):
        # print(child)
        if seen[child] == False:
            x, y = xy[child]
            if x + p == xy[parent][0] and y + q == xy[parent][1] or \
                    x - p == xy[parent][0] and y - q == xy[parent][1]:
                dfs(child, p, q)


m = N
for i in range(N - 1):
    for j in range(i + 1, N):
        p = xy[i][0] - xy[j][0]
        q = xy[i][1] - xy[j][1]
        cnt = 0
        seen = [False] * N
        for start in range(N):
            if seen[start] == False:
                dfs(start, p, q)
                cnt += 1
                # print(tosee)
        m = min(cnt, m)
        # print(p, q, group)
print(m)

Submission status: Accepted

Solution code:
from operator import itemgetter
from collections import defaultdict
n = int(input())
if n == 1:
  print(1)
  exit()
xy = sorted([list(map(int, input().split())) for i in range(n)], key = itemgetter(0,1))
a = defaultdict(int)
for key,(x1,y1) in enumerate(xy):
  for x2,y2 in xy[key+1:]:
    p,q = x2-x1, y2-y1
    if p != 0 or q != 0:
      a[(p,q)] += 1
ans = n - max(a.values())
print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations
from collections import Counter
N=int(input())
XY=[list(map(int,input().split())) for _ in range(N)]
if N==1:print(1);exit()
a=[((A[0]-B[0]),(A[1]-B[1])) for A,B in permutations(XY,2)]
cnt = Counter(a)
print(N-cnt.most_common()[0][1])