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

N=int(input())
xlist=[]
ylist=[]
dict = {}
for i in range(N):
  x, y = map(int, stdin.readline().rstrip().split())
  xlist.append(x)
  ylist.append(y)

for i in range(N):
  for j in range(N):
    if i != j:
      tupleStr=str(xlist[i] - xlist[j])+","+str(ylist[i] - ylist[j])
      if tupleStr in dict:
        dict[tupleStr]+=1
      else:
        dict[tupleStr]=1

maxNum=0
for val in dict.values():
  maxNum = max(maxNum, val)

print(N-maxNum)

Submission status: Accepted

Solution code:
from collections import Counter
import sys
n=int(input())
lst=[]
for i in range(n):
  X,Y=map(int,input().split())
  lst.append([X,Y])
lst_2=sorted(lst,key=lambda x: x[0])
lst_3=sorted(lst,key=lambda x: x[1])
z=[]
if n==1:
  print(1)
  sys.exit()
else:
  for j in range(n):
    for k in range(j+1,n):
      z.append((lst_2[j][0]-lst_2[k][0],lst_2[j][1]-lst_2[k][1]))
u=[]
if n==1:
  print(1)
  sys.exit()
else:
  for j in range(n):
    for k in range(j+1,n):
      u.append((lst_3[j][0]-lst_3[k][0],lst_3[j][1]-lst_3[k][1]))
Z=Counter(z)
U=Counter(u)
m=max(Z.most_common()[0][1],U.most_common()[0][1])
print(n-m)

Submission status: Accepted

Solution code:
n = int(input())
xy_ls = []
count = 0
while count < n:
    xy_ls.append(list(map(int, input().split())))
    count = count + 1
count_diff = {}
for i in range(n):
    for j in range(n):
        x = xy_ls[i][0] - xy_ls[j][0]
        y = xy_ls[i][1] - xy_ls[j][1]
        xy = (x, y)
        if xy == (0,0):
            continue
        if count_diff.get(xy):
            count_diff[xy] += 1
        else:
            count_diff[xy] = 1
max_count = 0
for v in count_diff.values():
    if v > max_count:
        max_count = v
print(n-(int(max_count)))

Submission status: Accepted

Solution code:
import copy

n = int(input())
lst = [[0]*2 for i in range(n)]
for i in range(n):
    lst[i][0], lst[i][1] = map(int, input().split())

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

lst_copy = copy.deepcopy(lst)
saidai = 0
for i in range(n-1):
    for j in range(i+1, n):
        cnt = 0
        p = lst[j][0] - lst[i][0]
        q = lst[j][1] - lst[i][1]
        lst_copy = copy.deepcopy(lst)
        while lst_copy != []:
            xs, ys = lst_copy[0][0], lst_copy[0][1]
            lst_copy.pop(0)
            while [xs+p, ys+q] in lst_copy:
                cnt += 1
                xs, ys = xs+p, ys+q
                lst_copy.remove([xs, ys])
        saidai = max(saidai, cnt)

print(n-saidai)

Submission status: Accepted

Solution code:
from collections import Counter as c
N = int(input())
XY = [tuple(map(int, input().split())) for _ in range(N)]
XY.sort(key=lambda xy: (xy[0], xy[1]))
if N == 1 or N == 2:
    print(1)
    exit()

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

print(N - sorted(list(c(inclination).items()), key=lambda x: x[1])[-1][1])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
 
def f(_pts, p, q):
    pts = set(_pts[:])
    r = 0
 
    while len(pts) > 0:
        r += 1
        x = max(pts)
        while x in pts:
            pts.remove(x)
            x = (x[0]-p, x[1]-q)
 
    return r
 
################################################################################
 
n = int(input())
pts = []
for i in range(n):
    x, y = map(int, input().split())
    pts.append((x, y))
 
res = n
for i in range(len(pts)):
    for j in range(i+1, len(pts)):
        res = min(res, f(pts, -(pts[i][0]-pts[j][0]), -(pts[i][1]-pts[j][1])))
        res = min(res, f(pts, +(pts[i][0]-pts[j][0]), -(pts[i][1]-pts[j][1])))
        res = min(res, f(pts, -(pts[i][0]-pts[j][0]), +(pts[i][1]-pts[j][1])))
        res = min(res, f(pts, +(pts[i][0]-pts[j][0]), +(pts[i][1]-pts[j][1])))
 
print(res)

Submission status: Accepted

Solution code:
def main():
    num = int(input())
    data = [list(map(int, input().split())) for i in range(num)]

    ans = num
    for i in range(num):
        for j in range(num):
            if i == j:
                continue

            kyori = [data[i][0] - data[j][0], data[i][1] - data[j][1]]
            visit_list = [0 for i in range(num)]

            kari_num = 0

            for k in range(num):

                if visit_list[k]:
                    continue
                kari_num += 1
                visit_list[k] = 1
                flg = 1
                now_place = [data[k][0] + kyori[0], data[k][1] + kyori[1]]
                now_place_rev = [data[k][0] - kyori[0], data[k][1] - kyori[1]]

                while flg:
                    flg = 0
                    for l in range(num):
                        if visit_list[l]:
                            continue
                        if data[l] == now_place:
                            now_place = [now_place[0] + kyori[0], now_place[1] + kyori[1]]
                            visit_list[l] = 1
                            flg = 1
                        if data[l] == now_place_rev:
                            now_place_rev = [now_place_rev[0] - kyori[0], now_place_rev[1] - kyori[1]]
                            visit_list[l] = 1
                            flg = 1

            ans = min(ans, kari_num)




    print(ans)






if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def getN():
    return int(input())

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

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

def valid(steps):
    for i , x in enumerate(sorted(steps)):
        if i != x:
            return i - 1

    return len(steps) - 1
#
n = getN()
za = []
for i in range(n):
    za.append(getlist())
ans = 0
from collections import defaultdict
kumi = defaultdict(int)

for i, pa in enumerate(za):
    for j, pb in enumerate(za):
        xa, ya = pa
        xb, yb = pb
        dfx = xa - xb
        dfy = ya - yb

        diff = str(dfx) + str(dfy)
        kumi[diff] += 1

if n == 1:
    print(1)
    import sys;sys.exit()
del kumi["00"]
print(n - max(list(kumi.values())))

# for p1 in za:
#     for p2 in za:
#         steps = []
#         if p1 == p2:
#             continue
#         xa, ya = p1
#         xb, yb = p2
#         dfx = xb - xa
#         dfy = yb - ya
#         if not (dfx or dfy):
#             continue
#         for p3 in za:
#             xc, yc = p3
#             if dfx:
#                 if (xc - xa) % dfx == 0:
#                     step = (xc - xa) // dfx
#                     if yc - ya == dfy * step:
#                         steps.append(step)
#
#             else:
#                 if xc == xa:
#                     if (yc - ya) % dfy == 0:
#                         steps.append((yc - ya) // dfy)
#         tmp = valid(steps)
#         print(p1, p2, tmp, steps)
#         if tmp > ans:
#             ans = tmp
#             if tmp == 3:
#                 print(p1, p2)
#
# print(n-ans)

Submission status: Accepted

Solution code:
from sys import stdin

def solve(N, xys):
    diff = []
    diff_count = []
    idx = 0
    for i in range(N-1):
        for j in range(i+1,N):
            tmp_a = [xys[i][0] - xys[j][0], xys[i][1] - xys[j][1]]
            tmp_b = [xys[j][0] - xys[i][0], xys[j][1] - xys[i][1]]
            if tmp_a in diff:
                diff_count[diff.index(tmp_a)] += 1
            elif tmp_b in diff:
                diff_count[diff.index(tmp_b)] += 1
            else:
                diff.append(tmp_a)
                diff_count.append(1)
                idx += 1
    if diff == []:
        diff_count.append(0)
    return N - max(diff_count)

if __name__ == '__main__':
    N = int(stdin.readline().rstrip())
    xys = []
    for i in range(N):
        xys.append([int(x) for x in stdin.readline().rstrip().split()])
    print(solve(N, xys))

Submission status: Accepted

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

dl = {}
for i in range(N):
  for j in range(N):
    dx = str(xylist[j][0] - xylist[i][0])
    dy = str(xylist[j][1] - xylist[i][1])
    l = dx + "|" + dy
    if dx == "0" and dy == "0":
      continue
    if l in dl:
      dl[l] = dl[l] + 1
    else:
      dl[l] = 1

cnt = 0
if len(dl) != 0:
  cnt = N - max(dl.values())

print(cnt if cnt > 1 else "1")

Submission status: Accepted

Solution code:
from sys import stdin
n = int(stdin.readline().rstrip())
data = [[int(s) for s in stdin.readline().rstrip().split()] for _ in range(n)]
d = {}

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

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

Submission status: Accepted

Solution code:
import sys
from itertools import combinations

def main():
    input = sys.stdin.readline
    N = int(input())
    cord = set()
    for _ in range(N):
        x, y = map(int, input().split())
        cord.add((x, y))

    if N <= 2:
        return 1

    ans = 50
    for a in combinations(cord, 2):
        x1, y1 = a[0]
        x2, y2 = a[1]

        p = x2 - x1
        q = y2 - y1

        cnt1 = 0
        cnt2 = 0

        if p == q == 0:
            continue

        A = set()
        B = set()
        for x, y in cord:
            A.add((x-p, y-q))
            B.add((x+p, y+q))

        ans = min(ans, len(A - cord), len(B - cord))

    return ans


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

Submission status: Accepted

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

vecs = {}
for i in range(n):
  for j in range(i+1, n):
    if xy[i][0] < xy[j][0]:
      vec = (xy[j][0] - xy[i][0], xy[j][1] - xy[i][1])
    elif xy[i][0] > xy[j][0]:
      vec = (xy[i][0] - xy[j][0], xy[i][1] - xy[j][1])
    else:
      vec = (0, abs(xy[j][1] - xy[i][1]))
    
    if vec in vecs:
      vecs[vec] += 1
    else:
      vecs[vec] = 1

vec_max = max(list(vecs.values()))
print(n - vec_max)

Submission status: Accepted

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

sabun_dict = {}

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

for i in range(n):
  for j in range(n):
    x = point_list[i][0] - point_list[j][0]
    y = point_list[i][1] - point_list[j][1]
    if x == 0 and y == 0:
      continue
    if (x, y) in sabun_dict:
      sabun_dict[(x, y)] = sabun_dict[(x, y)] + 1
    else:
      sabun_dict[(x, y)] = 1

max_v = max(sabun_dict.values())

print(n - max_v)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import itertools
import operator
import collections

def solve(N: int, x: "List[int]", y: "List[int]"):
    if N == 1:
        print(1)
        return

    PL = list(zip(x,y))
    PL.sort(key = operator.itemgetter(0,1))

    pqdic = collections.defaultdict(list)
    for i in range(N-1):
        for j in range(i+1,N):
            p = PL[j][0] - PL[i][0]
            q = PL[j][1] - PL[i][1]
            pqdic[p,q].append((i,j))

    max_pqlen = 0
    for k,v in pqdic.items():
        max_pqlen = max(max_pqlen,len(v))

    print(N - max_pqlen)




# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    x = [int()] * (N)  # type: "List[int]" 
    y = [int()] * (N)  # type: "List[int]" 
    for i in range(N):
        x[i] = int(next(tokens))
        y[i] = int(next(tokens))
    solve(N, x, y)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# coding: utf-8
import time
import re
import math

def main():
    N=int(input())
    XY=[]
    for a in range(N):
        XY.append(list(map(int,input().split())))
    DL=[]
    for a in range(N):
        xa=XY[a][0]
        ya=XY[a][1]
        for b in range(N):
            if(b==a):continue
            xb=XY[b][0]
            yb=XY[b][1]
            d=D(xa,ya,xb,yb)
            DL.append(d)
    mx=0
    for a in range(len(DL)):
        mx=max([mx,DL.count(DL[a])])
    #print(DL)
    print(N-mx)
def D(x1,y1,x2,y2):
    x=x2-x1
    y=y2-y1
    return [x,y]
start=time.time()
main()
#print("処理速度 {}sec".format(time.time()-start))
#"YNeos"[True::2]
#A=list(map(int,input().split()))
#n=int(input())
# global n,A,s,memo,mx,mn,L,B

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from itertools import product
n = int(input())
xy = [list(map(int, input().split())) for _ in range(n)]

m = 0
xy.sort(key=lambda x: (x[0], x[1]))
for l in range(n - 1):
    for r in range(l + 1, n):
        p = xy[r][0] - xy[l][0]
        q = xy[r][1] - xy[l][1]
        c = 0
        for i in range(n - 1):
            for j in range(i + 1, n):
                if xy[j][0] - xy[i][0] != p: continue
                if xy[j][1] - xy[i][1] != q: continue
                c += 1
                break
        m = max(m, c)

xy.sort(key=lambda x: (x[1], x[0]))
for l in range(n - 1):
    for r in range(l + 1, n):
        p = xy[r][0] - xy[l][0]
        q = xy[r][1] - xy[l][1]
        c = 0
        for i in range(n - 1):
            for j in range(i + 1, n):
                if xy[j][0] - xy[i][0] != p: continue
                if xy[j][1] - xy[i][1] != q: continue
                c += 1
                break
        m = max(m, c)

print(n - m)

Submission status: Accepted

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

stock=[]

for i in range(N):
    for j in range(i+1,N):
        if xy[i][0]-xy[j][0]==0:
            if xy[i][1]-xy[j][1]>0:
                stock.append([xy[i][0]-xy[j][0],xy[i][1]-xy[j][1]])
            else:
                stock.append([xy[j][0]-xy[i][0],xy[j][1]-xy[i][1]])
        elif xy[i][0]-xy[j][0]>0:
              stock.append([xy[i][0]-xy[j][0],xy[i][1]-xy[j][1]])
        else:
              stock.append([xy[j][0]-xy[i][0],xy[j][1]-xy[i][1]])

stock.sort(key=lambda x:(x[0],x[1]))
counter=0
ans=0
for i in range(1,len(stock)):

    if stock[i]==stock[i-1]:
        counter+=1
    else:
        ans=max(ans,counter)
        counter=0
ans=max(ans,counter)
print(max(N-ans-1,1))

Submission status: Accepted

Solution code:
from collections import Counter
from itertools import combinations

N = int(input())
R = [[int(i) for i in input().split()] for _ in range(N)]

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

L = []
for (x1, y1), (x2, y2) in combinations(R, 2):
    L.append((x1 - x2, y1 - y2))
    L.append((-x1 + x2, -y1 + y2))

C = Counter(L)
print(N - C.most_common(1)[0][1])

Submission status: Accepted

Solution code:
N = int(input())
l = [list(map(int,input().split(" "))) for _ in range(N)]
ll = [tuple(i) for i in l]
same = 1
n = N**2 - N
ans_l = [()]*n
cnt = 0
for i in l:
    x = i[0]
    y = i[1]
    for j in l:
        if i==j:
            continue
        k = (j[0]-x,j[1]-y)
        ans_l[cnt] = k[:]
        cnt+=1
ans = 0
ans_l.sort()
for i in ans_l:
    k = i[0]
    same = 0
    for j in ans_l:
        if j[0] > k:
            break
        if i==j:
            same+=1
    ans = max(ans,same)
print(N-ans)

Submission status: Accepted

Solution code:
n = int(input())
x = [list(map(int, input().split())) for _ in range(n)]
x.sort()
ans = float('inf')
for d1 in x:
    for d2 in x:
        tmp = n
        if d1 == d2:
            continue
        p = d1[0] - d2[0]
        q = d1[1] - d2[1]
        s = set()
        for idx, d3 in enumerate(x):
            for d4 in x:
                if tuple(d4) not in s and d3 != d4 and (d4[0] - d3[0] == p and d4[1] - d3[1] == q or d4[0] - d3[0] == -p and d4[1] - d3[1] == -q):
                    tmp -= 1
                    break
            s.add(tuple(d3))
        ans = min(ans, tmp)
if n == 1:
    print(1)
else:
    print(max(1, ans))

Submission status: Accepted

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

d = set()
for i in range(N):
    for j in range(N):
        d.add((D[i][0] - D[j][0], D[i][1] - D[j][1]))


d = list(d)
num = float('inf')
for p, q in d:
    if p == 0 and q == 0:
        continue
    used = [0] * N
    prex, prey = D[0][0], D[0][1]
    used[0] = 1
    tmp = 1
    for k in range(N - 1):
        for i in range(N):
            if used[i]:
                continue
            if D[i][0] - prex == p and D[i][1] - prey == q:
                prex = D[i][0]
                prey = D[i][1]
                used[i] = 1
                break
        else:
            tmp += 1
            for i in range(N):
                if not used[i]:
                    prex = D[i][0]
                    prey = D[i][1]
                    used[i] = 1
                    break
    num = min(tmp, num)

print(num)

Submission status: Accepted

Solution code:
def sol(inp=input):
    n=int(inp())
    pts=[tuple(map(int,inp().split())) for _ in range(n)]
    min_cost=n
    pt1=pts[0]
    for pt2 in pts[1:]:
        p,q=(pt1[0]-pt2[0],pt1[1]-pt2[1])
        cost=0
        for i,pt in enumerate(pts):
            if (pt[0]+p,pt[1]+q) not in pts:
                cost+=1
        min_cost=min(cost,min_cost)
    return '{}'.format(min_cost)
print(sol())

Submission status: Accepted

Solution code:
n=int(input())
z=[]
for i in range(n):
    x,y=map(int,input().split())
    z.append([x,y])
z.sort(reverse=True)
dif=[]
for i in range(n):
    for j in range(n):
        if i<j:
            x=z[j][0]-z[i][0]
            y=z[j][1]-z[i][1]
            dif.append([x,y])
dif.sort(reverse=True)
count=-1
buf=0
comp=[0,0]
ans=[0,0]
l=len(dif)
for i in range(l):
    if comp==dif[i]:
        buf+=1
    else:
        if count<buf:
            count=buf
            ans=comp
        buf=1
        comp=dif[i]
if count<buf:
    count=buf
    ans=comp
print(n-count)

Submission status: Accepted

Solution code:

N = int(input())
xy = [list(map(int, input().split())) for i in range(N)]
xy.sort(key=lambda x: x[0])
tilt_map = {}

if N == 1:
    print(1)
else:
    for i in range(N):
        for j in range(i+1, N):
            a = xy[i]
            b = xy[j]
            tilt_x = a[0] - b[0]
            tilt_y = a[1] - b[1]
            if tilt_x == 0 and tilt_y < 0:
                tilt_y *= -1
            key = str(tilt_x) + ":" + str(tilt_y)
            if key in tilt_map:
                tilt_map[key] += 1
            else:
                tilt_map[key] = 1


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

Submission status: Accepted

Solution code:
import collections
N = int(input())
ball_location = []
for i in range(N):
    x,y = map(int, input().split())
    ball_location.append([x,y])

vector = []
if N <= 2:
    print(1)
else:
    for i in range(N):
        first_point = ball_location[i]
        
        for next_point in ball_location[0:i] + ball_location[i+1:]:
            p = next_point[0] - first_point[0]
            q = next_point[1] - first_point[1]
            vector.append(str(p) + "," + str(q))
            
    print(N - collections.Counter(vector).most_common()[0][1])

Submission status: Accepted

Solution code:
import bisect
from operator import itemgetter
import math
import collections
import functools
import itertools
import numpy as np
import sys
MAX_INT = int(10e10)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N = I()
xy = [IL() for i in range(N)]

if N == 1 or N == 2:
  print(1)
else:
  data = []
  cnt = 0
  for i in itertools.combinations(xy,2):
    rex,rey = i[0]
    x,y = i[1]
    if rex > x:
      rex,rey,x,y = x,y,rex,rey
    if rex == x:
      if rey > y:
        rex,rey,x,y = x,y,rex,rey
    data.append(str(x-rex)+str(y-rey))
  else:
    d = collections.Counter(data)
    cnt = max(cnt,d.most_common()[0][1])
  
  print(N-cnt)

Submission status: Accepted

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

check = []
for i in range(n-1):
    for j in range(i+1,n):
        check.append([xy[i][0]-xy[j][0],xy[i][1]-xy[j][1]])
#print(check)
ans = 10**9
for i in check:
    b = []
    for j in range(n):
        b.append([xy[j][0]-i[0],xy[j][1]-i[1]])
    c = n
    for j in range(n):
        if b[j] in xy:
            c -= 1
    if c < ans:
        ans = c
if n == 1:
    print(1)
else:
    print(ans)

Submission status: Accepted

Solution code:
N = int(input())
P = sorted([list(map(int, input().split())) for i in range(N)])
Z = set()
for x, y in P:
    Z.add((x, y))
X = []
ans = N - 1
for i in range(N):
    for j in range(i + 1, N):
        xi, yi = P[i]
        xj, yj = P[j]

        p, q = (xj - xi), (yj - yi)
        X.append((p, q))

for p, q in X:
    hit = 0
    for x, y in P:
        if (x - p, y - q) in Z:
            hit += 1
    ans = min(ans, N - hit)
print(max(1, ans))

Submission status: Accepted

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

PQ = []
for i in range(N):
    for j in range(i+1, N):
        now = [ XY[j][0] - XY[i][0], XY[j][1] - XY[i][1] ]
        if not now in PQ:
            PQ.append(now)

ans = N
for r in range(len(PQ)):
    cnt = N
    for i in range(N):
        nxt = [ XY[i][0] + PQ[r][0], XY[i][1] + PQ[r][1] ]
        if nxt in XY:
            cnt -= 1
    ans = min(ans, cnt)

print(ans)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    n,k = LI()
    print(n%k)
    return

#B
def B():
    n = I()
    po = LIR(n)
    if n == 1:
        print(1)
        quit()
    ans = float("inf")
    for i in range(n):
        for j in range(n):
            if i == j:continue
            x,y = po[i]
            s,t = po[j]
            p,q = s-x,t-y
            m = n
            for k in range(n):
                for l in range(n):
                    if (po[k][0]-po[l][0],po[k][1]-po[l][1]) == (p,q):m -= 1
            if m < ans:
                ans = m
    print(ans)
    return

#C
def C():
    n = I()
    a = LI()
    a.sort()
    if a[0] >= 0:
        print(sum(a)-2*a[0])
        for i in range(1,n-1):
            print(a[0],a[i])
            a[0] -= a[i]
        print(a[n-1],a[0])
    else:
        if a[-1] < 0:
            print(2*a[-1]-sum(a))
            for i in range(n-1):
                print(a[-1],a[i])
                a[-1] -= a[i]
        else:
            m = bisect.bisect_left(a,0)
            p = n-m
            ans = -sum(a[:m])+sum(a[m:])
            print(ans)
            if p > m:
                l = a[-1]
                a = a[:-1]
                a = a[::-1]
                p -= 1
                p,m = m,p
                k = a[m]-a[m-1]
                print(a[m],a[m-1])
                for i in range(p-1):
                    print(a[m-i-2],k)
                    k = a[m-i-2]-k
                    print(a[m+i+1],k)
                    k = a[m+i+1]-k
                for i in range(m-p):
                    print(k,a[i])
                    k -= a[i]
                print(l,k)
            else:
                k = a[m]-a[m-1]
                print(a[m],a[m-1])
                for i in range(p-1):
                    print(a[m-i-2],k)
                    k = a[m-i-2]-k
                    print(a[m+i+1],k)
                    k = a[m+i+1]-k
                for i in range(m-p):
                    print(k,a[i])
                    k -= a[i]
    return

#D
def D():
    n = I()

    return

#E
def E():
    n = I()

    return

#F
def F():
    n = I()

    return

#G
def G():
    n = I()

    return

#H
def H():
    n = I()

    return

#I
def I_():
    n = I()

    return

#J
def J():
    n = I()

    return

#Solve
if __name__ == "__main__":
    B()

Submission status: Accepted

Solution code:
n=int(input())
l=[tuple(map(int,input().split())) for i in range(n)]
l.sort(key=lambda x:x[0])
s=set()
fa=n-1
if(n==1):
    print(1)
    quit()
for i in range(n):
    for j in range(i+1,n):
        x,y=sorted([l[i],l[j]],key=lambda x:x[0])
        p=l[j][0]-l[i][0]
        q=l[j][1]-l[i][1]
        s=set(l)
        ans=n
        for x,y in l:
            if((x+p,y+q) in s):
                ans-=1
        fa=min(fa,ans)
print(fa)

Submission status: Accepted

Solution code:
N = int(input())

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

if N == 1:
    print(1)
else:
    pq = {}
    for i in range(N-1):
        for j in range(i+1, N):
            p, q = balls[i][0] - balls[j][0], balls[i][1] - balls[j][1]
            if p < 0 or (p == 0 and q < 0):
                p, q = -p, -q
            if (p, q) in pq:
                pq[(p, q)] += 1
            else:
                pq[(p, q)] = 1

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

Submission status: Accepted

Solution code:
INF = 10 ** 100
n = int(raw_input())
ns = []

for i in xrange(n):
    (y, x) = map(int, raw_input().split())
    ns.append((y, x))

ns.sort()

ans = INF

if n == 1:
    ans = 1

for i in xrange(n):
    for j in xrange(i + 1, n):
        dy, dx = ns[j][0] - ns[i][0], ns[j][1] - ns[i][1]

        ps = ns[:]
        st = set(ps)
        cnt = 0

        for p in ps:
            if p not in st:
                continue
            st.remove(p)
            cnt += 1
            y, x = p
            while st:
                ny, nx = y + dy, x + dx
                if (ny, nx) not in st:
                    break
                st.remove((ny, nx))
                y, x = ny, nx
        ans = min(ans, cnt)

print ans

Submission status: Accepted

Solution code:
N = int(input())
xy = [[int(i) for i in input().split()] for i in range(N)]
xy = sorted(xy)
#xy = list(map(list, set(map(tuple, xy))))

d = {}
m = 0
for i in range(N):
    for j in range(i+1, N):
        a, b = xy[i][0]-xy[j][0], xy[i][1]-xy[j][1]
        if (a, b) in d:
            d[a, b] += 1
        else:
            d[a, b] = 1

for val in d.values():
    m = max(m, val)
#print(d)
print(N-m)

Submission status: Accepted

Solution code:
n = int(input())

balls = []

for _ in range(n):
    a, b = map(int, input().split())
    balls.append((a,b))

costmax = n
costmin = 0
ans = costmax

if n == 1:
    ans = 1
elif n == 2:
    ans = 1
else:
    c_divs = []
    for i in range(n):
        x = balls[i][0]
        y = balls[i][1]

        for j in range(n):
            c_divs.append((balls[j][0] - x, balls[j][1] - y))
            #print(i, j+1)


    import collections
    c = collections.Counter(c_divs)

    if c.most_common()[0][0] == (0,0):
        save = c.most_common()[1][1]
    else:
        save = c.most_common()[0][1]
    ans = ans - save


print(ans)
#print(balls)
#print(c_divs)
#print(c.most_common())
#print(c.most_common()[0][0])

Submission status: Accepted

Solution code:
N = int(input())

ball_position = []
for _ in range(N):
    i, j = map(int, input().split())
    ball_position.append((i, j))

    
def tup2_diff(a, b):
    ai, aj = a
    bi, bj = b
    return ((ai - bi, aj - bj))
  
calculation_list = []
for i in range(len(ball_position)):
    for j in range(len(ball_position)):
        if i == j:
            continue
        else:
            x , y = tup2_diff(ball_position[i], ball_position[j])
            if x > 0 or (x == 0 and y > 0):
                calculation_list.append((x, y))
           
import collections

c = collections.Counter(calculation_list).most_common(1)
if N == 1:
    print(1)
else:
    print(N - calculation_list.count(c[0][0]))

Submission status: Accepted

Solution code:
import itertools


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

candidates = list()
indices = itertools.combinations(range(n), 2)
points = sorted(points)
for i, j in indices:
    p = points[j][0] - points[i][0]
    q = points[j][1] - points[i][1]
    candidates.append((p, q))

ans = n * 2
for p, q in candidates:
    indices = list(range(n))
    cost = 0

    idx = 0
    cost += 1

    while True:
        x, y = points[idx]
        indices.remove(idx)
        if len(indices) == 0:
            break

        try:
            idx = points.index((x + p, y + q))
        except Exception:
            idx = indices[0]
            cost += 1
    
    ans = min(ans, cost)

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

Submission status: Accepted

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

distlist=[]
distnum=[]

for i in range(n):
    for j in range(n):
        vec=[xy[i][0]-xy[j][0], xy[i][1]-xy[j][1]]
        if(i==j):
             continue
        flag=0
        for k in range(len(distlist)):
            if(distlist[k][0]==vec[0] and distlist[k][1]==vec[1]):
                distnum[k] += 1
                flag=1
                break
        if(flag==0):
            distlist.append(vec)
            distnum.append(1)

if(n==1):
    print(1)
else:
    print(max(n-max(distnum),1))