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: Wrong Answer

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

D = []
for i in range(1,N):
    D.append((X[i] - X[i - 1], Y[i] - Y[i - 1]))

DS = list(set(D))

cnt = 0
for d in DS:
    cnt = max(cnt, D.count(d))

print(N-cnt)

Submission status: Wrong Answer

Solution code:
from itertools import count, combinations
N = int(input())

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


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

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

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

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

Submission status: Wrong Answer

Solution code:
from fractions import gcd
N=int(input())
x=[0 for i in range(N)]
y=[0 for i in range(N)]
for i in range(N):
    x[i],y[i]=map(int,input().split())
D=dict()
for i in range(N):
    for j in range(i+1,N):
        drtmp=(x[i]-x[j],y[i]-y[j])
        g=gcd(abs(drtmp[0]),abs(drtmp[1]))
        dr=(drtmp[0]//g,drtmp[1]//g)
        if dr in D:
            D[dr]+=1
        else:
            D[dr]=1
maxk=0
for v in D:
    if D[v]>maxk:
        maxk=D[v]
print(N-maxk)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
N = int( input())
ans = 50
X = [ tuple( map( int, input().split())) for _ in range(N)]
X.sort(reverse=True)
for i in range(N-1):
    for j in range(i+1,N):
        if i == j:
            continue
        p = X[i][0] - X[j][0]
        q = X[i][1] - X[j][1]
        d = defaultdict( int)
        now = 0
        for k in range(N):
            if d[X[k]] == 0:
                now += 1
            d[(X[k][0], X[k][1])] = 1
            d[(X[k][0]+p, X[k][1]+q)] = 1
            d[(X[k][0]-p, X[k][1]-q)] = 1
        if now < ans:
            ans = now
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())

XYs = []

for i in range(N):
    x,y = map(int,input().split())
    tmp = (x,y)
    XYs.append(tmp)


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

distances = {}

for index_fr in range(N):
    for index_to in range(N):
        if index_fr == index_to:
            continue
        fr = XYs[index_fr]
        to = XYs[index_to]
        key = str(fr[0] - to[0]) + str(fr[1] - to[1])
        if key in distances.keys():
            distances[key] += 1
        else:
            distances[key] = 1


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

Submission status: Wrong Answer

Solution code:
n = int(input())
P = [[int(x) for x in input().split()] for _ in range(n)]

diffs = [(P[j][0] - P[i][0], P[j][1] - P[i][1]) for i in range(n) for j in range(i+1,n)]

mini = 1e100
for p,q in diffs:
    if (p,q) == (0,0):
        continue
    count = n
    for i in range(n):
        for j in range(i+1,n):
            if (P[i][0]+p, P[i][1]+q) == (P[j][0], P[j][1]):
                count -= 1
    mini = min(count, mini)
print(mini)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!

from collections import defaultdict

N = int(input())
X = []
for _ in range(N):
    X.append(list(map(int, input().rstrip().split(' '))))
    
sorted_X1 = sorted(X, key=lambda x: (x[0], x[1]))
sorted_X2 = sorted(X, key=lambda x: (x[1], x[0]))

max_count = 0

d1 = defaultdict(lambda: defaultdict(int))
for i in range(1, N):
    d1[sorted_X1[i][0] - sorted_X1[i-1][0]][sorted_X1[i][1] - sorted_X1[i-1][1]] += 1
    max_count = max(max_count, d1[sorted_X1[i][0] - sorted_X1[i-1][0]][sorted_X1[i][1] - sorted_X1[i-1][1]])
    
d2 = defaultdict(lambda: defaultdict(int))
for i in range(1, N):
    d2[sorted_X2[i][0] - sorted_X2[i-1][0]][sorted_X2[i][1] - sorted_X2[i-1][1]] += 1
    max_count = max(max_count, d2[sorted_X2[i][0] - sorted_X2[i-1][0]][sorted_X2[i][1] - sorted_X2[i-1][1]])
    
print(N - max_count)

Submission status: Wrong Answer

Solution code:
n=int(input())
l=[list(map(int,input().split())) for i in range(n)]
s=set()
l.sort(key=lambda x:x[0],reverse=True)
ans=0
for i in range(n-1,0,-1):
    val=(l[i][0]-l[i-1][0],l[i][1]-l[i-1][1])
    if(val not in s):
        s.add(val)
        ans+=1
print(ans)

Submission status: Wrong Answer

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

for i in range(n):
    for j in range(n):
        pqs.append((balls[i][0] - balls[j][0], balls[i][1] - balls[j][1]))
ans = 1 << 30
for p, q in pqs:
    tmp = 0
    if p == 0 and q == 0:continue
    for x, y in balls:
        prev = (x-p, y-q)
        if prev not in balls:
            tmp += 1
    ans = min(ans, tmp)

print(ans)

Submission status: Wrong Answer

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

counts = {}
for i in range(N):
	x1, y1 = balls[i]
	for j in range(i):
		x2, y2 = balls[j]
		p = x2 - x1
		q = y2 - y1
		if p < 0:
			p = -p
			q = -q
		diff = (p, q)
		if diff in counts:
			s, l = counts[diff]
			s.add(i)
			s.add(j)
			l.append((i, j))
		else:
			counts[diff] = ({i, j}, [(i, j)])


min_cost = N
for s, l in counts.values():
	n = len(s)
	c = len(l)
	cost = (N - n) + n - (c + 1) + 1
	if cost < min_cost:
		min_cost = cost
print(min_cost)

Submission status: Wrong Answer

Solution code:
from operator import itemgetter

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

Submission status: Wrong Answer

Solution code:
n = int(input())
L = [tuple(map(int, input().split())) for _ in range(n)]
L.sort()
sub = lambda x, p: (x[0] - p[0], x[1] - p[1])
add = lambda x, p: (x[0] + p[0], x[1] + p[1])
def check(p):
    res = 0
    l = L[:]
    while len(l):
        res += 1
        e = l.pop(0)
        while add(e, p) in l:
            l.remove(add(e, p))
            e = add(e, p)
    return res
res = float('inf')
for i in range(n):
    for j in range(i + 1, n):
        res = min(res, check(sub(L[j], L[i])))
print(res)

Submission status: Wrong Answer

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)
    dicx = defaultdict(lambda: 0)
    xy.sort(key=lambda v: v[0])
    for i in range(1, len(xy)):
        dx = xy[i][0] - xy[i-1][0]
        dy = xy[i][1] - xy[i-1][1]
        key = '%d %d' % (dx, dy)
        dicx[key] += 1
    dicy = defaultdict(lambda: 0)
    xy.sort(key=lambda v: v[1])
    for i in range(1, len(xy)):
        dx = xy[i][0] - xy[i-1][0]
        dy = xy[i][1] - xy[i-1][1]
        key = '%d %d' % (dx, dy)
        dicy[key] += 1
    nm = 0
    for v in dicx.values():
        if nm < v:
            nm = v
    for v in dicy.values():
        if nm < v:
            nm = v
    print(N - nm)

main()

Submission status: Wrong Answer

Solution code:
from itertools import combinations


n = int(input())

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

min_cost = n
for xyi, xyj in combinations(xys, 2):
    xi, yi = xyi
    xj, yj = xyj
    p = xj - xi
    q = yj - yi

    line_set = set()
    for x, y in xys:
        line_set.add(q * x - p * y)
    cost = len(line_set)
    min_cost = min(min_cost, cost)

print(min_cost)

Submission status: Wrong Answer

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):
        list_.append((abs(xy[i][0]-xy[j][0]),abs(xy[i][1]-xy[j][1])))

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

Submission status: Wrong Answer

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

dic = {}
for x1,y1 in xy:
    for x2,y2 in xy:
        if x1 == x2 and y1 == y2:
            continue
        dx = x2 - x1
        dy = y2 - y1
        key = "{},{}".format(dx,dy)
        if key in dic:
            dic[key] += 1
        else:
            dic[key] = 1

for k, v in sorted(dic.items(), key=lambda x: -x[1]):
    print(n-dic[k])
    break

Submission status: Wrong Answer

Solution code:
N = int(input())
xy = [list(map(int, input().split())) for _ in range(N)]
List = []
for i in range(N):
    for j in range(i+1, N):
        x0, y0 = xy[i]
        x1, y1 = xy[j]
        dx = abs(x0-x1)
        dy = abs(y0-y1)
        List.append((dx, dy))
List.sort()
if List:
    tmp = List[0]
    count=1
    ans = 1
    for i in range(1, len(List)):
        if tmp[0] == List[i][0] and tmp[1] == List[i][1]:
            count += 1
        else:
            ans=max(ans, count)
            count = 1
            tmp = List[i]
    print(N-ans)
else:
    print(1)

Submission status: Wrong Answer

Solution code:
N=int(input())
x=[0 for i in range(N)]
y=[0 for i in range(N)]
for i in range(N):
    x[i],y[i]=map(int,input().split())
Mat=[[(x[i]-x[j],y[i]-y[j]) for j in range(i+1,N)] for i in range(N)]
D=dict()
for i in range(N):
    for j in range(i+1,N):
        dr=(x[i]-x[j],y[i]-y[j])
        if dr in D:
            D[dr]+=1
        else:
            D[dr]=1
maxk=0
for v in D:
    if D[v]>maxk:
        maxk=D[v]
print(N-maxk)

Submission status: Wrong Answer

Solution code:
N = int(input())

a = [list(map(int,input().split())) for i in range(N)]
pq = []
for i in range(N):
    if i == 0:
        x = a[0][0]
        y = a[0][1]
    else:
        p = a[i][0] - x
        q = a[i][1] - y
        x = a[i][0]
        y = a[i][1]
        if (p,q) not in pq:
            pq.append((p,q))
#print(pq)
print(len(pq))

Submission status: Wrong Answer

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

xy.sort()

ans = float('inf')

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: Wrong Answer

Solution code:
from fractions import *

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

ans = min(len(set(x)), len(set(y)))
for a in range(N):
  for b in range(a):
    p = x[a]-x[b]
    q = y[a]-y[b]
    g = gcd(p, q)
    p /= g
    q /= g
    if p!=0 and q!=0:
      s = set()
      for i in range(N):
        s.add(y[i]-x[i]*Fraction(q, p))
      ans = min(ans, len(s))
print ans

Submission status: Wrong Answer

Solution code:
n = int(input())
P = [[int(x) for x in input().split()] for _ in range(n)]

mini = 1e100
for p in range(-50,50):
    for q in range(-50,50):
        if (p,q) == (0,0):
            continue
        count = n
        for i in range(n):
            for j in range(i+1,n):
                if (P[i][0]+p, P[i][1]+q) == (P[j][0], P[j][1]):
                    count -= 1
        mini = min(count, mini)
print(mini)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

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

diffs = defaultdict(int)
for i in range(N):
    for j in range(N):
        if i == j:
            continue
        diffs[(X[i]-X[j], Y[i]-Y[j])] += 1

maxans = -1
maxkey = 0
for k, v in diffs.items():
    if v > maxans:
        maxans = v
        maxkey = k

print(N-maxans)

Submission status: Wrong Answer

Solution code:
n = int(input())
p = [tuple(map(int,input().split())) for _ in range(n)]
d = {}
for i in range(n):
    for j in range(i + 1, n):
        fx = p[i][0] - p[j][0]
        fy = p[i][1] - p[j][1]
        f = (fx, fy)
        if f not in d:
            d[f] = 0
        d[f] += 1
m = 0
for f, v in d.items():
    m = max((m, v))

print(n - m)

Submission status: Wrong Answer

Solution code:
n = int(input())
index=0
hashMap={}
befX = ""
befY = ""
sumP = 0
while index < n:
    x, y = map(int, input().split())
    if index == 0:
        pass
    else:
        key = str(x-befX)+" "+str(y-befY)
        if key in hashMap:
            hashMap[key]+=1
        else:
            hashMap[key]=1   
    sumP+=1
    befX = x
    befY = y
    index+=1

if index > 0:
    maxV = 0
    for key in hashMap:
        if hashMap[key] > maxV:
            maxV = hashMap[key]
    print(sumP-maxV)
else:
    print(1)

Submission status: Wrong Answer

Solution code:
n = int(input())
dc = {}

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

for i in range(n):
    for j in range(i + 1, n):
        key = (xy[i][0] - xy[j][0], xy[i][1] - xy[j][1])
        if key in dc:
            dc[key] += 1
        else:
            dc[key] = 1

mxv = 0
for key, value in dc.items():
    if value > mxv:
        mxv = value
print(n - mxv)

Submission status: Time Limit Exceeded

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

pq = []
for i in range(N):
    for j in range(N):
        if i != j:
            x1 = xy[i][0]
            y1 = xy[i][1]
            x2 = xy[j][0]
            y2 = xy[j][1]
            pq.append((x2 - x1, y2 - y1))

ans = N
for p,q in pq:
    tmp = 0
    for i in range(N):
        for j in range(N):
            if i != j:
                x1 = xy[i][0]
                y1 = xy[i][1]
                x2 = xy[j][0]
                y2 = xy[j][1]
                if x2 - x1 == p and y2 - y1 == q:
                    tmp += 1
    ans = min(ans, N - tmp)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

n = INT()
x = [LIST() for i in range(n)]
l = list(range(n))
ans = inf

for v in permutations(l, n):
    for i in range(n):
        for j in range(n):
            p = x[j][0] - x[i][0] 
            q = x[j][1] - x[i][1]
            cost = 1
            for k in range(1, n):
                if x[v[k-1]][0] == x[v[k]][0] - p and x[v[k-1]][1] == x[v[k]][1] - q:
                    continue
                else:
                    cost += 1
            ans = min(ans, cost)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def i(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10**9)
INF = 10**9
mod = 10**9+7

N = i()
S = [l() for _ in range(N)]
ans = 0
for _ in range(N):
    pq = []
    for i in S:
        for j in S:
            if i == j:
                continue
            pq.append((i[0]-j[0],i[1]-j[1]))
    for p,q in set(pq):
        cnt = 0
        for i in S:
            for j in S:
                if i == j:
                    continue
                if (i[0]-j[0],i[1]-j[1]) == (p,q):
                    cnt += 1
        ans = max(ans,cnt)
print(N-ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def i(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10**9)
INF = 10**9
mod = 10**9+7

N = i()
S = [l() for _ in range(N)]
ans = 0
for _ in range(N):
    pq = []
    for i in S:
        for j in S:
            if i == j:
                continue
            pq.append((i[0]-j[0],i[1]-j[1]))
    for p,q in pq:
        cnt = 0
        for i in S:
            for j in S:
                if i == j:
                    continue
                if (i[0]-j[0],i[1]-j[1]) == (p,q):
                    cnt += 1
        ans = max(ans,cnt)
print(N-ans)

Submission status: Time Limit Exceeded

Solution code:
import math

n=int(input())

XY=[]

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

v=[]

for i in range(n):
    for j in range(n):
        if j!=i:
            v.append([XY[i][0]-XY[j][0],XY[i][1]-XY[j][1]])


c=0
for vx,vy in v:
    cv=0
    for i in range(n):
        for j in range(n):
            if j!=i and [XY[i][0]-XY[j][0],XY[i][1]-XY[j][1]]==[vx,vy]:
                cv+=1
    c=max(cv,c)

print(n-c)

Submission status: Time Limit Exceeded

Solution code:
import math

n=int(input())

XY=[]

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

v=[]

for i in range(n):
    for j in range(n):
        if j!=i and [XY[i][0]-XY[j][0],XY[i][1]-XY[j][1]] not in v:
            v.append([XY[i][0]-XY[j][0],XY[i][1]-XY[j][1]])


c=0
for vx,vy in v:
    cv=0
    for i in range(n):
        for j in range(n):
            if j!=i and [XY[i][0]-XY[j][0],XY[i][1]-XY[j][1]]==[vx,vy]:
                cv+=1
    c=max(cv,c)

print(n-c)

Submission status: Time Limit Exceeded

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

ans = 0
for i in range(n):
    for j in range(n):
        if i == j:
            continue
        dpos = [pos[i][0] - pos[j][0], pos[i][1] - pos[j][1]]
        cnt = 0
        for k in range(n):
            for l in range(n):
                if k == l:
                    continue
                tmp = [pos[k][0] - pos[l][0], pos[k][1] - pos[l][1]]
                if dpos[0] == tmp[0] and dpos[1] == tmp[1]:
                    cnt += 1
        ans = max(cnt, ans)

print(n-ans)

Submission status: Time Limit Exceeded

Solution code:
import copy
import math

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

def dfs(parent, p, q):
    tosee.remove(parent)
    for el in xy:
        if el in tosee:
            x, y = el
            if x + p == parent[0] and y + q == parent[1] or \
                    x - p == parent[0] and y - q == parent[1]:
                dfs(el,p,q)

m = N
for i in range(N - 1):
    for j in range(i + 1, N):
        p = xy[i][0] - xy[j][0]
        q = xy[i][1] - xy[j][1]
        cnt = 0
        tosee = copy.copy(xy)
        while tosee:
            el = tosee[0]
            dfs(el,p,q)
            cnt += 1
            # print(tosee)
        m = min(cnt, m)
        # print(p, q, group)
print(m)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
lst = []
for i in range(n):
    x,y = map(int,input().split())
    lst.append([x,y])
lst.sort()
pmn = lst[0][0]
pmx = lst[-1][0]

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

res = 0
for p in range(pmx+1 - pmn):
    for q in range(qmx+1 - qmn):
        cnt = 0
        for i in range(n):
            tmp_x, tmp_y = lst[i][0], lst[i][1]
            if ([p,q]!=[0,0]) and ([tmp_x+p, tmp_y+q] in lst):
                cnt += 1
        res = max(res, cnt)
print(n - res)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
lists=[]
for i in range(n):
    a,b=map(int,input().split())
    lists.append([a,b])
diflist=[]
for i in range(n):
    for j in range(n):
        if i!=j:
            add=(lists[i][0]-lists[j][0],lists[i][1]-lists[j][1])
            diflist.append(add)
        else:
            continue
            
length=0
for some in diflist:
    cnt=0
    for i in range(n):
        for j in range(n):
            if i!=j:
                check=[lists[i][0]-lists[j][0],lists[i][1]-lists[j][1]]
                if check==[some[0],some[1]]:
                    cnt+=1
            else:
                continue

    length=max(length,cnt)
print(n-length)

Submission status: Time Limit Exceeded

Solution code:
import sys

# from collections import Counter, deque, defaultdict
# from itertools import accumulate, permutations, combinations, takewhile, compress, cycle
# from functools import reduce
# from math import ceil, floor, log10, log2, factorial

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7

# N = int(input())
# A = [int(x) for x in input().split()]
# V = [[0] * 100 for _ in range(100)]
# A = [int(input()) for _ in range(N)]

N = int(input())
# XY = set()
XY = []
for _ in range(N):
    x, y = [int(x) for x in input().split()]
    # XY.add((x,y))
    XY.append((x, y))

XY.sort()
ans = float("INF")
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]

        T = [0] * N
        for k in range(N):
            if T[k] != 0:
                continue
            T[k] = 1
            curXY = (XY[k][0], XY[k][1])

            for l in range(N):
                if (XY[l][0], XY[l][1]) == ((curXY[0] - p, curXY[1] - q)):
                    T[l] = 2
                    curXY = XY[l]

        # ans = min(T.count(1), ans)
        if ans > T.count(1):
            ans = T.count(1)
            ansP, ansQ = p, q
            # print("ans,p,q = {},{},{}".format(ans, p, q))

if N == 1:
    ans = 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

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

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

ans = 100
for l in list(itertools.permutations(balls)):
    dic = {}
    px = l[0][0]
    py = l[0][1]
    t_max = 1
    for i in range(1,len(l)):
        dx = l[i][0] - px
        px = l[i][0]
        dy = l[i][1] - py
        py = l[i][1]
        if (dx,dy) not in dic.keys():
            dic[(dx,dy)] = 1
        else:
            dic[(dx,dy)] += 1
            if (t_max < dic[(dx,dy)]):
                t_max = dic[(dx,dy)]
        kitai = + N - i
        if ans < (N - kitai):
            break
    d_max = t_max
    cost = N - d_max
    if (cost < ans):
        ans = cost
        if (ans == 1):
            print(ans)
            exit()

print(ans)

Submission status: Time Limit Exceeded

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

pqs = []
for i in range(N):
    for j in range(N):
        if i == j:
            continue

        dx = x[i] - x[j]
        dy = y[i] - y[j]
        pqs.append((dx, dy))

ans = N
for pq in pqs:
    p, q = pq
    count = 0
    for i in range(N):
        for j in range(N):
            if i == j:
                continue
            dx = x[i] - x[j]
            dy = y[i] - y[j]
            if dx == p and dy == q:
                count += 1
    ans = min(ans, N - count)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
from operator import itemgetter
N = int(input())
XY = [list(map(int, input().split())) for _ in range(N)]
X, Y = list(map(list, zip(*XY)))

P = [abs(x1 - x2) for x1, x2 in combinations(X, 2)]
P = set(P)
if 0 in P:
    P.remove(0)
P = list(P)
Q = [abs(y1 - y2) for y1, y2 in combinations(Y, 2)]
Q = set(Q)
if 0 in Q:
    Q.remove(0)
Q = list(Q)
ans = 10**10
geta = 10**10
for p in P:
    S = {(x+p)*geta+y for x, y in XY}
    la = 0
    for x, y in XY:
        if x*geta + y not in S:
            la += 1
    ans = min(ans, la)

for q in Q:
    S = {x*geta+y+q for x, y in XY}
    la = 0
    for x, y in XY:
        if x*geta + y not in S:
            la += 1
    ans = min(ans, la)
S = {x*geta+y for x, y in XY}
for p in P:
    for q in Q:
        S1 = {(x+p)*geta+y+q for x, y in XY}
        S2 = {(x+p)*geta+y-q for x, y in XY}
        ans = min(ans, N - len(S & S1), N - len(S & S2))
        
if N == 1:
    ans = 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
from operator import itemgetter
N = int(input())
XY = [list(map(int, input().split())) for _ in range(N)]
X, Y = list(map(list, zip(*XY)))

P = [abs(x1 - x2) for x1, x2 in combinations(X, 2)]
P = set(P)
if 0 in P:
    P.remove(0)
P = list(P)
Q = [abs(y1 - y2) for y1, y2 in combinations(Y, 2)]
Q = set(Q)
if 0 in Q:
    Q.remove(0)
Q = list(Q)
ans = 10**10
geta = 10**10
for p in P:
    S = {(x+p)*geta+y for x, y in XY}
    la = 0
    for x, y in XY:
        if x*geta + y not in S:
            la += 1
    ans = min(ans, la)

for q in Q:
    S = {x*geta+y+q for x, y in XY}
    la = 0
    for x, y in XY:
        if x*geta + y not in S:
            la += 1
    ans = min(ans, la)

for p in P:
    for q in Q:
        S1 = {(x+p)*geta+y+q for x, y in XY}
        S2 = {(x+p)*geta+y-q for x, y in XY}
        la1 = 0
        la2 = 0
        for x, y in XY:
            if x*geta + y not in S1:
                la1 += 1
            if x*geta + y not in S2:
                la2 += 1
        ans = min(ans, la1, la2)
        
if N == 1:
    ans = 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
from operator import itemgetter
N = int(input())
XY = [list(map(int, input().split())) for _ in range(N)]
X, Y = list(map(list, zip(*XY)))

P = [abs(x1 - x2) for x1, x2 in combinations(X, 2)]
P = set(P)
if 0 in P:
    P.remove(0)
P = list(P)
Q = [abs(y1 - y2) for y1, y2 in combinations(Y, 2)]
Q = set(Q)
if 0 in Q:
    Q.remove(0)
Q = list(Q)
ans = 10**10
geta = 10**10
XY.sort()
for p in P:
    S = set()
    la = 0
    for x, y in XY:
        if (x, y) not in S:
            la += 1
        S.add((x+p, y))
    ans = min(ans, la)
XY1 = XY[:]
XY1.sort(key = itemgetter(1))
for q in Q:
    S = set()
    la = 0
    for x, y in XY1:
        if (x, y) not in S:
            la += 1
        S.add((x, y+q))
    ans = min(ans, la)

for p in P:
    for q in Q:
        S1 = set()
        S2 = set()
        la1 = 0
        la2 = 0
        for x, y in XY:
            if x*geta + y not in S1:
                la1 += 1
            if x*geta + y not in S2:
                la2 += 1
            S1.add((x+p)*geta + y+q)
            S2.add((x+p)*geta + y-q)
        ans = min(ans, la1, la2)
        
if N == 1:
    ans = 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
from operator import itemgetter
N = int(input())
XY = [list(map(int, input().split())) for _ in range(N)]
X, Y = list(map(list, zip(*XY)))

P = [abs(x1 - x2) for x1, x2 in combinations(X, 2)]
P = set(P)
if 0 in P:
    P.remove(0)
P = list(P)
Q = [abs(y1 - y2) for y1, y2 in combinations(Y, 2)]
Q = set(Q)
if 0 in Q:
    Q.remove(0)
Q = list(Q)
ans = 10**10
geta = 10**10
XY.sort()
for p in P:
    S = set()
    la = 0
    for x, y in XY:
        if (x, y) not in S:
            la += 1
        S.add((x+p, y))
    ans = min(ans, la)
XY1 = XY[:]
XY1.sort(key = itemgetter(1))
for q in Q:
    S = set()
    la = 0
    for x, y in XY1:
        if (x, y) not in S:
            la += 1
        S.add((x, y+q))
    ans = min(ans, la)

for p in P:
    for q in Q:
        S = set()
        la = 0
        for x, y in XY:
            if x*geta + y not in S:
                la += 1
            S.add((x+p)*geta + y+q)
        ans = min(ans, la)
        S = set()
        la = 0
        for x, y in XY:
            if x*geta + y not in S:
                la += 1
            S.add((x+p)*geta + y-q)
        ans = min(ans, la)
if N == 1:
    ans = 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations, permutations

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

for b1, b2 in permutations(balls, 2):
    p, q = b1[0] - b2[0], b1[1] - b2[1]
    if p != 0 or q != 0:
        sub = 0
        for b3, b4 in permutations(balls, 2):
            dx, dy = b3[0] - b4[0], b3[1] - b4[1]
            if dx == p and dy == q:
                sub += 1
        cost = min(cost, n - sub)

print(max(cost, 1))

Submission status: Time Limit Exceeded

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

ps = set()
qs = set()
for s, t in product(range(n), repeat=2):
    if s == t:
        continue
    ps.add(x[t] - x[s])
    qs.add(y[t] - y[s])

m = 0
for p, q in product(ps, qs):
    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)