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 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import random
input = sys.stdin.readline

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

def main():

	N = int(input())
	#N, K = map(int, input().split(" "))

	xy = []
	for _ in range(N):
		x, y = map(int, input().split(" "))
		xy.append((x,y))

	gess = {}
	xm = 0
	ym = 0

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

	for i, val in enumerate(xy):
		if i == 0:
			x,y = val
			xm = x
			ym = y
			continue
		x, y = val

		p = x - xm
		q = y - ym
		if (p,q) in gess:
			gess[(p, q)] += 1
		else:
			gess[(p, q)] = 1
		xm = x
		ym = y

	p, q = max(gess, key=gess.get)
	nai = gess[(p,q)]

	#########
	xy = sorted(xy, key=lambda x:(x[0]))
	gess1 = {}
	xm = 0
	ym = 0

	for i, val in enumerate(xy):
		if i == 0:
			x,y = val
			xm = x
			ym = y
			continue
		x, y = val

		p = x - xm
		q = y - ym
		if (p,q) in gess1:
			gess1[(p, q)] += 1
		else:
			gess1[(p, q)] = 1
		xm = x
		ym = y

	p, q = max(gess1, key=gess1.get)
	nai1 = gess1[(p,q)]

	#########
	xy = sorted(xy, key=lambda x:(-x[0]))
	gess2 = {}
	xm = 0
	ym = 0

	for i, val in enumerate(xy):
		if i == 0:
			x,y = val
			xm = x
			ym = y
			continue
		x, y = val

		p = x - xm
		q = y - ym
		if (p,q) in gess2:
			gess2[(p, q)] += 1
		else:
			gess2[(p, q)] = 1
		xm = x
		ym = y

	p, q = max(gess2, key=gess2.get)
	nai2 = gess2[(p,q)]

	#########
	xy = sorted(xy, key=lambda x:(x[1]))
	gess3 = {}
	xm = 0
	ym = 0

	for i, val in enumerate(xy):
		if i == 0:
			x,y = val
			xm = x
			ym = y
			continue
		x, y = val

		p = x - xm
		q = y - ym
		if (p,q) in gess3:
			gess3[(p, q)] += 1
		else:
			gess3[(p, q)] = 1
		xm = x
		ym = y

	p, q = max(gess3, key=gess3.get)
	nai3 = gess3[(p,q)]

	#########
	xy = sorted(xy, key=lambda x:(-x[1]))
	gess4 = {}
	xm = 0
	ym = 0

	for i, val in enumerate(xy):
		if i == 0:
			x,y = val
			xm = x
			ym = y
			continue
		x, y = val

		p = x - xm
		q = y - ym
		if (p,q) in gess4:
			gess4[(p, q)] += 1
		else:
			gess4[(p, q)] = 1
		xm = x
		ym = y

	p, q = max(gess4, key=gess4.get)
	nai4 = gess4[(p,q)]

	#########
	xy = sorted(xy, key=lambda x:(x[0],-x[1]))
	gess5 = {}
	xm = 0
	ym = 0

	for i, val in enumerate(xy):
		if i == 0:
			x,y = val
			xm = x
			ym = y
			continue
		x, y = val

		p = x - xm
		q = y - ym
		if (p,q) in gess5:
			gess5[(p, q)] += 1
		else:
			gess5[(p, q)] = 1
		xm = x
		ym = y

	p, q = max(gess5, key=gess5.get)
	nai5 = gess5[(p,q)]

	#########
	random.shuffle(xy)
	gess6 = {}
	xm = 0
	ym = 0

	for i, val in enumerate(xy):
		if i == 0:
			x,y = val
			xm = x
			ym = y
			continue
		x, y = val

		p = x - xm
		q = y - ym
		if (p,q) in gess6:
			gess6[(p, q)] += 1
		else:
			gess6[(p, q)] = 1
		xm = x
		ym = y

	p, q = max(gess6, key=gess6.get)
	nai6 = gess6[(p,q)]

	#########
	random.shuffle(xy)
	gess7 = {}
	xm = 0
	ym = 0

	for i, val in enumerate(xy):
		if i == 0:
			x,y = val
			xm = x
			ym = y
			continue
		x, y = val

		p = x - xm
		q = y - ym
		if (p,q) in gess7:
			gess7[(p, q)] += 1
		else:
			gess7[(p, q)] = 1
		xm = x
		ym = y

	p, q = max(gess7, key=gess7.get)
	nai7 = gess7[(p,q)]
		#########
	xy = sorted(xy, key=lambda x:(-x[1],-x[0]))
	gess8 = {}
	xm = 0
	ym = 0

	for i, val in enumerate(xy):
		if i == 0:
			x,y = val
			xm = x
			ym = y
			continue
		x, y = val

		p = x - xm
		q = y - ym
		if (p,q) in gess8:
			gess8[(p, q)] += 1
		else:
			gess8[(p, q)] = 1
		xm = x
		ym = y

	p, q = max(gess8, key=gess8.get)
	nai8 = gess8[(p,q)]

		#########
	ans = -1

	for _ in range(10000):
		random.shuffle(xy)
		gess9 = {}
		xm = 0
		ym = 0
		for i, val in enumerate(xy):
			if i == 0:
				x,y = val
				xm = x
				ym = y
				continue
			x, y = val

			p = x - xm
			q = y - ym
			if (p,q) in gess9:
				gess9[(p, q)] += 1
			else:
				gess9[(p, q)] = 1
			xm = x
			ym = y

		p, q = max(gess9, key=gess9.get)
		nai9 = gess9[(p,q)]

		if nai9 > ans:
			ans = nai9

	tmp = max(nai, nai2, nai3,nai4, nai5,nai6,nai1,nai7,nai8,ans)

	print(N-tmp)



if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
import sys
N = int(input())
li = []
if N == 1:
    a = list(map(int,input().split()))
    print(1)
    sys.exit()   

for i in range(N):
    a = list(map(int,input().split()))
    li.append(a)

cross = []

##計算量に余裕があるので全探索します
for i in range(N):
    for j in range (i+1, N):
        a = [li[j][0]-li[i][0],li[j][1]-li[i][1]]
        if a[0] < 0 and a[1] < 0:
            b = [abs(li[j][0]-li[i][0]),abs(li[j][1]-li[i][1])]
            cross.append(b)
        if a[0] < 0 and a[1] > 0:
            c = li[j][1]-li[i][1]
            b = [abs(li[j][0]-li[i][0]),-c]
            cross.append(b)
        else:
            cross.append(a) 

lencross = len(cross)

res = 0
ans = []

for i in range (lencross):
    res = 0
    for j in range (lencross):
        if cross[i] == cross[j]:
            res += 1
    ans.append(res)
if N-1 < max(ans):
    reduce = N-1
else:
    reduce = max(ans)

print(N - reduce)

Submission status: Wrong Answer

Solution code:
N=int(input())
xy=[list(map(int,input().split())) for _ in range(N)]
 
from collections import Counter
list_=[]
 
for i in range(N):
    for j in range(i+1,N):
        list_.append((abs(xy[i][0]-xy[j][0]),abs(xy[i][1]-xy[j][1])))
 
if N==1:
    print("0")
else:
    print(N-Counter(list_).most_common()[0][1])

Submission status: Wrong Answer

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

if n <= 2:
    print(1)

else:
    L_sort = sorted(L)
    L_dict = {}
    for i in range(n-1):
        tmp0 = L_sort[i+1][0] - L_sort[i][0]
        tmp1 = L_sort[i+1][1] - L_sort[i][1]
        if tmp0 != 0 and tmp1 != 0:
            if (tmp0, tmp1) in L_dict:
                L_dict[(tmp0, tmp1)] += 1
            else:
                L_dict[(tmp0, tmp1)] = 1
    ans = n - max(L_dict.values())
    print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
N=int(input())
x = [0] * N
y = [0] * N
ans = N

for i in range(N):
  x[i], y[i] = map(int, input().split())
  
for i in range(N-1):
  cost = N
  for j in range(i+1,N-1):
    p = x[i] - x[j]
    q = y[i] - y[j]
    if p == 0 and q==0:
      cost = N*2
    diffx = np.diff(x)
    diffy = np.diff(y)
    for k in range(N-1):
      if diffx[k] == p and diffy[k] == q:
        cost = cost - 1
      if diffx[k] == -p and diffy[k] == -q:
        cost = cost - 1
  ans = min(ans,cost)

print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
xy=[list(map(int,input().split())) for _ in range(N)]
 
from collections import Counter
list_=[]
 
for i in range(N):
    for j in range(i+1,N):
        list_.append((abs(xy[i][0]-xy[j][0]),abs(xy[i][1]-xy[j][1])))
 
if N==1:
    print("1")
else:
    print(N-Counter(list_).most_common()[0][1])

Submission status: Wrong Answer

Solution code:
# 何本の数直線上にあるかを求める　1<=ans<=n-1
# 少なくとも2点を通る直線のみ調べれば良い
n=int(input())
xy=[list(map(int,input().split())) for _ in range(n)]
xy.sort(key=lambda x:(x[0],x[1]))
# print(xy)
if n<=2:
    print(1)
else:
    diff=[]
    for i in range(n):
        for j in range(i):
            diff.append((xy[i][0]-xy[j][0],xy[i][1]-xy[j][1]))

    ans=[]
    # print(set(diff))
    for p,q in set(diff):
        intercepts=[]
        for i in range(n):
            qxHIKUpy=q*xy[i][0]-p*xy[i][1]
            intercepts.append(qxHIKUpy)
        # print(q,'x-',p,'y=',intercepts)
        ans.append(len(set(intercepts)))
    # print(ans)
    print(min(ans))

Submission status: Wrong Answer

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

PQ = []
# 2点を選びp,q仮決め
for i in range(N):
    prev = XY[i]
    for j in range(N):
        next = XY[j]
        p = next[0] - prev[0]
        q = next[1] - prev[1]
        if PQ.count([p,q]) == 0 :
            PQ.append([p,q])

ans = 10**9
# スコア計算
for p,q in PQ:
    tmp_ans = 0
    # print(f'###  (p,q) = ({p},{q})')
    for next in XY: # 次の座標
        score = 1
        # print(f'(p,q)=({p},{q})で{next}に至る最小スコア')
        for prev in XY: # 直前の座標
            if prev == next: continue
            x_ = next[0]-prev[0]
            y_ = next[1]-prev[1]
        
            if ((p==0 and x_==0 )\
                or (p>0 and x_>0 and x_%p==0)) \
                and ((q==0 and y_==0 )\
                or (q>0 and y_>0 and y_%q==0)):
                tmp_score = 0
            else:
                tmp_score = 1
            # print(f'# n:{next} p:{prev} n-p:({x_},{y_}) p:{p},q:{q} tmp:{tmp_score} score:{score}')
            score = min(score, tmp_score)
        # print(f'  => {score}')
        tmp_ans += score
    # print(f'({p},{q}) のスコア = {tmp_ans}')
    ans = min(ans, tmp_ans)
    # print(f'現在のスコア：{ans}')
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
ball = []
dif = [[] for i in range(N-1)]
for i in range(N):
    x,y = map(int,input().split())
    ball += [[x,y]]
ball = sorted(ball)

for i in range(N-1):
    for j in range(N-i-1):
        dif[i].append([ball[j+1+i][0] - ball[i][0], ball[j+1+i][1] - ball[i][1]])

ans = 0
for i in range(N-1):
    for j in range(N-i-1):
        base = dif[i][j]
        point = 0
        for k in range(i+1,N-1):
            for l in range(N-k-1):
                if base == dif[k][l]:
                    point += 1
                    break
        if ans < point: ans = point

print(N-ans-1)

Submission status: Wrong Answer

Solution code:

def calc(XYi):
    dictX = {}
    dictY = {}
    for i in range(N - 1):
        x, y = XYi[i][0], XYi[i][1]
        nx, ny = XYi[i + 1][0], XYi[i + 1][1]
        tx = x - nx
        ty = y - ny

        vx = dictX.get(tx)
        vy = dictY.get(ty)

        if vx:
            dictX[tx] = vx + 1
        else:
            dictX[tx] = 1
        if vy:
            dictY[ty] = vy + 1
        else:
            dictY[ty] = 1

    ps = []
    qs = []
    maxv = 0
    for i in dictX.keys():
        v = dictX[i]
        if v > maxv:
            maxv = v
    for i in dictX.keys():
        v = dictX[i]
        if v == maxv:
            ps.append(i)

    maxv = 0
    for i in dictY.keys():
        v = dictY[i]
        if v > maxv:
            maxv = v
    for i in dictY.keys():
        v = dictY[i]
        if v == maxv:
            qs.append(i)

    min_cost = 99999
    for p in ps:
        for q in qs:
            cost = 1
            for i in range(N - 1):
                x, y = XYi[i][0], XYi[i][1]
                nx, ny = XYi[i + 1][0], XYi[i + 1][1]
                tx = x - nx
                ty = y - ny
                if tx == p and ty == q:
                    pass
                else:
                    cost += 1
            if cost < min_cost:
                min_cost = cost
    return min_cost


N = int(input())
XYi = [0] * N
for i in range(N):
    x, y = list(map(int, input().split()))
    XYi[i] = (x, y)

for i in range(N):
    for k in range(N):
        if i < k:
            if XYi[i][0] > XYi[k][0]:
                t = XYi[i]
                XYi[i] = XYi[k]
                XYi[k] = t
            elif XYi[i][0] == XYi[k][0]:
                if XYi[i][1] > XYi[k][1]:
                    t = XYi[i]
                    XYi[i] = XYi[k]
                    XYi[k] = t
costX = calc(XYi)

for i in range(N):
    for k in range(N):
        if i < k:
            if XYi[i][1] > XYi[k][1]:
                t = XYi[i]
                XYi[i] = XYi[k]
                XYi[k] = t
            elif XYi[i][1] == XYi[k][1]:
                if XYi[i][0] > XYi[k][0]:
                    t = XYi[i]
                    XYi[i] = XYi[k]
                    XYi[k] = t

costY = calc(XYi)
print(min(costX, costY))

Submission status: Wrong Answer

Solution code:
N = int(input())
xy = list(list(map(int,input().split()))+[0]for i in range(N))
xy=sorted(xy,reverse = True)
ans = 100
p,q = 0,0

def func(n):
    xy[n][2] = 1
    if [xy[n][0]+p,xy[n][1]+q,0] in xy:
        func(xy.index([xy[n][0]+p,xy[n][1]+q,0]))


for i in range(N-1):
    hoge = 0
    for j in range(i+1,N):
        p,q = xy[j][0]-xy[i][0],xy[j][1]-xy[i][1] # p,qのあり得るパターン
        
        for k in range(N):
            if xy[k][2] == 0:
                func(k)
                hoge += 1
        if not(p == 0 and q == 0):
            ans = min(hoge,ans)
        for k in range(N):
            xy[k][2] = 0
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import combinations


n = int(input())
balls = []
cost = n
for _ in range(n):
    x, y = map(int, input().split())
    balls.append((x, y))

for b1, b2 in combinations(balls, 2):
    p, q = b1[0] - b2[0], b1[1] - b2[1]
    if p != 0 and q != 0:
        sub = 1
        for ball in balls:
            bx, by = ball
            dx, dy = bx - b2[0], by - b2[1]
            if dx != 0 and dy != 0:
                if dx % p == 0 and dy % q == 0 and dx // p == dy // q:
                    sub += 1
        cost = min(cost, n - sub)

print(max(cost, 1))

Submission status: Wrong Answer

Solution code:
import itertools
from collections import Counter


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

    if N <= 2:
        return 1
    else:
        key_num = ( N*(N - 3) ) // 2 + N
        common_data = []
        max_common_num = 0

        for obj in itertools.combinations(data, 2):
            # print(obj)
            common_data.append( str(obj[0][0] - obj[1][0]) + "_" + str(obj[0][1] - obj[1][1]) )

        # カウント
        counter = Counter(common_data)
        for word, cnt in counter.most_common():
            max_common_num = cnt
            break

    print(N - max_common_num)
    # print(common_data)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import collections
N = int(input())
if N == 1:
    print("1")
elif N == 2:
    print("1")
else:
    L = []
    for i in range(N):
        [x, y] = map(int, input().split())
        L.append([x, y])
        L.sort()
        
    difL = []
    for i in range(N-1):
        [difx, dify] = L[i+1][0]-L[i][0], L[i+1][1]-L[i][1], 
        difL.append([difx, dify])

    t = map(tuple,difL)
    counted = collections.Counter(t)
    M = counted.most_common()[0][1]
    print(N-M)

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7

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

def main():
  n=I()
  l=[]

  for i in range(n):
    l.append(LI())

  # if n==2:
  #   return 1

  l2=[]
  for i in range(n):
    l3=[]
    for j in range(n):
      if i!=j:
        l3.append([l[j][0]-l[i][0],l[j][1]-l[i][1]])
    l2.append(l3)

  mx=0
  for i in range(n):
    _x=l2[i]

    for x in _x:
      sm=0
      for j in range(n):
        if i!=j:
          _y=l2[j]
          for y in _y:
            if x==y:
              sm+=1
      mx=max(mx,sm)

  return n-mx-1

print(main())

Submission status: Wrong Answer

Solution code:
n=int(input())
d=[list(map(int,input().split()))[::-1]for _ in range(n)]

def c(p,q,a):#p,qのときのスコア算出（多少おそくてもよし）
  global n
  s=n
  for i in a:
    if [i[0]-p,i[1]-q]in a:s-=1
  return s
ans=50
for i in range(n-1):
  for j in range(1+i,n):
    p,q=d[j][0]-d[i][0],d[j][1]-d[i][1]
    ans=min(ans,c(p,q,d[::-1]))
print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline


def read_int():
    return int(input())


def read_int_n():
    return tuple(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, XY):
    c = defaultdict(list)
    for i in range(N):
        x, y = XY[i]
        for j in range(i, N):
            if i == j:
                continue
            a, b = XY[j]
            c[(x-a, y-b)].append((i, j))

    ans = 0
    for _, v in c.items():
        l = set()
        r = set()

        for x, y in v:
            l.add(x)
            r.add(y)

        g = (len(l) - len(l & r))
        ans = max(ans, len(l | r) - g)
        # print(v, len(l | r), g, l & r)
    return N - ans


def main():
    N = read_int()
    XY = [read_int_n() for _ in range(N)]
    print(slv(N, XY))

    # N = 50
    # XY = set()
    # while len(XY) != N:
    #     XY.add((random.randint(1, 8), random.randint(1, 10)))
    # XY = list(XY)
    # print(slv(N, XY))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import random
input = sys.stdin.readline

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

def main():

	N = int(input())
	#N, K = map(int, input().split(" "))

	xy = []
	for _ in range(N):
		x, y = map(int, input().split(" "))
		xy.append((x,y))

	gess = {}
	xm = 0
	ym = 0

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

	for i, val in enumerate(xy):
		if i == 0:
			x,y = val
			xm = x
			ym = y
			continue
		x, y = val

		p = x - xm
		q = y - ym
		if (p,q) in gess:
			gess[(p, q)] += 1
		else:
			gess[(p, q)] = 1
		xm = x
		ym = y

	p, q = max(gess, key=gess.get)
	nai = gess[(p,q)]

	#########
	xy = sorted(xy, key=lambda x:(x[0]))
	gess1 = {}
	xm = 0
	ym = 0

	for i, val in enumerate(xy):
		if i == 0:
			x,y = val
			xm = x
			ym = y
			continue
		x, y = val

		p = x - xm
		q = y - ym
		if (p,q) in gess1:
			gess1[(p, q)] += 1
		else:
			gess1[(p, q)] = 1
		xm = x
		ym = y

	p, q = max(gess1, key=gess1.get)
	nai1 = gess1[(p,q)]

	#########
	xy = sorted(xy, key=lambda x:(-x[0]))
	gess2 = {}
	xm = 0
	ym = 0

	for i, val in enumerate(xy):
		if i == 0:
			x,y = val
			xm = x
			ym = y
			continue
		x, y = val

		p = x - xm
		q = y - ym
		if (p,q) in gess2:
			gess2[(p, q)] += 1
		else:
			gess2[(p, q)] = 1
		xm = x
		ym = y

	p, q = max(gess2, key=gess2.get)
	nai2 = gess2[(p,q)]

	#########
	xy = sorted(xy, key=lambda x:(x[1]))
	gess3 = {}
	xm = 0
	ym = 0

	for i, val in enumerate(xy):
		if i == 0:
			x,y = val
			xm = x
			ym = y
			continue
		x, y = val

		p = x - xm
		q = y - ym
		if (p,q) in gess3:
			gess3[(p, q)] += 1
		else:
			gess3[(p, q)] = 1
		xm = x
		ym = y

	p, q = max(gess3, key=gess3.get)
	nai3 = gess3[(p,q)]

	#########
	xy = sorted(xy, key=lambda x:(-x[1]))
	gess4 = {}
	xm = 0
	ym = 0

	for i, val in enumerate(xy):
		if i == 0:
			x,y = val
			xm = x
			ym = y
			continue
		x, y = val

		p = x - xm
		q = y - ym
		if (p,q) in gess4:
			gess4[(p, q)] += 1
		else:
			gess4[(p, q)] = 1
		xm = x
		ym = y

	p, q = max(gess4, key=gess4.get)
	nai4 = gess4[(p,q)]

	#########
	xy = sorted(xy, key=lambda x:(x[0],-x[1]))
	gess5 = {}
	xm = 0
	ym = 0

	for i, val in enumerate(xy):
		if i == 0:
			x,y = val
			xm = x
			ym = y
			continue
		x, y = val

		p = x - xm
		q = y - ym
		if (p,q) in gess5:
			gess5[(p, q)] += 1
		else:
			gess5[(p, q)] = 1
		xm = x
		ym = y

	p, q = max(gess5, key=gess5.get)
	nai5 = gess5[(p,q)]

	#########
	random.shuffle(xy)
	gess6 = {}
	xm = 0
	ym = 0

	for i, val in enumerate(xy):
		if i == 0:
			x,y = val
			xm = x
			ym = y
			continue
		x, y = val

		p = x - xm
		q = y - ym
		if (p,q) in gess6:
			gess6[(p, q)] += 1
		else:
			gess6[(p, q)] = 1
		xm = x
		ym = y

	p, q = max(gess6, key=gess6.get)
	nai6 = gess6[(p,q)]

	#########
	random.shuffle(xy)
	gess7 = {}
	xm = 0
	ym = 0

	for i, val in enumerate(xy):
		if i == 0:
			x,y = val
			xm = x
			ym = y
			continue
		x, y = val

		p = x - xm
		q = y - ym
		if (p,q) in gess7:
			gess7[(p, q)] += 1
		else:
			gess7[(p, q)] = 1
		xm = x
		ym = y

	p, q = max(gess7, key=gess7.get)
	nai7 = gess7[(p,q)]
		#########
	random.shuffle(xy)
	gess8 = {}
	xm = 0
	ym = 0

	for i, val in enumerate(xy):
		if i == 0:
			x,y = val
			xm = x
			ym = y
			continue
		x, y = val

		p = x - xm
		q = y - ym
		if (p,q) in gess8:
			gess8[(p, q)] += 1
		else:
			gess8[(p, q)] = 1
		xm = x
		ym = y

	p, q = max(gess8, key=gess8.get)
	nai8 = gess8[(p,q)]

		#########
	ans = -1

	for _ in range(10000):
		random.shuffle(xy)
		gess9 = {}
		xm = 0
		ym = 0
		for i, val in enumerate(xy):
			if i == 0:
				x,y = val
				xm = x
				ym = y
				continue
			x, y = val

			p = x - xm
			q = y - ym
			if (p,q) in gess9:
				gess9[(p, q)] += 1
			else:
				gess9[(p, q)] = 1
			xm = x
			ym = y

		p, q = max(gess9, key=gess9.get)
		nai9 = gess9[(p,q)]

		if nai9 > ans:
			ans = nai9

	tmp = max(nai, nai2, nai3,nai4, nai5,nai6,nai1,nai7,nai8,ans)

	print(N-tmp)



if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
from collections import Counter
n=int(input())
xy = [list(map(int, input().split())) for _ in range(n)]
xy=sorted(xy)

if n!=1:
    xy0_diff=[]
    for i in range(0,n-1):
        xy0_diff.append(xy[i][0]-xy[i+1][0])

    c=Counter(xy0_diff)
    mode1 = c.most_common()
    mode1=list(mode1)
    saihin_kaisu=mode1[0][1]
    saihin_list=[]
    for i in range(len(mode1)):
        if mode1[i][1]==saihin_kaisu:
            saihin_list.append(mode1[i][0])

    ans=[]
    for item in saihin_list:
        xy1_diff=[]
        for i in range(0,n-1):
            if xy[i][0]-xy[i+1][0]==item:
                xy1_diff.append(xy[i][1]-xy[i+1][1])
                d=Counter(xy1_diff)
                mode2 = d.most_common(1)
                ans.append(mode2[0][1])

    print(n-min(ans))

else:
    print(1)

Submission status: Wrong Answer

Solution code:
count = int(input())
difs = []
last_A = 0
last_B = 0
for _ in range(count):
  nums = input().split()
  A = int(nums[0])
  B = int(nums[1])
  difs.append([last_A-A,last_B-B])
  last_A = A
  last_B = B
best = 0
count_difs = 0
for i in range(count):
  count_difs = difs.count(difs[i])
  if(best < count_difs):
    best = count_difs
if(best == count):
  print(1)
else:
  print(count - best)

Submission status: Wrong Answer

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

if len(AB_list) ==1:
    print(1)
    exit(0)

AB_list = sorted(AB_list,key=lambda a:a[0])
kouho_list = []
for i, AB in enumerate(AB_list):
    for j,ab in enumerate(AB_list[i+1:]):
        kouho_list.append((ab[0]-AB[0] ,ab[1]-AB[1]))

from collections import Counter
kouho_counter = Counter(kouho_list).most_common()
pq = list(kouho_counter[0][0])

onaji_list = []
#print(pq)

result = []
for i,ab in enumerate(AB_list):
    for j,ab2 in enumerate(AB_list):
        if i == j:
            continue
        if ab[0] + pq[0] == ab2[0] and ab[1] + pq[1] == ab2[1]:
            result.append(tuple(ab2))
            continue
        #if ab[0] - pq[0] == ab2[0] and ab[1] - pq[1] == ab2[1]:
            #result.append(tuple(ab2))


#print(result)
result = list(set(result))
#print(onaji_list)
#print(result)
print(len(AB_list)-len(result))





'''
候補は49 + 48 + 47 + ...
この候補の中で、一番えらばれているものをp,qとして設定する
その後、ループを回して、実際にコストを計算する

'''


#print(AB_list)

Submission status: Wrong Answer

Solution code:
from functools import reduce

n = int(input())
nums = list(map(int, input().split()))
#max_num = max(nums)
#print(max_num)
#nums = sorted(nums)

nums.sort()
smalls = nums[:-1]

small = reduce(lambda a, b: a - b, smalls)
ans = nums[-1] - small

# print(nums)
# print(smalls)
# print(small)
print(ans)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
# -*- coding: utf-8 -*-
import sys
import numpy as np
# 行数
N = int(input().strip())

# 2次元配列
grid = []
for i in range(N):
    array = list(map(int, input().strip().split()))
    grid.append(array)

if N==1:
  print(1)
  sys.exit()
elif N==2:
  print(1)
  sys.exit()

Result=N-2
#print ("Result is" + str(Result))

#print(grid)
for a in range(N):
    #Re_t=1
    A = [grid[a][0],grid[a][1]]
    #print ("A equal")
    #print (A)
    for b in range(N):
        if a == b:
            continue
        B = [grid[b][0],grid[b][1]]
        #print ("A equal " + str(A) + " B equal " + str(B))
        #print (B)
        if (B[0]-A[0]) == 0:
        	k = 0
        else:
        	k = (B[1]-A[1])/(B[0]-A[0])
        #print ("katamuki is" + str(k))
        Re_t=1
        #print (k)
        for c in range(N):
            if (a == c) or (b == c):
                continue
            C = [grid[c][0],grid[c][1]]
            cy = B[1] + k*(C[0]-B[0])
            if cy == C[1]:
                #print("ack")
                continue
            else:
                #print("out")
                Re_t = Re_t + 1
            if int(Result) < int(Re_t) - 1:
                #print("out")
                break #
        #print ("result_tmp is" + str(Re_t))
        if Result > Re_t:
            Result = Re_t
            #print ("result is overritten")
            #print (Result)
                
#print("end")
print (Result)

Submission status: Wrong Answer

Solution code:
N = int(input())
X = []
Y = []
PQ = []
for i in range(0,N):
    x,y = map(int, input().split())
    X.append(x)
    Y.append(y)
for i in range(0,N-1):
    p = X[i+1]-X[i]
    q = Y[i+1]-Y[i]
    PQ.append((p,q))
result = []
for p,q in PQ:
    cnt = 0
    for test_p, test_q in PQ:
        if test_p == p and test_q == q:
            cnt += 1
    result.append(cnt)
result.sort()
if N > 2:
    print(N-1-result[len(result)-1]+1)
else:
    print(1)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from operator import sub

def main():
    N = int(input())
    balls = [tuple(map(int,input().split())) for _ in range(N)]
    d = defaultdict(int)
    for i in range(N):
        for j in range(N):
            if i == j:
                continue
            d[tuple(map(sub, balls[i], balls[j]))] += 1
    try:
        mmax = N - max(d.values())
        print(mmax)
    except ValueError:
        print(100)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# coding: UTF-8
import sys
#sys.setrecursionlimit(n)
import heapq
import re
import bisect
import random
import math
import itertools
from collections import defaultdict, deque
from copy import deepcopy
from decimal import *
 
readl= lambda: list(map(int, sys.stdin.readline().split()))
readt= lambda: tuple(map(int, sys.stdin.readline().split()))
read = lambda: sys.stdin.readline().rstrip()
readi = lambda: int(read())
readmi = lambda: map(int, sys.stdin.readline().split())
readms = lambda: map(str, sys.stdin.readline().split())
 
n = readi()
a = []
if n == 1:
    print(1)
    exit()
for i in range(n):
    x, y = readmi()
    a.append([x,y])
a.sort()
aa = defaultdict(int)
old1 = 0
old2 = 0
flg = True
for i in range(n - 1):
    aa[(a[i + 1][0] - a[i][0], a[i + 1][1] - a[i][1])] += 1
aaa = sorted(aa.items(), key=lambda x:x[1], reverse=True)
print(n - aaa[0][1])

Submission status: Wrong Answer

Solution code:
from collections import Counter
N = int(input())
xy = sorted([list(map(int, input().split())) for _ in range(N)])
def getCount(xy):
    diff = []
    for i in range(1, len(xy)):
        x = xy[i][0]-xy[i-1][0]
        y = xy[i][1]-xy[i-1][1]
        diff.append((x,y))
    return Counter(diff)

def getMax(c):
    xm = 0
    for i in c:
        xm = max(xm, c[i])
    return xm
ret = []
c = getCount(xy)
ret.append(getMax(c))
xy.sort(key=lambda x:x[1])
c = getCount(xy)
ret.append(getMax(c))
xy.sort(key=lambda x:x[0], reverse=True)
c = getCount(xy)
ret.append(getMax(c))
xy.sort(key=lambda x:x[1], reverse=True)
c = getCount(xy)
ret.append(getMax(c))
m = max(ret)
print(N-m)