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

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

	print(N-tmp)



if __name__ == "__main__":
	main()

Submission status: Wrong Answer

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

vectors = []
ans_inv = 0
for i in range(N):
    for j in range(i+1,N):
        vector = [x_y[i][0]-x_y[j][0],x_y[i][1]-x_y[j][1]]
#        print(vector)
        vector_inv = [x_y[j][0]-x_y[i][0],x_y[j][1]-x_y[i][1]]
        if not vector in vectors and not vector_inv in vectors:
            vectors.append(vector)
path = int(N*(N-1)/2) - len(vectors)
if N == 2:
    print('1')
else:
    print(path)

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
    tmp=0
    for j in range(len(l)):
        if l[i][0]==0:
            tmp=l[i][1]
            if l[i][0]==l[j][0] and l[i][1]==l[j][1] and i!=j and tmp==l[j][1] or l[i][0]==-l[j][0] and l[i][1]==-l[j][1] and i!=j and tmp==l[j][1]:
                cnt+=1
        elif l[i][1]==0:
            tmp=l[i][0]
            if l[i][0]==l[j][0] and l[i][1]==l[j][1] and i!=j and tmp==l[j][0] or l[i][0]==-l[j][0] and l[i][1]==-l[j][1] and i!=j and tmp==l[j][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:
N = int(input())
list1 = []
list2 = [0] * 2

for i in range(N):
    tmp1, tmp2 = map(int, input().split())
    list2[0] = tmp1
    list2[1] = tmp2
    list1.append(list2.copy())

list1.sort()
tmplist = []
tmp1 = list1[0][0]
tmp2 = list1[0][1]
for i in range(1, N):
    x1 = list1[i][0]
    y1 = list1[i][1]
    int1 = -(tmp1 - list1[i][0])
    int2 = -(tmp2 - list1[i][1])
    tmp1 = list1[i][0]
    tmp2 = list1[i][1]
    tmplist.append(str(int1) + ','+ str(int2))

maxcnt = -1
for i in range(len(tmplist)):
    maxcnt = max(maxcnt, tmplist.count(tmplist[i]))

tmp1list = []
tmp1 = list1[0][0]
tmp2 = list1[0][1]
for i in range(1, N):
    x1 = list1[i][0]
    y1 = list1[i][1]
    if x1 != list1[i][0]:
        int1 = -(tmp1 - list1[i][0])
        int2 = -(tmp2 - list1[i][1])
        tmp1 = list1[i][0]
        tmp2 = list1[i][1]
        tmp1list.append(str(int1) + ','+ str(int2))

for i in range(len(tmp1list)):
    maxcnt = max(maxcnt, tmplist.count(tmp1list[i]))

tmp2list = []
tmp1 = list1[0][0]
tmp2 = list1[0][1]
for i in range(1, N):
    x1 = list1[i][0]
    y1 = list1[i][1]
    if x1 != list1[i][0] and y1 != list1[i][0]:
        int1 = -(tmp1 - list1[i][0])
        int2 = -(tmp2 - list1[i][1])
        tmp1 = list1[i][0]
        tmp2 = list1[i][1]
        tmp1list.append(str(int1) + ','+ str(int2))

for i in range(len(tmp1list)):
    maxcnt = max(maxcnt, tmplist.count(tmp2list[i]))

print(N - maxcnt)

Submission status: Wrong Answer

Solution code:
N=int(input())
dic=[]

for i in range(N):
    dic.append(input().split())
    dic[i][0] = int(dic[i][0])
    dic[i][1] = int(dic[i][1])
dic=sorted(dic, key=lambda x:(x[0],-x[1]))
#print(dic)

min=N-1
cnt=0
for i in range(N-1):
    p=dic[i+1][0]-dic[i][0]
    q=dic[i+1][1]-dic[i][1]
    if p==0 and q==0:
        cnt=0
    else:
            for k in range(N-1):
                if(dic[k+1][0]-p!=dic[k][0])or(dic[k+1][1]-q!=dic[k][1]):
                    cnt+=1
            #print(cnt)
            if(min>=cnt):
                min=cnt
    cnt=0
print(min+1)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)

def gcd(x,y):
	if x<y:
		x,y = y,x
	if y == 0:
		return x
	return gcd(y,x%y)

def main():
	n = int(input())
	xy = []
	for _ in range(n):
		xy +=[list(map(int,input().split()))]
	xy.sort(key=lambda x:(x[0],x[1]))
	dic = {}
	for i in range(n):
		for j in range(i+1,n):
			x,y = xy[i][0] - xy[j][0], xy[i][1] - xy[j][1]
			if x*y == 0:
				temp = "{}.{}".format(x,y)
			else:
				k = "" if x*y > 0 else "-"
				x = abs(x)
				y = abs(y)
				temp = "{}.{}{}".format(x,k,y)
			if temp in dic:
				dic[temp] = dic[temp]+1
			else:
				dic[temp] = 1
	ans = 100
	# print(dic, xy)
	for d in dic:
		p,q = map(int,d.split("."))
		nlst = xy
		tans = 0
		lenn = n
		while lenn != 0:
			tans += 1
			f = nlst[0]
			nnlst = []
			# print("print f ", f)
			for i in range(1,lenn):
				if p == 0:
					if ((nlst[i][1] - f[1]) % q != 0) or (nlst[i][0] != f[0]):
						nnlst += [nlst[i]]
					else:
						lenn -= 1
				elif q == 0:
					if ((nlst[i][0] - f[0]) % p != 0) or (nlst[i][1] != f[1]):
						nnlst += [nlst[i]]
					else:
						lenn -= 1
				else:
					# print(f"{abs(nlst[i][1] - f[1]) % q} {abs(nlst[i][0] - f[0]) % p}")
					if (((nlst[i][1] - f[1]) % q) != 0) or (((nlst[i][0] - f[0]) % p) != 0):
						nnlst +=[nlst[i]]
					else:
						if (nlst[i][1]-f[1]) == 0 or ((nlst[i][0]-f[0])==0):
							nnlst += [nlst[i]]
						else:	lenn -= 1
			lenn -= 1
			# print(nnlst)
			nlst = nnlst
		# print(f"{d},{tans}")
		ans = min(tans,ans)
	print(ans)
	return

main()

Submission status: Wrong Answer

Solution code:
def calc(XYi, pq):
    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

    p = 0
    q = 0
    maxv = 0
    for i in dictX.keys():
        if i == 0 and pq:
            continue
        v = dictX[i]
        if v > maxv:
            maxv = v
            p = i

    maxv = 0
    for i in dictY.keys():
        if i == 0 and not pq:
            continue
        v = dictY[i]
        if v > maxv:
            maxv = v
            q = i

    print(p, q)
    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
    return 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 = min(calc(XYi, True), calc(XYi, False))

print(costX)

Submission status: Wrong Answer

Solution code:
import itertools

N = int(input())
balls = []

for i in range(N):
    x, y = map(int, input().split(' '))
    balls.append((x,y))

ans = 100
for pat in list(itertools.permutations(balls)):
    dic = {}
    l = list(pat)
    px = l[0][0]
    py = l[0][1]
    t_max = 0
    for i in range(1,len(l)):
        dx = l[i][0] - px
        px = l[i][0]
        dy = l[i][1] - py
        py = l[i][1]
        if (dx,dy) not in dic.keys():
            dic[(dx,dy)] = 1
        else:
            dic[(dx,dy)] += 1
            if (t_max < dic[(dx,dy)]):
                t_max = dic[(dx,dy)]
        kitai = + N - i
        if ans < (N - kitai):
            break
    d_max = t_max
    cost = N - d_max
    if (cost < ans):
        ans = cost
        if (ans == 1):
            print(ans)
            exit()

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

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

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

	print(N-tmp)



if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
from collections import Counter
N = int(input())
AB =[]
for i in range(N):
    AB.append(list(map(int, input().split())))
AB.sort()
a = []
b = []
pre_AA=0
pre_BB=0
for i in AB:
    AA = int(i[0])
    a.append(abs(AA-pre_AA))
    BB = int(i[1])
    b.append(abs(BB-pre_BB))
    pre_AA = AA
    pre_BB = BB

a.sort()
b.sort()
temp_a = Counter(a)
#print(temp_a)
temp_b = Counter(b)
#print(temp_b)
p = temp_a.most_common()[0][0]
q = temp_b.most_common()[0][0]
if p == 0 and q == 0:
    p1 = temp_a.most_common()[1][0]
    q1 = temp_a.most_common()[1][0]
    if p1 < q1:
        p = p1
    else:
        q = q1
#print(p)
#print(q)
cost = 1
pre_a = AB[0][0]
pre_b = AB[0][1]
for j in AB[1:]:
    a = int(j[0])
    b = int(j[1])
    if a-p == pre_a and b-q == pre_b:
        pre_a = a
        pre_b = b
        continue
    else:
        cost += 1
        pre_a = a
        pre_b = b
print(cost)

Submission status: Wrong Answer

Solution code:
import sys
from itertools import combinations
from collections import defaultdict

sys.setrecursionlimit(100000000)

class UnionFind(object):
    def __init__(self, N):
        self._parent = list(range(N))
        self.__num_components = [1] * N

    def root(self, x):
        if self._parent[x] == x:
            return x
        else:
            # root abbreviation
            self._parent[x] = self.root(self._parent[x])
            return self._parent[x]

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

    def num_connected(self, x):
        return self.__num_components[self.root(x)]

    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if (x == y):
            return
        rank_x = self.__num_components[x]
        rank_y = self.__num_components[y]
        if rank_x < rank_y:
            self._parent[x] = y
            self.__num_components[y] += rank_x
        else:
            self._parent[y] = x
            self.__num_components[x] += rank_y
        return


fin = sys.stdin.readline

N = int(fin())
coordinates = [[int(elem) for elem in fin().split()] + [i] for i in range(N)]

# p, qのペアを計算
all_dists = defaultdict(list)
for each_pair in combinations(coordinates, 2):
    each_p = each_pair[0][0]-each_pair[1][0]
    each_q = each_pair[0][1] - each_pair[1][1]
    if each_p < 0:
        each_p = -each_p
        each_q = -each_q
    if each_p * each_q == 0:
        each_p = abs(each_p)
        each_q = abs(each_q)
    each_pq = (each_p, each_q)
    all_dists[each_pq].append([each_pair[0][2], each_pair[1][2]])

# 適当にスタート，探索を行う
count_list = [1]
for each_pq in all_dists:
    uf = UnionFind(N)
    for x, y in all_dists[each_pq]:
        uf.unite(x, y)
    num_distinct_components = 0
    for i in range(N):
        if uf.root(i) == i:
            num_distinct_components += 1
    count_list.append(num_distinct_components)

print(min(count_list))

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 :
            if q < 0 :
                q = -q
            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 :
            if p < 0 :
                p = -p
                q = -q
            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 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([xy[i][0] - xy[j][0], 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)

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    n, k = LI()
    a = n - k
    if k == 1:
        print(0)
        return
    print(a)
    return

#B
def B():
    n = II()
    xy = LIR(n)
    if n == 1:
        print(1)
        return
    ans = inf
    for i in range(n):
        for k in range(n):
            if i != k:
                b = 1
                check = []
                check.append((i,k))
                p = xy[i][0] - xy[k][0]
                q = xy[i][1] - xy[k][1]
                for l in range(n):
                    for m in range(n):
                        if b > ans:
                            break
                        if not((l,m) in check) and p == xy[l][0] - xy[m][0] and q == xy[l][1] - xy[m][1]:
                            b += 1
                            check.append((l, m))
                ans = min(ans, n-b)
    print(ans)

    return

#C
def C():
    m = II()
    a = LI()
    a.sort()
    check = [0] * m
    anslis = []
    ans = 0
    if m % 2:
        ans += a[m // 2]
        for i in range(m//2):
            anslis.append((a[i], a[-1 - i]))
            anslis.append((ans,-a[-1 - i]+a[i]))
            ans += a[-1 - i] - a[i]
    else:
        ans += a[m//2] - a[m//2-1]
        for i in range(m//2-1):
            anslis.append((a[i], a[-1 - i]))
            anslis.append((ans,-a[-1 - i]+a[i]))
            ans += a[-1 - i] - a[i]
    print(ans)
    for a, b in anslis:
        print(a,b)
    return

#D
def D():
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == '__main__':
    B()

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 :
            if q < 0 :
                q = -q
            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 :
            if p < 0 :
                p = -p
            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:
#!/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 = [abs(x[i+1]-x[i]) for i in range(N-1)]
    sy = [abs(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


N = int(input())
p = []
dic = {}
sameX = {}
allNum = []

for i in range(N):

    x,y = map(int,input().split())

    p.append([x,y])

    allNum.append(i)


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

for i in range(N):

    for j in range(i):

        ji = [j,i]
        

        if p[j][0] - p[i][0] != 0:

            a = ( p[j][1] - p[i][1] ) / ( p[j][0] - p[i][0] )
            b = p[j][1] - ( a * p[j][1] )

            if a == -0.0:
                a = 0.0
            
            ab = [a,b]

            if ( str (ab) )  in dic:
                dic[ str (ab) ].append(ji)

            else:
                dic[ str(ab) ] = [ji]

        elif p[j][0] - p[i][0] == 0:

            if p[j][0] in sameX:
                sameX[ p[j][0] ].append(ji)
            else:
                sameX[ p[j][0] ] = [ji]
            

#print  (dic,sameX)
        

DorS = 0
maxi = 0
keys = ""
ans = 0

while len(allNum) > 0:

    DorS = 0
    maxi = 0
    keys = ""

    for i in dic:
        
        eable = {}
        
        for j in dic[i]:

            if j[0] in allNum:
                eable[j[0]] = 1
            if j[1] in allNum:
                eable[j[1]] = 1            
                

        if len(eable) > maxi:

            
            DorS = 0
            maxi = len(dic[i])
            keys = i

    for i in sameX:

        eable = {}

        for j in sameX[i]:

            if j[0] in allNum:
                eable[j[0]] = 1
            if j[1] in allNum:
                eable[j[1]] = 1            

        if len(eable) > maxi:

            DorS = 1
            maxi = len(sameX[i])
            keys = i


    if DorS == 0:

        delPs = dic[keys]
        del dic[keys]

    else:

        delPs = sameX[keys]
        del sameX[keys]


    #print (delPs)

    rmFlag = False

    for i in delPs:

        if i[0] in allNum :
            allNum.remove(i[0])
            rmFlag = True

        if i[1] in allNum :
            allNum.remove(i[1])
            rmFlag = True

    if rmFlag :
        ans += 1

    #print (allNum)


print (ans)

Submission status: Wrong Answer

Solution code:
import fractions
N = int(input())
sheet = []
for i in range(N):
  line = input().split()
  sheet+=[(int(line[0]), int(line[1]))]
dic = {}
for i in range(N):
  start = sheet[i]
  for j in range(i+1, N):
    vec = [(sheet[j][0]-start[0]), (sheet[j][1]-start[1])]
    size = fractions.gcd(vec[0],vec[1])
    vec[0] = vec[0]//size
    vec[1] = vec[1]//size
    vec = tuple(vec)
    if vec not in dic.keys():
      dic[vec] = set([j])
    else:
      dic[vec].add(j)
m = 0
for s in dic.values():
  if len(s)>m:
    m = len(s)
if m==1:
  print(N)
else:
  print(N-m)

Submission status: Wrong Answer

Solution code:
N = int(input())
list1 = []
list2 = [0] * 2

for i in range(N):
    tmp1, tmp2 = map(int, input().split())
    list2[0] = tmp1
    list2[1] = tmp2
    list1.append(list2.copy())

list1.sort()
tmplist = []
tmp1 = list1[0][0]
tmp2 = list1[0][1]
for i in range(1, N):
    x1 = list1[i][0]
    y1 = list1[i][1]
    int1 = -(tmp1 - list1[i][0])
    int2 = -(tmp2 - list1[i][1])
    tmp1 = list1[i][0]
    tmp2 = list1[i][1]
    tmplist.append(str(int1) + ','+ str(int2))

maxcnt = -1
for i in range(len(tmplist)):
    maxcnt = max(maxcnt, tmplist.count(tmplist[i]))

tmp1list = []
tmp1 = list1[0][0]
tmp2 = list1[0][1]
for i in range(1, N):
    x1 = list1[i][0]
    y1 = list1[i][1]
    if x1 != list1[i][0]:
        int1 = -(tmp1 - list1[i][0])
        int2 = -(tmp2 - list1[i][1])
        tmp1 = list1[i][0]
        tmp2 = list1[i][1]
        tmp1list.append(str(int1) + ','+ str(int2))

for i in range(len(tmp1list)):
    maxcnt = max(maxcnt, tmplist.count(tmp1list[i]))

print(N - maxcnt)