Problem:


Score : 300 points

Problem Statement

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

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

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

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

Constraints

1 \leq N \leq 50

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

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

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
x_1 y_1
:
x_N y_N

Output

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

Sample Input 1

2
1 1
2 2

Sample Output 1

1

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

Sample Input 2

3
1 4
4 6
7 8

Sample Output 2

1

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

Sample Input 3

4
1 1
1 2
2 1
2 2

Sample Output 3

2



Sample input:
2
1 1
2 2


Sample output:
1

Submission status: Accepted

Solution code:
n=int(input())
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[j][0]-xy[i][0]
		q = xy[j][1]-xy[i][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:
import numpy as np

def main():
    n = int(input())
    ball = [list(map(int, input().split(' '))) for i in range(n)]
    ball = np.array(ball, dtype=int)
    if n == 1:
        print(1)
        exit()

    l1 = []
    for i in range(len(ball)):
        for j in range(len(ball)):
            if i == j: continue
            dis1 = ball[i] - ball[j]
            l1.append(list(dis1))

    c1 = []
    for i in range(len(l1)):
        c1.append(l1.count(l1[i]))
    m1 = np.max(np.array(c1, dtype=int))

    print(n-m1)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:

# -*- coding: utf-8 -*-
# @Date    : 2019-06-15 20:02:29
# @Author  : raj lath (oorja.halt@gmail.com)
# @Link    : link
# @Version : 1.0.0

import sys
sys.setrecursionlimit(10**5+1)

inf     =  int(10 ** 20)
max_val =  inf
min_val = -inf

RW  = lambda : sys.stdin.readline().strip()
RI  = lambda : int(RW())
RMI = lambda : [int(x) for x in sys.stdin.readline().strip().split()]
RWI = lambda : [x for x in sys.stdin.readline().strip().split()]
from collections import defaultdict

nb_points = RI()
points    = [RMI() for _ in range(nb_points)]
if nb_points == 1:
    print(1)
else:
    pq = defaultdict(int)
    for i in range(nb_points):
        for j in range(nb_points):
            if i == j : continue
            p1 = points[i][0] - points[j][0]
            q1 = points[i][1] - points[j][1]
            pq[(p1, q1)]  = pq.get((p1, q1), 0) + 1
    print(nb_points - max(pq.values()))

Submission status: Accepted

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

ans = float("inf")

if N < 3:
  ans = 1
else:   
  for i in range(N):
    x, y = xy[i][0], xy[i][1]
    for j in range(N):
      if i == j:
        continue
      p, q = xy[j][0] - x, xy[j][1] - y
      cnt = 0
      for k in range(N):
        xk, yk = xy[k][0], xy[k][1]
        for l in range(N):
          if k == l:
            continue
          if xy[l][0] - xk == p and xy[l][1] - yk == q:
            cnt += 1
      ans = min(ans, N - cnt)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
xy = []
ans = []

for i in range(n):
    xin,yin = map(int,input().split())
    xy.append([xin,yin])

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

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

for i in range(n):
    for j in range(n):
        if( i==j ):
            continue
        t = (xy[i][0]-xy[j][0],xy[i][1]-xy[j][1])
        ans.append(t)

res = [ans.count(e) for e in set(ans)]
print(n-max(res))

Submission status: Accepted

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

def func(p,q):
    flag = [0]*n
    for i in range(n):
        for j in range(n):
            if i==j or flag[j-1]==1:
                continue
            if xy[j][0]-xy[i][0]==p and xy[j][1]-xy[i][1]==q:
                flag[j-1]=1
    return n-sum(flag)

ans = n
for i in range(n):
    for j in range(n):
        if i==j:
            continue
        ans = min(ans,func(xy[j][0]-xy[i][0],xy[j][1]-xy[i][1]))
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import deque  # 双方向キュー
from collections import defaultdict  # 初期化済み辞書
from heapq import heapify, heappush, heappop, heappushpop  # プライオリティキュー
from bisect import bisect_left, bisect_right  # 二分探索
#import numpy as np  # 1.8.2
#import scipy  # 0.13.3

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

def main():
    N = i2n()
    xy = ii2nnn(N)
    if N == 1:
        print(1)
        return
    dic = defaultdict(lambda: 0)
    for i in range(N):
        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 == 0 and dy == 0:
                continue
            dic[(dx, dy)] += 1
    n = N - max(dic.values())
    print(n)

main()

Submission status: Accepted

Solution code:
from collections import Counter
N = int(input())
if N == 1:
    print(1)
else:
    X = []
    for i in range(N):
        xi,yi = map(int,input().split())
        X.append((xi,yi))
    L = []
    for i in range(N):
        for j in range(N):
            if i == j:
                continue
            x,y = X[i][0]-X[j][0],X[i][1]-X[j][1]
            L.append((x,y))
    m = Counter(L).most_common()[0][1]
    print(N-m)

Submission status: Accepted

Solution code:
from collections import deque
n=int(input())
balls=[[int(i) for i in input().split()] for _ in range(n)]
diff=deque()
if n<=2:
    print(1)
else:
    for i in balls:
        for j in balls:
            if i!=j:
                diff.append((j[0]-i[0],j[1]-i[1]))
    ans=100000000000
    for p,q in set(diff):
        cnt=n
        for i in balls:
            for j in balls:
                if i!=j and j[0]-i[0]==p and j[1]-i[1]==q:
                    cnt-=1
        if cnt<ans:
            ans=cnt
    print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)
#'''
N = int(input())
x, y = [0] * N, [0] * N

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

pq = []
m = 1

if N == 1:
	print(1)
else:	
	for i in range(N):
		for j in range(N):
			if i == j:
				continue
				
			p, q = x[j] - x[i], y[j] - y[i]
			pq.append([p, q])
			
	for i in range(len(pq) - 1):
		n = 1
		for j in range(i + 1, len(pq)):
			if pq[i] == pq[j]:
				n += 1
				
		if n > m:
			m = n
			
	cost = N - m
	print(cost)

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:
import itertools
from collections import Counter
from collections import defaultdict

d = defaultdict(lambda:-1)
N = int(input())
X = [0]*N
Y = [0]*N
for i in range(N):
    X[i],Y[i] = map(int,input().split())
    d[(X[i],Y[i])] = i

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

o = []
for i,j in itertools.product(range(N),range(N)):
    if i == j:
        continue
    x = X[i] - X[j]
    y = Y[i] - Y[j]
    o.append((x,y))

p,q = Counter(o).most_common()[0][0]
o = []
for i in range(N):
    a = i
    while True:
        b = d[(X[a]+p,Y[a]+q)]
        if b == -1:
            o.append(a)
            break
        a = b

print(len(set(o)))

Submission status: Accepted

Solution code:
n = int(input())
x = [0]*n
y = [0]*n

if n == 1:
  print(1)
else:
  for i in range(n):
    x[i],y[i] = map(int, input().split())
  ans = []
  for i in range(n):
    for j in range(n):
      if i == j:
        continue
      p = x[i]-x[j]
      q = y[i]-y[j]
      count = 0
      for k in range(n):
        for l in range(n):
          if p == x[k]-x[l] and q == y[k]-y[l]:
            count += 1
            ans.append(count)
  print(n-max(ans))

Submission status: Accepted

Solution code:
# div2019-2B - Picking Up
from collections import defaultdict

n = int(input())
arr = sorted([list(map(int, input().rstrip().split())) for _ in range(n)])
cnt = defaultdict(int)
for i in range(n):
    for j in range(i + 1, n):
        dif = (arr[j][0] - arr[i][0], arr[j][1] - arr[i][1])
        cnt[dif] += 1
print(n - max(cnt.values(), default=0))

Submission status: Accepted

Solution code:
from collections import Counter

N = int(input())

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

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

d = []
for i, p1 in enumerate(p):
    for j, p2 in enumerate(p):
        if i == j:
            continue
        x = p1[0] - p2[0]
        y = p1[1] - p2[1]
        d.append((x, y))

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

Submission status: Accepted

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

balls.sort()

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]
        useds = [False] * N
        num = 0
        for a in range(N):
            if useds[a]: continue
            useds[a] = True
            num += 1
            x, y = balls[a]
            for b in range(a+1, N):
                if useds[b]: continue
                if balls[b] == (x+p, y+q):
                    useds[b] = True
                    x, y = balls[b]
        ans = min(ans, num)

print(ans)

Submission status: Accepted

Solution code:
n = int(input());
if n==1:
	print(n)
	exit(0)
point = [[0]*2 for i in range(n) ];
for i in range(n) :
	s = input().split(" ");
	point[i][0] = int(s[0]);
	point[i][1] = int(s[1]);

dict = {}
for i in range(n) :
	for j in range(n) :
		if i != j  :
			x = point[i][0] - point[j][0];
			y = point[i][1] - point[j][1];
			if (x,y) in dict:
				dict[(x,y)] += 1
			else:
				dict[(x,y)] = 1
print(n-max(dict.values()));

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline


def read_int():
    return int(input())


def read_int_n():
    return tuple(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, XY):
    c = Counter()
    for i in range(N):
        x, y = XY[i]
        for j in range(N):
            if i == j:
                continue
            a, b = XY[j]
            c[(x-a, y-b)] += 1

    if not c:
        return N
    return N - c.most_common(1)[0][1]


def main():
    N = read_int()
    XY = [read_int_n() for _ in range(N)]
    print(slv(N, XY))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict
n = int(input())
s = [list(map(int,input().split())) for i in range(n)]
s.sort()
c = []
if n == 1:
    print(1)
else:
    for i in range(n):
        for j in range(i+1,n):
            x = s[j][0] - s[i][0]
            y = s[j][1] - s[i][1]
            c.append(str(x) + " " + str(y))
    r = defaultdict(int)
    for g in c:
        r[g] += 1
    q = list(r.values())
    q1 = max(q)
    print(n-q1)

Submission status: Accepted

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

vectors = []
ans_inv = 0
for i in range(N):
    for j in range(i+1,N):
        vector = [x_y[i][0]-x_y[j][0],x_y[i][1]-x_y[j][1]]
#        print(vector)
        if vector[0]<0:
            vector = [x_y[j][0]-x_y[i][0],x_y[j][1]-x_y[i][1]]
        elif vector[0] == 0 and vector[1]<0:
            vector = [x_y[j][0]-x_y[i][0],x_y[j][1]-x_y[i][1]]
        vectors.append(vector)
cnt = 0
for i in range(len(vectors)):
    cnt = max(cnt,vectors.count(vectors[i]))

print(N-cnt)

Submission status: Accepted

Solution code:
from collections import Counter
 
n = int(input())
XY = [list(map(int,input().split())) for i in range(n)]
ball = []
 
for i,xy in enumerate(XY):
	for j,xxyy in enumerate(XY):
		# print(i,j)
		if i == j:
			continue
		ball.append([xy[0]-xxyy[0],xy[1]-xxyy[1]])
 
ball.sort()
 
count = 1
ans = 0
inf = float("inf")
xx = inf
yy = inf
for x,y in ball:
	if x == xx and y == yy:
		count += 1
	else:
		ans = max(ans,count)
		count = 1
		xx = x
		yy = y
ans = max(ans,count)
if n == 1:
	ans = 0
print(n-ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
n = int(input())
s = [list(map(int,input().split())) for i in range(n)]
s.sort()
c = []
if n == 1:
    print(1)
else:
    for i in range(n):
        for j in range(i+1,n):
            x = s[j][0] - s[i][0]
            y = s[j][1] - s[i][1]
            c.append(str(x) + " " + str(y))
    r = defaultdict(int)
    for g in c:
        r[g] += 1
    q = list(r.values())
    q1 = max(q)
    print(n-q1)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
N = int(input())
li = []
if N == 1:
    a = list(map(int,input().split()))
    print(1)
    sys.exit()   

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

cross = []

##計算量に余裕があるので全探索します
for i in range(N):
    for j in range (i+1, N):
        a = [li[j][0]-li[i][0],li[j][1]-li[i][1]]
        if a[0] <= 0 and a[1] <= 0:
            b = [abs(li[j][0]-li[i][0]),abs(li[j][1]-li[i][1])]
            cross.append(b)
        elif a[0] < 0 and a[1] >= 0:
            c = li[j][1]-li[i][1]
            b = [abs(li[j][0]-li[i][0]),-c]
            cross.append(b) ####
        else:
            cross.append(a) 
lencross = len(cross)

res = 0
ans = []

for i in range (lencross):
    res = 0
    for j in range (lencross):
        if cross[i] == cross[j]:
            res += 1
    ans.append(res)
reduce = max(ans)

print(N - reduce)

Submission status: Accepted

Solution code:
from collections import Counter
N = int(input())
ball = [[int(i) for i in input().split()] for k in range(N)]
ball.sort(key=lambda x: x[1])
ball.sort()
diff = []
if N == 1:
    print(1)
else:
    for i in range(N-1):
        for j in range(i+1, N):
            diff.append([(ball[j][n]-ball[i][n]) for n in range(2)])
    k = Counter(map(tuple, diff)).most_common()[0][1]
#    print(diff)
    print(max(1,N-k))

Submission status: Accepted

Solution code:
from collections import Counter
import sys

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

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

dc_c = []
dc_c = []
dc_ans = []
for i in range(n):
    ii = 0
    d = [[-1]*2 for i in range(n)]
    for j in range(n):
        if i != j:
            d[ii][0] = x[i]-x[j]
            d[ii][1] = y[i]-y[j]
            ii += 1
    dc = Counter(map(tuple, d))
    dc_ans = Counter(dc_ans) + dc
dc_ans = dc_ans.most_common()
if dc_ans[0][0] == (-1, -1):
    print(n-dc_ans[1][1])
else:
    print(n-dc_ans[0][1])

Submission status: Accepted

Solution code:
from collections import defaultdict as de
s=de(int)
n=int(input())
a=sorted([list(map(int,input().split()))for i in range(n)])
for i in range(n):
    for j in range(i):
        s[(a[i][0]-a[j][0],a[i][1]-a[j][1])]+=1
print(n-max(s.values(),default=0))

Submission status: Accepted

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

pq = {0:0}
for i in range(N):
    for j in range(N):
        if i==j:continue
        p = xy[i][0] - xy[j][0]
        q = xy[i][1] - xy[j][1]
        pq[(p,q)] = pq.get((p,q),0)+1

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

Submission status: Accepted

Solution code:
import sys

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

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

ans = []
for i in range(n):
    for j in range(n):
        if i == j:
            continue
        p = x[i]-x[j]
        q = y[i]-y[j]
        count = 0
        for k in range(n):
            for l in range(n):
                if p == x[k]-x[l] and q == y[k]-y[l]:
                    count += 1
                ans.append(count)

print(n-max(ans))

Submission status: Accepted

Solution code:
n=int(input())
r=[]
a=[]
for i in range(n):
  b,c=(int(j) for j in input().split())
  for k in range(i):
    d=a[k][0]-b
    e=a[k][1]-c
    if d<0:
      d=-d
      e=-e
    elif d==0:
      if e<0:
        e=-e
    r.append([d,e])
  a.append([b,c])
r.sort()
if n>1:
  p=r[0]
x=1
z=0
t=0
q=[]
for i in range(len(r)-1):
  if r[i]==r[i+1]:
    x=x+1
    if x>z:
      p=r[i]
      z=x
  else:
    x=1
for j in range(n-1):
  for i in range(n-1):
    if a[i][0]>a[i+1][0]:
      w=a[i]
      a[i]=a[i+1]
      a[i+1]=w
    elif a[i][0]==a[i+1][0]:
      if (a[i][1]-a[i+1][1])*p[1]>0:
        w=a[i]
        a[i]=a[i+1]
        a[i+1]=w
if n==1:
  print(1)
else:
  for i in range(n):
    if a[i] not in q:
      t=t+1
    q.append([a[i][0]+p[0],a[i][1]+p[1]])
  print(t)

Submission status: Accepted

Solution code:
n = int(input())
l = []
l2 = []

for i in range(n):
    a, b = list(map(int, input().split()))
    l.append([a,b])
l.sort()

for i in range(len(l)-1):
    for j in range(i+1, len(l)):
        dif1 = l[i][0] - l[j][0]
        dif2 = l[i][1] - l[j][1]
        l2.append(str(dif1) + ' ' + str(dif2))
##print(l2)

try:
    cnt = max(l2, key=l2.count)
except:
    cnt = "1000000 1000000"
x, y = list(map(int, cnt.split()))

ans = 0

for i in range(len(l)):
    if [l[i][0] + x, l[i][1] + y] in l:
        ans += 1

print(n - ans)

Submission status: Accepted

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

PQ = []
# 2点を選びp,q仮決め
for i in range(N):
    prev = XY[i]
    for j in range(N):
        if i!=j:
            next = XY[j]
            p = next[0] - prev[0]
            q = next[1] - prev[1]
            PQ.append((p,q))

ans = 1
for pq in PQ:
    ans = max(ans, PQ.count(pq))
print(N - ans if N>1 else 1)

Submission status: Accepted

Solution code:
import sys
N = int(input())
li = []
if N == 1 or N == 2:
    a = list(map(int,input().split()))
    print(1)
    sys.exit()   

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

cross = []

##計算量に余裕があるので全探索します
for i in range(N):
    for j in range (i+1, N):
        a = [li[j][0]-li[i][0],li[j][1]-li[i][1]]
        if a[0] <= 0 and a[1] <= 0:
            b = [abs(li[j][0]-li[i][0]),abs(li[j][1]-li[i][1])]
            cross.append(b)
        elif a[0] < 0 and a[1] >= 0:
            c = li[j][1]-li[i][1]
            b = [abs(li[j][0]-li[i][0]),-c]
            cross.append(b) ####
        else:
            cross.append(a) 
lencross = len(cross)

res = 0
ans = []

for i in range (lencross):
    res = 0
    for j in range (lencross):
        if cross[i] == cross[j]:
            res += 1
    ans.append(res)
reduce = max(ans)

print(N - reduce)

Submission status: Accepted

Solution code:
import sys
# input = sys.stdin.readline
inf = 10 ** 18

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

x = [xi for xi, yi in xy]
y = [yi for xi, yi in xy]

ans = inf
for i in range(N - 1):
    xi, yi = xy[i]
    for j in range(i + 1, N):
        xj, yj = xy[j]
        #
        p = xj - xi
        q = yj - yi
        #
        ans_tmp = 0
        for n, (xn, yn) in enumerate(xy):
            xm = xn - p
            ym = yn - q
            # print("##", (xm, ym))
            if [xm, ym] not in xy: ans_tmp += 1
        #
        # print("#", xy, ans_tmp)
        if ans > ans_tmp: ans = ans_tmp

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

Submission status: Accepted

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

chk=0
for i in range(n):
    a=d[i][0]
    b=d[i][1]
    for j in range(n):
        if i==j: continue
        p=d[j][0]
        q=d[j][1]
        if (a-p,b-q) in w:
            w[(a-p,b-q)]+=1
        else:
            w[(a-p,b-q)]=1
        chk=max(chk,w[(a-p,b-q)])
print(n-chk)

Submission status: Accepted

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

from collections import Counter
list_=[]

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

if N==1:
    print(1)
else:
    print(N-Counter(list_).most_common()[0][1])

Submission status: Accepted

Solution code:
import sys
N=int(input())
# N=50

p = []
for n in range(N):
    x,y = map(int,input().split())
    # x,y = n,n
    p.append( (x,y) )

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

p = list(sorted(p))

diffs = {}
for i,pi in enumerate(p):
    for j,pj in enumerate(p):
        if i < j:
            diff = (pi[0]-pj[0], pi[1]-pj[1])
            if diff not in diffs:
                diffs[diff] = 0
            diffs[diff] += 1

mxdiff = 0
for k in diffs:
    mxdiff = max(mxdiff, diffs[k])
print(N-mxdiff)

Submission status: Accepted

Solution code:
N=int(input())
point=[]
merge=0
for num in range(0,N):
    x,y=map(int,input().split())
    point.append([x,y])
p=0
q=0
point.sort()
ans=0
for i in range(0,N-1):
    for j in range(i+1,N):
        p=point[j][0]-point[i][0]
        q=point[j][1]-point[i][1]
        merge=0
        for k in range(0,N):
            if([point[k][0]+p,point[k][1]+q] in point):
                merge+=1
        ans=max(ans,merge)
print(N-ans)

Submission status: Accepted

Solution code:
l = input().split()
N = int(l[0])

XY = []

for i in range(N):
    l = input().split()
    XY.append((int(l[0]), int(l[1])))

# print(N, XY)

diffs = []

for i in range(N):
    for j in range(N):
        if i == j:
            continue
        diff = (XY[i][0] - XY[j][0], XY[i][1] - XY[j][1])
        if diff not in diffs:
            diffs.append(diff)

# print(diffs)

def same_diff(d1, d2):
    return d1[0] == d2[0] and d1[1] == d2[1]

max_count = 0
for diff in diffs:
    count = 0
    for i in range(N):
        for j in range(N):
            if i == j:
                continue
            d = (XY[i][0] - XY[j][0], XY[i][1] - XY[j][1])
            if d == diff:
                count += 1
                # print(diff, i, j, count)
    max_count = max(max_count, count)

print(N - max_count)

Submission status: Accepted

Solution code:
from collections import Counter
N = int(input())
L = sorted([list(map(int,input().split())) for k in range(N)])
D = []
if N == 1:
    print(1)
    exit(0)
for k in range(N-1):
    for l in range(k+1,N):
        D.append((L[k][0]-L[l][0],L[k][1]-L[l][1]))

E = Counter(D).most_common()[0]
x, y = E[0][0], E[0][1]
used = []
ans = N
for k in range(N-1):
    for l in range(k+1,N):
        if L[k][0]-L[l][0] == x and L[k][1]-L[l][1] == y:
            if L[k] not in used and L[l] not in used:
                used.append(L[k])
                used.append(L[l])
                ans -= 1
            elif L[k] in used and L[l] not in used:
                used.append(L[l])
                ans -= 1
            elif L[k] not in used and L[l] in used:
                used.append(L[k])
                ans -= 1
            else:
                pass
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from collections import defaultdict

n = int(input())
pairs = list()
patterns = defaultdict(int)

for _ in range(n):
    pairs.append(tuple((map(int, input().split()))))

for i in range(n):
    for j in range(n):
        if i != j:
            patterns[(pairs[i][0] - pairs[j][0], pairs[i][1] - pairs[j][1])] += 1

ans = 1
if n > 1:
    ans = n - max(patterns.values())

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
xy=[list(map(int,input().split())) for _ in range(n)]
xy.sort(key=lambda x:(x[0],x[1]))
# print(xy)
if n<=2:
    print(1)
else:
    diff=[]
    for i in range(n):
        for j in range(i):
            diff.append((xy[i][0]-xy[j][0],xy[i][1]-xy[j][1]))

    ans=[]
    # print(set(diff))
    for p,q in set(diff):
        cnt=n
        for i in range(n):
            for j in range(i):
                if xy[i][0]-xy[j][0]==p and xy[i][1]-xy[j][1]==q:
                    cnt-=1
        ans.append(cnt)
    print(min(ans))

Submission status: Accepted

Solution code:
n = int(input())
xy = [list(map(int, input().split())) for i in range(n)]
sa = {}
for i in xy:
    for j in xy:
        if i != j:
            a = ",".join([str(i[0] - j[0]), str(i[1] - j[1])])
            if a not in sa:
                sa[a] = 1
            else:
                sa[a] += 1
ans = 0
for i in sa.values():
    ans = max(ans, i)
print(n - ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from collections.abc import Iterable
from math import *
from itertools import *
from collections import *
from functools import *
from operator import *
try:
    from math import gcd
except Exception:
    from fractions import gcd


def solve(N: int, x: "List[int]", y: "List[int]"):
    ds = []
    for i in range(N):
        for j in range(N):
            if i == j:
                continue
            dx = x[j] - x[i]
            dy = y[j] - y[i]
            ds.append((dx, dy))

    return 1 if N == 1 else (N - max(Counter(ds).values()))


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))
    result = solve(N, x, y)
    print(result)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict
from operator import itemgetter

N = int(input())
p = []
for _ in range(N):
    p.append(tuple(map(int, input().split())))
p.sort(key=itemgetter(0), reverse=True)

if N == 1:
    print(1)
else:
    d = defaultdict(int)
    for i, pp1 in enumerate(p):
        for j in range(N):
            if i == j:
                continue
            pp2 = p[j]
            d[(pp1[0] - pp2[0], pp1[1] - pp2[1])] += 1
    # print(d)

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
from collections import Counter
N = int(input())
answer = []
answer2 = []
lis = []
lis2 = []
for i in range(N):
    x, y = map(int, input().split())
    lis.append([x, y])
    lis2.append([y, x])
sort_lis = sorted(lis)
sort_lis2 = sorted(lis2)

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

for i in range(N-1):
    for j in range(i+1,N):
        answer.append([sort_lis[i][0] -sort_lis[j][0],sort_lis[i][1]-sort_lis[j][1]])
ans = list(map(tuple,answer))

a = Counter(ans).most_common()

print(len(lis)-a[0][1])

Submission status: Accepted

Solution code:
n=int(input())
arr=[list(map(int,input().split())) for _ in range(n)]
arr=sorted(arr,key=lambda x:x[1])
arr=sorted(arr,key=lambda x:x[0])
ans=n
for i in range(n):
  for j in range(i+1,n):
    p,q=arr[j][0]-arr[i][0],arr[j][1]-arr[i][1]
    cnt=0
    flag=[0]*n
    for k in range(n):
      if flag[k]==1:
        continue
      flag[k]=1
      a,b=arr[k][0],arr[k][1]
      while 1:
        for l in range(n):
          if flag[l]==1:
            continue
          if a+p==arr[l][0] and b+q==arr[l][1]:
            flag[l]=1
            a=arr[l][0]
            b=arr[l][1]
            break
        else:
          break
      cnt+=1
    ans=min(ans,cnt)
print(ans)

Submission status: Accepted

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import numpy as np

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

N = int(input())
xy = [[] for i in range(N)]
for i in range(N):
    xy[i] = [int(i) for i in input().split()]

xy = np.array(xy)
count_dic = {}
for i in range(N):
    for j in range(i+1,N):
        diff = xy[i] - xy[j]
        p,q = diff
        if p == 0 and q == 0:
            pass
        else:
            k = (p,q)
            if k in count_dic:
                count_dic[k] += 1
            else:
                count_dic[k] = 1
            k = (-p,-q)
            if k in count_dic:
                count_dic[k] += 1
            else:
                count_dic[k] = 1


"""
            p = int(p)
            q = int(q)
            pq = str(p)+str(q)
            pq2 = str(-p)+str(-q)
            if pq in count_dic:
                count_dic[pq] += 1
            else:
                count_dic[pq] = 1
            if pq2 in count_dic:
                count_dic[pq2] += 1
            else:
                count_dic[pq2] = 1

"""
# print(count_dic)
ans = 1
for k,v in sorted(count_dic.items(), key = lambda x:-x[1]):
    ans = N - v
    break
print(max(1,ans))