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:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AtoZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)


#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1:
    arr.append([temp, 1])
  if arr==[]:
    arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  divisors.sort()
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n:
    return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############
N = I()
data = ILL(N)

kouho = []
for i in range(N):
  for j in range(i+1,N):
    a,b = data[i]
    c,d = data[j]
    kouho.append((c-a,d-b))
MIN = INF
for x,y in kouho:
  ans = N
  for i in range(N):
    for j in range(i+1,N):
      a,b = data[i]
      c,d = data[j]
      if (a+x == c and b+y == d) or (c+x == a and d+y == b):
        ans -= 1
  MIN = min(MIN,ans)
print(MIN)

Submission status: Wrong Answer

Solution code:
n = int(input())
s = [list(map(int, input().split())) for _ in range(n)]
for i in range(n):
    for j in range(2):
        s[i][j] += pow(10, 9)
d = {}
for i in range(n):
    for j in range(n):
        if not i == j:
            m = abs(s[i][0] - s[j][0]) + abs(s[i][1] - s[j][1]) * pow(10, 10)
            if not m in d:
                d[m] = 1
            else:
                d[m] += 1
m = 0
for i in d:
    m = max(d[i] // 2, m)
ans = n - m
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter
n=int(input())
if n==1:
  print(1)
  exit()
xy=[tuple(map(int,input().split())) for _ in range(n)]

print(xy)
xy.sort()
print(xy)
l=[]
for i in range(n-1):
  for j in range(i+1,n):
    l.append((xy[j][0]-xy[i][0],xy[j][1]-xy[i][1]))

#most_common(): (要素、出現回数)という形のタプルを出現回数順に並べたリストを返す
print(n-Counter(l).most_common()[0][1])

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

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

for i in range(n):
    for j in range(n):
        data[x[j] - x[i], y[j] - y[i]] += 1

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

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

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

for i in range(n):
    for j in range(i + 1, n):
        data_x[x[j] - x[i]] += 1
        data_y[y[j] - y[i]] += 1
data_x = sorted(data_x.items(), key = lambda x: x[1])
data_y = sorted(data_y.items(), key = lambda x: x[1])
ans = 10 ** 5
for i in range(len(data_x)):
    for j in range(len(data_y)):
        p = data_x[i][0]
        q = data_y[j][0]
        cnt = 0
        for k in range(n):
            if k == 0:
                cnt += 1
            elif pre_x + p != x[k] or pre_y + q != y[k]:
                cnt += 1
            pre_x = x[k]
            pre_y = y[k]
        ans = min(ans, cnt)

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
N = int(sys.stdin.readline().rstrip())

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

zahyo = []
for _ in range(N):
    x, y = map(int, sys.stdin.readline().rstrip().split())
    zahyo.append((x, y))
zahyo.sort()

p_q = set()
for i in range(N - 1):
    for j in range(i + 1, N):
        p = zahyo[j][0] - zahyo[i][0]
        q = zahyo[j][1] - zahyo[i][1]
        p_q.add((p, q))

ans = float("inf")
for p, q in p_q:
    used = set()
    ans_tmp = 0
    for i in range(N - 1):
        if i not in used:
            x_base = zahyo[i][0]
            y_base = zahyo[i][1]
            ans_tmp += 1
            for j, (x, y) in enumerate(zahyo[i + 1:], 1):
                if x - x_base == p and y - y_base == q:
                    used.add(i + j)
                    x_base = x
                    y_base = y
    ans = min(ans_tmp, ans)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
N = int(sys.stdin.readline().rstrip())

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

zahyo = []
for _ in range(N):
    x, y = map(int, sys.stdin.readline().rstrip().split())
    zahyo.append((x, y))
zahyo.sort()

p_q = set()
for i in range(N - 1):
    for j in range(i + 1, N):
        p = zahyo[j][0] - zahyo[i][0]
        q = zahyo[j][1] - zahyo[i][1]
        p_q.add((p, q))

ans = float("inf")
for p, q in p_q:
    used = set()
    ans_tmp = 0
    for i in range(N - 1):
        if i not in used:
            x_base = zahyo[i][0]
            y_base = zahyo[i][1]
            ans_tmp += 1
            for j, (x, y) in enumerate(zahyo[i + 1:], 1):
                if p != 0 and q != 0:
                    if x - x_base == p and y - y_base == q:
                        used.add(i + j)
                        x_base = x
                        y_base = y
    ans = min(ans_tmp, ans)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
N = int(sys.stdin.readline().rstrip())

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

zahyo = []
for _ in range(N):
    x, y = map(int, sys.stdin.readline().rstrip().split())
    zahyo.append((x, y))

p_q = set()
for i in range(N - 1):
    for j in range(i + 1, N):
        p = zahyo[j][0] - zahyo[i][0]
        q = zahyo[j][1] - zahyo[i][1]
        p_q.add((p, q))

ans = float("inf")
for p, q in p_q:
    used = set()
    ans_tmp = 0
    for i in range(N - 1):
        if i not in used:
            x_base = zahyo[i][0]
            y_base = zahyo[i][1]
            ans_tmp += 1
            for j, (x, y) in enumerate(zahyo[i + 1:], 1):
                if p != 0 and q != 0:
                    if (x - x_base) % p == 0 and (y - y_base) % q == 0 and (
                            x - x_base) // p == (y - y_base) // q:
                        used.add(i + j)
                elif p == 0:
                    if (y - y_base) % q == 0 and x == x_base:
                        used.add(i + j)
                elif q == 0:
                    if (x - x_base) % p == 0 and y == y_base:
                        used.add(i + j)
    ans = min(ans_tmp, ans)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
N = int(sys.stdin.readline().rstrip())

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

zahyo = []
for _ in range(N):
    x, y = map(int, sys.stdin.readline().rstrip().split())
    zahyo.append((x, y))

import decimal

katamuki = set()
for i in range(N - 1):
    for j in range(i + 1, N):
        if zahyo[j][0] - zahyo[i][0] != 0:
            katamuki.add(
                decimal.Decimal(zahyo[j][1] - zahyo[i][1]) /
                decimal.Decimal(zahyo[j][0] - zahyo[i][0]))
        else:
            katamuki.add("reigai")

ans = float("inf")
for k in katamuki:
    used = set()
    ans_tmp = 0
    for i in range(N - 1):
        if i not in used:
            b = zahyo[i][0]
            c = zahyo[i][1]
            ans_tmp += 1
            for j, (x, y) in enumerate(zahyo[i + 1:], 1):
                if k != "reigai":
                    if y == k * (x - b) + c:
                        used.add(i + j)
                else:
                    if x == b:
                        used.add(i + j)
    ans = min(ans_tmp, ans)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
N = int(sys.stdin.readline().rstrip())

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

zahyo = []
for _ in range(N):
    x, y = map(int, sys.stdin.readline().rstrip().split())
    zahyo.append((x, y))

katamuki = set()
for i in range(N - 1):
    for j in range(i + 1, N):
        if zahyo[j][0] - zahyo[i][0] != 0:
            katamuki.add((zahyo[j][1] - zahyo[i][1]) / (zahyo[j][0] - zahyo[i][0]))
        else:
            katamuki.add("reigai")
    
ans = float("inf")
for k in katamuki:
    used = set()
    ans_tmp = 0
    for i in range(N - 1):
        if i not in used:
            b = zahyo[i][0]
            c = zahyo[i][1]
            ans_tmp += 1
            for j, (x, y) in enumerate(zahyo[i + 1:], 1):
                if k != "reigai":
                    if y == k * (x - b) + c:
                        used.add(i + j)
                else:
                    if x == b:
                        used.add(i + j)
    ans = min(ans_tmp, ans)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
N = int(sys.stdin.readline().rstrip())

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

zahyo = []
for _ in range(N):
    x, y = map(int, sys.stdin.readline().rstrip().split())
    zahyo.append((x, y))

katamuki = set()
for i in range(N - 1):
    for j in range(i + 1, N):
        if zahyo[j][0] - zahyo[i][0] != 0:
            katamuki.add((zahyo[j][1] - zahyo[i][1]) / (zahyo[j][0] - zahyo[i][0]))
        else:
            katamuki.add("reigai")
    
ans = float("inf")
for k in katamuki:
    used = set()
    group = []
    for i in range(N - 1):
        if i not in used:
            b = zahyo[i][0]
            c = zahyo[i][1]
            tmp = [i]
            for j, (x, y) in enumerate(zahyo[i + 1:], 1):
                if k != "reigai":
                    if y == k * (x - b) + c:
                        used.add(i + j)
                        tmp.append(i + j)
                else:
                    if x == b:
                        used.add(i + j)
                        tmp.append(i + j)
            group.append(tmp)
    ans = min(len(group), ans)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
N = int(sys.stdin.readline().rstrip())

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

zahyo = []
for _ in range(N):
    x, y = map(int, sys.stdin.readline().rstrip().split())
    zahyo.append((x, y))
zahyo.sort()

p_q = []
for i in range(N - 1):
    for j in range(i + 1, N):
        p = zahyo[j][0] - zahyo[i][0]
        q = zahyo[j][1] - zahyo[i][1]
        p_q.append((p, q, i))

ans = float("inf")
for p, q, i in p_q:
    ans_tmp = 1
    for j in range(i + 1, N - 1):
        if zahyo[j][0] - zahyo[i][0] == p and zahyo[j][1] - zahyo[i][1] == q:
            i = j
        else:
            ans_tmp += 1
    for j in range(i)[::-1]:
        if zahyo[i][0] - zahyo[j][0] == p and zahyo[i][1] - zahyo[j][1] == q:
            i = j
        else:
            ans_tmp += 1
    ans = min(ans_tmp, ans)
print(ans)

Submission status: Wrong Answer

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

dic = {}
tmp = 0

for i in range(N):
  for j in range(N):
    if i == j:
      continue
    p = XYs[j][0] - XYs[i][0]
    q = XYs[j][1] - XYs[i][1]

    if "{}_{}".format(p,q) not in dic:
      dic["{}_{}".format(p,q)] = 1
    else:
      dic["{}_{}".format(p,q)] += 1
      
for k in dic:
  if tmp < dic[k]:
    tmp = dic[k]

print(dic)
print(N-tmp)

Submission status: Wrong Answer

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

dic = {}
tmp = 0

for i in range(N):
  for j in range(i+1,N):
    p = XYs[j][0] - XYs[i][0]
    q = XYs[j][1] - XYs[i][1]
    if p < 0:
      p = -p
      q = -q
    if "{}_{}".format(p,q) not in dic:
      dic["{}_{}".format(p,q)] = 1
    else:
      dic["{}_{}".format(p,q)] += 1
      
for k in dic:
  if tmp < dic[k]:
    tmp = dic[k]
    
print(N-tmp)

Submission status: Wrong Answer

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

buf.sort()

ans = 1e9
for i in range(n):
    for j in range(i+1,n):
        p,q = buf[j][0]-buf[i][0],buf[j][1]-buf[i][1]

        ind = 0
        used = set()
        tcost = 0
        befx = 0
        befy = 0
        flag = False
        while True:
            befx,befy = buf[ind][0],buf[ind][1]
            tcost += 1
            for l in range(n):
                if l not in used:
                    tx,ty = buf[l][0],buf[l][1]
                    if tx-befx == p and ty-befy == q:
                        befx = tx
                        befy = ty
                        used.add(l)
            while True:
                ind += 1
                if ind == n:
                    flag = True
                    break
                if ind in used:
                    continue
                else:
                    break
            if flag:
                break
        if ans > tcost:
            # print(used)
            # print(p,q,tcost)
            ans = tcost

print(ans)

Submission status: Wrong Answer

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

v={}
for i in range(N):
    for j in range(N):
        vect=[x[i][0]-x[j][0],x[i][1]-x[j][1]]
        vs=str(vect[0])+","+str(vect[1])
        if vs in v:
            v[vs]+=1
        else:
            v[vs]=1
v["0,0"]=0
VM=0
for m in v:
    VM=max(VM,v[m]//2)
print(N-VM-1)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import numpy as np
import sys

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

if n == 1:
    print(1)
    sys.exit()

x = xy[xy.argsort(axis=0)[:, 0]]
y = xy[xy.argsort(axis=0)[:, 1]]

x = [list(x) for x in np.diff(x, axis=0)]
y = [list(y) for y in np.diff(y, axis=0)]


memo_x = defaultdict(int)
memo_y = defaultdict(int)

for i, j in zip(x, y):
    memo_x[str(i)] += 1
    memo_y[str(j)] += 1

print(n - max(max(memo_x.values()), max(memo_y.values())))

Submission status: Wrong Answer

Solution code:
import math

n=int(input())

XY=[]

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

v=[]

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

print(v)

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

print(n-c)

Submission status: Wrong Answer

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

ans = 1000
for i in range(n):
    for j in range(n):
        if i == j:
            continue
        temp = 0
        x0, y0 = ball[i]
        x1, y1 = ball[j]
        p, q = x1-x0, y1-y0
        used = [False]*(n)
        for k in range(n):
            if not used[k]:
                temp += 1
                x0, y0 = ball[k]
                used[k] = True

                x, y = x0, y0
                while True:
                    f = 0
                    for l in range(n):
                        if used[l]:
                            continue
                        if x + p == ball[l][0] and y + q == ball[l][1]:
                            used[l] = True
                            x += p
                            y += q
                            f = 1
                    if f == 0:
                        break

                x, y = x0, y0
                while True:
                    f = 0
                    for l in range(n):
                        if used[l]:
                            continue
                        if x - p == ball[l][0] and y - q == ball[l][1]:
                            used[l] = True
                            x -= p
                            y -= q
                            f = 1
                    if f == 0:
                        break

        ans = min(ans, temp)

print(ans)

Submission status: Wrong Answer

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

ans = 1000
for i in range(n):
    for j in range(n):
        if i == j:
            continue
        temp = 0
        x0, y0 = ball[i]
        x1, y1 = ball[j]
        p, q = x1-x0, y1-y0
        used = [False]*(n)
        for k in range(n):
            if not used[k]:
                temp += 1
                x0, y0 = ball[k]
                used[k] = True
                for l in range(n):
                    x1, y1 = ball[l]
                    if p == 0:
                        x = x1 == x0
                    else:
                        x = (x1-x0)%p == 0

                    if q == 0:
                        y = y1 == y0
                    else:
                        y = (y1-y0)%q == 0
                    if x and y and (q*(x1-x0) == p*(y1-y0)):
                        used[l] = True
        ans = min(ans, temp)

print(ans)

Submission status: Wrong Answer

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

ans = 1000
for i in range(n):
    for j in range(i+1, n):
        temp = 0
        x0, y0 = ball[i]
        x1, y1 = ball[j]
        p, q = x1-x0, y1-y0
        used = [False]*(n)
        for k in range(n):
            if not used[k]:
                temp += 1
                x0, y0 = ball[k]
                used[k] = True
                for l in range(n):
                    x1, y1 = ball[l]
                    if p == 0:
                        x = x1 == x0
                    else:
                        x = (x1-x0)%p == 0

                    if q == 0:
                        y = y1 == y0
                    else:
                        y = (y1-y0)%q == 0
                    if x and y and (q*(x1-x0) == p*(y1-y0)):
                        used[l] = True
        ans = min(ans, temp)

print(ans)

Submission status: Wrong Answer

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

ans = 1000
for i in range(n):
    for j in range(i+1, n):
        temp = 0
        x0, y0 = ball[i]
        x1, y1 = ball[j]
        p, q = x1-x0, y1-y0
        used = [False]*(n)
        for k in range(n):
            if not used[k]:
                temp += 1
                x0, y0 = ball[k]
                used[k] = True
                for l in range(n):
                    x1, y1 = ball[l]
                    if p == 0:
                        x = True
                    else:
                        x = (x1-x0)%p == 0

                    if q == 0:
                        y = True
                    else:
                        y = (y1-y0)%q == 0
                    if x and y and (q*(x1-x0) == p*(y1-y0)):
                        used[l] = True
        ans = min(ans, temp)

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
grid = []
for _ in range(n):
    x,y = map(int,input().split())
    grid.append((x,y))
S = set(grid)
ans = float("inf")
for i in range(n-1):
    for j in range(i+1,n):
        cnt = 0
        p = grid[i][0]-grid[j][0]
        q = grid[i][1]-grid[j][1]
        for k in range(n):
            if (grid[k][0]-p,grid[k][1]-q) in S:
                cnt += 1
        else:
            ans = min(n-cnt,ans)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys,os
from collections import defaultdict, deque
from math import ceil, floor
if sys.version_info[1] >= 5:
    from math import gcd
else:
    from fractions import gcd
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in os.environ else lambda *x: 0
def main(given=sys.stdin.readline):
    input = lambda: given().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    MOD = 10**9+7

    
    N = II()
    coordinates = []
    diffs = defaultdict(int)
    for i in range(N):
        coordinates.append(LMIIS())
    for i in range(N):
        x1,y1 = coordinates[i]
        for j in range(i+1,N):
            x2,y2 = coordinates[j]
            diffs[(abs(x1-x2),abs(y1-y2))] += 1
    
    max_diff = ()
    max_count = 0

    for k,v in diffs.items():
        if max_count < v:
            max_count = v
            max_diff = k
    print(N-max_count)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
import collections

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(tin())
mod=1000000007

#+++++

def main():
	n = int(input())
	dd=[]
	for _ in range(n):
		b , c = tin()
		dd.append([b,c])
	#s = input()
	dist_dict=collections.defaultdict(lambda :0)
	for i,(xa, ya) in enumerate(dd):
		for xb, yb in dd:#[i+1:]:
			if xa==xb and ya == yb:
				continue
			dist_dict[str(xa-xb)+'_'+str(ya-yb)]+=1
			dist_dict[str(xb-xa)+'_'+str(yb-ya)]+=1
	rr=0
	for k in dist_dict:
		rr=max(rr,dist_dict[k])
		print(k,dist_dict[k])
	return n-int(rr//2)
		
	
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Wrong Answer

Solution code:
from itertools import combinations
from collections import Counter


def main():
    n = int(input())
    if n == 1:
        print(1)

    XY = [list(map(int, input().split())) for _ in range(n)]
    d = []
    for A, B in combinations(XY, 2):
        x1, y1 = A[0], A[1]
        x2, y2 = B[0], B[1]
        p, q = x2 - x1, y2 - y1
        d.append((p, q))
        d.append((-p, -q))
    # print(d)
    # print(Counter(d))

    C = Counter(d)
    ans = 0
    for v in C.values():
        ans = max(ans, v)
    print(n - ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from itertools import combinations
from collections import Counter

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

    XY = [list(map(int, input().split())) for _ in range(n)]
    d = []
    for A, B in combinations(XY, 2):
        x1, y1 = A[0], A[1]
        x2, y2 = B[0], B[1]
        p, q = x2 - x1, y2 - y1
        d.append((p,q))
    # print(d)
    # print(Counter(d))

    C = Counter(d)
    ans = 0
    for v in C.values():
        ans = max(ans, v)
    print(n-ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from itertools import combinations
from collections import Counter


def main():
    n = int(input())
    if n == 1:
        print(1)

    XY = [list(map(int, input().split())) for _ in range(n)]
    d = []
    for A, B in combinations(XY, 2):
        x1, y1 = A[0], A[1]
        x2, y2 = B[0], B[1]
        p, q = x2 - x1, y2 - y1
        d.append((p, q))
        d.append((-p, -q))

    # print(d)
    # print(Counter(d))

    C = Counter(d)
    ans = 0
    for v in C.values():
        ans = max(ans, v)
    print(n-ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from itertools import combinations
from collections import Counter


def main():
    n = int(input())
    if n == 1:
        print(1)

    XY = [list(map(int, input().split())) for _ in range(n)]
    d = []
    for A, B in combinations(XY, 2):
        x1, y1 = A[0], A[1]
        x2, y2 = B[0], B[1]
        p, q = x2 - x1, y2 - y1
        d.append((p, q))
        d.append((-p, -q))

    # print(d)
    # print(Counter(d))

    C = Counter(d)
    ans = 0
    for v in C.values():
        ans = max(ans, v)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from itertools import combinations
from collections import Counter


def main():
    n = int(input())
    if n == 1:
        print(1)

    XY = [list(map(int, input().split())) for _ in range(n)]
    d = []
    for A, B in combinations(XY, 2):
        x1, y1 = A[0], A[1]
        x2, y2 = B[0], B[1]
        p, q = x2 - x1, y2 - y1
        d.append((p,q))
    # print(d)
    # print(Counter(d))

    C = Counter(d)
    ans = 0
    for v in C.values():
        ans = max(ans, v)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

maxi=0
for i in range(N-1):
  for j in range(i+1,N):
    if (x[j]-x[i],y[j]-y[i]) not in d:
      d[ (x[j]-x[i],y[j]-y[i]) ] =1
      d[ (x[i]-x[j],y[i]-y[j]) ] =1
    else:
      d[ (x[j]-x[i],y[j]-y[i]) ] +=1
      d[ (x[i]-x[j],y[i]-y[j]) ] +=1
#print(d)      

for p in d:
  maxi=max(maxi,d[p])
if maxi==1:
  maxi=0
ans= (N-1-maxi)+1
print(ans)

Submission status: Wrong Answer

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

maxi=0
for i in range(N-1):
  for j in range(i+1,N):
    if (x[j]-x[i],y[j]-y[i]) not in d:
      d[ (x[j]-x[i],y[j]-y[i]) ] =1
    else:
      d[ (x[j]-x[i],y[j]-y[i]) ] +=1

#print(d)
for p in d:
  maxi=max(maxi,d[p])
if maxi==1:
  maxi=0
ans= (N-1-maxi)+1
print(ans)

Submission status: Wrong Answer

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

maxi=0
for i in range(N-1):
  for j in range(i+1,N):
    if (x[j]-x[i],y[j]-y[i]) not in d:
      d[ (x[j]-x[i],y[j]-y[i]) ] =1
    else:
      d[ (x[j]-x[i],y[j]-y[i]) ] +=1

#print(d)
for p in d:
  maxi=max(maxi,d[p])
ans= (N-1-maxi)+1
print(ans)

Submission status: Wrong Answer

Solution code:
import collections
n = int(input())
if n != 1:
    dic = collections.defaultdict(list)
    ls = []
    for i in range(n):
        [x,y] = [int(j) for j in input().split()]
        if x not in ls:
            ls.append(x)
        dic[x].append(y)

    ls.sort()
    for key in dic.keys():
        dic[key].sort()

    diffs = []

    dic_ans = collections.defaultdict(int)
    count = 0

    for i in range(len(ls)):
        xs = ls[i]
        for j in range(len(dic[xs])):
            #同じxの中
            if j != len(dic[xs])-1:
                diff_x = 0
                diff_y = dic[xs][j+1] - dic[xs][j]
            #xが違う場合
            else:
                #最後の1つでない場合
                if i != len(ls)-1:
                    diff_x = ls[i+1] - xs
                    diff_y = dic[ls[i+1]][0] - dic[xs][j]

            if [diff_x,diff_y] in diffs:
                dic_ans[diffs.index([diff_x,diff_y])] += 1
            else:
                diffs.append([diff_x,diff_y])
                dic_ans[len(diffs)-1] += 1
    #最後のやつだけ外す
    dic_ans[diffs.index([diff_x,diff_y])] -= 1
    print(n - max(dic_ans.values()))
    #print(dic_ans)
    #print(diffs)

else:
    print(1)

Submission status: Wrong Answer

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

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

print(n-ans)