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: Runtime Error

Solution code:
#!/usr/bin/env pypy
from __future__ import division, print_function

import os
import sys
from __builtin__ import xrange as range
from collections import defaultdict
from cStringIO import StringIO
from future_builtins import ascii, filter, hex, map, oct, zip
from io import IOBase

import __pypy__


def gcd(x, y):
    """greatest common divisor of x and y"""
    while y:
        x, y = y, x % y
    return x


def get_2dline(p1, p2):
    if p1 == p2:
        return (0, 0, 0)
    _p1, _p2 = min(p1, p2), max(p1, p2)
    a, b, c = _p2[1] - _p1[1], _p1[0] - _p2[0], _p1[1] * _p2[0] - _p1[0] * _p2[1]
    g = gcd(gcd(a, b), c)
    return (a // g, b // g, c // g)


def main():
    n = int(input())
    points = []
    for _ in range(n):
        points.append(tuple(map(int, input().split())))

    line_set = defaultdict(int)
    for i in range(n):
        for j in range(i):
            a, b, c = get_2dline(points[i], points[j])
            line_set[(a, b)] += 1

    p, q = max(line_set.items(), key=lambda x: x[1])[0]
    counter = defaultdict(int)
    for i in range(n):
        x, y = points[i]
        counter[p * x + q * y] += 1
    print(len(counter))


# region fastio

BUFSIZE = 8192


class FastI(IOBase):
    def __init__(self, file):
        self._fd = file.fileno()
        self._buffer = StringIO()
        self.newlines = 0

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count("\n") + (not b)
            ptr = self._buffer.tell()
            self._buffer.seek(0, 2), self._buffer.write(b), self._buffer.seek(ptr)
        self.newlines -= 1
        return self._buffer.readline()


class FastO(IOBase):
    def __init__(self, file):
        self._fd = file.fileno()
        self._buffer = __pypy__.builders.StringBuilder()
        self.write = lambda s: self._buffer.append(s)

    def flush(self):
        os.write(self._fd, self._buffer.build())
        self._buffer = __pypy__.builders.StringBuilder()


def print(*args, **kwargs):
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


sys.stdin, sys.stdout = FastI(sys.stdin), FastO(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from collections import defaultdict
n = int(input())
xy = [list(map(int, input().split())) for i in range(n)]
xy.sort()
s = defaultdict(int)
for i in range(n-1):
  s[(xy[i+1][0]-xy[i][0], xy[i+1][1]-xy[i][1])] += 1
m = max(s.values())
ans = 1 + (n-m-1)
print(ans)

Submission status: Runtime Error

Solution code:
import collections
LX=[]
LY=[]
N=int(input())
for i in range(N):
    x,y=(int(t) for t in input().split())
    LX.append(x)
    LY.append(y)

LLX=[]
LLY=[]
for i,x1 in enumerate(LX):
    for j,x2 in enumerate(LX):
        if i==j:
            continue
        LLX.append(x2-x1)

for i,y1 in enumerate(LY):
    for j,y2 in enumerate(LY):
        if i==j:
            continue
        LLY.append(y2-y1)


LLL=[str(dx)+'&'+str(dy) for dx,dy in zip(LLX,LLY)]

print(N-collections.Counter(LLL).most_common(1)[0][1])

Submission status: Runtime Error

Solution code:
import sys
input=sys.stdin.readline
from collections import deque
from heapq import heappush,heappop
import re

def int_raw():
    return int(input())
 
def ss_raw():
    return input().split()
 
def ints_raw():
    return tuple(map(int, ss_raw()))


def mod_inv(a, b):
    r = a
    w = b
    u = 1
    v = 0
    while w != 0:
        t = r//w
        r -= t*w
        r, w = w, r
        u -= t*v
        u, v = v, u
    return (u % b+b) % b


DIV = 10**9+7

def ncr(n, r, mod=DIV):
	r = min(r, n-r)
	ret = 1
	for i in range(1, r+1):
		ret = ret * (n-i+1) % mod
		ret = ret * mod_inv(i, mod) % mod
	return ret


def main():
    ans = 0
    N = int_raw()
    bxys = [ints_raw() for _ in range(N)]
    bxys.sort()
    dtables = {}
    for idx in range(1,N):
        dxy = (bxys[idx][0]-bxys[idx-1][0],bxys[idx][1]-bxys[idx][1])
        if dxy in dtables:
            dtables[dxy]+=1
        else:
            dtables[dxy]=1
    dmax = max(dtables.values())
    return N-dmax

print(main())

Submission status: Runtime Error

Solution code:
N = int(input())
X = []
for _ in range(N):
  a, b = map(int, input().split())
  X.append((a, b))
mi = 1000
X = sorted(X)
for i in range(N):
    for j in range(i+1, N):
        p = X[j][0]-X[i][0]
        q = X[j][1]-X[i][1]
        if p == 0 and q == 0:
            continue
        if p < 0:
            p, q = -p, -q
        Y = [0] * (p*q)
        c = 0
        for k in range(N):
            for l in range(k):
                if X[l][0] == X[k][0] - p and X[l][1] == X[k][1] - q:
                    break
            else:
                c += 1
        mi = min(mi, c)
print(mi)

Submission status: Runtime Error

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

from itertools import permutations
from collections import Counter
l = [((A[0]-B[0]),(A[1]-B[1])) for A,B in permutations(XY,2)]
c = Counter(l)
print(N - c.most_common()[0][1] )

Submission status: Runtime Error

Solution code:
n = int(input())
xys = {}
xy = []
for _ in range(n):
  x, y = map(int, input().split())
  xys[(x,y)] = True
  xy.append((x,y))

scores = []

for i in range(n):
  for j in range(n):
    if i == j:
      continue
    xi, yi = xy[i]
    xj, yj = xy[j]
    p = xj-xi
    q = yj-yi
    score = n
    for k in range(n):
      xk, yk = xy[k]
      if (xk+p, yk+q) in xys:
        score -= 1
    scores.append(score)

print(min(scores))

Submission status: Runtime Error

Solution code:
n = int(input())
c = [tuple(map(int, input().split())) for _ in range(n)]
s = {}
for i in range(n):
    for j in range(i + 1, n):
        (p, q) = [b - a for a, b in zip(c[i], c[j])]
        s[(p, q)] = s.get((p, q), 0) + 1
print(n - max(s.values()))

Submission status: Runtime Error

Solution code:
from collections import defaultdict
N = int(input())
D = []
for i in range(N):
    x, y = map(int, input().split())
    D.append((x, y))

d = defaultdict(int)
for i in range(N):
    for j in range(i + 1, N):
        d[(D[i][0] - D[j][0], D[i][1] - D[j][1])] += 1

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

Submission status: Runtime Error

Solution code:
N = int(input())
if N == 1:
    return 1
points = []
for _ in range(N):
    x, y = map(int, input().split())
    points.append((x, y))
diff = dict()
for i in range(N):
    for j in range(N):
        if i == j:
            continue
        x1, y1 = points[i]
        x2, y2 = points[j]
        pq = x1-x2, y1-y2
        diff[pq] = diff.get(pq, 0) + 1
val, key = max((v, k) for k, v in diff.items())
print(N-val)

Submission status: Runtime Error

Solution code:
def main():
    N = int(input())
    P = [None] * N
    for i in range(N):
        x, y = map(int, input().split())
        P[i] = (x, y)
    P.sort()
    cnt = {}
    for i in range(N):
        for j in range(i+1, N):
            ix, iy = P[i]
            jx, jy = P[j]
            d = (jx - ix, jy - iy)
            if d not in cnt:
                cnt[d] = 0
            cnt[d] += 1
    print(N - max(cnt.values()))


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from collections import Counter
N = int(input())
P = [list(map(int, input().split())) for _ in range(N)]
ct = Counter()
for i in range(len(P)):
  x1, y1 = P[i]
  for j in range(i+1, len(P)):
    x2, y2 = P[j]
    dx, dy = x2-x1, y2-y1
    if dx < 0:
      dx, dy = -dx, -dy
    ct[(dx, dy)] += 1

print(N - ct.most_common(1)[0][1])

Submission status: Runtime Error

Solution code:
N = int(input())
points = []
for _ in range(N):
    x, y = map(int, input().split())
    points.append((x, y))
diff = dict()
for i in range(N):
    for j in range(N):
        if i == j:
            continue
        x1, y1 = points[i]
        x2, y2 = points[j]
        pq = x1-x2, y1-y2
        diff[pq] = diff.get(pq, 0) + 1
val, key = max((v, k) for k, v in diff.items())
print(N-val)

Submission status: Runtime Error

Solution code:
import math
from decimal import Decimal
def na():
	n = int(input())
	b = [int(x) for x in input().split()]
	return n,b
 
 
def nab():
	n = int(input())
	b = [int(x) for x in input().split()]
	c = [int(x) for x in input().split()]
	return n,b,c
 
 
def dv():
	n, m = map(int, input().split())
	return n,m
 
 
def dva():
	n, m = map(int, input().split())
	a = [int(x) for x in input().split()]
	b = [int(x) for x in input().split()]
	return n,m,b
 
 
def eratosthenes(n): 
	sieve = list(range(n + 1))
	for i in sieve:
		if i > 1:
			for j in range(i + i, len(sieve), i):
				sieve[j] = 0
	return sorted(set(sieve))
 
 
 
def nm():
	n = int(input())
	b = [int(x) for x in input().split()]
	m = int(input())
	c = [int(x) for x in input().split()]
	return n,b,m,c
 
 
def dvs():
	n = int(input())
	m = int(input())
	return n, m
 

n = int(input())
a = []
for i in range(n):
	x, y = map(int, input().split())
	a.append((x, y))
d = {}
for i in range(n):
	tc = a[i]
	for j in range(i + 1, n):
		nd = a[j]
		x1, y1, = tc[0], tc[1]
		x2, y2, = nd[0], nd[1]
		rz1 = abs(x1- x2)
		rz2 = abs(y1 - y2)
		d[(rz1, rz2)] = d.get((rz1,rz2), 0) + 1
print(n - max(d.values()))

Submission status: Runtime Error

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

from collections import Counter
cnt = Counter()
    
for i in range(n):
    for j in range(i+1,n):
        cnt[str((x[j]-x[i],y[j]-y[i]))]+=1

print(n-cnt.most_common()[0][1])

Submission status: Runtime Error

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((xy[i][0]-xy[j][0],xy[i][1]-xy[j][1]))

print(N-Counter(list_).most_common()[0][1])

Submission status: Runtime Error

Solution code:
from collections import defaultdict as ddict
d = ddict(int)
n = int(input())
l = [tuple(map(int, input().split())) for _ in range(n)]
l.sort()
for i in range(n-1):
  for j in range(i+1,n):
    curx = l[j][0] - l[i][0]
    cury = l[j][1] - l[i][1]
    d[(curx,cury)] += 1
print(n-max(d.values()))

Submission status: Runtime Error

Solution code:
import itertools
N = int(input())

XY = [[int(x) for x in input().split()] for _ in range(N)]

vectors = []

for xy1,xy2 in itertools.combinations(XY,2):
  p = xy2[0] - xy1[0]
  q = xy2[1] - xy1[1]
  vectors.append((p,q))
  vectors.append((-p,-q))

from collections import Counter
c = Counter(vectors)

x = max(c.values())

answer = N - x
print(answer)

Submission status: Runtime Error

Solution code:
def inverse(a):
    return pow(a, mod - 2, mod)

def main():
    n = int(input())
    a = [0] * n
    b = [0] * n
    for i in range(n):
        x, y  =tuple(map(int, input().split()))
        a[i] = x
        b[i] = y
    from collections import defaultdict
    d = defaultdict(lambda : 0)
    for i in range(n):
        for j in range(i+1, n):
            d[(abs(a[i] - a[j]), abs(b[i] - b[j]))] += 1

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

main()

Submission status: Runtime Error

Solution code:
import collections
N=int(input())
xy=[tuple([int(i) for i in input().split()])  for j in range(N)]
dist = []
for n,(x,y) in enumerate(xy):
    for j in range(n+1,N):
        gx,gy = xy[j]
        dx,dy = gx-x,gy-y
        dist.append((dx,dy))
zerocost = max(collections.Counter(dist).values())
print(N-zerocost)