Problem:


Score : 300 points

Problem Statement

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

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

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

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

Constraints

1 \leq N \leq 50

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

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

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
x_1 y_1
:
x_N y_N

Output

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

Sample Input 1

2
1 1
2 2

Sample Output 1

1

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

Sample Input 2

3
1 4
4 6
7 8

Sample Output 2

1

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

Sample Input 3

4
1 1
1 2
2 1
2 2

Sample Output 3

2



Sample input:
2
1 1
2 2


Sample output:
1

Submission status: Accepted

Solution code:
N = int(input())

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

if (N != 1):
    dis_dic = {}
    for n in range(N):
        for m in range(N):
            if (n != m):
                distance_tuple = (position[n][0] - position[m]
                                  [0], position[n][1] - position[m][1])

                if distance_tuple in dis_dic.keys():
                    dis_dic[distance_tuple] += 1
                else:
                    dis_dic[distance_tuple] = 1

    print(N - max(dis_dic.values()))
else:
    print(1)

Submission status: Accepted

Solution code:
n = int(input())
a = []
for i in range(n):
	x, y = map(int, input().split())
	a.append((x, y))
d = {}
if n == 1:
	print(1)
	exit()
a = sorted(a)
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 = x1 - x2
		rz2 = y1 - y2
		d[(rz1, rz2)] = d.get((rz1,rz2), 0) + 1
print(n - max(d.values()))

Submission status: Accepted

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
Max = sys.maxsize
def l():
    return list(map(int,input().split()))
def m():
    return map(int,input().split())
def onem():
    return int(input())
def s(x):
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa == x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x):
    return " ".join(map(str,x))

n = onem()
if n == 1:
    l()
    print(1)
else:
    a = []
    for i in range(n):
        a.append(l())
    aa = []
    for i in range(n-1):
        for j in range(i,n):
            if not (a[i][0] - a[j][0] == 0 and a[i][1] - a[j][1] == 0):
                aa.append([a[i][0] - a[j][0],a[i][1] - a[j][1]])
                aa.append([a[j][0] - a[i][0],a[j][1] - a[i][1]])
    aa.sort()
    c = 1
    cc = 1
    lp = aa[0]
    for i in range(1,len(aa)):
        if lp == aa[i]:
            c += 1
        else:
            if c >= cc:
                cc = c
            lp = aa[i]
            c = 1
    if c >= cc:
        cc = c


    print(n - cc )

Submission status: Accepted

Solution code:
N = int(input())

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

X = []
for i in range(N-1):
    for j in range(i+1,N):
        X.append((balls[i][0] - balls[j][0], balls[i][1] - balls[j][1]))
        X.append((balls[j][0] - balls[i][0], balls[j][1] - balls[i][1]))


Y = set(X)
res = 0
for x in X:
    res = max(res, X.count(x))
print(N-res)

Submission status: Accepted

Solution code:
n= int(input())
if n == 1:
    print(1)
    exit(0)
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: Accepted

Solution code:
from collections import Counter
n = int(input())
ball = sorted([list(map(int,input().split())) for i in range(n)])
diff = []
for k in range(1,n):
    for i in range(1,n):
        if i-k>=0:
            p,q = ball[i][0]-ball[i-k][0],ball[i][1]-ball[i-k][1]
            diff.append((p,q))
D = Counter(diff)
p = 0
for v in D.values():
    p = max(p,v)
print(n-p)

Submission status: Accepted

Solution code:
import sys,heapq
from collections import deque,defaultdict
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True  and False
def ddprint(x):
  if DBG:
    print(x)

n = inn()
if n==1:
    print(1)
    exit()
    
a = []
for i in range(n):
    x,y = inm()
    a.append((x,y))

h = defaultdict(int)
for i in range(n-1):
    z = a[i]
    for j in range(i+1,n):
        u = a[j]
        p = z[0]-u[0]
        q = z[1]-u[1]
        if p<0:
            p = -p
            q = -q
        elif p==0 and q<0:
            q = -q
        h[(p,q)] += 1

ddprint(h)
mx = max(h.values())
print(n-mx)

Submission status: Accepted

Solution code:
from collections import Counter, deque, defaultdict
from operator import itemgetter, xor, mul

import sys
#input = sys.stdin.readline
from sys import setrecursionlimit
setrecursionlimit(10**9)

def inpl(): return list(map(int, input().split()))
g0 = itemgetter(0)
N = int(input())
X, Y = [0]*N, [0]*N
P = []
for i in range(N):
    P.append(inpl())
P = sorted(P)
for i in range(N):
    X[i], Y[i] = P[i]

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

ans = N
for ux, uy in U:
    if ux < 0:
        continue
    tmp = 0
    searched = [0]*(N)
    for i in range(N):
        if not searched[i]:
            tmp += 1
            searched[i] = 1
        j = D[(X[i]+ux), (Y[i]+uy)]
        if j:
            searched[j-1] = 1
    ans = min(tmp, ans)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
xy = [[int(item) for item in input().split()] for _ in range(n)]
xy.sort()
pq = []
for x1, y1 in xy:
    for x2, y2 in xy:
        p = x1 - x2
        q = y1 - y2
        if p >= 0 and (p != 0 or q !=0):
            pq.append([p, q])
ans = n
for p, q in pq:
    val = n
    possible = {} 
    for x, y in xy:
        possible[str(x+p) + "_" + str(y+q)] = 1
    for x, y in xy:
        if str(x) + "_" + str(y) in possible:
            val -= 1
    ans = min(ans, val)
print(ans)

Submission status: Accepted

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

import os
import sys
from collections import defaultdict
from io import BytesIO, IOBase

if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip


def main():
    n = int(input())
    p = [list(map(int, input().split())) for _ in range(n)]

    p.sort()

    c = defaultdict(int)

    for i in range(n):
        for j in range(i):
            c[(p[i][0] - p[j][0], p[i][1] - p[j][1])] += 1

    print((n - max(c.values())) if c else 1)


# region fastio

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    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(b"\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()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    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()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion

if __name__ == "__main__":
    main()

Submission status: Accepted

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

xys.sort()
diffs = []
count = []
# 全探索して、一番共通項が多い差分から計算する
for i in range(N):
    for j in range(i+1,N):
        x1,y1 = xys[i]
        x2,y2 = xys[j]
        diff = (x1-x2, y1-y2)
        if diff not in diffs:
            diffs.append(diff)
            count.append(1)
        else:
            k = diffs.index(diff)
            count[k] += 1
if N == 1:
    print(1)
else:
    print(N-max(count))

Submission status: Accepted

Solution code:
#!venv/bin/python
 
import math
import numpy as np
import random
import copy
import statistics 
import bisect
import heapq
from collections import defaultdict 
import time
import sys
from pprint import pprint

N = int(input())
P = []
for _i in range(N):
    P.append([ int(x) for x in input().split() ])

diff = defaultdict(int)
for i in range(N):
    for j in range(N):
        if i == j:
            continue
        key = "{} - {}".format(P[i][0]-P[j][0], P[i][1]-P[j][1])
        diff[key] += 1

if N == 1:
    print(1)
else:
    key = max(diff.keys(), key=lambda x: diff[x])
    print(N-diff[key])

Submission status: Accepted

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

case = [N]
for x,y in xy:
    for xx, yy in xy:
        if x == xx and y == yy:
            continue
        score = N
        xs = xx - x
        ys = yy - y
        for xxx,yyy in xy:
            if x == xxx and y == yyy:
                continue
            if (xxx - xs,yyy - ys) in xy:
                score -= 1
        case.append(score)
print(min(case))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys


def solve(N: int, x: "List[int]", y: "List[int]"):
    diffs = []
    for i in range(N):
        for j in range(i + 1, N):
            diffs.append([x[j] - x[i], y[j] - y[i]])
            diffs.append([x[i] - x[j], y[i] - y[j]])
    diffs.sort()
    cnt = 0
    tmp = 1
    for i in range(1, len(diffs)):
        if diffs[i] == diffs[i - 1]:
            tmp += 1
        else:
            cnt = max(tmp, cnt)
            tmp = 1
    ret = N - cnt
    print(ret)
    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:
n = int(input())
dc = {}

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

for i in range(n):
    for j in range(n):
        if i == j:
            continue
        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
mxk = None
for key, value in dc.items():
    if value > mxv:
        mxv = value
        mxk = key
# print(mxk)
print(n - mxv)

Submission status: Accepted

Solution code:
from sys import stdin
import math
import fractions
from collections import deque
import collections
import itertools

INF = 10 ** 10


# N個のボールがあり、i番目のボールは(xi, yi)にある
N = int(stdin.readline().rstrip())
xy = [list(map(int, stdin.readline().rstrip().split())) for _ in range(N)]

data = []

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

for i in range(N):
    for j in range(i+1, N):
        x_diff = xy[i][0] - xy[j][0]
        y_diff = xy[i][1] - xy[j][1]
        data.append("{0},{1}".format(x_diff, y_diff))
        data.append("{0},{1}".format(-x_diff, -y_diff))

c = collections.Counter(data)

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

Submission status: Accepted

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

if N ==1:
    print(1)
else:
    pqlis = []
    lis.sort()
    dxdic ={}
    for i in range(N):
        for j in range(i):
            dx = lis[i][0] -lis[j][0]
            if dx in dxdic.keys():
                dxdic[dx].append([i,j])
            else:
                dxdic[dx] =[[i,j]]
    ans = 0
    for li in dxdic.values():
        foo = 0
        dydic = {}
        for i,j in li:
            dy = lis[i][1] -lis[j][1]
            if dy in dydic.keys():
                dydic[dy] += 1
            else:
                dydic[dy] = 1
        foo = max(dydic.values())
        if ans < foo:
            ans = foo
    print(N-ans)

Submission status: Accepted

Solution code:
points=[]
N=int(input())
dic={}
for _ in range(N):
    a,b=list(map(int,input().strip().split(' ')))
    points+=[(a,b)]

points=sorted(points)
for i in range(len(points)):
    dic[points[i]]=i

def find(points):
    diff={}
    for i in range(len(points)):
        for j in range(i+1,len(points)):
            a=points[j][0]-points[i][0]
            b=points[j][1]-points[i][1]
            if a!=0 or b!=0:
                diff[(a,b)]=1
    
    return diff

diff=find(points)

def find(X):
    a,b=X
    checked=[0]*len(points)
    ans=0
    for i in range(len(checked)):
        if checked[i]==0:
            ans+=1
            x,y=points[i]
            for j in range(1,len(checked)+1):
                temp_x,temp_y=x+a*j,y+b*j
                if (temp_x,temp_y) in dic:
                    order=dic[(temp_x,temp_y)]
                    checked[order]=1
                else:
                    break
    return ans

ANS=len(points)

for X in diff:
    ANS=min(ANS,find(X))
print(ANS)

Submission status: Accepted

Solution code:
n=int(input())
l=[]
for i in range(n):
  l.append(list(map(int,input().split())))
lpq=[]
for i in range(n):
  for j in range(n):
    if i==j:
      pass
    else:
      lpq.append([l[i][0]-l[j][0],l[i][1]-l[j][1]])
score=n-1
for i in lpq:
  s1=0
  for j in l:
    for k in l:
      if j==k:
        pass
      else:
        if j[0]-k[0]==i[0] and j[1]-k[1]==i[1]:
          s1+=1
  s=n-s1
  if s<score:
    score=s
if n==1:
  print(1)
else:
  print(score)

Submission status: Accepted

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

def f(N, XY):
    S = set(XY)
    sc = N

    for i in range(N):
        x0, y0 = XY[i]

        for j in range(i+1, N):
            x1, y1 = XY[j]

            sc = min(sc, N - g(S, x1-x0, y1-y0))

    return sc


def g(S, p, q):
    cnt = 0

    for x,y in S:
        if (x+p, y+q) in S:
            cnt += 1

    return cnt
            
    


def main():
    N = int(input())
    XY = [tuple(map(int, input().split())) for i in range(N)]

    print(f(N, XY))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np
from collections import defaultdict
from functools import reduce
from itertools import permutations

# s = input()
n = int(input())
# A = list(map(int, input().split()))
# a, b = map(int, input().split())

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

res = n

for n1, n2 in permutations(range(n) ,2):
    p = lis[n1][0] - lis[n2][0]
    q = lis[n1][1] - lis[n2][1]
    s = set(range(n))
    s.remove(n1)
    s.remove(n2)

    score = 1
    x = lis[n1][0]
    y = lis[n1][1]

    while True:
        x2 = x
        y2 = y
        while True:
            if ((x2+p), (y2+q)) in dic:
                i = dic[((x2+p), (y2+q))]
                if i in s:
                    s.remove(i)
                x2 = lis[i][0]
                y2 = lis[i][1]
            else:
                break
        x2 = x
        y2 = y
        while True:
            if ((x2-p), (y2-q)) in dic:
                i = dic[((x2-p), (y2-q))]
                if i in s:
                    s.remove(i)
                x2 = lis[i][0]
                y2 = lis[i][1]
            else:
                break

        if len(s) == 0:
            break
        i = s.pop()
        x = lis[i][0]
        y = lis[i][1]
        score += 1
    res = min(res, score)
print(res)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))#親ノード
        self.size = [1]*n #グループの要素数
 
    def root(self, x): #root(x): xの根ノードを返す．
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]
            x = self.parent[x]
        return x 
 
    def merge(self, x, y): #merge(x,y): xのいるグループと$y$のいるグループをまとめる
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return False
        if self.size[x] < self.size[y]: 
            self.size[y] += self.size[x] #yの要素数を更新
            self.parent[x] = y #xをyにつなぐ
        else:
            self.size[x] += self.size[y] #xの要素数を更新
            self.parent[y] = x #yをxにつなぐ
        return True
 
    def issame(self, x, y): #same(x,y): xとyが同じグループにあるならTrue
        return self.root(x) == self.root(y)
        
    def size(self,x): #size(x): xのいるグループの要素数を返す
        return self.size[self.root(x)]

n = int(input())
xy = [[int(i) for i in input().split()] for j in range(n)] # 縦「n」行

ans = n
s = {(x1-x2, y1-y2) for (x1,y1) in xy for (x2,y2) in xy}
s.remove((0,0))

for dx,dy in s:
    uf = UnionFind(n)
    c = 0
    for i, (xi,yi) in enumerate(xy):
        for j, (xj,yj) in enumerate(xy):
#        for j in range(i+1,n):
#            xj, yj = xy[j]
            if xj-xi == dx and yj-yi == dy:
                uf.merge(i,j)
                c+=1
#    print(uf.parent)
    if ans > n-c:
        ans = n-c
                

print(ans)

Submission status: Accepted

Solution code:
import collections
N = int(input())
xy_array = [list(map(int, input().split())) for i in range(N)]
if N == 1:
    print(1)
    exit()
# print(xy_array)
distance_array = []
for i in range(N):
    x_i, y_i = xy_array[i]
    for j in range(N):
        if i == j:
            continue
        x_j, y_j = xy_array[j]
        distance_array.append((x_i - x_j, y_i - y_j))

ans_array = collections.Counter(distance_array)
max_count = ans_array.most_common()[0][1]
print(N - max_count)

Submission status: Accepted

Solution code:
import collections

n = int(input())

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

vec = []
vec_set = []

for i in range(n):
    vec2 = []
    for j in range(n):
        vec2.append((x[i] - x[j], y[i] - y[j]))
        vec_set.append((x[i] - x[j], y[i] - y[j]))
    vec.append(vec2)

cc = collections.Counter(vec_set)

v_l = []
for key,value in cc.items():
    if key != (0,0):
        v_l.append(value)
if len(v_l) != 0:
    print(n - max(v_l))
else:
    print(1)

Submission status: Accepted

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(N):
        if i==j:
            continue
        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: Accepted

Solution code:
n=int(input())
A=[]
B=[]
for i in range(n):
  a,b=map(int,input().split())
  A.append([a,b])
  
for i in range(n):
  for j in range(i):
    B.append([A[i][0]-A[j][0],A[i][1]-A[j][1]])
  for j in range(i+1,n):
    B.append([A[i][0]-A[j][0],A[i][1]-A[j][1]])
    

l=0
for i in B:
  l=max(l,B.count(i))
print(n-l)

Submission status: Accepted

Solution code:
from itertools import combinations as c
from collections import Counter

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

if n==1:
    print(1)
else:
    l.sort()
    m=c(l,2)
    ans=[]
    for v in m:
        ans.append(str([v[1][0]-v[0][0],v[1][1]-v[0][1]]))
    a=Counter(ans).most_common()[0][1]
    print(n-a)

Submission status: Accepted

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

if N==1:
    print(1)
    exit(0)
diff={}
for i in range(N):
    for j in range(i+1, N):
        a=(xy[i][0]-xy[j][0], xy[i][1]-xy[j][1])
        diff[a]=diff.get(a,0)+1
print(N-max(diff.values()))

Submission status: Accepted

Solution code:
import collections

def solve(n, points):
    if n == 1:
        return 1
    a = []
    for i in range(n-1):
        for j in range(i + 1, n):
            x = points[i][0] - points[j][0]
            y = points[i][1] - points[j][1]
            if x > 0:
                a.append((x, y))
            elif x < 0:
                a.append((-x, -y))
            else:
                a.append((0, abs(y)))

    c = collections.Counter(a).most_common()[0][1]
    return n - c

n = int(input())
points = [list(map(int, input().split(' '))) for _ in range(n)]
print(solve(n, points))

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
xy = [LIST() for _ in range(N)]
xy.sort(key=lambda x:(x[0], x[1]))
# print(xy)
delta = defaultdict(int)
if N == 1:
	print(1)
else:
	for i in range(N):
		for j in range(N):
			if i != j:
				delta[(xy[j][0]-xy[i][0], xy[j][1]-xy[i][1])] += 1
	print(1+(N-1)-max(delta.values()))

Submission status: Accepted

Solution code:
from collections import defaultdict

n = int(input())
if n == 1:
	print(1)
else:
	balls = [list(map(int, input().split())) for _ in range(n)]

	d = defaultdict(lambda: 0)
	for x in range(n):
		for y in range(n):
			d[(balls[x][0] - balls[y][0], balls[x][1] - balls[y][1])] += 1

	del d[(0, 0)]
	print(n - max(d.values()))

Submission status: Accepted

Solution code:
N = int(input())
src = [tuple(map(int,input().split())) for i in range(N)]
pq = []
for i in range(N):
    for j in range(N):
        if i==j: continue
        x0,y0 = src[i]
        x1,y1 = src[j]
        pq.append((x1-x0, y1-y0))

ss = set(src)

ans = N
for p,q in pq:
    tmp = 0
    for x,y in src:
        if (x+p, y+q) not in ss:
            tmp += 1
    ans = min(ans, tmp)
print(ans)

Submission status: Accepted

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)]
    if N==1:
        return 1
    bxys.sort()
    dtables = {}

    for idx in range(0,N):
        for idx2 in range(idx+1,N):
            dxy = (bxys[idx2][0]-bxys[idx][0],bxys[idx2][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: Accepted

Solution code:
import itertools
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")


class UnionFind:
    def __init__(self, size=None, nodes=None):
        """
        size か nodes どっちか指定。
        nodes は set、size は list を使う。
        set の最悪計算量は O(N) なので size 指定のほうが若干速い
        :param int size:
        :param collections.Iterable nodes:
        """
        assert size is not None or nodes is not None
        if size is not None:
            self._parents = [i for i in range(size)]
            self._ranks = [0 for _ in range(size)]
            self._sizes = [1 for _ in range(size)]
        else:
            self._parents = {k: k for k in nodes}
            self._ranks = {k: 0 for k in nodes}
            self._sizes = {k: 1 for k in nodes}

    def unite(self, x, y):
        """
        x が属する木と y が属する木を併合
        :param x:
        :param y:
        :return:
        """
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return

        # rank が小さい方が下
        if self._ranks[x] > self._ranks[y]:
            # x が root
            self._parents[y] = x
            self._sizes[x] += self._sizes[y]
        else:
            # y が root
            self._parents[x] = y
            self._sizes[y] += self._sizes[x]
            if self._ranks[x] == self._ranks[y]:
                self._ranks[y] += 1

    def find(self, x):
        """
        x が属する木の root
        :param x:
        :return:
        """
        if self._parents[x] == x:
            return x
        self._parents[x] = self.find(self._parents[x])
        return self._parents[x]

    def size(self, x):
        """
        x が属する木のノード数
        :param x:
        :return:
        """
        return self._sizes[self.find(x)]


N = int(sys.stdin.readline())
X, Y = list(zip(*[map(int, sys.stdin.readline().split()) for _ in range(N)]))

min_x = min(X)
min_y = min(Y)
max_x = max(X)
max_y = max(Y)

coo = {}
for i, (x, y) in enumerate(zip(X, Y)):
    coo[(x, y)] = i

ans = N
for i, j in itertools.combinations(range(N), r=2):
    x1, x2 = X[i], X[j]
    y1, y2 = Y[i], Y[j]
    p = x1 - x2
    q = y1 - y2

    uf = UnionFind(size=N)
    for k in range(N):
        x, y = X[k], Y[k]
        if (x + p, y + q) in coo:
            uf.unite(k, coo[(x + p, y + q)])
        if (x - p, y - q) in coo:
            uf.unite(k, coo[(x - p, y - q)])
    roots = set()
    for k in range(N):
        roots.add(uf.find(k))
    ans = min(len(roots), ans)
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
arr=[]
for i in range(n):
	x,y=map(int,input().split())
	arr.append((x,y))
arr.sort()
ans=1000000000000000
for i in range(n-1):
	for j in range(i+1,n):
		currp=arr[j][0]-arr[i][0]
		currq=arr[j][1]-arr[i][1]
		mark=[0]*n
		temp=0
		k=0
		while(k<n):
			if(mark[k]==0):
				xval=arr[k][0]
				yval=arr[k][1]
				l=k+1
				while(l<n):
					if(arr[l][0]==xval+currp and arr[l][1]==yval+currq):
						mark[l]=1
						xval=arr[l][0]
						yval=arr[l][1]
					l+=1
				temp+=1
			k+=1
		ans=min(ans,temp)
if(ans==1000000000000000):
	ans=1
print(ans)

Submission status: Accepted

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

d = dict()
for i in range(n):
    for j in range(n):
        if i == j:
            continue
        x1,y1 = l[i]
        x2,y2 = l[j]
        if d.__contains__((x2-x1,y2-y1)):
            d[(x2-x1,y2-y1)] += 1
        else:
            d[(x2-x1,y2-y1)] = 1

ll = list(d.values())
if ll == []:
    maxV = 0
else:
    maxV = max(list(d.values()))

print(n-maxV)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
x, y = (
    zip(*(map(int, input().split()) for _ in range(N))) if N else
    ((), ())
)

class UnionFindTree:
    def __init__(self, n):
        self.p = [i for i in range(n + 1)]
        self.r = [0 for _ in range(n + 1)]

    def find(self, x):
        if self.p[x] != x:
            self.p[x] = self.find(self.p[x])
        return self.p[x]

    def union(self, x, y):
        px = self.find(x)
        py = self.find(y)
        if px != py:
            if self.r[px] < self.r[py]:
                self.p[px] = py
            else:
                self.p[py] = px
                if self.r[px] == self.r[py]:
                    self.r[px] += 1

    def same(self, x, y):
        return self.find(x) == self.find(y)


ans = 10**10

for i in range(N):
    for j in range(N):
        p, q = (x[i] - x[j], y[i] - y[j])
        uft = UnionFindTree(N)
        for u in range(N - 1):
            for v in range(u + 1, N):
                if (x[u] - x[v], y[u] - y[v]) == (p, q) or (x[u] - x[v], y[u] - y[v]) == (-p, -q):
                    uft.union(u, v)
        ans = min(ans, len({uft.find(z) for z in range(N)}))

print(ans)

Submission status: Accepted

Solution code:
import collections
n = int(input())
xy =[]
for i in range(n):
    x,y = map(int,input().split())
    xy.append((x,y))
xy2 = xy[:]
c = collections.Counter()
for x,y in xy:
    for w,z in xy2:
        c[(x-w,y-z)] +=1
if n==1:
    print(1)            
else:    
    print(n-c.most_common(2)[1][1])