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:
# -*- coding: utf-8 -*-
n=int(input())
x=[]
y=[]
total=[]
count=[]
for _ in range(n):
    x1,y1=map(int,input().split())
    x.append(x1)
    y.append(y1)
for i in range(n):
    for j in range(n):
        if i==j:
            continue
        else:
            temporary=(x[i]-x[j],y[i]-y[j])
            if temporary in total:
                count[total.index(temporary)]=count[total.index(temporary)]+1
            else:
                total.append(temporary)
                count.append(0)
if n==1:
    print(1)
else:
    print(n-max(count)-1)

Submission status: Accepted

Solution code:
N = int(input())
xys = []
for i in range(N):
  x, y = map(int, input().split())
  xys.append((x,y))
xys.sort()
#print(xys)
def count(p,q):
  c = N
  for i in range(0, N):
    for j in range(i+1, N):
      if p == xys[j][0]-xys[i][0] and q == xys[j][1]-xys[i][1]:
        c -= 1
        break
  return c
r = N
for i in range(0, N):
  for j in range(0, i):
    p = xys[i][0]-xys[j][0]
    q = xys[i][1]-xys[j][1]
    r = min(r, count(p, q))
print(r)

Submission status: Accepted

Solution code:
N = int(raw_input())
ret = ()

for i in range(N):
  ret += (tuple([int(_) for _ in raw_input().split(" ")]),)

t = [[0]*N for _ in range(N)]
d = {}
for i in range(N):
  for j in range(i+1, N):    
    x = ret[i][0] - ret[j][0]
    y = ret[i][1] - ret[j][1]
    if not (x,y) in d:
      d[(x,y)] = []
    if not (-x, -y) in d:
      d[(-x, -y)] = []

    d[(x,y)] += [(i,j)]
    d[(-x,-y)] += [(j, i)]

d = [(len(d[_]), _, d[_]) for  _ in d]
if len(d) == 0:
  print 1
  exit()
d.sort(reverse=True)
d = d[0][2]
ans = [1] * N
current = d[0]
count = 0
while(len(d) > 0):
  count += 1
  current = d[0]
  ans[current[0]] = 0
  ans[current[1]] = 0
  d.remove(current)
  t = [current[0], current[1]]
  c1 = t[0]
  c2 = t[1]

  while(len(d) > 0):
    for i in d:
      if i[1] == c1:
        d.remove(i)
        c1 = i[0]
        ans[c1] = 0
        t = [c1] + t
        break
    else:
      break

  while(len(d) > 0):
    for i in d:
      if c2 == i[0]:
        d.remove(i)
        c2 = i[1]
        ans[c2] = 0
        t = t + [c2]
        break
    else:
      break
  
  #print t
print sum(ans) + count

Submission status: Accepted

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

d = []
c = []
for i in range(n):
    for j in range(n):
        tmp = [l[i][0]-l[j][0],l[i][1]-l[j][1]]
        if tmp[0] != 0 or tmp[1] != 0:
          d.append(tmp)
          if tmp not in c:
            c.append(tmp)
#print(d,c)
t = 0
for x in c:
    num = d.count(x)
    if num > t:
        t = num
ans = n - t
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
n = int(input())
a = []
b = []
for i in range(n):
    c,d = map(int,input().split())
    e = np.array([c,d])
    if a!=[]:
        for j in range(len(a)):
            b.append(list(a[j]-e))
            b.append(list(e-a[j]))
    a.append(e)
f = []
for x in b:
    if x not in f:
        f.append(x)
m = -100
for i in range(len(f)):
    if b.count(f[i])>m:
        m = b.count(f[i])
m = max(0,m)
print(n-m)

Submission status: Accepted

Solution code:
from collections import Counter
from itertools import permutations

N = int(input())
x, y = (
    zip(*(map(int, input().split()) for _ in range(N))) if N else
    ((), ())
)

# (p, q) = (x_i - x_j, y_i - y_j) を満たす組(i, j)の個数が最大となるように
# p, qを定めればよい
ans = (
    1 if N == 1 else
    N - max(
        Counter(
            (x[i] - x[j], y[i] - y[j])
            for i, j in permutations(range(N), 2)
        ).values()
    )
)

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
from itertools import permutations

N = int(input())
balls = [tuple(map(int, input().split())) for _ in range(N)]
if N == 1: print(1)
else:
    cnt = defaultdict(int)
    for b1, b2 in permutations(balls, 2):
        cnt[(b2[0] - b1[0], b2[1] - b1[1])] += 1
    _, n = max(cnt.items(), key=lambda x: x[1])
    cost = N - n
    print(cost)

Submission status: Accepted

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

if N == 1:
    print(1)
else:
    pq_conbination = {}
    for a in coodinates:
        for b in coodinates:
            if a == b:
                continue
            else:
                p, q = a[0]-b[0], a[1]-b[1]
                if (p, q) in pq_conbination:
                    pq_conbination[(p, q)] += 1
                else:
                    pq_conbination[(p, q)] = 1

    pq_conbination = sorted(pq_conbination.items(), key=lambda x: x[1], reverse=True)

    print(N - pq_conbination[0][1])

Submission status: Accepted

Solution code:
N = int(input())

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

flag = True
if N == 1:
    print(1)
    flag = False

if flag:
    # p, qを求める
    d = {}  # [p, q]をkeyにもつ辞書
    cnt=0
    for a in coodinates:
        for b in coodinates:
            if a == b:
                continue
            p, q = a[0] - b[0], a[1] - b[1]
            if (p, q) in d:
                d[(p, q)] += 1
            else:
                d[(p, q)] = 1
            cnt=max(cnt,d[(p,q)])

    print(N - cnt)

Submission status: Accepted

Solution code:
def cal(dx,dy):
    cnt=0
    for x in s:
        flag=False
        for y in s:
            if(x==y):
                continue
            if(x[0]+dx==y[0] and x[1]+dy==y[1]):
                flag=True
        if(flag==False):
            cnt+=1
    return cnt

n=int(input())
s=[list(map(int,input().split())) for _ in range(n)]
ans=n
for x in s:
    for y in s:
        if(x==y):
            continue
        dx=x[0]-y[0]
        dy=x[1]-y[1]
        tmp=cal(dx,dy)
        if(tmp<ans):
            ans=tmp
print(ans)

Submission status: Accepted

Solution code:
N = int(input())

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

flag = True
if N == 1:
    print(1)
    flag = False

if flag:
    # p, qを求める
    d = {}  # [p, q]をkeyにもつ辞書
    for a in coodinates:
        for b in coodinates:
            if a == b:
                continue
            p, q = a[0]-b[0], a[1]-b[1]
            if (p, q) in d:
                d[(p, q)] += 1
            else:
                d[(p, q)] = 1

    good_distance_count = list(sorted(d.values(), reverse=True))[0]

    print(N - good_distance_count)

Submission status: Accepted

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

if N == 1:
    print(1)
    exit()
A.sort()
grid = {}
for i in range(N):
    for j in range(i+1,N):
        if (A[j][0] - A[i][0], A[j][1] - A[i][1]) not in grid:
            grid[A[j][0] - A[i][0], A[j][1] - A[i][1]] = 1
        else:
            grid[A[j][0] - A[i][0], A[j][1] - A[i][1]] += 1

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

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)
else:
  d = defaultdict(int)
  for i in range(N):
    xi,yi = xy[i]
    for j in range(N):
      if i==j:
        continue
      else:
        xj,yj = xy[j]
      d[(xj-xi,yj-yi)] += 1
  max_v = max(d.values())
  print(N-max_v)

Submission status: Accepted

Solution code:
from collections import defaultdict

n = int(input())
z = [list(map(int, input().split())) for _ in range(n)]
if n == 1:
    ans = 1
else:
    d = defaultdict(int)
    for i in range(n):
        xi, yi = z[i]
        for j in range(n):
            if i == j:
                continue
            xj, yj = z[j]
            d[(xi - xj, yi - yj)] += 1
    ans = n - max(d.values())
print(ans)

Submission status: Accepted

Solution code:
import copy
n = int(input())
L = []
for i in range(n):
    L.append(list(map(int,input().split())))
s = []
for i in range(n):
    for j in range(i):
        s.append([L[i][0]-L[j][0],L[i][1]-L[j][1]])
        s.append([L[j][0]-L[i][0],L[j][1]-L[i][1]])
u = []
for i in range(len(s)):
  if s[i] not in u:
    u.append(s[i])
ans = 0
for i in range(len(u)):
    cur = s.count(u[i])
    if ans < cur:
        ans = cur
print(n-ans)

Submission status: Accepted

Solution code:
import sys
from collections import Counter

N = int(input())
points = []
for i, line in enumerate(sys.stdin):
    x, y = map(int, line.split())
    points.append([x, y])
    if i == N - 1:
        break
if len(points) == 1:
    print(1)
    sys.exit(0)

counts = []
for i in range(N):
    for j in range(N):
        if i == j:
            continue
        p = points[j][0] - points[i][0]
        q = points[j][1] - points[i][1]
        counts.append((p, q))

pq = Counter(counts).most_common()[0][1]
cost = N - pq
print(cost)

Submission status: Accepted

Solution code:
n=int(input())
x=[0]*n
y=[0]*n
for i in range(n):
        x[i],y[i]=list(map(int,input().split()))
dic={}
if n==1:
        print(1)
        exit()
dic={}
for i in range(n):
        for j in range(n):
                if i!=j:
                        dx=x[i]-x[j]
                        dy=y[i]-y[j]
                        if (dx,dy) in list(dic.keys()):
                                dic[(dx,dy)]+=1
                        else:
                                dic[(dx,dy)]=1
print(n-max(list(dic.values())))

Submission status: Accepted

Solution code:
import sys
N = int(input())
arr = []

for i in range(N):
    arr.append(list(map(int, input().split())))

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

d = {}

for i in range(N):
    for j in range(N):
        if i != j:
            x = arr[i][0] - arr[j][0]
            y = arr[i][1] - arr[j][1]
            if (x, y) in list(d.keys()):
                d[(x, y)] += 1
            else:
                d[(x, y)] = 1

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

Submission status: Accepted

Solution code:
(lambda collections: (lambda n: (lambda a: (lambda c: print(n-max(c.values(),default=0)))(collections.Counter((y[0]-x[0],y[1]-x[1]) for x in a for y in a if x<y)))([tuple(map(int,input().split())) for _ in range(n)]))(int(input())))(__import__('collections'))

Submission status: Accepted

Solution code:
import collections
import itertools
N = int(input())
balls =[list(map(int, input().split())) for _ in range(N)]
pq = collections.defaultdict(int)
for a, b in itertools.combinations(balls, 2):
    x1, y1 = a
    x2, y2 = b
    p = x1-x2
    q = y1-y2
    pq[(p, q)] += 1
    pq[(-p, -q)] += 1
cnt = 0
for c in pq.values():
    if c > cnt:
        cnt = c
ans = N-cnt
print(ans)

Submission status: Accepted

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

import sys

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

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

	re = {}
	for i, val in enumerate(xy):
		x, y = val
		for j, vol in enumerate(xy):
			if i == j:
				continue
			nx, ny = vol
			p = nx - x
			q = ny -y
			if (p, q) in re:
				re[(p, q)] += 1
			else:
				re[(p, q)] = 1


	ans = N - max(re.values())

	print(ans)


if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import copy
import collections
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import numpy as np
import statistics
from statistics import mean, median,variance,stdev
import math

def main():
	N = int(input())
	xy = []
	for i in range(N):
		x, y = map(int, input().split(" "))
		xy.append((x, y))
		
	if N == 1:
		print(1)
		sys.exit()
		
	re = {}
	for i, val in enumerate(xy):
		x, y = val
		for j, vol in enumerate(xy):
			if i == j:
				continue
			nx, ny = vol
			p = nx - x
			q = ny -y
			if (p, q) in re:
				re[(p, q)] += 1
			else:
				re[(p, q)] = 1
				
	ans = N - max(re.values())
	
	print(ans)
	
	
if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:

def solve2():
    N = int(raw_input())
    xy = [None] * N
    for i in range(N):
        xi, yi = [int(_) for _ in raw_input().split()]
        xy[i] = (xi, yi)
    if N == 1:
        print N
        return
    xy.sort()
    dist = []
    for i in range(N):
        for j in range(i+1, N):
            p = xy[j][0] - xy[i][0]
            q = xy[j][1] - xy[i][1]
            dist.append((p,q))
    dist.sort()
    max_cnt = 0
    cnt = 1
    save = dist[0]
    for i in range(1, len(dist)):
        if dist[i] == save:
            cnt += 1
        else:
            max_cnt = max(cnt, max_cnt)
            cnt = 1
            save = dist[i]
    max_cnt = max(cnt, max_cnt)
    print N - max_cnt

if __name__ == '__main__':
    solve2()

Submission status: Accepted

Solution code:
from collections import Counter

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

if N == 1:
    ans = 1
else:
    diffs = Counter()
    for i in range(N):
        x1, y1 = balls[i]
        for j in range(N):
            if i == j: continue
            x2, y2 = balls[j]
            diffs.update([(x2-x1, y2-y1)])
    ans = N - diffs.most_common(1)[0][1]

print(ans)

Submission status: Accepted

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

ans = N
for i in range(N):
    for j in range(i+1, N):
        p, q = balls[j][0]-balls[i][0], balls[j][1]-balls[i][1]
        cost = N
        for a in range(N):
            x1, y1 = balls[a]
            for b in range(N):
                x2, y2 = balls[b]
                if (x2-x1, y2-y1) == (p, q):
                    cost -= 1
                    break
        ans = min(ans, cost)

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
def inpl(): return list(map(int, input().split()))

N = int(input())
XY = sorted([inpl() for _ in range(N)])
D = defaultdict(int)
for i in range(N):
    for j in range(i+1, N):
        D[(XY[j][0] - XY[i][0]), (XY[j][1] - XY[i][1])] += 1

print(N - max(D.values()) if N > 1 else 1)

Submission status: Accepted

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

L = sorted(L)

D = {}

for i in range(N-1) :
    ax,ay = L[i]
    for j in range(i+1,N) :
        bx,by = L[j]
        
        p = bx - ax
        q = by - ay
        
        k = str(p)+str(q)
        
        if k not in D :
            D[k] = 1
        else :
            D[k] += 1

if len(D) == 0 :
    ans = 1
else :
    ans = N - max(D.values())

print(ans)

Submission status: Accepted

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

if n == 1:
    print(1)
    exit()
li2 = [(x[0]-y[0],x[1]-y[1]) for x in li for y in li]
data = list(set(li2)) #かぶりを消すような作業や、カウントする前はsetがよい
data.remove((0,0))
data2 = tuple(data) #forなどでlistの中身をたくさん参照する場合はtupleがよい
qty = list(map(lambda x: li2.count(x),data2))

print(n-max(qty))

Submission status: Accepted

Solution code:
n,*t=map(int,open(0).read().split())
*z,=zip(t[::2],t[1::2])
m=1e18
for ax,ay in z:
  for bx,by in z:
    p,q=bx-ax,by-ay
    if not p+q:continue
    t=0
    for cx,cy in z:
      for dx,dy in z:
        if dx+p==cx and dy+q==cy:break
      else:t+=1
    if t<m:m=t
print(+(m>1e17)or m)

Submission status: Accepted

Solution code:
N=int(input())
XY =  [list(map(int, input().split())) for _ in range(N)]
if N==1:
    print(1)
    exit()
vecs = [  (x[0]-y[0], x[1]-y[1]) for y in XY   for x in XY]
pattern = list(set(vecs))
pattern.remove((0,0))
pattern2 = tuple(pattern)
qty = map(lambda x: vecs.count(x), pattern2)
data = zip(qty, pattern)
data2 = list(data)
data2.sort()
d = int(data2[-1][0])
print(N-d)

Submission status: Accepted

Solution code:
n=int(input())
xy=[list(map(int,input().split())) for _ in range(n)]
if n==1:
    print(1)
    exit()
pq={}
for i in range(n):
    x,y=xy[i]
    for j in range(n):
        if j==i:continue
        xx,yy=xy[j]
        p=xx-x
        q=yy-y
        pq.setdefault((p,q),0)
        pq[(p,q)]+=1
print(n-max(pq.values()))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
b = sorted([list(map(int,input().split())) for i in range(n)])
d = {}
for i in range(n):
    for j in range(i+1,n):
        x = (b[j][0]-b[i][0],b[j][1]-b[i][1])
        if x in d:
            d[x]+=1
        else:
            d[x]=1
if n==1:
    print(1)
else:
    print(n-max(d.values()))

Submission status: Accepted

Solution code:
n=int(input())
a=[tuple(map(int,input().split())) for i in range(n)]
p=[]
q=[]
ans=0
for i in range(n):
    for j in range(n):
        p.append(a[i][0]-a[j][0])
        q.append(a[i][1]-a[j][1])
for i in range(len(p)):
    cnt=0
    for j in range(n):
        if p[i]==0 and q[i]==0:
            break
        for k in range(n):
            if p[i]==a[j][0]-a[k][0] and q[i]==a[j][1]-a[k][1]:
                cnt+=1
    ans=max(cnt,ans)
print(n-ans)

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

ans = 1000

for i in range(N):
    for j in range(N):
        if i==j:continue
        cnt = 0
        p = x[i]-x[j]
        q = y[i]-y[j]
        for l in range(N):
            for m in range(N):
                if l==m : continue
                if x[l] - x[m] == p and y[l] - y[m] == q:
                    cnt += 1
        ans = min(ans,max(1,N-cnt))        
        
                
        
        
if N == 1 :
    print(1)
else:
    print(ans)

Submission status: Accepted

Solution code:
n=int(input())
l=[list(map(int,input().split())) for i in range(n)]
s=[list() for i in range(n)]
for i in range(n):
	a,b=l[i]
	for j in range(i):
		c,d=l[j]
		s[i].append((a-c,b-d))
		s[i].append((c-a,d-b))
D=set()
for i in range(n):
	D=D|set(s[i])
ans=0
for x in D:
	cnt=0
	for k in s:
		cnt+=k.count(x)
	ans=max(ans,cnt)
print(n-ans)

Submission status: Accepted

Solution code:
from itertools import count, combinations

def solve(p,q, limit, balls):
    cost = 0
    while balls:
        cost += 1
        if cost >= limit:
            return limit

        x,y = next(iter(balls))
        balls.discard((x,y))
        try:
            for n in count(1):
                balls.remove((x-n*p, y-n*q))
        except KeyError:
            pass

        try:
            for n in count(1):
                balls.remove((x+n*p, y+n*q))
        except KeyError:
            pass
    return cost


N = int(input())

balls = set(tuple(map(int,input().split())) for _ in range(N))

cost = len(balls)
for (a,b),(c,d) in combinations(sorted(balls), 2):
    cost = solve(a-c, b-d, cost, balls.copy())
print(cost)

Submission status: Accepted

Solution code:
N = int(input())
if N == 1:
    print(1)
else:
    xy = [tuple(int(e) for e in input().split()) for _ in range(N)]
    xy.sort()
    d = {}
    for i in range(N):
        for j in range(i + 1, N):
            p = xy[i][0] - xy[j][0]
            q = xy[i][1] - xy[j][1]
            if (p, q) in d:
                d[(p, q)] += 1
            else:
                d[(p, q)] = 1
    print(N - max(d.values()))

Submission status: Accepted

Solution code:
N = int(input())
if N == 1:
    print(1)
    exit()
xy = [tuple(int(e) for e in input().split()) for _ in range(N)]
d_list = [(i[0] - j[0], i[1] - j[1]) for i in xy for j in xy if i != j]
items = list(set(d_list))
s = 1
for item in items:
    c = d_list.count(item)
    if c > s:
        s = c
print(N - s)

Submission status: Accepted

Solution code:
import sys

def main():
    N = int(input())
    xy = [[int(e) for e in input().split()] for _ in range(N)]
    if N == 1:
        print(1)
        return
    else:
        d_list = [(i[0] - j[0], i[1] - j[1]) for i in xy for j in xy if i != j]
        items = list(set(d_list))
        s = 1
        for item in items:
            c = d_list.count(item)
            if c > s:
                s = c
        print(N - s)
        return

main()

Submission status: Accepted

Solution code:
N = int(input())
xy = [[int(e) for e in input().split()] for _ in range(N)]
if N == 1:
    print(1)
else:
    d_list = [(i[0] - j[0], i[1] - j[1]) for i in xy for j in xy if i != j]
    items = list(set(d_list))
    s = 1
    for item in items:
        c = d_list.count(item)
        if c > s:
            s = c
    print(N - s)

Submission status: Accepted

Solution code:
N = int(input())
xy = [list(map(int, input().split())) for _ in range(N)]
if N == 1:
    print(1)
else:
    d_list = [(i[0] - j[0], i[1] - j[1]) for i in xy for j in xy if i != j]
    items = list(set(d_list))
    s = 1
    for item in items:
        c = d_list.count(item)
        if c > s:
            s = c
    print(N - s)

Submission status: Accepted

Solution code:
import sys
import numpy as np


def main():
    n = int(input())
    balls = [[int(e) for e in input().split()] for _ in range(n)]
    if n == 1:
        print(n)
        sys.exit()
    diff = {}
    for i in range(n):
        for j in range(n):
            if i == j:
                continue
            if ((balls[i][0] - balls[j][0]), (balls[i][1] - balls[j][1])) in diff:
                diff[((balls[i][0] - balls[j][0]), (balls[i][1] - balls[j][1]))] += 1
            else:
                diff[((balls[i][0] - balls[j][0]), (balls[i][1] - balls[j][1]))] = 1
    print(n - max(diff.values()))


main()

Submission status: Accepted

Solution code:
from collections import defaultdict
n=int(input())
m=[[(0,0) for j in range(n)] for i in range(n)]
b=[]
if n==1:
    ans=1
else:
    for i in range(n):
        x,y=map(int,input().split())
        b.append((x,y))
    C=defaultdict(int)
    for i in range(n):
        for j in range(i+1,n):
            p,q=b[i][0]-b[j][0],b[i][1]-b[j][1]
            C[(p,q)]+=1
            C[(-p,-q)]+=1
                
    l=[]
    for i in C.items():
        l.append(i)
    l.sort(key=lambda x:x[1],reverse=True)

    ans=n-l[0][1]
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
import functools
import itertools

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

D = defaultdict(list)
for p1, p2 in itertools.combinations(P, 2):
    d = (p1[0] - p2[0], p1[1] - p2[1])
    if d[0] == 0 and d[1] == 0:
        continue
    elif d[0] == 0:
        d = (0, abs(d[1]))
    elif d[0] < 0:
        d = (-d[0], -d[1])
    for S in D[d]:
        if p1 in S:
            S.add(p2)
            break
        elif p2 in S:
            S.add(p1)
            break
    else:
        D[d].append({p1, p2})

ans = 50
for L in D.values():
    ans = min(ans, len(L) + N - functools.reduce(lambda x, S: x + len(S), L, 0))
print(ans if N >= 2 else 1)

Submission status: Accepted

Solution code:
from collections import Counter
n = int(input())
xy = [tuple([int(_) for _ in input().split()]) for i in range(n)]
if n == 1:
    result = 1
else:
    xy.sort()
    dxy = [(xy[i][0]-xy[j][0], xy[i][1]-xy[j][1])
           for i in range(n)
           for j in range(i+1, n)]
    cdxy = Counter(dxy)
    result = n - max(cdxy.values())
print(result)

Submission status: Accepted

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

if N == 1:

    result = 1

else:

    XY.sort()

    dxy = [
        (XY[i][0] - XY[j][0], XY[i][1] - XY[j][1])
        for i in range(N)
        for j in range(i + 1, N)
    ]

    from collections import Counter

    cdxy = Counter(dxy)

    m = max(cdxy.values())

    #print(XY)
    #print(dxy)
    #print(cdxy)

    result = N - m

print(result)

Submission status: Accepted

Solution code:
n = int(input())
if n ==1:
    print( 1)
    exit()
cost = 0
points = []
for i in range(n):
    points.append(list(map(int, input().split())))

points.sort()
dictpq = {}
for i in range(n):
    for j in range(i+1,n):
        p = points[i][0] - points[j][0]
        q = points[i][1] - points[j][1]
        if (p,q) in dictpq:
            dictpq[(p,q)] +=1
        else:
            dictpq[(p,q)] =1
print(n-max(dictpq.values()))

Submission status: Accepted

Solution code:
N = int(input())
if N <= 2:
    print(1)
else:
    xy = []
    for _ in range(N):
        xy.append(list(map(int, input().split())))
    
    xy.sort()

    max_dup = 0
    for i in range(N-1):
        curr_i = xy[i]
        for j in range(i+1, N):
            curr_j =xy[j]
            p, q = curr_j[0] - curr_i[0], curr_j[1] - curr_i[1]
            
            cnt = 0
            for n in range(N):
                if n == 0:
                    continue
                if [xy[n][0]-p, xy[n][1]-q] in xy:
                # (xy[n][0]-xy[n-1][0] == p) and (xy[n][1]-xy[n-1][1] == q):
                
                    cnt += 1
            max_dup = max(max_dup, cnt)
    print('{}'.format(N-max_dup))

Submission status: Accepted

Solution code:
n=int(input())
xy=[]
for i in range(n):
    a=[int(j) for j in input().split()]
    xy.append(a)

if n==1:
    print(1)
    import sys
    sys.exit()
l=[]
ans=0
import itertools
for a,b in itertools.combinations(xy,2):
    p=(a[0]-b[0])
    q=(a[1]-b[1])
    if p!=0 or q!=0:
        l.append((p,q))
        l.append((-p,-q))

import collections
c=collections.Counter(l)
p=c.most_common()

for i in p:
   ans=max(ans,i[1])
print(n-ans)

Submission status: Accepted

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

D={}
for i in range(N):
    for j in range(N):
        D[(L[i][0]-L[j][0],L[i][1]-L[j][1])]=1
#print(D)

ANS=N

for i in D.keys():
    cnt=0
    for j in range(len(L)):
        for k in range(len(L)):
            if j==k:
                continue
            elif i[0]==(L[j][0]-L[k][0]) and i[1]==(L[j][1]-L[k][1]):
                cnt+=1
    ANS=min(ANS,N-cnt)
print(ANS)

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")
    exit()
#(p,q)に対応するグラフの辺の数
dic = {}

#すべての点について検討
for i in range(N):
    for j in range(i+1,N):
        #dx,dy == p,qの候補
        dx = balls[j][0] - balls[i][0]
        dy = balls[j][1] - balls[i][1]

        if (dx,dy) not in dic:
            dic[(dx,dy)] = 1
        else:
            dic[(dx,dy)] += 1
        
        dx *= -1
        dy *= -1
        if (dx,dy) not in dic:
            dic[(dx,dy)] = 1
        else:
            dic[(dx,dy)] +=1 
d_max = max(dic.values())
print(N-d_max)

Submission status: Accepted

Solution code:
#[R,G,B,N] = list(map(int,input().split()))
import collections
N = int(input())
xy = [tuple(map(int,input().split())) for i in range(N)]
xy.sort( key = lambda x: (x[0],x[1]))
l = []
for i in range(N):
    for j in range(i+1,N):
        (x_diff, y_diff) = [xy[i][0]-xy[j][0],xy[i][1]-xy[j][1]]
        l.append((x_diff, y_diff))
dic = collections.Counter(l)
val = dic.values()
if len(val) == 0:
    print(1)
else:
    print(N - max(val))

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

dic = {}
for i in range(N):
    for j in range(i+1,N):
        dx = balls[j][0] - balls[i][0]
        dy = balls[j][1] - balls[i][1]
        if (dx,dy) not in dic.keys():
            dic[(dx,dy)] = 1
        else:
            dic[(dx,dy)] += 1
        dx *= -1
        dy *= -1
        if (dx,dy) not in dic.keys():
            dic[(dx,dy)] = 1
        else:
            dic[(dx,dy)] += 1

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

Submission status: Accepted

Solution code:
n=int(input())
if n==1:
	print(1)
	exit()
xy = sorted([list(map(int,input().split())) for i in range(n)])
p=q=0
ans=0
dic={}
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]
		if (p,q) in dic:
			dic[(p,q)]+=1
		else:
			dic[(p,q)]=1
print(n-max(dic.values()))

Submission status: Accepted

Solution code:
from collections import defaultdict
from collections import deque
from string import ascii_uppercase
import sys, bisect, math, heapq

stdin = sys.stdin
read_int = lambda : list(map(int,stdin.readline().split()))
read_str = lambda : stdin.readline().rstrip()

N = read_int()[0]
xy = [read_int() for _ in range(N)]

def solve():
    pq = defaultdict(lambda: int())
    res = []
    M = 0
    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]
            count = 0
            # print(p,q)
            for ii in range(N):
                for jj in range(N):
                    if ii == jj: continue
                    if xy[ii][0] - xy[jj][0] == p and xy[ii][1] - xy[jj][1] == q:
                        count += 1
            # res.append(count)
            M = max(M, count)
    # print(res)
    ans = N - M
    return ans

if __name__ == "__main__":
    print(solve())

Submission status: Accepted

Solution code:
N = int(input())

xy = [[0,0] for i in range(N)]

for i in range(N):
    tmp_x, tmp_y = map(int, input().split())
    xy[i][0] = tmp_x
    xy[i][1] = tmp_y

#x座標でソート
xy = sorted(xy, key = lambda x: x[0])



ans = 9999
for i in range(N):
    for j in range(N):
        if i == j:
            continue
        else:
            p = xy[i][0] - xy[j][0]
            q = xy[i][1] - xy[j][1]
        tmp = 0
        for x in range(N):
            for y in range(N):
                if x == y:
                    continue
                else:
                    if  xy[x][0] - xy[y][0] == p and xy[x][1] - xy[y][1] == q:
                        tmp += 1
        ans = min(ans, N - tmp)
if N == 1:
    print(1)
else:
    print(ans)

Submission status: Accepted

Solution code:
N = int(input())

xys = []
from collections import defaultdict
for i in range(N):
    x, y = map(int, input().split())
    xys.append((x, y))
pqs = []
for xy1 in xys:
    x1, y1 = xy1

    for xy2 in xys:
        x2, y2 = xy2

        dx = x1 - x2
        dy = y1 - y2

        if dx != 0 or dy != 0:
            pqs.append((dx, dy))

ans = N
for pq in pqs:
    p, q = pq
    count = 0
    for xy1 in xys:
        x1, y1 = xy1

        for xy2 in xys:
            x2, y2 = xy2

            dx = x1 - x2
            dy = y1 - y2
            if dx == p and dy == q:
                count += 1

    ans = min(ans, N - count)

print(ans)