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:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
from math import sqrt
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

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

    # これ追加
    def count_group(self):
        return len({self.find(x) for x in range(N)})

N = getN()
que = [getList() for i in range(N)]

dis = []
# [p, q]の通りは50C2通りある
for i in range(N):
    for j in range(i + 1, N):
        dis.append([que[i][0] - que[j][0], que[i][1] - que[j][1]])

ans = float('inf')
for p, q in dis:
    U = UnionFind(N)
    for i in range(N):
        for j in range(i + 1, N):
            if (que[i][0] + p == que[j][0] and que[i][1] + q == que[j][1]) or (que[i][0] - p == que[j][0] and que[i][1] - q == que[j][1]):
                U.union(i, j)
    ans = min(ans, U.count_group())
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import combinations
def main():
    n = int(input())
    X = [list(map(int, input().split())) for _ in range(n)]
    ans = 1 if n == 1 else 100
    for (x1, y1), (x2, y2) in combinations(X, 2):
        a, b = y2 - y1, x1 - x2
        ans = min(ans, len(set(a * x + b * y for x, y in X)))
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from itertools import combinations
def main():
    n = int(input())
    X = [list(map(int, input().split())) for _ in range(n)]
    ans = 100
    for (x1, y1), (x2, y2) in combinations(X, 2):
        a, b = y2 - y1, x1 - x2
        c = set()
        for (x, y) in X:
            c.add(a * x + b * y)
        ans = min(ans, len(c))
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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)]
reg = 0

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

ans = n - reg
print(ans)

Submission status: Wrong Answer

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

for v in permutations(l, n):
    a = []
    for i in range(1, n):
        a.append((x[v[i]][0]-x[v[i-1]][0], x[v[i]][1]-x[v[i-1]][1]))
    a.sort()
    count = 1
    for j in range(1, n-1):
        if a[j][:] == a[j-1][:]:
            count += 1
            reg = max(reg, count)
        else:
            count = 1

ans = n - reg
print(ans)

Submission status: Wrong Answer

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

for v in permutations(l, n):
    a = []
    for i in range(1, n):
        a.append((x[v[i]][0]-x[v[i-1]][0], x[v[i]][1]-x[v[i-1]][1]))
    a.sort()
    count = 1
    for j in range(1, n-1):
        if a[j][:] == a[j-1][:]:
            count += 1
        else:
            count = 1
    reg = max(reg, count)

ans = n - reg
print(ans)

Submission status: Wrong Answer

Solution code:
# ベクトルを固定して全探索まではわかる 実装がわからん
# いやべつに順番は関係ないのか？ 「残っているボールを 1つ選んで回収する。」

n = int(input())
if n == 1:
    print(0)
    exit()
points = []
for _ in range(n):
    points.append(list(map(int, input().split())))

ans = 10**18
for p in range(n):
    for q in range(n):
        if p == q:
            continue
        vector = [points[p][0] - points[q][0], points[p][1] - points[q][1]]
        tmp = 0
        for i in range(n):
            for j in range(n):
                if i == j:
                    continue
                if points[i][0] - points[j][0] == vector[
                        0] and points[i][1] - points[j][1] == vector[1]:
                    tmp += 1

        ans = min(ans, n - tmp)

print(ans)

Submission status: Wrong Answer

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(1, n):
        p = x[v[i]][0] - x[v[i-1]][0] 
        q = x[v[i]][1] - x[v[i-1]][1]
        cost = 1
        for j in range(1, n):
            if x[v[j-1]][0] == x[v[j]][0] - p and x[v[j-1]][1] == x[v[j]][1] - q:
                continue
            else:
                cost += 1
        ans = min(ans, cost)

print(ans)

Submission status: Wrong Answer

Solution code:
# ベクトルを固定して全探索まではわかる 実装がわからん
# いやべつに順番は関係ないのか？ 「残っているボールを 1つ選んで回収する。」

n = int(input())
if n == 1:
    print(0)
    exit()
points = []
for _ in range(n):
    points.append(list(map(int, input().split())))

ans = 10**18
for p in range(n):
    for q in range(n):
        if p == q:
            continue
        vector = [points[p][0] - points[q][0], points[p][1] - points[q][1]]
        tmp = 0
        for i in range(n):
            for j in range(i + 1, n):
                if points[i][0] - points[j][0] == vector[
                        0] and points[i][1] - points[j][1] == vector[1]:
                    tmp += 1

        ans = min(ans, n - tmp)

print(ans)

Submission status: Wrong Answer

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

a = []
for i in range(n):
    for j in range(n):
        if x[j][0]-x[i][0] == x[j][1]-x[i][1] == 0:
            continue
        else:
            a.append((x[j][0]-x[i][0], x[j][1]-x[i][1]))

a.sort()
count = 1
max_reg = 1

for i in range(1, len(a)):
    if a[i][:] == a[i-1][:]:
        count += 1
        max_reg = max(max_reg, count)
    else:
        count = 1

ans = n - max_reg
print(ans)

Submission status: Wrong Answer

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

a = []
for i in range(n):
    for j in range(n):
        if x[j][0]-x[i][0] == x[j][1]-x[i][1] == 0:
            continue
        else:
            a.append((x[j][0]-x[i][0], x[j][1]-x[i][1]))

a.sort()
count = 0
max_reg = 0

for i in range(1, len(a)):
    if a[i][:] == a[i-1][:]:
        count += 1
        max_reg = max(max_reg, count)
    else:
        count = 0

ans = n - 1 - max_reg
print(ans)

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

a = {}
for i in range(n):
    for j in range(i + 1, n):
        v = x[j] - x[i], y[j] - y[i]
        if v not in a:
            a[v] = 1
        else:
            a[v] += 1
ans = n
if len(a.values()) > 0:
    ans -= max(a.values())
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
x=[]
for i in range(n):
    a,b=map(int,input().split())
    x.append([a,b])
x.sort()
ans=float("inf")
for i in range(n-1):
    for j in range(i+1,n):
        p,q=x[j][0]-x[i][0],x[j][1]-x[i][1]
        cnt=0
        flg=[False for i in range(n)]
        for k in range(n):
            if flg[k]==False:
                flg[k]=True
                cnt+=1
                fl=True
                xx,yy=x[k][0],x[k][1]
                while fl:
                    nx,ny=xx+p,yy+q
                    if [nx,ny] in x:
                        a=x.index([nx,ny])
                        flg[a]=True
                        xx,yy=nx,ny
                    else:
                        fl=False
        if cnt<ans:
            ans=cnt
print(ans)

Submission status: Wrong Answer

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

res = 0
for i in range(N):
    for j in range(N):
        if i == j:
            continue
        p = x[i] - x[j]
        q = y[i] - y[j]
        
        cnt = 0
        for ii in range(N - 1):
            for jj in range(ii + 1, N):
                pp = x[jj] - p
                qq = y[jj] - q
                if ii == jj:
                    continue
                if pp == x[ii] and qq == y[ii]:
                    cnt += 1
            res = max(res, cnt)

print(N - res)

Submission status: Wrong Answer

Solution code:
from collections import Counter
n = int(input())
XY = [list(map(int,input().split())) for _ in range(n)]
XY.sort(key=lambda x: x[0], reverse=True)
dXY = Counter([])
for i in range(n-1):
    for j in range(i+1,n):
        dXY += Counter([str(XY[i][0]-XY[j][0])+'_'+str(XY[i][1]-XY[j][1])])
if n==1:
    print(1)
else:
    print(n-dXY.most_common()[0][1])

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

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

cnt = defaultdict(int)
for xi, yi in xy:
    for xj, yj in xy:
        cnt[(xi - xj, yi - yj)] += 1
cnt[(0, 0)] = 1
ans = n - max(cnt.values())
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
def main():
  N = int(input())
  posi = []
  for i in range(N):
    posi.append(list(map(int, input().split())))
  posi.sort()
  num = [i for i in range(N)]
  ans = 1000000000
  for pair in itertools.combinations(num,2):
    p = posi[pair[1]][0]-posi[pair[0]][0]
    q = posi[pair[1]][1]-posi[pair[0]][1]
    ch = [True]*N
    ans_temp = 0
    for i in range(N):
      if ch[i]:
        ans_temp += 1
        ch[i] = False
      now = posi[i]
      while [now[0] +  p, now[1] + q] in posi:
        ch[posi.index([now[0] +  p, now[1] + q])] = False
        now = [now[0] +  p, now[1] + q]
    ans = min(ans, ans_temp)
  print(ans)
    
  
if __name__ == "__main__":
  main()

Submission status: Wrong Answer

Solution code:
import itertools
def main():
  N = int(input())
  posi = []
  for i in range(N):
    posi.append(list(map(int, input().split())))
  posi.sort()
  num = [i for i in range(N)]
  ans = 1000000000
  for pair in itertools.combinations(num,2):
    p = posi[pair[1]][0]-posi[pair[0]][0]
    q = posi[pair[1]][1]-posi[pair[0]][1]
    ch = [True]*N
    ans_temp = 0
    for i in range(N):
      if ch[i]:ans_temp += 1
      now = posi[i]
      while [now[0] +  p, now[1] + q] in posi:
        ch[posi.index([now[0] +  p, now[1] + q])] = False
        now = [now[0] +  p, now[1] + q]
    ans = min(ans, ans_temp)
  print(ans)
    
  
if __name__ == "__main__":
  main()

Submission status: Wrong Answer

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 k(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def X(): return list(input())
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)
def gcd(*numbers): reduce(math.gcd, numbers)
sys.setrecursionlimit(10 ** 9)
mod = 10**9+7
count = 0
ans = 0

N = k()
ball = [l() for _ in range(N)]
kaisa_a = []
kaisa_b = []

for j in range(N-1):
    a = abs(ball[j+1][0]-ball[j][0])
    b = abs(ball[j+1][1]-ball[j][1])
    kaisa_a.append(a)
    kaisa_b.append(b)

kaisa_a = list(set(kaisa_a))
kaisa_b = list(set(kaisa_b))

x = len(kaisa_a)
y = len(kaisa_b)

print(max(x,y))

Submission status: Wrong Answer

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

import sys
from typing import Any, Callable, Deque, Dict, List, Mapping, Optional, Sequence, Set, Tuple, TypeVar, Union
# import time
# import math, cmath
# import numpy as np
# import scipy.sparse.csgraph as cs            # csgraph_from_dense(ndarray, null_value=inf), bellman_ford(G, return_predecessors=True), dijkstra, floyd_warshall
# import random                                # random, uniform, randint, randrange, shuffle, sample
# import string                                # ascii_lowercase, ascii_uppercase, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from datetime import date, datetime          # date.today(), date(year,month,day) => date obj; datetime.now(), datetime(year,month,day,hour,second,microsecond) => datetime obj; subtraction => timedelta obj
# from datetime.datetime import strptime       # strptime('2019/01/01 10:05:20', '%Y/%m/%d/ %H:%M:%S') returns datetime obj
# from datetime import timedelta               # td.days, td.seconds, td.microseconds, td.total_seconds(). abs function is also available.
# from copy import copy, deepcopy              # use deepcopy to copy multi-dimentional matrix without reference
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import _heapify_max, _heappop_max, _siftdown_max
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from fractions import Fraction               # Fraction(a, b) => a / b ∈ Q. note: Fraction(0.1) do not returns Fraciton(1, 10). Fraction('0.1') returns Fraction(1, 10)



def main():
    Num = Union[int, float]
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79e+308
    # inf = 2 ** 63 - 1             # (for fast JIT compile in PyPy) 9.22e+18
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def isp():   return input().split()
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    # def _heappush_max(h, item): h.append(item); _siftdown_max(h, 0, len(h)-1)
    

    def calc_cost(p, q, points):
        selected = [False] * n
        cnt = 0
        for i in range(n):
            if not selected[i]:
                selected[i] = True
                cnt += 1
                x, y = points[i]
                while True:
                    if [x + p, y + q] in points:
                        selected[points.index([x + p, y + q])] = True
                        x, y = x + p, y + q
                    else:
                        break
                x, y = points[i]
                while True:
                    if [x - p, y - q] in points:
                        selected[points.index([x - p, y - q])] = True
                        x, y = x - p, y - q
                    else:
                        break
        return cnt
    
    
    n = ii()
    points = [lmi() for _ in range(n)]

    cost = inf
    for i in range(n):
        for j in range(n):
            if i != j:
                p = points[i][0] - points[j][0]
                q = points[i][1] - points[j][1]
                cost = min(cost, calc_cost(p, q, points))
    
    print(cost)



if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

import sys
from typing import Any, Callable, Deque, Dict, List, Mapping, Optional, Sequence, Set, Tuple, TypeVar, Union
# import time
# import math, cmath
# import numpy as np
# import scipy.sparse.csgraph as cs            # csgraph_from_dense(ndarray, null_value=inf), bellman_ford(G, return_predecessors=True), dijkstra, floyd_warshall
# import random                                # random, uniform, randint, randrange, shuffle, sample
# import string                                # ascii_lowercase, ascii_uppercase, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from datetime import date, datetime          # date.today(), date(year,month,day) => date obj; datetime.now(), datetime(year,month,day,hour,second,microsecond) => datetime obj; subtraction => timedelta obj
# from datetime.datetime import strptime       # strptime('2019/01/01 10:05:20', '%Y/%m/%d/ %H:%M:%S') returns datetime obj
# from datetime import timedelta               # td.days, td.seconds, td.microseconds, td.total_seconds(). abs function is also available.
# from copy import copy, deepcopy              # use deepcopy to copy multi-dimentional matrix without reference
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import _heapify_max, _heappop_max, _siftdown_max
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from fractions import Fraction               # Fraction(a, b) => a / b ∈ Q. note: Fraction(0.1) do not returns Fraciton(1, 10). Fraction('0.1') returns Fraction(1, 10)



def main():
    Num = Union[int, float]
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79e+308
    # inf = 2 ** 63 - 1             # (for fast JIT compile in PyPy) 9.22e+18
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def isp():   return input().split()
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    # def _heappush_max(h, item): h.append(item); _siftdown_max(h, 0, len(h)-1)
    

    def calc_cost(p, q, points):
        selected = [False] * n
        cnt = 0
        for i in range(n):
            if not selected[i]:
                selected[i] = True
                cnt += 1
                x, y = points[i]
                while True:
                    if [x + p, y + q] in points:
                        selected[points.index([x + p, y + q])] = True
                        x, y = x + p, y + q
                    else:
                        break
                x, y = points[i]
                while True:
                    if [x - p, y - q] in points:
                        selected[points.index([x - p, y - q])] = True
                        x, y = x - p, y - q
                    else:
                        break
        return cnt
    
    
    n = ii()
    points = [lmi() for _ in range(n)]

    cost = 100
    for i in range(n-1):
        for j in range(i+1, n):
            p = points[i][0] - points[j][0]
            q = points[i][1] - points[j][1]
            cost = min(cost, calc_cost(p, q, points))
            p = -p
            q = -q
            cost = min(cost, calc_cost(p, q, points))
    
    print(cost)



if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    ################
    class UnionFind():
        """
        parents : 親要素(findしない場合は根ではないことの注意)，根の場合は"-(要素数）"
        find(x):要素xの属するグループの根を返す
        size(x):要素xの属するグループの要素数を返す
        same(x,y):x,yが同じグループに属しているか返す
        members(x):要素xが属するグループに属する要素をリストで返す
        roots:全ての根の要素を返す
        group_count():グループの数を返す
        all_group_members():{根要素：[そのグループに含まれる要素のリスト]}の辞書を返す
        """
        def __init__(self, n):
            self.n = n
            self.parents = [-1] * n

        def find(self, x):
            #根を探す&つなぎかえる
            if self.parents[x] < 0:
                return x
            else:
                self.parents[x] = self.find(self.parents[x])
                return self.parents[x]

        def union(self, x, y):
            x = self.find(x)
            y = self.find(y)

            if x == y:
                return

            if self.parents[x] > self.parents[y]:
                x, y = y, x

            self.parents[x] += self.parents[y]
            self.parents[y] = x

        def size(self, x):
            return -self.parents[self.find(x)]

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

        def members(self, x):
            root = self.find(x)
            return [i for i in range(self.n) if self.find(i) == root]

        def roots(self):
            return [i for i, x in enumerate(self.parents) if x < 0]

        def group_count(self):
            return len(self.roots())

        def all_group_members(self):
            return {r: self.members(r) for r in self.roots()}

        def __str__(self):
            return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
    
################


    mod=10**9+7
    N=I()
    X=[0]*N
    Y=[0]*N
    for i in range(N):
        X[i],Y[i]=MI()
    
    ans=N
    
    for ii in range(N):
        for jj in range(N):
            p=X[ii]-X[jj]
            q=Y[ii]-Y[jj]
            uf=UnionFind(N)
    
            for j in range(N):
                for k in range(j+1,N):
                    if X[k]-X[j]==p and Y[k]-Y[j]==q:
                        uf.union(j,k)
            temp=uf.group_count()
            ans=min(ans,temp)
    print(ans)
        
        

main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
def main():
    N = int(input())
    if N == 1:print(1);exit();
    x = [None] * N
    y = [None] * N
    for i in range(N):
        x[i], y[i] = map(int, input().split())
    
    diffx = []
    diffy = []
    nums = []
    for i in range(N-1):
        for j in range(i+1,N):
            tmp = (x[j]-x[i],y[j]-y[i])
            if tmp[0] in diffx and tmp[1] in diffy:
                nums[diffx.index(tmp[0])] += 1
            else:
                diffx.append(tmp[0])
                diffy.append(tmp[1])
                nums.append(1)
    print(N-max(nums))

if __name__ == "__main__":
    main()