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:
#!/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[0],x[1]), 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)


    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
from itertools import combinations

def main():
    input = sys.stdin.readline
    N = int(input())
    cord = set()
    for _ in range(N):
        x, y = map(int, input().split())
        cord.add((x, y))

    ans = 50
    for a in combinations(cord, 2):
        x1, y1 = a[0]
        x2, y2 = a[1]

        p = x2 - x1
        q = y2 - y1

        cnt1 = 0
        cnt2 = 0

        for x, y in cord:
            if (x - p, y - q) not in cord:
                cnt1 += 1

            if (x + p, y + q) not in cord:
                cnt2 += 1

        ans = min(ans, cnt1, cnt2)

    return ans


if __name__ == '__main__':
    print(main())

Submission status: Wrong Answer

Solution code:
N = int(input())
if N == 1:
    print(1)
    exit()
D = []
for i in range(N):
    x, y = map(int, input().split())
    D.append((i, x, y))
D = sorted(D)

d = set()
for i in range(N):
    for j in range(N):
        d.add((D[i][0] - D[j][0], D[i][1] - D[j][1]))


d = list(d)
num = float('inf')
for p, q in d:
    if p == 0 and q == 0:
        continue
    for y in range(N):
        used = [0] * N
        prex, prey = D[y][0], D[y][1]
        used[y] = 1
        tmp = 1

        for k in range(N - 1):
            for i in range(N):
                if used[i]:
                    continue
                if D[i][0] - prex == p and D[i][1] - prey == q:
                    prex = D[i][0]
                    prey = D[i][1]
                    used[i] = 1
                    break
            else:
                tmp += 1
                for i in range(N):
                    if not used[i]:
                        prex = D[i][0]
                        prey = D[i][1]
                        used[i] = 1
                        break
        num = min(tmp, num)

print(num)

Submission status: Wrong Answer

Solution code:
N = int(input())
xy = [list(map(int,input().split())) for i in range(N)]
cst_p = 1
cst_q = 1
xy.sort(key = lambda x:x[0])
keep = xy[0]
if N != 1:
    p = xy[1][0]-xy[0][0]
    q = xy[1][1]-xy[0][1]
    for i in range(1,N-1):
        if not(xy[i][0] == keep[0]+p and xy[i][1] == keep[1]+q):
            cst_p += 1
            keep = xy[i]
        else:
            keep = xy[i]
    if not(xy[N-1][0] == keep[0]+p and xy[N-1][1] == keep[1]+q):
        cst_p+= 1
else:
    print(1)
    exit()

xy.sort(key = lambda x:x[1])
keep = xy[0]
if N != 1:
    p = xy[1][0]-xy[0][0]
    q = xy[1][1]-xy[0][1]
    for i in range(1,N-1):
        if not(xy[i][0] == keep[0]+p and xy[i][1] == keep[1]+q):
            cst_q+= 1
            keep = xy[i]
        else:
            keep = xy[i]
    if not(xy[N-1][0] == keep[0]+p and xy[N-1][1] == keep[1]+q):
        cst_q += 1
else:
    print(1)
    exit()

print(min(cst_p,cst_q))

Submission status: Wrong Answer

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


ans = 0
res = []
for i in range(N):
    for j in range(N):
        if i == j:
            continue
        x1, y1 = items[i]
        x2, y2 = items[j]
        res.append((abs(x1-x2), abs(y1 -y2)))

for i in range(len(res)):
    x, y = res[i]
    cnt = 0
    for j in range(len(res)):
        if i == j:
            continue
        if x == res[j][0] and y == res[j][1]:
            cnt += 1
    ans = max(ans, cnt)

if ans == 1:
    print(N - 1)
else:

    if ans % 2 == 0:
        print(N - ans // 2)
    else:
        print(N - (ans // 2 + 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 == 1:
    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, tmp1) in L_dict:
            L_dict[(tmp0, tmp1)] += 1
        else:
            L_dict[(tmp0, tmp1)] = 1

    if max(L_dict.values()) == 1:
        print(n)
    else:
        ans = n - max(L_dict.values())
        print(ans)

Submission status: Wrong Answer

Solution code:

N = int(input())
xy = [list(map(int, input().split())) for i in range(N)]
xy.sort(key=lambda x: x[0], reverse=True)
tilt_map = {}

if N == 1:
    print(1)
else:
    for i in range(N):
        for j in range(i+1, N):
            a = xy[i]
            b = xy[j]
            tilt_x = a[0] - b[0]
            tilt_y = a[1] - b[1]
            if tilt_x == 0 and tilt_y == 0:
                continue
            key = str(tilt_x) + ":" + str(tilt_y)
            if key in tilt_map:
                tilt_map[key] += 1
            else:
                tilt_map[key] = 1


    most_tilt = sorted(tilt_map.items(), key=lambda x: x[1], reverse=True)[0][1]
    print(N-most_tilt)

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

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

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

print(min(costX, costY))

Submission status: Wrong Answer

Solution code:
from itertools import*
from math import*
from collections import*
from heapq import*
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf = float("inf")
mod = 10**9+7
from functools import reduce
import sys
sys.setrecursionlimit(10**7)

N = int(input())
pair=defaultdict(int)
xy = []
for i in range(N):
    x,y = map(int,input().split())
    xy.append((x,y))
for i in range(N-1):
    for j in range(i+1,N):
        pair[(xy[j][0]-xy[i][0],xy[j][1]-xy[i][1])] += 1

m = 0
for v in pair.values():
    m = max(m,v)
print(N-m)

Submission status: Wrong Answer

Solution code:
n=int(input())

x=list()
y=list()
for i in range(n):
  xt,yt = map(int,input().split())
  x.append(xt)
  y.append(yt)
  
z=1
t=[]
for i in range(n):
  zz=0
  for j in range(n):
    if i != j:
      if x[i] == x[j]:
        zz+=1
      else:
        t.append((y[j] - y[i])/(x[j] - x[i]))
  #print(t,set(t))
  if zz > 0 :
    zz-=1
  z=max(z,len(set(t))+zz)
  t.clear()
  
print(z)

Submission status: Wrong Answer

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

# define p,q
for c_ in c:
    if c_[0] != c[0][0]:
        p = c_[0] - c[0][0]
        q = c_[1] - c[0][1]
        break

cost = 1
counter = 0
for i in reversed(c):
    if counter == 0:
        even = i
        counter += 1
        continue
    else:
        even_ = (even[0]-p, even[1]-q)
        if even_ == i:
            even = i
            continue
        else:
            cost += 1

print(cost)

Submission status: Wrong Answer

Solution code:
import collections
N = int(input())
alllist = []
minaslist = []

if N == 1:
    print("1")
else:
    for i in range(N):
        a,b = map(int,input().split())
        alllist.append([a,b])

    alllist.sort()

    for i in range(N-1):
        minaslist.append((alllist[i+1][0]-alllist[i][0])**2 - (alllist[i+1][1]-alllist[i][1])**2)



    countdict = collections.Counter(minaslist)

    lista = list(countdict.most_common())
    mostnum = lista[0][1]

    print(len(minaslist) - mostnum + 1)

Submission status: Wrong Answer

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

count = []

for i in range(1, n):
    a_p = xy[i][0] - xy[i-1][0]
    b_q = xy[i][1] - xy[i-1][1]
    count.append([a_p, b_q])

from collections import Counter
ans = Counter(tuple(item) for item in count)
print(len(ans))

Submission status: Wrong Answer

Solution code:
N = int(input())

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

X = sorted(XY, key=lambda x: x[0])



def dfs(current, diff, counter):
    ans = [counter]
    x0, y0 = X[current]
    if diff == None:
        for i, (x1,y1) in enumerate(X[current+1:]):
            diff = (x1-x0,y1-y0)
            ans.append(dfs(current+1+i, diff, counter))
    else:
        for i, (x1,y1) in enumerate(X[current+1:]):
            tmp_diff = (x1-x0,y1-y0)
            #print(diff, tmp_diff)
            if tmp_diff == diff:
                ans.append(dfs(current+1+i, diff, counter+1))
            else:
                ans.append(dfs(current+1+i, diff, counter))
    return max(ans)

count_list = []
for i in range(N):
    count_list.append(dfs(i, None, 1))

#print(count_list)
ans = N-max(count_list)
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)]

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

	print(N-tmp)



if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
import sys
from fractions import gcd
N = int(input())
arr = []

def get_unique_list(seq):
    seen = []
    return [x for x in seq if x not in seen and not seen.append(x)]

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

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

C = []
for i in range(N):
    for j in range(N):
        if i < j:
            x = arr[i][0]-arr[j][0]
            y = arr[i][1]-arr[j][1]
            g = gcd(x, y)
            x = int(x / g)
            y = int(y / g)
            C.append([x, y])

C = get_unique_list(C)
S = [0 for i in range(len(C))]

for c in range(len(C)):
    tmp = [[arr[0][0], arr[0][1]]]
    for i in range(1, N):
        l = len(tmp)
        for j in range(l):
            if C[c][0] == 0:
                if (tmp[j][1] - arr[i][1])%C[c][1] == 0:
                    pass
                else:
                    tmp.append([arr[i][0], arr[i][1]])

            elif C[c][1] == 0:
                if (tmp[j][0] - arr[i][0])%C[c][0] == 0:
                    pass
                else:
                    tmp.append([arr[i][0], arr[i][1]])
            else:
                if (tmp[j][0] - arr[i][0])%C[c][0] == 0 and (tmp[j][1] - arr[i][1])%C[c][1] == 0:
                    pass
                else:
                    tmp.append([arr[i][0], arr[i][1]])
    S[c] = len(tmp)

print(min(S))

Submission status: Wrong Answer

Solution code:
from operator import itemgetter
import itertools

n = int(input())
xy = [list(map(int, input().split())) for i in range(n)]
sa = {}
for i in itertools.combinations(xy, 2):
    a, b = i
    c = ",".join([str(b[0] - a[0]), str(b[1] - a[1])])
    if c not in sa:
        sa[c] = 1
    else:
        sa[c] += 1
ans_1 = 0
for i in sa.values():
    ans_1 = max(ans_1, i)


xy = sorted(sorted(xy, key=itemgetter(0)), key=itemgetter(1))
a = {}
last = []
for i in range(n):
    if i != 0:
        b = ",".join([str(xy[i][0] - last[0]), str(xy[i][1] - last[1])])
        if b not in a:
            a[b] = 1
        else:
            a[b] += 1
    last = xy[i]
ans = 0
for i in a.values():
    ans = max(ans, i)

xy = sorted(sorted(xy, key=itemgetter(1)), key=itemgetter(0))
a = {}
last = []
for i in range(n):
    if i != 0:
        b = ",".join([str(xy[i][0] - last[0]), str(xy[i][1] - last[1])])
        if b not in a:
            a[b] = 1
        else:
            a[b] += 1
    last = xy[i]
ans_ = 0
for i in a.values():
    ans_ = max(ans_, i)
print(n - max(ans, ans_, ans_1))

Submission status: Wrong Answer

Solution code:
# 2019 6/15
# diverta 2019 B Picking Up

import sys

ball = []


def cal_cost(li, p, q, cost):
    if (li[i][0] == li[i-1][0] - p) and (li[i][1] == li[i-1][1] - q):
        return cost
    else:
        cost += 1
        return cost


def total_cost(li, p, q, cost):
    for i in range(1, len(li)):
        cost = cal_cost(li, p, q, cost)
    return cost


def cal_grad(li):
    count = 0
    count_x = 0
    count_y = 0
    for i in range(1, len(li)):
        a = li[i][0] - li[i-1][0]
        b = li[i][1] - li[i-1][1]
        if a == 0 or b == 0:
            continue
            # tmp = -2
            # for j in range(len(li)):
            #     if li[j][0] == 0:
            #         tmp += 1
            #         count = tmp
            #         count_x = 0
            #         count_y = b
        for j in range(len(li)):
            if j != i and j != i-1:
                tmp = 0
                if li[j][0] % a == li[i][0] % a and li[j][1] % b == li[i][1] % b:
                    tmp += 1
                if count < tmp:
                    count = tmp
                    count_x = a
                    count_y = b
    return count_x, count_y


if __name__ == '__main__':
    N = int(input())
    for i in range(N):
        ball.append(list(map(int, input().split())))

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

    p, q = cal_grad(ball)

    cost = total_cost(ball, p, q, 1)
    print(cost)

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]==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())
P = sorted([list(map(int, input().split())) for i in range(N)])
Z = set()
for x, y in P:
    Z.add((x, y))
X = []
ans = float('inf')
for i in range(N):
    for j in range(i + 1, N):
        xi, yi = P[i]
        xj, yj = P[j]

        p, q = (xj - xi), (yj - yi)
        X.append((p, q))

for p, q in X:
    hit = 0
    for x, y in P:
        if (x - p, y - q) in Z:
            hit += 1
    ans = min(ans, N - hit)
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
l = list()
for i in range(n):
  a,b = list(map(int,input().split()))
  l.append(a)
  l.append(b)
p = l[n*2-2]
q = l[n*2-1]

print(p-l[0],q-l[1])

Submission status: Wrong Answer

Solution code:
###template###
import sys
def input(): return sys.stdin.readline().rstrip()
def mi(): return map(int, input().split())
###template###
import collections

N = int(input())
XYs = [tuple(mi()) for _ in range(N)]

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

sa_list = []
import itertools
for (ax, ay), (bx, by) in itertools.combinations(XYs, 2):
  sa_list.append((ax-bx,ay-by) if ax-bx>=0 else (-(ax-bx),-(ay-by)))

#最も多い差の個数（これ-1を短縮できるはず）
#print(N-collections.Counter(sa_list).most_common()[0][1])

#最も多い差をタプルで受ける
mostcommon = collections.Counter(sa_list).most_common()[0][0]
#print(mostcommon)


#print(sa_list)
cnt = 0
ans = N #ここから引いていく
#aとbの差がmostcommonと一致したらvisitedに入れる
visited = [0] * N
for a in range(0, N):
  tmpsame = 0 #今見ているaと差が同じものの数
  for b in range(0, N):
    if a>=b or visited[b]: continue
    sa = sa_list[cnt]
    if sa == mostcommon:
#      print('same')
      ans -= 1
      visited[b] = 1
    cnt += 1
#    print(sa)

if len(sa_list)>=2:
  #次に多い差をタプルで受ける
  mostcommon = collections.Counter(sa_list).most_common()[1][0]
  cnt = 0
  ans2 = N #ここから引いていく
  #aとbの差がmostcommonと一致したらvisitedに入れる
  visited = [0] * N
  for a in range(0, N):
    tmpsame = 0 #今見ているaと差が同じものの数
    for b in range(0, N):
      if a>=b or visited[b]: continue
      sa = sa_list[cnt]
      if sa == mostcommon:
        ans2 -= 1
      cnt += 1
  print(min(ans, ans2))
else:
  print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
import statistics
import math
from collections import Counter
N=int(input())
x=[]
y=[]
for a in range(N):
    b,c=(int(x) for x in input().split())
    x.append(b)
    y.append(c)
sa=deque([[0,0]])
if N>1:
    for a in range(N):
        for b in range(N-a-1):
            sx=abs(x[a]-x[a+b+1])
            sy=abs(y[a]-y[a+b+1])
            sa.append([sx,sy])
    sa.remove([0,0])
    ans=[]
    nagasa=len(sa)
    for a in range(nagasa):
        xx,yy=sa.pop()
        ss=sa.count([xx,yy])
        ans.append(ss)
        if len(sa)==0:
            break
    kotae=max(ans)
    if N==2:
        print(1)
    elif kotae>0:
        print(N-kotae-1)
    else:
        print(N)

else:
    print(1)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import functools
import itertools

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

D = defaultdict(list)
for p1, p2 in itertools.combinations(P, 2):
    d = (p1[0] - p2[0], p1[1] - p2[1])
    if d[0] == 0 and d[1] == 0:
        continue
    elif d[0] == 0:
        d = (0, abs(d[1]))
    elif d[0] < 0:
        d = (-d[0], -d[1])
    for S in D[d]:
        if p1 in S:
            S.add(p2)
            break
        elif p2 in S:
            S.add(p1)
            break
    else:
        D[d].append({p1, p2})

ans = 50
for L in D.values():
    ans = min(ans, len(L) + N - functools.reduce(lambda x, S: x + len(S), L, 0))
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[0],x[1]), 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()]
    pm = [-1*i for i in p]
    q = [i for i,v in csy.most_common()]
    qm = [-1*i for i in q]
    p = p + pm
    q = q + qm
    p.sort()
    q.sort()
    # print(p)

    ans = 10000000000
    for i in p:
        for j in q:
            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:
#!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
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    n,k = LI()
    print(n%k)
    return

#B
def B():
    n = I()
    po = LIR(n)
    ans = float("inf")
    for i in range(n):
        for j in range(n):
            if i == j:continue
            x,y = po[i]
            s,t = po[j]
            p,q = s-x,t-y
            m = n
            for k in range(n):
                for l in range(n):
                    if (po[k][0]-po[l][0],po[k][1]-po[l][1]) == (p,q):m -= 1
            if m < ans:
                ans = m
    print(ans)
    return

#C
def C():
    n = I()
    a = LI()
    a.sort()
    if a[0] >= 0:
        print(sum(a)-2*a[0])
        for i in range(1,n-1):
            print(a[0],a[i])
            a[0] -= a[i]
        print(a[n-1],a[0])
    else:
        if a[-1] < 0:
            print(2*a[-1]-sum(a))
            for i in range(n-1):
                print(a[-1],a[i])
                a[-1] -= a[i]
        else:
            m = bisect.bisect_left(a,0)
            p = n-m
            ans = -sum(a[:m])+sum(a[m:])
            print(ans)
            if p > m:
                l = a[-1]
                a = a[:-1]
                a = a[::-1]
                p -= 1
                p,m = m,p
                k = a[m]-a[m-1]
                print(a[m],a[m-1])
                for i in range(p-1):
                    print(a[m-i-2],k)
                    k = a[m-i-2]-k
                    print(a[m+i+1],k)
                    k = a[m+i+1]-k
                for i in range(m-p):
                    print(k,a[i])
                    k -= a[i]
                print(l,k)
            else:
                k = a[m]-a[m-1]
                print(a[m],a[m-1])
                for i in range(p-1):
                    print(a[m-i-2],k)
                    k = a[m-i-2]-k
                    print(a[m+i+1],k)
                    k = a[m+i+1]-k
                for i in range(m-p):
                    print(k,a[i])
                    k -= a[i]
    return

#D
def D():
    n = I()

    return

#E
def E():
    n = I()

    return

#F
def F():
    n = I()

    return

#G
def G():
    n = I()

    return

#H
def H():
    n = I()

    return

#I
def I_():
    n = I()

    return

#J
def J():
    n = I()

    return

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

Submission status: Wrong Answer

Solution code:

from collections import defaultdict

def read_input():
    n = int(input())

    points = []
    for i in range(n):
        points.append(tuple(map(int, input().split())))

    return n, points


# calc p3 is on line made by p1 and p2
def check_on_line(p1, p2, p3):
    a = (p2[0] - p1[0], p2[1] - p1[1])
    b = (p3[0] - p1[0], p3[1] - p1[1])

    axb = a[0]*b[1] - a[1]*b[0]

    # on line
    if axb == 0:
        return True
    return False


def dist_point_to_point(p1, p2):
    return (p2[0] - p1[0], p2[1] - p1[1])


def submit():
    n, points = read_input()

    if n == 1:
        print(1)
        return

    p2p_dist = {}
    pd_list = defaultdict(list)
    for p1 in points:
        for p2 in points:
            if p1 == p2:
                continue
            p2p_dist[(p1, p2)] = dist_point_to_point(p1, p2)

            for p3 in points:
                if check_on_line(p1, p2, p3):
                    pd_list[(p1, p2p_dist[(p1, p2)])].append(p3)

    pq_list = list(set(p2p_dist.values()))

    min_line_c = 51
    for p, q in pq_list:
        line_c = 0
        point_c = 0
        used = {}
        for s in points:
            used[s] = False

        # print(p, q)
        for s in points:
            if used[s]:
                continue
            lines = pd_list[(s, (p, q))]

            if lines:
                for pl in lines:
                    if not used[pl]:
                        used[pl] = True
                        point_c += 1
            else:
                used[s] = True
                point_c += 1

            line_c += 1
            # print(used, line_c)

            if point_c == n:
                break

        if min_line_c > line_c:
            min_line_c = line_c

    print(min_line_c)

if __name__ == '__main__':
    submit()

Submission status: Wrong Answer

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


ans = 0
res = []
for i in range(N):
    for j in range(N):
        if i == j:
            continue
        x1, y1 = items[i]
        x2, y2 = items[j]
        res.append((abs(x1-x2), abs(y1 -y2)))

for i in range(len(res)):
    x, y = res[i]
    cnt = 0
    for j in range(len(res)):
        if i == j:
            continue
        if x == res[j][0] and y == res[j][1]:
            cnt += 1
    ans = max(ans, cnt)

if ans == 1:
    print(N - 1)
else:
    print(N - (ans // 2  + 1))