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:
import sys
input = sys.stdin.readline
from collections import defaultdict


def read():
    N = int(input().strip())
    XY = []
    for i in range(N):
        x, y = map(int, input().strip().split())
        XY.append((x, y))
    return N, XY


def solve(N, XY):
    min_cost = 1000000
    for j in range(N):
        for i in range(N):
            if i == j:
                continue
            rdict = defaultdict(list)
            x0, y0 = XY[i]
            x1, y1 = XY[j]
            p, q = abs(x1-x0), abs(y1-y0)
            for k in range(N):
                x, y = XY[k]
                rdict[q * x - p * y].append((x, y))
            cost = 0
            for v in rdict.values():
                vs = list(sorted(v))
                x0, y0 = vs[0]
                for x1, y1 in vs:
                    if abs(x1 - x0) != p or abs(y1 - y0) != q:
                        cost += 1
                    x0, y0 = x1, y1
            min_cost = min(min_cost, cost)
    return min_cost


if __name__ == '__main__':
    inputs = read()
    print(solve(*inputs))

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from collections import defaultdict


def read():
    N = int(input().strip())
    XY = []
    for i in range(N):
        x, y = map(int, input().strip().split())
        XY.append((x, y))
    return N, XY


def solve(N, XY):
    min_cost = 1000000
    for j in range(N):
        for i in range(j):
            rdict = defaultdict(list)
            x0, y0 = XY[i]
            x1, y1 = XY[j]
            p, q = abs(x1-x0), abs(y1-y0)
            for k in range(N):
                x, y = XY[k]
                rdict[q * x - p * y].append((x, y))
            cost = 0
            for v in rdict.values():
                vs = list(sorted(v))
                x0, y0 = vs[0]
                for x1, y1 in vs:
                    if abs(x1 - x0) != p or abs(y1 - y0) != q:
                        cost += 1
                    x0, y0 = x1, y1
            min_cost = min(min_cost, cost)
    return min_cost


if __name__ == '__main__':
    inputs = read()
    print(solve(*inputs))

Submission status: Wrong Answer

Solution code:
N = int(input())
graph = []
for _ in range(N):
    x, y = map(int, input().split())
    graph.append([x, y])
ans = float('inf')
for i in range(N):
    for j in range(N):
        if i == j:
            continue
        p = graph[i][0] - graph[j][0]
        q = graph[i][1] - graph[j][1]
        vec_cnt = 0
        for k in range(N):
            for l in range(N):
                if p == graph[k][0] - graph[l][0] and q == graph[k][1] - graph[l][1]:
                    vec_cnt += 1
        ans = min(ans, N - vec_cnt)
print(ans)

Submission status: Wrong Answer

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

if N <= 2:
    print(1)
    exit()
ans = float('inf')
for i in range(N - 2):
    x1, y1 = balls[i]
    ball_flags = [False] * N
    ball_flags[i] = True
    tmp_ans = 0
    for j in range(i + 1, N - 1):
        x2, y2 = balls[j]
        ball_flags[j] = True
        while not all(ball_flags):
            tmp_ans += 1
            tmp_x1, tmp_y1 = float('inf'), float('inf')
            tmp_x2, tmp_y2 = float('inf'), float('inf')
            for k in range(N):
                if ball_flags[k]:
                    continue
                x, y = balls[k]
                if (y - y1) * (x2 - x1) == (y2 - y1) * (x - x1):
                    ball_flags[k] = True
                else:
                    if tmp_x1 == float('inf'):
                        tmp_x1, tmp_y1 = x, y
                        idx1 = k
                    if tmp_x2 == float('inf'):
                        tmp_x2, tmp_y2 = x, y
                        idx2 = k
            if all(ball_flags):
                break
            elif sum(ball_flags) == N - 1:
                tmp_ans += 1
                break
            else:
                x1, x2 = tmp_x1, tmp_x2
                ball_flags[idx1] = True
                y1, y2 = tmp_y1, tmp_y2
                ball_flags[idx2] = True
        ans = min(tmp_ans, ans)
print(ans)

Submission status: Wrong Answer

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

if N <= 2:
    print(1)
    exit()
ans = float('inf')
for i in range(N - 2):
    x1, y1 = balls[i]
    ball_flags = [False] * N
    ball_flags[i] = True
    tmp_ans = 0
    for j in range(i + 1, N - 1):
        x2, y2 = balls[j]
        ball_flags[j] = True
        while not all(ball_flags):
            tmp_ans += 1
            tmp_x1, tmp_y1 = float('inf'), float('inf')
            tmp_x2, tmp_y2 = float('inf'), float('inf')
            for k in range(N):
                if ball_flags[k]:
                    continue
                x, y = balls[k]
                if (y - y1) * (x2 - x1) == (y2 - y1) * (x - x1):
                    ball_flags[k] = True
                else:
                    if tmp_x1 == float('inf'):
                        tmp_x1, tmp_y1 = x, y
                    if tmp_x2 == float('inf'):
                        tmp_x2, tmp_y2 = x, y
            if sum(ball_flags) == N - 1:
                tmp_ans += 1
            else:
                x1, x2 = tmp_x1, tmp_x2
                y1, y2 = tmp_y1, tmp_y2
        ans = min(tmp_ans, ans)
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter

n=int(input())
if n==1:
    print(1)
    exit()

l=[list(map(int,input().split())) for i in range(n)]
pq_0=[]
pq_1=[]

l=sorted(l,key=lambda x:x[0])
for i in range(n-1):
    pq_0.append(str(l[i+1][0]-l[i][0])+" "+str(l[i+1][1]-l[i][1]))
c_0=Counter(pq_0)
p_0,q_0=c_0.most_common()[0][0].split(" ")
p_0=int(p_0)
q_0=int(q_0)
num_0=c_0.most_common()[0][1]

l=sorted(l,key=lambda x:x[1])
for i in range(n-1):
    pq_1.append(str(l[i+1][0]-l[i][0])+" "+str(l[i+1][1]-l[i][1]))
c_1=Counter(pq_1)
p_1,q_1=c_1.most_common()[0][0].split(" ")
p_1=int(p_1)
q_1=int(q_1)
num_1=c_1.most_common()[0][1]

if num_0>=num_1:
    p=p_0
    q=q_0
    l=sorted(l,key=lambda x:x[0])
else:
    p=p_0
    q=q_0
    l=sorted(l,key=lambda x:x[1])

cnt=0
for i in range(n):
    if i==0:
        cnt+=1
    else:
        if not(l[i][0]-p==l[i-1][0] and l[i][1]-q==l[i-1][1]):
            cnt+=1
print(cnt)

Submission status: Wrong Answer

Solution code:
n = int(input())
balls = []
diffs = [[None] * n for _ in range(n)]
for _ in range(n):
    x, y = [int(i) - 1 for i in input().split()]
    balls.append((x, y))

cands = set()

# 各ボールの差分を計算する
for i in range(n - 1):
    for j in range(i + 1, n):
        ax, ay = balls[i]
        bx, by = balls[j]
        diffs[i][j] = (bx - ax, by - ay)
        if bx - ax != 0 or by - ay != 0:  # p≠0 または q≠0
            cands.add((bx - ax, by - ay))

_max = 0

for cand in cands:
    tmp = 0
    for i in range(n):
        if cand in [diffs[k][i] for k in range(n)]:
            tmp += 1
    _max = max(_max, tmp)

print(n - _max)

Submission status: Wrong Answer

Solution code:
n = int(input())
balls = []
diffs = [[None] * n for _ in range(n)]
for _ in range(n):
    x, y = [int(i) - 1 for i in input().split()]
    balls.append((x, y))

cands = set()

# 各ボールの差分を計算する
for i in range(n - 1):
    for j in range(i + 1, n):
        ax, ay = balls[i]
        bx, by = balls[j]
        diffs[i][j] = (bx - ax, by - ay)
        if bx - ax != 0 or by - ay != 0:  # p≠0 または q≠0
            cands.add((bx - ax, by - ay))

_max = 0

for cand in cands:
    tmp = 0
    for i in range(n):
        if cand in diffs[i]:
            tmp += 1
    _max = max(_max, tmp)

print(n - _max)

Submission status: Wrong Answer

Solution code:
n = int(input())
balls = []
diffs = [[None] * n for _ in range(n)]
for _ in range(n):
    x, y = [int(i) - 1 for i in input().split()]
    balls.append((x, y))

cands = set()

# 各ボールの差分を計算する
for i in range(n - 1):
    for j in range(i + 1, n):
        ax, ay = balls[i]
        bx, by = balls[j]
        diffs[i][j] = (bx - ax, by - ay)
        cands.add((bx - ax, by - ay))

_max = 0

for cand in cands:
    tmp = 0
    for i in range(n):
        if cand in diffs[i]:
            tmp += 1
    _max = max(_max, tmp)

print(n - _max)

Submission status: Wrong Answer

Solution code:
from decimal import Decimal

N = int(input())

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

cnt ={}

for i in range(N):
    xi = xy[i][0]
    yi = xy[i][1]

    for j in range(i+1,N):
        xj = xy[j][0]
        yj = xy[j][1]

        x_dif =xi-xj
        y_dif = yi-yj
        if x_dif<0:
            x_dif = -x_dif
            y_dif = -y_dif

        if (x_dif,y_dif)  in cnt.keys():
            cnt[x_dif,y_dif] += 1
        else:
            cnt[x_dif, y_dif] =1

if N == 1:
    print(1)
else: print(N-max(cnt.values()))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
n=int(input())
c=[]
for _ in range(n): c.append(list(map(int,input().split())))
dic=defaultdict(int)
for i in range(0,n-1):
    for j in range(i+1,n):
        if c[i][0]>=c[j][0]: temp=(c[i][0]-c[j][0],c[i][1]-c[j][1])
        else: temp=(c[j][0]-c[i][0],c[j][1]-c[i][1])
        dic[temp]+=1
if dict(dic): print(n-max(dic.values()))
else: print(1)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
n=int(input())
c=[]
for _ in range(n): c.append(list(map(int,input().split())))
dic=defaultdict(int)
for i in range(0,n-1):
    for j in range(i+1,n):
        if c[i][0]>=c[j][0]: temp=(c[i][0]-c[j][0],c[i][1]-c[j][1])
        else: temp=(c[j][0]-c[i][0],c[j][1]-c[i][1])
        dic[temp]+=1
if dict(dic):
    temp=max(dic.values())
    if temp==1: print(n)
    else: print(n-temp)
else: print(1)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

n=int(input())
if n==1:
    print(1)
    exit()
c=[]
for _ in range(n): c.append(list(map(int,input().split())))
dic=defaultdict(int)
for i in range(0,n-1):
    for j in range(i+1,n):
        if c[i][0]>=c[j][0]: temp=(c[i][0]-c[j][0],c[i][1]-c[j][1])
        else: temp=(c[j][0]-c[i][0],c[j][1]-c[i][1])
        dic[temp]+=1
print(n-max(dic.values()))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

n=int(input())
if n==1:
    print(1)
    exit()
c=[]
for _ in range(n): c.append(list(map(int,input().split())))
dic=defaultdict(int)
for i in range(0,n-1):
    for j in range(i+1,n):
        if c[i][0]>=c[j][0]: temp=(c[i][0]-c[j][0],c[i][1]-c[j][1])
        else: temp=(c[j][0]-c[i][0],c[j][1]-c[j][1])
        dic[temp]+=1
print(n-max(dic.values()))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

n=int(input())
if n==1:
    print(1)
    exit()
c=[]
for _ in range(n): c.append(list(map(int,input().split())))
dic=defaultdict(int)
for i in range(0,n-1):
    for j in range(i+1,n):
        temp=(abs(c[i][0]-c[j][0]),abs(c[i][1]-c[j][1]))
        temp=(c[i][0]-c[j][0],c[i][1]-c[j][1])
        dic[temp]+=1
print(n-max(dic.values()))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

n=int(input())
if n==1:
    print(1)
    exit()
c=[]
for _ in range(n): c.append(list(map(int,input().split())))
dic=defaultdict(int)
for i in range(0,n-1):
    for j in range(i+1,n):
        temp=(abs(c[i][0]-c[j][0]),abs(c[i][1]-c[j][1]))
        if c[i][0]>=c[j][0]: temp=(c[i][0]-c[j][0],c[i][1]-c[j][1])
        else: temp=(c[j][0]-c[i][0],c[j][1]-c[i][1])
        dic[temp]+=1
print(n-max(dic.values()))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

n=int(input())
if n==1:
    print(1)
    exit()
c=[]
for _ in range(n): c.append(list(map(int,input().split())))
dic=defaultdict(int)
for i in range(0,n-1):
    for j in range(i+1,n):
        temp=(abs(c[i][0]-c[j][0]),abs(c[i][1]-c[j][1]))
        dic[temp]+=1
print(n-max(dic.values()))

Submission status: Wrong Answer

Solution code:
# # Make IO faster
# import sys
# input = sys.stdin.readline

# # get single (or) multiple str
# X = input()

# # get single int
# N = int(input())
# # get multiple int (e.g., 2)
# X, Y = map(int, input().split())
# # get multiple int (e.g., 2) for N lines
# XY = [list(map(int, input().split())) for _ in range(N)]

# from IPython import embed; embed(); exit();

# 全部入り
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
import numpy as np
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()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
coords = []
for i in range(N):
    x, y = MAP()
    coords.append((x, y))

dic = defaultdict(int)
pq_pairs = []
for i in range(N):
    for j in range(N):
        if i >= j: continue
        p = coords[i][0] - coords[j][0]
        q = coords[i][1] - coords[j][1]
        if p < 0:
            p = -p
            q = -q
        dic[(p, q)] += 1

ans = 0
for k, v in dic.items():
    if v > ans:
        ans = v
print(N - ans)

Submission status: Wrong Answer

Solution code:
ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
import collections
import math
import itertools
import heapq as hq
n = ni()
xy = []
for i in range(n):
    xy.append(tma())
co = collections.Counter()

for i in range(n):
    for j in range(n):
        if i==j:
            continue
        x1,y1 = xy[i]
        x2,y2 = xy[j]
        co[(x2-x1,y2-y1)] +=1

ans = 10**9
for num in co.values():
    ans = min(ans,n-num)
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import combinations
from collections import defaultdict


def main():
    N = int(input())
    points = [list(map(int, input().split())) for _ in range(N)]
    ans = N
    for i, j in combinations(range(N), 2):
        p1, p2 = points[i], points[j]
        if p1 == p2:
            continue
        base_x, base_y = min(p1[0], p2[0]), min(p1[1], p2[1])
        dx, dy = p1[0] - p2[0], p1[1] - p2[1]
        counter = defaultdict(int)
        for point in points:
            x, y = point
            if dx == 0 and dy != 0:
                y = (y - base_y) % abs(dy)
                counter[(x, y)] += 1
            elif dx != 0 and dy == 0:
                x = (x - base_x) % abs(dx)
                counter[(x, y)] += 1
            if dx != 0 and dy != 0:
                intercept = x * dy - y * dx
                x = (x - base_x) % abs(dx)
                y = (y - base_y) % abs(dy)
                counter[(intercept, x, y)] += 1
        cost = len(counter.keys())
        ans = min(ans, cost)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import itertools

def main():
    N = int(input())
    z = []
    ans = 51
    for i in range(N):
        z.append(tuple(map(int, input().split())))
    z.sort(key=lambda x: x[0], reverse=True)
    if len(z) == 1:
        print(1)
        return
    for i, j in itertools.combinations(range(N), 2):
        p = z[i][0] - z[j][0]
        q = z[i][1] - z[j][1]
        ans = min(ans, solve(N, z, p, q))
    print(ans)

def solve(N, z, p, q):
    if p < 0:
        p, q = -p, -q
    passlist = set()
    cnt = 0
    for i in range(N):
        if z[i] in passlist:
            continue
        x, y = z[i][0], z[i][1]
        for j in range(N):
            s, t = x-p, y-q
            if (s, t) not in z:
                cnt += 1
                break
            passlist.add((s, t))
            x, y = s, t
    return cnt

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import itertools

def main():
    N = int(input())
    z = []
    ans = 51
    for i in range(N):
        z.append(tuple(map(int, input().split())))
    z.sort(key=lambda x: x[0], reverse=True)
    for i, j in itertools.combinations(range(N), 2):
        p = z[i][0] - z[j][0]
        q = z[i][1] - z[j][1]
        ans = min(ans, solve(N, z, p, q))
    print(ans)

def solve(N, z, p, q):
    if p < 0:
        p, q = -p, -q
    passlist = set()
    cnt = 0
    for i in range(N):
        if z[i] in passlist:
            continue
        x, y = z[i][0], z[i][1]
        for j in range(N):
            s, t = x-p, y-q
            if (s, t) not in z:
                cnt += 1
                break
            passlist.add((s, t))
            x, y = s, t
    return cnt

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import itertools

def main():
    N = int(input())
    z = []
    ans = 51
    for i in range(N):
        z.append(tuple(map(int, input().split())))
    z.sort(key=lambda x: x[0])
    for i, j in itertools.combinations(range(N), 2):
        p = z[i][0] - z[j][0]
        q = z[i][1] - z[j][1]
        ans = min(ans, solve(N, z, p, q))
    print(ans)

def solve(N, z, p, q):
    if p < 0:
        p, q = -p, -q
    passlist = set()
    cnt = 0
    for i in range(N):
        if z[i] in passlist:
            continue
        x, y = z[i][0], z[i][1]
        for j in range(N):
            s, t = x-p, y-q
            if (s, t) not in z:
                cnt += 1
                break
            passlist.add((s, t))
            x, y = s, t
    return cnt

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def main():
    import sys

    def input(): return sys.stdin.readline().rstrip()

    n = int(input())
    x, y = [0]*n, [0]*n
    for i in range(n):
        x[i], y[i] = map(int, input().split())
    cnt = 1
    for i in range(n):
        for j in range(i, n):
            if (i == j): continue
            if abs(x[i]-x[j]) > 0 and abs(y[i]-y[j]) > 0:
                x[i+1], x[j] = x[j], x[i+1]
                y[i+1], y[j] = y[j], y[i+1]
                break
        else:
            if i != n-1:
                cnt+= 1
    print(cnt)
            

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


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


def main():
    from itertools import combinations
    n = int(readline())
    mat = [list(map(int, readline().split())) for _ in range(n)]

    if n == 1:
        return print(1)

    ans = INF
    for com in combinations(range(n), r=2):
        first, second = com
        dx = abs(mat[first][0] - mat[second][0])
        dy = abs(mat[first][1] - mat[second][1])
        uf = UnionFind(n)
        for i in range(n):
            cx, cy = mat[i]
            for j in range(n):
                nx, ny = mat[j]
                if abs(cx - nx) == dx and abs(cy - ny) == dy:
                    uf.union(i, j)
        ans = min(ans, uf.group_count())

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


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


def main():
    from itertools import combinations
    n = int(readline())
    mat = [list(map(int, readline().split())) for _ in range(n)]

    if n == 1:
        return print(1)

    ans = INF
    for com in combinations(range(n), r=2):
        first, second = com
        dx = abs(mat[first][0] - mat[second][0])
        dy = abs(mat[first][1] - mat[second][1])
        uf = UnionFind(n)
        for i in range(n):
            cx, cy = mat[i]
            for j in range(n):
                nx, ny = mat[j]
                if abs(cx - nx) == dx and abs(cy - ny) == dy:
                    uf.union(i, j)
        ans = min(ans, n - uf.group_count())

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
(n,), *z = [[*map(int, o.split())] for o in open(0)]
if n == 1:
    print(1)
    exit()
from itertools import*
from collections import*
print(n - Counter((z[i][0] - z[j][0], z[i][1] - z[j][1]) for i, j in combinations(range(n), 2)).most_common()[0][1])

Submission status: Wrong Answer

Solution code:
(n,), *z = [[*map(int, o.split())] for o in open(0)]
if n == 1:
    print(1)
    exit()
from itertools import*
from collections import*
print(n - Counter((abs(z[i][0] - z[j][0]), abs(z[i][1] - z[j][1])) for i, j in combinations(range(n), 2)).most_common()[0][1])

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import math 

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

    ans = len(XY)
    
    for i in range(len(XY)):
        for j in range(i+1,len(XY)):
            p,q = XY[i][0] - XY[j][0], XY[i][1] - XY[j][1]
            g = math.gcd(p,q)
            # print(p,q)
            if p != 0 and q != 0:
                p,q = p//g,q//g
            else:
                if p == 0:
                    p,q = 0,1
                elif q == 0:
                    p,q = 1,0

            ch = [0] * len(XY)
            c = 0
            for i in range(len(XY)):
                a,b = XY[i][0],XY[i][1]
                if ch[i] == 1:
                    continue
                c += 1
                for j in range(i+1,len(XY)):
                    x,y = XY[j][0],XY[j][1]
                    if p != 0 and q != 0:
                        if (a-x)*q == (b-y)*q:
                            ch[j] = 1
                    else:
                        if ((a-x) == 0 and p == 0) or ((b-y) and (p==0)):
                            ch[j] = 1

            # print(c)
            ans = min(ans,c)

    print(ans)
            

main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import math 

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

    ans = len(XY)
    
    for i in range(len(XY)):
        for j in range(i+1,len(XY)):
            p,q = XY[i][0] - XY[j][0], XY[i][1] - XY[j][1]
            g = math.gcd(p,q)
            # print(p,q)
            if p != 0 and q != 0:
                p,q = p//g,q//g
            else:
                if p == 0:
                    p,q = 0,1
                elif q == 0:
                    p,q = 1,0

            ch = [0] * len(XY)
            c = 0
            for i in range(len(XY)):
                a,b = XY[i][0],XY[i][1]
                if ch[i] == 1:
                    continue
                c += 1
                for j in range(i+1,len(XY)):
                    x,y = XY[j][0],XY[j][1]
                    if p != 0 and q != 0:
                        if (a-x)*q == (b-y)*q:
                            ch[j] = 1
                    else:
                        if ((a-x) == 0 and p == 0) or ((b-y) and (p==0)):
                            ch[j] = 1

            # print(c)
            ans = min(ans,c)

    print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import math 

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

    ans = len(XY)
    
    for i in range(len(XY)):
        for j in range(i+1,len(XY)):
            p,q = abs(XY[i][0] - XY[j][0]), abs(XY[i][1] - XY[j][1])
            g = math.gcd(p,q)
            # print(p,q)
            if p != 0 and q != 0:
                p,q = p//g,q//g
            else:
                if p == 0:
                    p,q = 0,1
                elif q == 0:
                    p,q = 1,0

            ch = [0] * len(XY)
            c = 0
            for i in range(len(XY)):
                a,b = XY[i][0],XY[i][1]
                if ch[i] == 1:
                    continue
                c += 1
                for j in range(i+1,len(XY)):
                    x,y = XY[j][0],XY[j][1]
                    if p != 0 and q != 0:
                        if (a-x)*q == (b-y)*q:
                            ch[j] = 1
                    else:
                        if ((a-x) == 0 and p == 0) or ((b-y) and (p==0)):
                            ch[j] = 1

            # print(c)
            ans = min(ans,c)

    print(ans)
            

main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import math 

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

    ans = len(XY)
    
    for i in range(len(XY)):
        for j in range(i+1,len(XY)):
            p,q = abs(XY[i][0] - XY[j][0]), abs(XY[i][1] - XY[j][1])
            g = math.gcd(p,q)
            # print(p,q)
            if p != 0 and q != 0:
                p,q = p//g,q//g
            else:
                if p == 0:
                    p,q = 0,1
                elif q == 0:
                    p,q = 1,0

            ch = [0] * len(XY)
            c = 0
            for i in range(len(XY)):
                a,b = XY[i][0],XY[i][1]
                if ch[i] == 1:
                    continue
                c += 1
                for j in range(i+1,len(XY)):
                    x,y = XY[j][0],XY[j][1]
                    if p != 0 and q != 0:
                        if (a-x)*q == (b-y)*q:
                            ch[j] = 1
                    else:
                        if ((a-x) == 0 and p == 0) or ((b-y) and (p==0)):
                            ch[j] = 1

            # print(c)
            ans = min(ans,c)

    print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
INF = int(1e13)
A = [list(map(int, input().split())) for _ in range(N)]
X = [[[0, 0] for __ in range(N)] for _ in range(N)]
for i in range(N):
  for j in range(N):
    X[i][j] = [A[i][0]-A[j][0], A[i][1] - A[j][1]]
for i in range(N):
  X[i][i][0], X[i][i][1] = INF + 2*i, INF + 2*i+1
D = {}
for i in range(N):
  for j in range(N):
    if X[i][j][0]*(10*INF)+X[i][j][1] in D:
      D[X[i][j][0]*(10*INF)+X[i][j][1]] += 1
    else:
      D[X[i][j][0]*(10*INF)+X[i][j][1]] = 1
print(N-max(D[i] for i in D))

Submission status: Wrong Answer

Solution code:
N=int(input())
l=[]
l_a=[]
if N==1:
   print(1)
   exit()
for i in range(N):
   l.append(list(map(int,input().split())))
for i in range(N):
   for j in range(i+1,N):
      tmp=str(abs(l[j][0]-l[i][0]))+" "+str(abs(l[j][1]-l[i][1]))
      l_a.append(tmp)
import collections
l_a=collections.Counter(l_a).most_common()
print(N-l_a[0][1])

Submission status: Wrong Answer

Solution code:
N=int(input())
l=[]
l_a=[]
if N==1:
   print(1)
   exit()
for i in range(N):
   l.append(list(map(int,input().split())))
for i in range(N):
   for j in range(i+1,N):
      tmp=str(l[j][0]-l[i][0])+" "+str(l[j][1]-l[i][1])
      l_a.append(tmp)
import collections
l_a=collections.Counter(l_a).most_common()
print(N-l_a[0][1])