Problem:


Score : 300 points

Problem Statement

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

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

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

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

Constraints

1 \leq N \leq 50

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

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

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
x_1 y_1
:
x_N y_N

Output

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

Sample Input 1

2
1 1
2 2

Sample Output 1

1

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

Sample Input 2

3
1 4
4 6
7 8

Sample Output 2

1

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

Sample Input 3

4
1 1
1 2
2 1
2 2

Sample Output 3

2



Sample input:
2
1 1
2 2


Sample output:
1

Submission status: Accepted

Solution code:
from collections import defaultdict
N = int(input())
B = [[0, 0] for i in range(N)]
D = [[[0, 0] for j in range(N)] for i in range(N)]
G = defaultdict(int)
for i in range(N):
  B[i] = [int(x) for x in input().split()]
B.sort()
for i in range(N):
  for j in range(i, N):
    if i == j:
      continue
    D[i][j] = [B[j][0] - B[i][0], B[j][1] - B[i][1]]
    D[j][i] = [-D[i][j][0], -D[i][j][1]]
for i in range(N):
  for j in range(i, N):
    if i == j:
      continue
    G[str(D[i][j])] += 1
ans = N
for p in G.keys():
  v = N - G[p]
  ans = min(ans, v)
print(ans)

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

#j-iの全組み合わせの差分を取る-①
m=0
for j in range(n):
	for i in range(n):
		if i==j:
			continue
		p = xy[j][0]-xy[i][0]
		q = xy[j][1]-xy[i][1]
		c = 0
		#全組み合わせで引き算をして①になったらカウント
		for k in range(n):
			for l in range(n):
				if k==l:
					continue
				if xy[l][0]-xy[k][0]==p and xy[l][1]-xy[k][1]==q:
					c+=1
		#最も多いものを採用
		m = max(m,c)
print(n-m)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
INF = float("inf")


def solve(N: int, x: "List[int]", y: "List[int]"):
    if N == 1:
        print(1)
        return
    x, y = zip(*sorted(list(zip(x, y))))
    p_cand = [x[j]-x[i] for i in range(N) for j in range(i+1, N)]
    q_cand = [y[j]-y[i] for i in range(N) for j in range(i+1, N)]

    minimum = INF
    for p, q in set(zip(p_cand, q_cand)):
        # print("(p, q) = ({}, {})".format(p, q))
        xy = list(zip(x, y))
        cost = 0
        while len(xy) > 0:
            xx, yy = xy.pop()
            cost += 1
            # print(xx, yy, xy, xx-p, yy-q)
            while (xx-p, yy-q) in xy:
                xy.remove((xx-p, yy-q))
                xx -= p
                yy -= q
        if minimum > cost:
            minimum = cost
    print(minimum)

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    x = [int()] * (N)  # type: "List[int]"
    y = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        x[i] = int(next(tokens))
        y[i] = int(next(tokens))
    solve(N, x, y)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import itertools, collections
N = int(input())
XY = sorted([[int(_) for _ in input().split()] for _ in range(N)])
count = collections.defaultdict(int)
for i, j in itertools.combinations(range(N), 2):
    x1, y1 = XY[i]
    x2, y2 = XY[j]
    count[y2 - y1 + (x2 - x1) * 10**10] += 1
if count:
    print(N - max(count.values()))
else:
    print(1)

Submission status: Accepted

Solution code:
from collections import Counter
n = int(input())

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

l = []
for i in range(n):
    pre = [x[i], y[i]]
    for j in range(n):
        if i == j:
            continue
        l.append("{}_{}".format(x[j] - pre[0], y[j] - pre[1]))

if len(l) > 0:
    c = Counter(l)
    a = int(c.most_common()[0][1])
    print(n - a)
else:
    print(1)

Submission status: Accepted

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

ans = 0
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]
        merge = 0
        for k in range(N):
            if [xy[k][0]+p, xy[k][1]+q] in xy:
                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)]
x, y = [], []
for i, j in xy:
    x += [i]
    y += [j]
memo = {}
for i in range(N):
    for j in range(N):
        if i == j:
            continue
        p = x[j] - x[i]
        q = y[j] - y[i]
        pq = str(i) + '_' + str(j)
        for k in range(N):
            for l in range(N):
                if k == l:
                    continue
                if (x[k] - x[l]) == p and (y[k] - y[l]) == q:
                    if pq in memo:
                        memo[pq] += 1
                    else:
                        memo[pq] = 1
if N != 1:
    print(N-max(memo.values()))
else:
    print('1')

Submission status: Accepted

Solution code:
N = int(input())
xy = [list(map(int, input().split())) for _ in range(N)]
x, y = [], []
for i, j in xy:
    x += [i]
    y += [j]
ans = 0
for i in range(N):
    for j in range(N):
        if i == j:
            continue
        p = x[j] - x[i]
        q = y[j] - y[i]
        c = 0
        for k in range(N):
            for l in range(N):
                if k == l:
                    continue
                if (x[k] - x[l]) == p and (y[k] - y[l]) == q:
                    c += 1
        ans = max(ans, c)
if N != 1:
    print(N-ans)
else:
    print('1')

Submission status: Accepted

Solution code:
import itertools
from collections import Counter

def main():
    N = int(input())
    data = []
    common_data = []
    max_common_num = 0
    for _ in range(N):
        data.append( list(map(int, input().split())) )

    data.sort()

    if N == 1:
        return 1
    else:
        for obj in itertools.combinations(data, 2):
            # print(obj)
            common_data.append( str(obj[0][0] - obj[1][0]) + "_" + str(obj[0][1] - obj[1][1]) )

        # カウント
        counter = Counter(common_data)
        for word, cnt in counter.most_common():
            if cnt >= max_common_num:
                max_common_num = cnt

    # print(common_data)
    return N - max_common_num

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

Submission status: Accepted

Solution code:
from collections import defaultdict
inpl = lambda: list(map(int,input().split()))
 
N = int(input())
xy = []
for _ in range(N):
    x, y = inpl()
    xy.append((x,y))
xy.sort()

edges = defaultdict(int)
edges[(0,0)] = 0
for i in range(N):
    for j in range(i+1,N):
        x1, y1 = xy[i]
        x2, y2 = xy[j]
        p, q = x2-x1, y2-y1
        edges[(p,q)] += 1
 
print(N - max(edges.values()))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from itertools import product
n = int(input())
x = [None] * n
y = [None] * n
for i in range(n):
    x[i], y[i] = map(int, input().split())

m = 0
for i, j in product(range(n), repeat=2):
    if i == j:
        continue
    p = x[j] - x[i]
    q = y[j] - y[i]
    c = 0
    for s, t in product(range(n), repeat=2):
        if s == t:
            continue
        if x[t] - x[s] == p and y[t] - y[s] == q:
            c += 1
    m = max(m, c)

print(n - m)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys

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

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

    w = [tuple(map(int,input().split())) for x in range(n)]
    w.sort()

    pqs = {}
    for i in range(n-1):
        for j in range(i+1,n):
            xy = (w[j][0] - w[i][0], w[j][1] - w[i][1])
            if xy not in pqs:
                pqs[xy] = 1
            else:
                pqs[xy] += 1
    print(n - max(pqs.values()))

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
###############################################################################

from sys import stdout
from bisect import bisect_left as binl
from copy import copy, deepcopy
from collections import defaultdict
import math


mod = 1


def intin():
    input_tuple = input().split()
    if len(input_tuple) <= 1:
        return int(input_tuple[0])
    return tuple(map(int, input_tuple))


def intina():
    return [int(i) for i in input().split()]


def intinl(count):
    return [intin() for _ in range(count)]


def modadd(x, y):
    global mod
    return (x + y) % mod


def modmlt(x, y):
    global mod
    return (x * y) % mod


def mod_inv(x):
    # available only when mod is prime
    global mod
    return pow(x, mod - 2, mod)


def gcm(x, y):
    while y != 0:
        z = x % y
        x = y
        y = z
    return x


def combination(x, y):
    assert(x >= y)

    ret = math.factorial(x)
    ret = ret // (math.factorial(x - y) * math.factorial(y))

    return ret


def get_divisors(x):
    retlist = []
    for i in range(1, int(x**0.5) + 3):
        if x % i == 0:
            retlist.append(i)
            retlist.append(x // i)
    return retlist


def get_factors(x):
    retlist = []
    for i in range(2, int(x**0.5) + 3):
        while x % i == 0:
            retlist.append(i)
            x = x // i
    retlist.append(x)
    return retlist


def make_linklist(xylist):
    linklist = {}
    for a, b in xylist:
        linklist.setdefault(a, [])
        linklist.setdefault(b, [])
        linklist[a].append(b)
        linklist[b].append(a)
    return linklist


def calc_longest_distance(linklist, v=1):
    distance_list = {}
    distance_count = 0
    distance = 0
    vlist_previous = []
    vlist = [v]
    nodecount = len(linklist)

    while distance_count < nodecount:
        vlist_next = []
        for v in vlist:
            distance_list[v] = distance
            distance_count += 1
            vlist_next.extend(linklist[v])
        distance += 1
        vlist_to_del = vlist_previous
        vlist_previous = vlist
        vlist = list(set(vlist_next) - set(vlist_to_del))

    max_distance = -1
    max_v = None
    for v, distance in distance_list.items():
        if distance > max_distance:
            max_distance = distance
            max_v = v

    return (max_distance, max_v)


def calc_tree_diameter(linklist, v=1):
    _, u = calc_longest_distance(linklist, v)
    distance, _ = calc_longest_distance(linklist, u)
    return distance


class UnionFind:

    def __init__(self, n):
        self.parent = [i for i in range(n)]

    def root(self, i):
        if self.parent[i] == i:
            return i
        self.parent[i] = self.root(self.parent[i])
        return self.parent[i]

    def unite(self, i, j):
        rooti = self.root(i)
        rootj = self.root(j)
        if rooti == rootj:
            return
        if rooti < rootj:
            self.parent[rootj] = rooti
        else:
            self.parent[rooti] = rootj

    def same(self, i, j):
        return self.root(i) == self.root(j)


###############################################################################


def main():
    n = intin()
    xylist = intinl(n)

    pqtoij = defaultdict(list)

    for i in range(n):
        for j in range(n):
            if i == j:
                continue
            x1, y1 = xylist[i]
            x2, y2 = xylist[j]

            p = x1 - x2
            q = y1 - y2

            pqtoij[(p, q)].append((i, j))

    maxcount = 0

    for (p, q), ijlist in pqtoij.items():
        maxcount = max(maxcount, len(ijlist))

    print(n - maxcount)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def b_picking_up(N, Positions):
    if N == 1:
        return 1  # 最初のボールに移動するのは必ずコスト1

    from collections import defaultdict
    difference_count = defaultdict(int)  # xの差分とyの差分の組について、現れた回数

    for i in range(N):
        for j in range(N):
            if i == j:
                continue
            # diff_x と diff_y がともに0となることは、入力の制約よりありえない
            diff_x = Positions[j][0] - Positions[i][0]
            diff_y = Positions[j][1] - Positions[i][1]
            difference_count[(diff_x, diff_y)] += 1
    return N - max(difference_count.values())  # 第2項はコスト0で移動できる座標の数

N = int(input())
Positions = [[int(i) for i in input().split()] for j in range(N)]
print(b_picking_up(N, Positions))

Submission status: Accepted

Solution code:
from itertools import permutations
from collections import Counter


n = int(input())
balls = []

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

if n == 1:
    print(1)
else:
    counter = Counter()
    for b1, b2 in permutations(balls, 2):
        p, q = b1[0] - b2[0], b1[1] - b2[1]
        counter[(p, q)] += 1

    (p, q), val = counter.most_common(1)[0]
    print(n - val)

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    if n ==1:
        print(1)
        exit()
    x_y_list = []
    p_q_dic = {}
    for i in range(n):
        x,y = map(int,input().split(' '))
        x_y_list.append((x,y))
    for i in range(n):
        x_i = x_y_list[i][0]
        y_i = x_y_list[i][1]
        for j in range(n):
            if i == j:
                continue
            x_j = x_y_list[j][0]
            y_j = x_y_list[j][1]
            p = x_j - x_i
            q = y_j - y_i
            if (p !=0 or q !=0) and (p,q) in p_q_dic:
                p_q_dic[(p,q)] += 1
            elif p != 0 or q != 0:
                p_q_dic[(p,q)] = 1
    p_q_sorted = sorted(p_q_dic.values(),reverse=True)
    print(n-p_q_sorted[0])

main()

Submission status: Accepted

Solution code:
import collections
N = int(input())
if N == 1:
  print(1)
elif N == 2:
  print(1)
else:
  ball = [tuple(map(int, input().split())) for _ in range(N)]
  ball.sort(key=lambda x:(x[0], x[1]))
  diff = [tuple((ball[i][0] - ball[j][0], ball[i][1] - ball[j][1])) for i in range(N) for j in range(i + 1, N)]
  c = collections.Counter(diff)
  ans = c.most_common()[0][1]
  print(N - ans)

Submission status: Accepted

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

import itertools
import collections

if N==1:
    print(1)
    
else:
    arr = list(itertools.combinations(List, 2))
    vec1 = []
    vec2 = []
    for i in range(len(arr)):
        vec1.append([arr[i][1][0]-arr[i][0][0], arr[i][1][1]-arr[i][0][1]])
        vec2.append([arr[i][0][0]-arr[i][1][0], arr[i][0][1]-arr[i][1][1]])
        
    vec = vec1+vec2
    counter = collections.Counter(map(tuple, vec))
    
    v =  counter.most_common(1)[0][0]
    num = counter.most_common(1)[0][1]
    
    print(N-num)

Submission status: Accepted

Solution code:
N = int(input())
XY = sorted([tuple(map(int, input().split())) for _ in range(N)])
PQ = []
for i in range(N):
    for j in range(i+1, N):
        PQ.append((XY[j][0]-XY[i][0], XY[j][1]-XY[i][1]))

ans = N
for p, q in PQ:
    cnt = 0
    for i in range(N):
        for j in range(i+1, N):
            if XY[j][0] - p == XY[i][0] and XY[j][1] - q == XY[i][1]:
                cnt += 1
    ans = min(ans, N-cnt)
print(ans)

Submission status: Accepted

Solution code:
import collections

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

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

pq = []
cost = N

for xyi in xy:
    for xyj in xy:
        pq.append((xyi[0]-xyj[0], xyi[1]-xyj[1]))

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

Submission status: Accepted

Solution code:
# Picking Up
# グラフ,有向グラフ,ベクトル, ２次元、コスト,

N = int(input())
S = []
for _ in range(N):
    x, y = map(int, input().split())
    S.append([x, y])
cost = N
d = {}

if N==1:
    print(1)
    exit()
for l,le in enumerate(S):
    for m, me in enumerate(S):
        if l == m:
            continue
        t = (me[0] - le[0], me[1] - le[1])
        if t in d:
            d[t] +=1
        else:
            d[t] = 1

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

Submission status: Accepted

Solution code:
def search(p,q):
  count = 0
  for i in range(n):
    for j in range(n):
      if a[i][0]-a[j][0] == p and a[i][1]-a[j][1] == q:
        count += 1
  return count
n = int(input())
a = []
for i in range(n):
  a.append(tuple(map(int,input().split())))
cc = 0
for i in range(n):
  for j in range(n):
    if i == j:
      continue
    else:
      p = a[i][0]-a[j][0]
      q = a[i][1]-a[j][1]
      cc = max(cc,search(p,q))
print(n-cc)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())

d = {}
x = [0] * N
y = [0] * N
from collections import defaultdict
for i in range(N):
    x[i], y[i] = map(int, input().split())

d = defaultdict(int)
for i in range(N):
    for j in range(N):
        dx = x[i] - x[j]
        dy = y[i] - y[j]
        if i == j:
            continue
        d[(dx, dy)] += 1
        
if N == 1:
    print(1)
else:
    print(N - max(d.values()))

Submission status: Accepted

Solution code:
import itertools
n=int(input())
ball=[]
for i in range(n):
    ball.append([int(i) for i in input().split()])

ball.sort()

# p,qの候補取得
pq_cand=set()
for v in itertools.combinations(ball,2):
    xdiff=v[0][0]-v[1][0]
    ydiff=v[0][1]-v[1][1]
    pq_cand.add((xdiff,ydiff))
    
cost=n
for pq in pq_cand:
    cost_tmp=0
    for point in ball:
        if [point[0]+pq[0],point[1]+pq[1]] not in ball:
            cost_tmp+=1
    cost=min(cost,cost_tmp)
print(cost)

Submission status: Accepted

Solution code:
#!/usr/bin/env python

from collections import deque
import itertools as ite
import sys
import math

sys.setrecursionlimit(1000000)

INF = 10 ** 18
MOD = 10 ** 9 + 7

N = input()
ls = []
for loop in range(N):
	x, y = map(int, raw_input().split())
	ls += [(x, y)]
ans = 0
for i in range(N):
	for j in range(i + 1, N):
		dx = ls[i][0] - ls[j][0]
		dy = ls[i][1] - ls[j][1]
		cnt = 0
		for k in range(N):
			for l in range(N):
				if ls[k][0] - ls[l][0] == dx and ls[k][1] - ls[l][1] == dy:
					cnt += 1
		ans = max(cnt, ans)
print N - ans

Submission status: Accepted

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

if N==1:
    print(1)
    exit(0)
xy_list.sort(key=lambda x:x[1]) #yの値でソート
xy_list.sort(key=lambda x:x[0]) #xの値でソート
#print(xy_list)
#差をすべて調べる
for i in range(N):
  for j in range(N):
    if( i==j ):     #xとyの重複はなし
      continue
    t = (xy_list[i][0]-xy_list[j][0],xy_list[i][1]-xy_list[j][1])
    ans.append(t)
    #print(ans)  
#差の種類ごとの個数を調べる
res = [ans.count(e) for e in set(ans)]
#Nから一番多かった差の個数を引いたものが答え
print(N-max(res))

Submission status: Accepted

Solution code:
n = int(input())
arr = sorted([list(map(int, input().split())) for _ in range(n)])
d = {}

if n == 1:
  print(1)
  exit()
  
for i in range(n):
  for j in range(i+1, n):
    x = (arr[j][0]-arr[i][0], arr[j][1]-arr[i][1])
    if x in d:
      d[x] += 1
    else:
      d[x] = 1

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

Submission status: Accepted

Solution code:

N = int(input())
xy = []

for i in range(N):

    newxy = list(map(int,input().split()))
    xy.append(newxy)

ans = -1
now = 0

for i in range(N):

    for j in range(i):

        now = 0

        p = xy[j][0] - xy[i][0]
        q = xy[j][1] - xy[i][1]


        #print ("p:",p,"q:",q)
        

        xydic = {}

        for k in xy:

            if str(k) in xydic:

                continue
                #print (k,"はすでにxydicに含まれています！")

            else:

                now += 1

                xydic[str(k)] = 1

                #print(k,"をxydicに始点として含めました")

                plbul = True

                cnt = 1
                while plbul:

                    if [ k[0] + cnt * p , k[1] + cnt * q ] in xy :

                        xydic [str([k[0] + cnt * p , k[1] + cnt * q])] = 1
                        #print ([k[0] + cnt * p , k[1] + cnt * q],"を+でxydicに含めました")
                        cnt += 1

                    else:
                        plbul = False

                cnt = -1

                plbul = True
                
                while plbul:

                    if [ k[0] + cnt * p , k[1] + cnt * q ] in xy :

                        xydic [str([k[0] + cnt * p , k[1] + cnt * q])] = 1
                        #print ([k[0] + cnt * p , k[1] + cnt * q] ,"を-でxydicに含めました" )
                        cnt -= 1

                    else:
                        plbul = False

                #print ("now",now)

                                
        if now < ans or ans < 0:
            ans = now
            #print (xydic)

if N == 1:
    ans = 1

print (ans)

Submission status: Accepted

Solution code:
from itertools import combinations
from collections import Counter

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

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

X.sort()
diff = []
for i, j in combinations(range(N), 2):
    diff.append((X[i][0] - X[j][0], X[i][1] - X[j][1]))
print(N - Counter(diff).most_common()[0][1])

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left, bisect_right
from copy import copy
inf=float('inf')
mod = 10**9+7
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():

    N = I()
    XY = LLIN(N)
    XY.sort()
    if N == 1:
        print(1)
        exit()
    
    count = defaultdict(int)
    for i, (x1, y1) in enumerate(XY):
        for j, (x2, y2) in enumerate(XY[i+1:]):
            dx, dy = x1 - x2, y1 - y2
            count[(dx, dy)] += 1
    print(N - max(count.values()))
    
    
                        
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
from collections import defaultdict
from copy import copy
N = int(input())
XY = list(sorted([tuple(map(int, input().split())) for _ in range(N)]))
PQ = []
for i in range(N-1):
    for j in range(i, N):
        PQ.append((XY[j][0]-XY[i][0], XY[j][1]-XY[i][1]))
PQ = list(set(PQ))
ans = N
for p, q in PQ:
    tmp1 = 1
    T = deque(copy(XY))
    x, y = T.popleft()
    cnt = 1
    while cnt < N:
        tmp2 = 1
        for s, t in T:
            if s - p == x and t - q == y:
                tmp2 = 0
                break
        if tmp2:
            x, y = T.popleft()
        else:
            T.remove((s, t))
            x, y = s, t
        tmp1 += tmp2
        cnt += 1      
    ans = min(ans, tmp1)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
point = []
for i in range(n):
    x_, y_ = map(int, input().split())
    point.append([x_, y_])

point.sort(key=lambda x: x[1])
point.sort(key=lambda x: x[0])
ans = 0
x = []
y = []
for i in range(n):
    x.append(point[i][0])
    y.append(point[i][1])

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

print(n - ans)

Submission status: Accepted

Solution code:
# 未完成

import sys
N = int(input())
x = [0]*N
y = [0]*N
kouholist = []
ans = N
if N == 1:
    print(1)
    sys.exit()

for i in range(N):
    x[i], y[i] = map(int, input().split())
for m in range(N):
    for p in range(N):
        if m == p:
            continue
        diff_x = x[m] - x[p]
        diff_y = y[m] - y[p]
        ans_kari = N
        for r in range(N):
            for q in range(N):
                if x[q] - x[r] == diff_x and y[q] - y[r] == diff_y:
                    ans_kari -= 1
        if ans_kari < ans:
            ans = ans_kari

print("{}".format(ans))

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left, bisect_right
from copy import copy
inf=float('inf')
mod = 10**9+7
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():

    N = I()
    XY = LLIN(N)
    if N == 1:
        print(1)
        exit()
    XY.sort()

    count = defaultdict(int)
    for i, (x1, y1) in enumerate(XY):
        for j, (x2, y2) in enumerate(XY[i+1:]):
            dx, dy = x1 - x2, y1 - y2
            count[(dx, dy)] += 1
    maxim = -inf
    for v in count.values():
        maxim = max(maxim, v)
    print(N - maxim)
    
    
                        
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import itertools
n=int(input())
ball=[]
for i in range(n):
    ball.append([int(i) for i in input().split()])

ball.sort()

# p,qの候補取得
pq_cand=set()
for v in itertools.combinations(ball,2):
    xdiff=v[0][0]-v[1][0]
    ydiff=v[0][1]-v[1][1]
    pq_cand.add((xdiff,ydiff))
    
connect=0
for pq in pq_cand:
    con=0
    for point in ball:
        if [point[0]+pq[0],point[1]+pq[1]] in ball:
            con+=1
    connect=max(connect,con)
print(n-connect)

Submission status: Accepted

Solution code:
N = int(input())
xy = [list(map(int,input().split())) for i in range(N)]
xy.sort()
from collections import defaultdict
d = defaultdict(int)
for i in range(N):
    for j in range(i+1,N):
        tmp = (xy[j][0]-xy[i][0],xy[j][1]-xy[i][1])
        d[tmp] += 1
if N == 1:
    print(1)
else:
    print(N-max(d.values()))

Submission status: Accepted

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

xy.sort()
if n == 1:
    print(1)
    exit()
ans = 10**7

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]
        a = 0
        for k in range(n):
            if [xy[k][0] - p, xy[k][1] - q] not in xy:
                a += 1
        ans = min(a, ans)

print(ans)

Submission status: Accepted

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

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

for (x, y) in xy:
    for (a, b) in xy:
        if (x, y) != (a, b):
            if (x-a, y-b) in pq.keys():
                pq[(x-a, y-b)] = pq[(x-a, y-b)] + 1
            else:
                pq[(x-a, y-b)] = 1

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

Submission status: Accepted

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

Submission status: Accepted

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

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

ans=0
for i in range(0,N-1):
  for j in range(i+1,N):
    sax = balls[j][0]-balls[i][0]
    say = balls[j][1]-balls[i][1]
    merge=0
    for k in range(0,N):
      if([balls[k][0]+sax,balls[k][1]+say] in balls):
          merge+=1
    ans=max(ans,merge)
print(N-ans)

Submission status: Accepted

Solution code:
from collections import Counter
N = int(input())
XY = []
XY_cand = []
for _ in range(N):
        x, y = map(int, input().split())
        XY.append((x,y))
for (x, y) in XY:
        for (i, j) in XY:
                if i != x or j != y:
                        XY_cand.append((i-x, j-y))
if XY_cand == []:
        print(N)
else:
        print(N - Counter(XY_cand).most_common()[0][1])

Submission status: Accepted

Solution code:
#-------------------------------------------------------------------
import sys
def p(*a):
  s=" ".join(map(str,a))
  #print(s)
  sys.stderr.write(s+"\n")
#-------------------------------------------------------------------

N = int(input())						# 5

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

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

#print(P)


from itertools import permutations
from itertools import combinations
L = list(combinations(P, 2))
#print( L )
#print( len(L) )

A=[]

for l in L:
	a=l[1][0]-l[0][0]
	b=l[1][1]-l[0][1]
	if a<0:
		a,b=-a,-b
	if a==0 and b<0:
		b=-b
	A.append((a,b))

#print(A)


# 各朝食メニューの回数を調べる
from collections import defaultdict

d = defaultdict(int)
for b in A:
	d[b] += 1

#print("dict(d)", dict(d))
# => {'pan': 2, 'kome': 4, 'cereal': 1}

# Value降順
B=[]
for k, v in sorted(d.items(), key=lambda x: -x[1]):
	#print(str(k) + ": " + str(v))
	break

#print("k,v", k,v)

print(N-v)