Problem:


Score : 300 points

Problem Statement

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

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

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

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

Constraints

1 \leq N \leq 50

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

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

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
x_1 y_1
:
x_N y_N

Output

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

Sample Input 1

2
1 1
2 2

Sample Output 1

1

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

Sample Input 2

3
1 4
4 6
7 8

Sample Output 2

1

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

Sample Input 3

4
1 1
1 2
2 1
2 2

Sample Output 3

2



Sample input:
2
1 1
2 2


Sample output:
1

Submission status: Accepted

Solution code:

# from collections import Counter

def solve():
    N = int(input())
    XY = [[int(i) for i in input().split()] for _ in range(N)]
    # print(XY)
    length_list = []
    for i in range(N):
        xi, yi = XY[i]
        for j in range(N):
            if i == j:
                continue
            xj, yj = XY[j]
            length_list.append([xi - xj, yi - yj])
    # print(length_list)
    max_count = 0
    for xy in length_list:
        count = length_list.count(xy)
        max_count = max(max_count, count)
    # print(max_count)
    print(N - max_count)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
# coding: utf-8

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

N = int(input())
# L = [int(x) for x in input().split()]
# N, M = map(int, input().split())
# S = input()

ball = [[int(x) for x in input().split()] for _ in range(N)]
dist = {}

for i, a in enumerate(ball):
    x0 = a[0]
    y0 = a[1]

    for j, b in enumerate(ball):
        x1 = b[0]
        y1 = b[1]

        xy = (x1-x0, y1-y0)

        if xy == (0, 0):
            continue

        if not xy in dist:
            dist[xy] = 1
        else:
            dist[xy] += 1

try:
    num = max(dist.values())
except:
    num = 0

print(N - num)

Submission status: Accepted

Solution code:
from itertools import*
from math import*
from collections import*
from heapq import*
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf = float("inf")
mod = 10**9+7
from functools import reduce
import sys
sys.setrecursionlimit(10**7)


N = int(input())
pair=defaultdict(int)
xy = []
for i in range(N):
    x,y = map(int,input().split())
    xy.append((x,y))
for i in range(N):
    for j in range(N):
        if i != j:
            pair[(xy[j][0]-xy[i][0],xy[j][1]-xy[i][1])] += 1

m = 0
for v in pair.values():
    m = max(m,v)
print(N-m)

Submission status: Accepted

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

li.sort(key = lambda x:x[0])
li2 = []

for i in range(n):
    for j in range(i):
        a = [li[i][0]-li[j][0],li[i][1]-li[j][1]]
        li2.append(a)

for i in li2:
    if i[0] < 0:
        i[0] = -i[0]
        i[1] = -i[1]
    if i[0] == 0 and i[1] < 0:
        i[1] = -i[1]

ans = 0

for i in li2:
    ans = max(ans,li2.count(i))

print(n-ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys
from itertools import combinations
from collections import Counter

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N=INT()

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

xy=[]
for i in range(N):
    x,y=MAP()
    xy.append((x, y))

C=Counter()
for comb in combinations(xy, 2):
    a,b=comb
    if a[0]-b[0]==0:
        key=INF
    else:
        key=(a[1]-b[1])/(a[0]-b[0])
    C[(key, abs(a[0]-b[0]), abs(a[1]-b[1]))]+=1

mx=max(C.values())
print(N-mx)

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 = 0

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 = 0
		for j in range(i + 1, len(pq)):
			if pq[i] == pq[j]:
				n += 1
				
		if n > m:
			m = n
			
	cost = N - m - 1
	print(cost)

Submission status: Accepted

Solution code:
import numpy as np
import scipy.stats as stats

n = int(input())
p = np.array([complex(0,0)]*n)
for i in range(n):
    x, y = (int(k) for k in input().split())
    p[i] = complex(x, y)
m = np.zeros((n, n), dtype=np.complex)
m[:, :] = np.nan
for i in range(n):
    for j in range(i+1, n):
        m[i, j] = p[i] - p[j]
        m[j, i] = p[j] - p[i]
mode_val, mode_num =stats.mode(np.array(m).ravel())
print(np.sum(np.all(m != mode_val, axis=1)))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-


def main():
    N = int(input())
    balls = [list(map(int, input().split())) for _ in range(N)]
    diffs = []
    for i in range(N):
        for j in range(i + 1, N):
            diffs.append([balls[i][0] - balls[j][0],
                          balls[i][1] - balls[j][1]])
    max_balls_on_line = 1
    for d in diffs:
        count = 0
        for e in diffs:
            if (d[0] == e[0] and d[1] == e[1]) or (d[0] == -e[0] and d[1] == -e[1]):
                count += 1
        if count > max_balls_on_line:
            max_balls_on_line = count

    if N == 1:
        print(1)
    else:
        print(N - max_balls_on_line)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from itertools import combinations as comb
import copy

N = int(input())
if N == 1:
    print(1)
else:
    xy = [[int(_) for _ in input().split()] for _ in range(N)]
    xy = sorted(xy, key=lambda x: (x[0],x[1]))
    ans = 50
    cand = list(comb(xy, 2))
    pq = set()
    
    for i in cand:
        pq.add((i[1][0]-i[0][0], i[1][1]-i[0][1]))
    
    
    for i in pq:
        p = i[0]
        q = i[1]
        tmpxy = copy.deepcopy(xy)
        tmp = 0
        while len(tmpxy) > 0:
            tmp += 1
            s = tmpxy.pop(0)
            while [s[0]+p, s[1]+q] in tmpxy:
                tmpxy.remove([s[0]+p, s[1]+q])
                s[0] += p
                s[1] += q
        
        if tmp < ans:
            ans = tmp
    
    print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
n = int(input())
list_ = [tuple(map(int, input().split())) for i in range(n)]
list_.sort()

if n == 1:
    print(1)
else:
    ab = []
    for i in range(len(list_)-1):
        x_1, y_1 = list_[i]
        
        for j in range(i+1, len(list_)):
            x_2, y_2 = list_[j]
            a = x_2 - x_1
            b = y_2 - y_1
            ab.append((a, b))

    p, q = Counter(ab).most_common()[0][0]

    res = 0
    while len(list_):
        res += 1
        x, y = list_.pop(0)
        while True:
            if (x+p, y+q) in list_:
                list_.remove((x+p, y+q))
                x, y = x+p, y+q
            else:
                break

    print(res)

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

PQ = []
for i in range(1,N):
    for j in range(i):
        x1,y1 = XY[i]
        x2,y2 = XY[j]
        P = x2-x1
        Q = y2-y1
        if P<0:
            P *= -1
            Q *= -1
        elif P==0 and Q<0:
            Q *= -1
        if not([P,Q] in PQ):
            PQ.append([P,Q])

if N <= 2:
    print(1)
else:
    ans = 50

    for p,q in PQ:
        ans_tmp = 0
        for x,y in XY:
            if not([x-p,y-q] in XY):
                ans_tmp += 1
        ans = min(ans,ans_tmp)
    print(ans)

Submission status: Accepted

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

pq = []
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]
        pq.append((p, q))
        
pq = list(set(pq))

ret = N
for p, q in pq :
    tmp = 0
    visited = [0] * N
    for i in range(N) :
        if visited[i] :
            continue
            
        visited[i] = 1
        
        queue = [i]
        while queue :
            que = queue.pop()
            for j in range(N) :
                if visited[j] :
                    continue
                    
                dx = xy[j][0] - xy[que][0]
                dy = xy[j][1] - xy[que][1]
                if (dx == p and dy == q) or (dx == -p and dy == -q) :
                    queue.append(j)
                    visited[j] = 1
    
        tmp += 1
        
    ret = min(tmp, ret)
    
print(ret)

Submission status: Accepted

Solution code:
import collections

N = int(input())
xy = [list(map(int, input().split())) for _ in range(N)]
ans = N
if N == 1:
  print(1)
  exit()
pq = []

for i in range(N):
  for j in range(N):
    pq.append((xy[j][0]-xy[i][0], xy[j][1]-xy[i][1]))
c = collections.Counter(pq)
if c.most_common()[0][0] == (0,0):
  ans -= c.most_common()[1][1]
else:
  ans -= c.most_common()[0][1]
print(ans)

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(i + 1, N):
            pp2 = p[j]
            d[(pp1[0] - pp2[0], pp1[1] - pp2[1])] += 1
        # print(d)

    cnt = 0
    keys = tuple(d.keys())
    for k in keys:
        x, y = k
        cnt = max(cnt, d[k] + d[(-x, -y)])

    print(N - cnt)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import sys
import itertools
N = int(input())
balls = []
for i in range(N):
    l = list(map(int,input().split()))	
    balls.append(l)

d = list(itertools.permutations(balls, 2))

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

dic = {}

for i in range(len(d)):
   p = d[i][1][0] - d[i][0][0]
   q = d[i][1][1] - d[i][0][1]
   dic[str(p) + "," + str(q)] = 0
   
for i in range(len(d)):
   p = d[i][1][0] - d[i][0][0]
   q = d[i][1][1] - d[i][0][1]
   dic[str(p) + "," + str(q)] += 1

dic[str(0) + "," + str(0)] = -1


max_num = max(dic.values())
ans = N - max_num
p_q = max(dic.items(), key = lambda x:x[1])[0]
p,q = map(int,p_q.split(","))

#if p == 0 && q == 0:
    
#print(max_num)


print(ans)

Submission status: Accepted

Solution code:
N = int(input())


def solve():

    initial_cost = 1

    # (x,y) list
    xy_list = []
    for i in range(N):
        x, y = map(int, input().split())
        xy_list.append((x, y))
    xy_list_sorted = sorted(xy_list, key=lambda a: a[0])

    if N == 1 or N == 2:
        return initial_cost

    xy_sub_dic = {}
    for i in range(N):
        for j in range(N):
            xs = xy_list_sorted[j][0] - xy_list_sorted[i][0]
            ys = xy_list_sorted[j][1] - xy_list_sorted[i][1]
            if xs != 0 or ys != 0:
                if xy_sub_dic.get((xs, ys)) is None:
                    xy_sub_dic[(xs, ys)] = 1
                else:
                    xy_sub_dic[(xs, ys)] += 1

    xy_sub_dic_sorted = sorted(xy_sub_dic.items(), key=lambda a: a[1], reverse=True)

    return initial_cost + (N - 1) - xy_sub_dic_sorted[0][1]
print(solve())

Submission status: Accepted

Solution code:
from collections import Counter

n = int(input())
q_list = []
a_list = []
for i in range(n):
    q = []
    x, y = map(int, input().split())
    q.append(x)
    q.append(y)
    q_list.append(q)
    if i != 0:
        for j in range(i):
            difx1 = q_list[j][0] - q_list[i][0]
            dify1 = q_list[j][1] - q_list[i][1]
            difx2 = q_list[i][0] - q_list[j][0]
            dify2 = q_list[i][1] - q_list[j][1]
            a_list.append(str(difx1)+str(dify1))
            a_list.append(str(difx2)+str(dify2))
if n != 1:
    zero = Counter(a_list).most_common()[0][1]
    print(n-zero)
else:
    print(1)

Submission status: Accepted

Solution code:
import math
import copy

N = int(input())

if N == 1 :
    print(1)
else :
    ball = [0] * N

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

    ans = N - 1
    pq = []

    # p,q の組
    for i in range(N) :
        for j in range(N) :
            p = ball[j][0] - ball[i][0]
            q = ball[j][1] - ball[i][1]

            if p == 0 and q == 0 :
                continue
            pq.append((p,q))

    ans = N - 1

    for p , q in pq :
        check = [0] * N
        count = 0

        for i in range(N) :
            if check[i] == 0 :
                check[i] = 1
                count += 1
                for j in range(1,N) : # 上
                    if [ball[i][0] - j * p , ball[i][1] - j * q] in ball :
                        index = ball.index([ball[i][0] - j * p , ball[i][1] - j * q])
                        check[index] = 1
                    else :
                        break
                for j in range(1,N) : # 下
                    if [ball[i][0] + j * p , ball[i][1] + j * q] in ball :
                        index = ball.index([ball[i][0] + j * p , ball[i][1] + j * q])
                        check[index] = 1
                    else :
                        break
        ans = min(ans,count)
    print(ans)

Submission status: Accepted

Solution code:
import math
import collections


def f(target):
    c = collections.Counter()
    for k in target.keys():
        l = sorted(target[k])
        for i in range(len(l) - 1):
            c.update([l[i + 1] - l[i]])
    v, cc = c.most_common(1)[0] if len(c) != 0 else (0, 0)
    return cc


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

    d = collections.defaultdict(lambda: [])
    for x, y in XY:
        d[x] = d[x] + [y]
    cc1 = f(d)
    d = collections.defaultdict(lambda: [])
    for x, y in XY:
        d[y] = d[y] + [x]
    cc2 = f(d)
    r = N - max(cc1, cc2)

    for i in range(N):
        x1, y1 = XY[i]
        for j in range(i + 1, N):
            x2, y2 = XY[j]
            dx = x1 - x2
            dy = y1 - y2
            if dx == 0 or dy == 0:
                continue

            if dx < 0:
                dx = -dx
                dy = -dy

            bs = collections.defaultdict(lambda: [])
            for x, y in XY:
                k = math.ceil(-x / dx)
                while True:
                    if x + k * dx < 0:
                        k += 1
                    elif x + (k - 1) * dx >= 0:
                        k -= 1
                    else:
                        break

                # while not x + k * dx>=0:

                t = x + k * dx, y + k * dy
                bs[t] = bs[t] + [k]
            # print(bs)
            r = min(N - f(bs), r)

    print(r)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

N = int(input())
x = []
y = []
for i in range(N):
    xin, yin = map(int,input().split())
    x.append(xin)
    y.append(yin)
relative_co = [[] for i in range(N)]
pattern = []
min_cost = 50

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

for i in range(N):
    for j in range(N):
        tempx = x[i]-x[j]
        tempy = y[i]-y[j]
        pattern.append((tempx, tempy))
        relative_co[i].append((tempx, tempy))
patterns = len(pattern)
for i in range(patterns):
    if pattern[i] == (0,0):
        continue
    cur_cost = 0
    for j in range(N):
        if not pattern[i] in relative_co[j]:
            cur_cost += 1
    if cur_cost < min_cost:
        min_cost = cur_cost
print(str(min_cost))

Submission status: Accepted

Solution code:
N = int(input())
xlist = []
ylist = []
pqlist = []
pqcount = {}
for i in range(N):
  x, y = map(int, input().split(" "))
  xlist.append(x)
  ylist.append(y)

for i in range(N):
  for j in range(i+1, N):
    p = xlist[i] - xlist[j]
    q = ylist[i] - ylist[j]
    tuple_pq = (p, q,)
    if (-p, -q,) in pqlist:
      tuple_pq = (-p, -q)
    if not (tuple_pq in pqlist):
      pqlist.append(tuple_pq)
      pqcount[tuple_pq] = 1
    else:
      pqcount[tuple_pq] += 1

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

Submission status: Accepted

Solution code:
import sys
import numpy as np

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

matrix = [input().split() for l in range(n)]

matrix.sort()

# 全部の点の差分を求める
slope_list = []
for i in range(n-1):
    for j in range(i+1, n):
        a = (int(matrix[i][0])-int(matrix[j][0]), int(matrix[i][1])-int(matrix[j][1]))
        if a not in slope_list:
            slope_list.append(a)
#print(slope_list)

max_count = 0
for slope in slope_list:
    count = 0 # 被った回数をカウント
    for i in range(n):
        a = [str(int(matrix[i][0])-slope[0]), str(int(matrix[i][1])-slope[1])]
        #print(a)
        if a in matrix:
            count += 1
            continue
    if max_count < count:
        max_count = count
#print(max_count)

ans = n - max_count
        
print(ans)

Submission status: Accepted

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

xy.sort()

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

sub = []
for i in range(n-1):
    for j in range(i+1,n):
        sub.append((xy[j][0]-xy[i][0],xy[j][1]-xy[i][1]))

res = 10**9

for x,y in sub:
    used = [True]*n
    cnt = 0
    for i in range(n-1,-1,-1):
        if used[i]:
            cnt += 1
        if [xy[i][0]-x,xy[i][1]-y] in xy:
            r = xy.index([xy[i][0]-x,xy[i][1]-y])
            used[r] = False
    res = min(cnt,res)
print(res)

Submission status: Accepted

Solution code:
import collections

n=int(input())

if n==1:
    a,b=(map(int, input().split()))
    print(1)
else:

    arr=[]
    for i in range(n):
        a,b=(map(int, input().split()))
        arr.append([a,b])
    arr=sorted(arr, key=lambda x: x[1], reverse=True)
    arr=sorted(arr, key=lambda x: x[0])
    
    tmparr=[]
    for num in range(len(arr)-1):
        #print(num)
        #tmparr=[]
        #for nn,i in enumerate(arr):
        for nn,i in enumerate(arr[num+1:]):
            #if nn==num:
            #    continue
            #g=gcd(arr[num][0]-i[0],arr[num][1]-i[1])
            tmparr.append(((arr[num][0]-i[0]),(arr[num][1]-i[1])))
            #print(tmparr)
        #print(tmparr)
    #print(set(tmparr))
    c = collections.Counter(tmparr)
    print(n-c.most_common()[0][1])

Submission status: Accepted

Solution code:
def make_key(x, y):
    return str(x) + "k" + str(y)


inp = input()
n = int(inp)
balls = []
for i in range(n):
    inp = input()
    split_input = inp.split()
    x = int(split_input[0])
    y = int(split_input[1])
    balls.append([x, y])
possible_pq = {}
max_key = None
max_number = 0
for base_ball in balls:
    for target_ball in balls:
        diff_x = target_ball[0] - base_ball[0]
        diff_y = target_ball[1] - base_ball[1]
        if diff_x < 0:
            diff_x = diff_x * -1
            diff_y = diff_y * -1
        elif diff_x == 0 and diff_y < 0:
            diff_y = diff_y * -1
        if diff_y == 0 and diff_x == 0:
            continue
        diff = make_key(diff_x, diff_y)
        if diff in possible_pq:
            possible_pq[diff] = possible_pq[diff] + 1
        else:
            possible_pq[diff] = 1
        if max_number < possible_pq[diff]:
            max_number = possible_pq[diff]
            max_key = diff
print(n - max_number // 2)

Submission status: Accepted

Solution code:
n=int(input())
d=[list(map(int,input().split()))for _ in range(n)]
def c(p,q,a):
  global n
  s=n
  for i in a:
    if [i[0]-p,i[1]-q]in a:s-=1
  return s
ans=50
for i in range(n):
  for j in range(n):
    p,q=d[j][0]-d[i][0],d[j][1]-d[i][1]
    if not(p==q==0):ans=min(ans,c(p,q,d))
if n==1:print(1)
else:print(ans)

Submission status: Accepted

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

if len(AB_list) ==1:
    print(1)
    exit(0)

AB_list = sorted(AB_list,key=lambda a:a[0])
kouho_list = []
for i, AB in enumerate(AB_list):
    for j,ab in enumerate(AB_list):
        if i == j:
            continue
        kouho_list.append((ab[0]-AB[0] ,ab[1]-AB[1]))

from collections import Counter
kouho_counter = Counter(kouho_list).most_common()
pq = list(kouho_counter[0][0])

onaji_list = []
#print(kouho_counter)

result = []
for i,ab in enumerate(AB_list):
    for j,ab2 in enumerate(AB_list):
        if i == j:
            continue
        if ab[0] + pq[0] == ab2[0] and ab[1] + pq[1] == ab2[1]:
            result.append(tuple(ab2))
            continue
        #if ab[0] - pq[0] == ab2[0] and ab[1] - pq[1] == ab2[1]:
            #result.append(tuple(ab2))


#print(result)
result = list(set(result))
#print(onaji_list)
#print(result)
print(len(AB_list)-len(result))





'''
候補は49 + 48 + 47 + ...
この候補の中で、一番えらばれているものをp,qとして設定する
その後、ループを回して、実際にコストを計算する

'''


#print(AB_list)

Submission status: Accepted

Solution code:
N = int(input())
xy = list(list(map(int,input().split()))+[0]for i in range(N))
ans = 50
hoge = 0
p,q = 0,0

def func(n):
    xy[n][2] = 1
    if [xy[n][0]+p,xy[n][1]+q,0] in xy:
        func(xy.index([xy[n][0]+p,xy[n][1]+q,0]))
    if [xy[n][0]-p,xy[n][1]-q,0] in xy:
        func(xy.index([xy[n][0]-p,xy[n][1]-q,0]))
    


for i in range(N):
    for j in range(N):
        p,q = xy[j][0]-xy[i][0],xy[j][1]-xy[i][1]
        for k in range(N):
            if xy[k][2] == 0:
                func(k)
                hoge += 1
        ans = min(hoge,ans)
        hoge = 0
        for k in range(N):
            xy[k][2] = 0
print(ans)

Submission status: Accepted

Solution code:
import copy
N = int(input())
C = [[int(i) for i in input().split()] for i in range(N)]
pq_list = []
min_score = N
for i in range(N):
    for j in range(N):
        if(i == j):
            continue
        p = C[i][0] - C[j][0]
        q = C[i][1] - C[j][1]
        pq_list.append([p, q])

for i in range(len(pq_list)):
    score = N
    p = pq_list[i][0]
    q = pq_list[i][1]
    if(p >= 0):
        C.sort(key=lambda x: x, reverse=True)
    else:
        C.sort(key=lambda x: x, reverse=False)
    for j in range(N-1):
        for k in range(j+1, N):
            if((C[j][0] == C[k][0] + p) and (C[j][1] == C[k][1] + q)):
                score += -1
                break
    min_score = min(min_score, score)
    
print(min_score)

Submission status: Accepted

Solution code:
from copy import deepcopy

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

# p, qが決まっている場合のコスト
def cost(p, q):
    reduction = 0
    W = deepcopy(Z)
    for i in range(N):
        for j in range(N):
            if W[j][0] - W[i][0] == p and W[j][1] - W[i][1] == q:
                reduction += 1
    return N - reduction

ans = N
for i in range(N-1):
    for j in range(i+1, N):
        p = Z[j][0] - Z[i][0]
        q = Z[j][1] - Z[i][1]
        cos = cost(p, q)
        
        ans = min(ans, cos)

print(ans)

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 = defaultdict(list)
    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)].append((i, j))

    ans = 0
    for _, v in c.items():
        l = set()
        r = set()

        for x, y in v:
            l.add(x)
            r.add(y)

        g = (len(l) - len(l & r))
        ans = max(ans, len(l | r) - g)
        # print(v, len(l | r), g, l & r)
    return N - ans


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 Counter

N = int(raw_input())

points = [map(int, raw_input().split()) for _ in xrange(N)]

if N == 1:
    print 1
else:
    dist = lambda p1, p2: (p1[0]-p2[0], p1[1]-p2[1])

    vecs = []
    for i in xrange(N):
        for j in xrange(N):
            if j == i:
                continue
            vecs.append(dist(points[i], points[j]))

    vecs_cnt = Counter(vecs)
    # print Counter(vecs)
    ans = max(vecs_cnt.values())

    print N-ans

Submission status: Accepted

Solution code:
import collections
N = int(input())
x = []
for i in range(N):
	x.append(list(map(int, input().split())))
if N == 1:
	print(1)
else:
	L = []
	for i in range(N):
		a, b = x[i][0], x[i][1]
		for j in range(N):
			if a > x[j][0] or b > x[j][1]:
				L.append((a - x[j][0], b - x[j][1]))
	c = collections.Counter(L)
	max = c.most_common(1)[0][1]
	print(N - max)

Submission status: Accepted

Solution code:
import collections

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

if N > 1:
    tmp = []
    for i in range(N):
        for j in range(N):
            tmp.append((co[i][0]-co[j][0],co[i][1]-co[j][1]))
    c = collections.Counter(tmp)
    print(N - c.most_common()[1][1])
else:
    print("1")

Submission status: Accepted

Solution code:
N = int(input())
ball = []
dif = [[] for i in range(N-1)]
for i in range(N):
    x,y = map(int,input().split())
    ball += [[x,y]]
ball = sorted(ball)

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

ans = 0
for i in range(N-1):
    for j in range(N-i-1):
        base = dif[i][j]
        point = 0
        for k in range(i+1,N-1):
            for l in range(N-k-1):
                if base == dif[k][l]:
                    point += 1
                    break
        if ans < point: ans = point

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

Submission status: Accepted

Solution code:
N = int(input())
xylist = []
for n in range(N) :
    xylist.append(list(map(int, input().split())))

def minus2d(list1, list2) :
    return [list1[0]-list2[0],
            list1[1]-list2[1]]
longsabun = []
cmax = 0
for key in xylist :
    sabun = list(map(lambda a : minus2d(a, key), xylist))
    longsabun += sabun
for skey in longsabun :
    if skey != [0,0] :
        counter = longsabun.count(skey)
        cmax = max(cmax, counter)
print(N-cmax)

Submission status: Accepted

Solution code:
N = int(input())
XY = []
for n in range(N):
    XY.append([int(i) for i in input().split()])
XY = sorted(XY)
cnt = {}
for n in range(N):
    for nn in range(n+1,N): 
        dist = [XY[n][0]-XY[nn][0],XY[n][1]-XY[nn][1]]
        if str(dist) in cnt:
            cnt[str(dist)] += 1
        else:
            cnt[str(dist)] = 1
if N == 1:
    print(1)
else:
    print(N - max(cnt.values()))