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

	xy = sorted(xy, key=lambda x:(x[0]))
	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]))
	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)]

	#########
	#xy = sorted(xy, key=lambda x:(-x[0],-x[1]))
	xy = sorted(xy, key=lambda x:(x[1],-x[0]))
	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)]

	tmp = max(nai, nai2, nai3,nai4, nai5,nai6)

	print(N-tmp+1)



if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
import math

N = int(input())

ball = [0] * N

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

ans = N

# p,q の組
for i in range(N) :
    for j in range(N) :
        p = ball[j][0] - ball[i][0]
        q = ball[j][1] - ball[i][1]

        if p == 0 and q == 0 :
            continue

        group = []

        if p == 0 :
            for k in range(N) : # xがゼロ以下になるまで引き，切片を求める
                if ball[k][1] >= 0 :
                    mul = math.ceil(ball[k][1] / q)
                    b = ball[k][1] - q * mul
                else :
                    mul = math.ceil(ball[k][1] / q) - 1
                    b = ball[k][1] + q * mul
                x = ball[k][0]
                group.append((x,b))
        else :
            for k in range(N) :
                if ball[k][0] >= 0 :
                    mul = math.ceil(ball[k][0] / p)
                    b = ball[k][1] - q * mul
                    x = ball[k][0] - p * mul
                else :
                    mul = math.ceil(ball[k][0] / p) - 1
                    b = ball[k][1] + q * mul
                    x = ball[k][0] + p * mul
                group.append((x,b))
        count = set(group)
        ans = min(ans,len(count))

print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import combinations
import sys

N = int(input()) 
X_Y = [0] * N

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


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

combo = list(combinations(X_Y, 2))
diff = [0] * (len(combo))

dict_diff = {}

for i, item in enumerate(combo):
    x_dif = item[0][0] - item[1][0]
    y_dif = item[0][1] - item[1][1]
    diff[i] = [abs(x_dif), abs(y_dif)]
    if str(diff[i]) in dict_diff:
        dict_diff[str(diff[i])] += 1
    else:
        dict_diff[str(diff[i])] = 1

print((N) - max(dict_diff.values()))

Submission status: Wrong Answer

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


def solve(N: int, x: "List[int]", y: "List[int]"):
    # rted(a, key=lambda x:x[1], reverse=True)

    a = [[x[i],y[i]] for i in range(N)]
    a = sorted(a, key=lambda x:(x[1],x[0]), reverse=True)

    x.sort()
    y.sort()

    sx = [x[i+1]-x[i] for i in range(N-1)]
    sy = [y[i+1]-y[i] for i in range(N-1)]

    from collections import Counter

    csx = Counter(sx)
    csy = Counter(sy)

    p = [i for i,v in csx.most_common()] + [-1*i for i,v in csx.most_common()]
    q = [i for i,v in csy.most_common()] + [-1*i for i,v in csy.most_common()]
    p.sort()
    q.sort()
    # print(p)

    ans = 10000000000
    for i in p:
        for j in q:
            if(i == 0 and j == 0):
                continue
            tans = 1
            for k in range(1,N):
                s,t = a[k]
                if(a[k-1][0] == s-i and a[k-1][1] == t-j):
                    continue
                else:
                    tans += 1
            ans = min(ans,tans)

    a = sorted(a, key=lambda x:(x[0],x[1]), reverse=True)
    for i in p:
        for j in q:
            if(i == 0 and j == 0):
                continue
            tans = 1
            for k in range(1,N):
                s,t = a[k]
                if(a[k-1][0] == s-i and a[k-1][1] == t-j):
                    continue
                else:
                    tans += 1
            ans = min(ans,tans)


    print(ans)

    return


# Generated by 1.1.3 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    x = [int()] * (N)  # type: "List[int]" 
    y = [int()] * (N)  # type: "List[int]" 
    for i in range(N):
        x[i] = int(next(tokens))
        y[i] = int(next(tokens))
    solve(N, x, y)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

def f(_pts, p, q):
    pts = set(_pts[:])
    r = 0

    while len(pts) > 0:
        r += 1
        x = max(pts)
        while x in pts:
            pts.remove(x)
            x = (x[0]-p, x[1]-q)

    print(r)
    return r

################################################################################

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

res = n
for i in range(len(pts)):
    for j in range(i+1, len(pts)):
        res = min(res, f(pts, -(pts[i][0]-pts[j][0]), -(pts[i][1]-pts[j][1])))
        res = min(res, f(pts, +(pts[i][0]-pts[j][0]), -(pts[i][1]-pts[j][1])))
        res = min(res, f(pts, -(pts[i][0]-pts[j][0]), +(pts[i][1]-pts[j][1])))
        res = min(res, f(pts, +(pts[i][0]-pts[j][0]), +(pts[i][1]-pts[j][1])))

print(res)

Submission status: Wrong Answer

Solution code:
from sys import stdin

N=int(input())
xlist=[]
ylist=[]
dict = {}
for i in range(N):
  x, y = map(int, stdin.readline().rstrip().split())
  xlist.append(x)
  ylist.append(y)

for i in range(N):
  for j in range(N):
    if i != j:
      tupleStr=str(xlist[i] - xlist[j])+","+str(ylist[i] - ylist[j])
      if tupleStr in dict:
        dict[tupleStr]+=1
      else:
        dict[tupleStr]=1

#maxNum = max(dict.values())
maxNum=2
print(N-maxNum)

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 = max(d.values())
        mmax = int(N - mmax)
    except:
        print(100)
    print(N)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n=int(input())
l=[]
l2=[]
sum1=0
sum2=0
sum1,sum2=map(int,input().split())
for i in range(n-1):
    x,y=map(int,input().split())
    c=x-sum1
    c2=y-sum2
    l.append(c)
    l2.append(c2)
    sum1=x
    sum2=y
#print(set(l),set(l2))
print(max(len(set(l)),len(set(l2))))

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

	xy = sorted(xy, key=lambda x:(x[0]))
	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]))
	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)]

	#########
	#xy = sorted(xy, key=lambda x:(-x[0],-x[1]))
	xy = sorted(xy, key=lambda x:(x[1],-x[0]))
	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)]

	tmp = max(nai, nai2, nai3,nai4, nai5,nai6)

	print(N-tmp-2)



if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
n = int(input())
xy = [list(map(int, input().split())) for _ in range(n)]
xy.sort()
h = defaultdict(int)
for x, y in xy:
    h[(x, y)] = True
mx, my = xy[-1]
d = defaultdict(int)
ans = 0
for i in range(n):
    x1, y1 = xy[i]
    for j in range(i+1, n):
        x2, y2 = xy[i+1]
        z1 = x2-x1
        z2 = y2-y1

        a = 0
        x, y = x1, y1
        while x <= mx and y <= my:
            if (x, y) in h:
                a += 1
            x += z1
            y += z2
        if ans < a:
            ans = a

if ans <= 1:
    print(n)
else:
    print(max(1, n-ans))

Submission status: Wrong Answer

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

li.sort(key = lambda x:x[0])
li2 = []

for i in range(n):
    for j in range(i):
        a = [li[i][0]-li[j][0],li[i][1]-li[j][1]]
        li2.append(a)

ans = 0

for i in li2:
    ans = max(ans,li2.count(i))

print(n-ans)

Submission status: Wrong Answer

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

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


def calc(p,q):
    result = set()
    if p == 0:
        for x,y in XY:
            result.add(x) # x 切片
        return len(result)
    if q == 0:
        for x,y in XY:
            result.add(y) # x 切片
        return len(result)

    for x,y in XY:
        result.add(Fraction(y*p - (x * q),p)) # y切片

    return len(result)

ans = 5000

for i in range(N-1):
    for j in range(i+1,N):
        p = XY[i][0] - XY[j][0]
        q = XY[i][1] - XY[j][1]
        # print(p,q,calc(p,q))
        ans = min(ans,calc(p,q))

if ans == 5000:
    raise ValueError
print(ans)

Submission status: Wrong Answer

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


for i in range(n):
    for j in range(i+1,n):
        l.append([p[j][0]-p[i][0],p[j][1]-p[i][1]])

m=0
for i in range(len(l)):
    cnt=0
    for j in range(len(l)):
        if l[i][0]==0:
            if l[j][0]==0:
                cnt+=1
        elif l[i][1]==0:
            if l[j][1]==0:
                cnt+=1
        elif l[i][0]==l[j][0] and l[i][1]==l[j][1] and i!=j or l[i][0]==-l[j][0] and l[i][1]==-l[j][1] and i!=j:
                cnt+=1
        if cnt>m:
            m=cnt
        
ans=n
if m!=0:
    ans=n-m-1
if n==2:
    ans=1
print(ans)

Submission status: Wrong Answer

Solution code:
from copy import deepcopy

N = int(input())
Z = [[] for i in range(N)]
for i in range(N):
    x, y = map(int, input().split())
    Z[i] = [x, y]

# p, qが決まっている場合のコスト
def cost(p, q):
    reduction = 0
    W = deepcopy(Z)
    for i in range(N-1):
        x, y = W[i]
        if x == 10**10:
            pass
        else:
            for j in range(i+1, N):
                if p != 0 and q != 0:
                    if W[j] != [10**10, 10**10] and (W[j][0] - x) / p == (W[j][1] - y) / q:
                        reduction += 1
                        W[j] = [10**10, 10**10]
                elif p == 0:
                    if W[j] != [10**10, 10**10] and W[j][0] == x and (W[j][1] - y) % q == 0:
                        reduction += 1
                        W[j] == [10**10, 10**10]
                else:
                    if W[j] != [10**10, 10**10] and (W[j][0] - x) % p == 0 and W[j][1] == y:
                        reduction += 1
                        W[j] == [10**10, 10**10]
        
    return N - reduction

ans = N
for i in range(N-1):
    for j in range(i+1, N):
        p = Z[j][0] - Z[i][0]
        q = Z[j][1] - Z[i][1]
        cos = cost(p, q)
        
        ans = min(ans, cos)

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
XY = [list(map(int,input().split())) for _ in range(N)]
XY.sort(key = lambda x: (x[0], x[1]))

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

diff = []
for X, Y in XY:
  for X2, Y2 in XY:
    p = X2-X
    q = Y2-Y
    if (p, q) == (0, 0) or (p, q) in diff:
      continue
    diff.append((p, q))

pre = []
ans = []
for p, q in diff:
  cost = 1
  for a, b in XY:
    if not pre:
      pre = (a, b)
      continue
    if (a - p, b - q) == pre:
      pass
    else:
      cost += 1
    pre = (a, b)
  ans.append(cost)
  pre = []
print(min(ans))

Submission status: Wrong Answer

Solution code:
import numpy as np
from operator import itemgetter

n = int(input())
if n == 1:
    print(1)
else:
    xy = []
    for i in range(n):
        xy_i = list(map(int, input().split()))
        xy.append(xy_i)

    st_xy1 = sorted(xy, key=itemgetter(0))
    st_xy = sorted(st_xy1, key=itemgetter(1))

    s = np.array(st_xy)

    L = list(map(list,np.diff(s.transpose()).transpose()))

    ans = []
    for LL in list(map(list, set(map(tuple, L)))):
        if LL[0] !=0 or LL[1] !=0:
            ans.append(L.count(LL))
    if len(ans) != 0:
        print(n - max(ans))
    else:
        print(n - 1)

Submission status: Wrong Answer

Solution code:
from itertools import combinations as comb

N = int(input())
xy = []
xy_ap = xy.append

for i in range(N):
    xy_ap(list(map(int, input().split())))

ls = [i for i in range(N)]

result = []


for i, j in comb(ls, 2):
    result.append([abs(xy[i][0] - xy[j][0]), abs(xy[i][1] - xy[j][1])])

cnt = 0
for i in range(len(result)):
    if result.count(result[i]) > cnt:
        cnt = result.count(result[i])
        
print(N - (cnt - 1))

Submission status: Wrong Answer

Solution code:
from collections import Counter as c
N = int(input())
XY = [tuple(map(int, input().split())) for _ in range(N)]
XY.sort(key=lambda xy: xy[0])
if N == 1 or N == 2:
    print(1)
    exit()

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

print(N - sorted(list(c(inclination).items()), key=lambda x: x[1])[-1][1])

Submission status: Wrong Answer

Solution code:
import math

N = int(input())

ball = [0] * N

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

ans = N

# p,q の組
for i in range(N) :
    for j in range(N) :
        p = ball[j][0] - ball[i][0]
        q = ball[j][1] - ball[i][1]

        if p == 0 and q == 0 :
            continue

        group = []

        if p == 0 :
            for k in range(N) : # xがゼロ以下になるまで引き，切片を求める
                if ball[k][1] >= 0 :
                    mul = math.ceil(ball[k][1] / q)
                    b = ball[k][1] - q * mul
                else :
                    mul = math.floor(ball[k][1] / q)
                    b = ball[k][1] + q * mul
                x = ball[k][0]
                group.append((x,b))
        else :
            for k in range(N) :
                mul = math.ceil(ball[k][0] / p) # 引く回数
                if ball[k][0] >= 0 :
                    mul = math.ceil(ball[k][0] / p)
                    b = ball[k][1] - q * mul
                    x = ball[k][0] - p * mul
                else :
                    mul = math.floor(ball[k][0] / p)
                    b = ball[k][1] + q * mul
                    x = ball[k][0] + p * mul
                group.append((x,b))
        count = set(group)
        ans = min(ans,len(count))

print(ans)

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

	xy = sorted(xy, key=lambda x:(x[0]))
	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]))
	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)]

	#########
	#xy = sorted(xy, key=lambda x:(-x[0],-x[1]))
	xy = sorted(xy, key=lambda x:(x[1],-x[0]))
	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)]

	tmp = max(nai, nai2, nai3,nai4, nai5,nai6)

	print(N-tmp-1)



if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
from collections import deque
N = int(input())
xy = [list(map(int, input().split())) for _ in range(N)]
cost = float('Inf')
if N == 1:
    print(1)
    exit()
for st in xy:
    for nx in xy:
        if st != nx:
            p = nx[0] - st[0]
            q = nx[1] - st[1]
        else:
            continue
        que = deque()
        que.append(st)
        for t in xy:
            if t != st:
                que.append(t)
        tmp = 0
        flag = True
        while len(que) > 0:
            if flag:
                st2 = que.popleft()
                tmp += 1
            flag = True
            nque = deque()
            for nx2 in que:
                if flag and (nx2[0] - st2[0]) == p and (nx2[1] - st2[1]) == q:
                    st2 = nx2
                    flag = False
                else:
                    nque.append(nx2)
            que = nque
        if tmp < cost:
            cost = tmp
print(cost)

Submission status: Wrong Answer

Solution code:
N = int(input())
L = [list(map(int,input().split())) for _ in range(N)]
A = []
p, q = 0, 0

for i in range(N-1):
    for j in range(i+1,N):
        p = L[j][0] - L[i][0]
        q = L[j][1] - L[i][1]
        if p*q != 0:
            if p*q > 0 and p < 0:
                A.append([-1*p,-1*q])
            else:
                A.append([p,q])

A.sort()
S = []
ctr = 0
for k in range(len(A)-1):
    for l in range(k+1, len(A)):
        if A[k] == A[l]:
            ctr += 1
        else:
            S.append(ctr)
            ctr = 0


if len(S) == 0:
    print((N+1)//2)
elif max(S) == 0:
    print((N+1)//2)
else:
    n = max(S) + 2
    print( 1 + (N-n+1)//2 )

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


class UnionFind():
    def __init__(self):
        self.__table = {}
        self.__size = defaultdict(lambda: 1)

    def __root(self, x):
        if x not in self.__table:
            self.__table[x] = x
        elif x != self.__table[x]:
            self.__table[x] = self.__root(self.__table[x])

        return self.__table[x]

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

    def union(self, x, y):
        x = self.__root(x)
        y = self.__root(y)
        if x != y:
            self.__size[y] += self.__size[x]
            self.__table[x] = y

    def size(self, x):
        return self.__size[self.__root(x)]

    def num_of_group(self):
        g = 0
        for k, v in self.__table.items():
            if k == v:
                g += 1
        return g


@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():
        uf = UnionFind()
        tmp = set()
        for x, y in v:
            tmp.add(x)
            tmp.add(y)
            uf.union(x, y)

        ans = max(ans, len(tmp) - uf.num_of_group())
    return N - ans


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

    # N = 50
    # XY = [(random.randint(1, 10), random.randint(1, 10)) for _ in range(N)]
    # print(slv(N, XY))


if __name__ == '__main__':
    main()