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:
n=int(input())
x=[]
y=[]
sm=[]
count=1
for _ in range(n):
    xi,yi=map(int,input().split())
    smi=xi+yi
    x.append(xi)
    y.append(yi)
    sm.append(smi)

for i in range(n-2):
    if sm[i]!=sm[i+1]:
        if x[i+1]-x[i]==x[i+2]-x[i+1] and y[i+1]-y[i]==y[i+2]-y[i+1]:
            count+=0
        else:
            count+=1
    else:
        count+=0
print(count)

Submission status: Wrong Answer

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

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


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


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


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


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


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


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


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


def mt(f):
    import time

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

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

    return wrap


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

    ans = 0
    for _, v in c.items():
        tmp = set()
        for x, y in v:
            tmp.add(x)
            tmp.add(y)
        ans = max(ans, len(v))
    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()

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

for i, item in enumerate(combo):
    x_dif = item[0][0] - item[1][0]
    y_dif = item[0][1] - item[1][1]
    diff[i] = [x_dif, y_dif]

count_list = [0] * len(diff)
for k, d in enumerate(diff):
    p = d[0]
    q = d[1]
    count = 0
    for i in range(0, len(X_Y) - 1):
        if (X_Y[i][0] == X_Y[i + 1][0] + p) and X_Y[i][1] == X_Y[i + 1][1] + q:
            count += 0
        else:
            count += 1
    count_list[k] = count
print(min(count_list) + 1)

Submission status: Wrong Answer

Solution code:
n=int(input())
l=[tuple(map(int,input().split())) for i in range(n)]
l.sort(key=lambda x:x[0])
s=set()
fa=n-1
for i in range(n):
    for j in range(i+1,n):
        x,y=sorted([l[i],l[j]],key=lambda x:x[0])
        p=l[j][0]-l[i][0]
        q=l[j][1]-l[i][1]
        s=set(l)
        ans=n
        for x,y in l:
            if((x+p,y+q) in s):
                ans-=1
        fa=min(fa,ans)
print(fa)

Submission status: Wrong Answer

Solution code:
import numpy as np
N = int(input())
x = np.zeros(N)
y = np.zeros(N)

for i in range(N):
    x[i], y[i] = map(int, input().split())
for j in range(N-1):
    for k in range(N-1):
        if x[k] > x[k + 1]:
            x[k], y[k] = x[k + 1], y[k + 1]
        if x[k] == x[k + 1] and y[k] > y[k + 1]:
            x[k], y[k] = x[k + 1], y[k + 1]

ans = np.full(N * N, N)
ite = 0
for m in range(N):
    for p in range(m):
        diff_x = x[m] - x[p]
        diff_y = y[m] - y[p]
        for q in range(N):
            for r in range(q):
                if x[q] - x[r] == diff_x and y[q] - y[r] == diff_y:
                    ans[ite] -= 1
        ite += 1
ans_min = ans[0]
for z in range(ite):
    if ans_min > ans[z]:
        ans_min = ans[z]

print("{}".format(ans_min))

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


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

	print(N-tmp)



if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
import numpy as np

n = int(input())

A = []

for i in range(n):
    A.append(list(map(int, input().split())))

A = np.array(A)

X = np.eye(n, k = 1, dtype = int)
X[n-1, 0] = 1

B = []
a = np.copy(A)

for i in range(n-1):
    a = np.dot(X, a)
    B.append(A - a)

B = np.array(B)

B = np.reshape(B, (-1, 2))

B = B[np.argsort(B[:, 1])]
B = B[np.argsort(B[:, 0])]

c = 1
max_cont = 0
for i in range(1, B.shape[0]):
    if B[i][0] == B[i-1][0] and B[i][1] == B[i-1][1]:
        c += 1
    elif c > max_cont:
        max_cont = c
        c = 1
    else:
        c =1

print(n - max_cont)

Submission status: Wrong Answer

Solution code:
# coding: UTF-8
import sys
#sys.setrecursionlimit(n)
import heapq
import re
import bisect
import random
import math
import itertools
from collections import defaultdict, deque
from copy import deepcopy
from decimal import *

readl= lambda: list(map(int, sys.stdin.readline().split()))
readt= lambda: tuple(map(int, sys.stdin.readline().split()))
read = lambda: sys.stdin.readline().rstrip()
readi = lambda: int(read())
readmi = lambda: map(int, sys.stdin.readline().split())
readms = lambda: map(str, sys.stdin.readline().split())

n = readi()
a = []
b = []
if n == 1:
    print(1)
    exit()
for i in range(n):
    x, y = readmi()
    a.append([x,y])
    b.append([y,x])
a.sort()
b.sort()
aa = defaultdict(int)
bb = defaultdict(int)
cc = defaultdict(int)
dd = defaultdict(int)
old1 = 0
old2 = 0
flg = True
for i in range(n - 1):
    aa[(a[i + 1][0] - a[i][0], a[i + 1][1] - a[i][1])] += 1
    bb[(b[i + 1][0] - b[i][0], b[i + 1][1] - b[i][1])] += 1
    cc[(-a[i + 1][0] + a[i][0], -a[i + 1][1] + a[i][1])] += 1
    dd[(-b[i + 1][0] + b[i][0], -b[i + 1][1] + b[i][1])] += 1
aaa = sorted(aa.items(), key=lambda x:x[1], reverse=True)
bbb = sorted(bb.items(), key=lambda x:x[1], reverse=True)
ccc = sorted(cc.items(), key=lambda x:x[1], reverse=True)
ddd = sorted(dd.items(), key=lambda x:x[1], reverse=True)
print(n - max(aaa[0][1],bbb[0][1],ccc[0][1],ddd[0][1]))

Submission status: Wrong Answer

Solution code:
import copy
import sys
sys.setrecursionlimit(50000)
N = int(input())
C = [[int(i) for i in input().split()] for i in range(N)]
pq_list = []
score = 50
def jump(p, q, now, cost, ball_list):
    a = ball_list[now][0]
    b = ball_list[now][1]
    ball_list.pop(now)
    if(len(ball_list) == 0):
        return(cost)
    for i in range(len(ball_list)):
        if(ball_list[i][0] == a + p and ball_list[i][1] == b + q):
            return jump(p, q, i, cost, ball_list)
    else:
        for j in range(len(ball_list)):
            return jump(p, q, j, cost+1, ball_list)
        
for i in range(N):
    for j in range(N):
        if(i == j):
            continue
        p = C[i][0] - C[j][0]
        q = C[i][1] - C[j][1]
        pq_list.append([p, q])

for i in range(N):
    for j in range(len(pq_list)):
        p = pq_list[j][0]
        q = pq_list[j][1]
        ball_list = copy.copy(C)
        result = jump(p, q, i, 1, ball_list)
        score = min(score, result)

print(score)

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
cnt=0
for i in range(N-1):
    #p=x[i+1]-x[i]
    #q=y[i+1]-y[i]
    p=dic[i+1][0]-dic[i][0]
    q=dic[i+1][1]-dic[i][1]
    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:
#XY = [[1,2],[1,1],[2,2],[2,1]]
N=int(input())
XY =  [list(map(int, input().split())) for _ in range(N)]
cnt = 1
n=0
for i in range(N-1):
    xy = XY.pop(n)
    #print(XY)
    flag = False
    for k in range(len(XY)):
        if xy[0] != XY[k][0] and xy[1] != XY[k][1]:
            n = k
            #print("aa")
            flag=True
            break
    if flag ==False:
        #print("bb")
        cnt +=1
        n=-1
print(cnt)

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_key = sorted(tilt_map.items(), key=lambda x: x[1], reverse=True)[0][0]
    idx = most_key.index(":")
    m_dx = int(most_key[:idx])
    m_dy = int(most_key[idx+1:])

    if m_dx == 0:
        if m_dy < 0:
            m_dy *= -1
        xy.sort(key=lambda x: x[1])
    else:
        if m_dx < 0:
            m_dx *= -1
            m_dy *= -1
        xy.sort(key=lambda x: x[0])

    pos = xy.pop(0)
    cost = 1

    while len(xy) > 0:
        next_x = pos[0] + m_dx
        next_y = pos[1] + m_dy
        isNext = False
        for _xy in xy[::]:
            if _xy[0] == next_x and _xy[1] == next_y:
                xy.remove([next_x, next_y])
                pos = [next_x, next_y]
                isNext = True
                break
        if not isNext:
            pos = xy.pop(0)
            cost += 1
    print(cost)

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(k):
                    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:
n = int(input())
cost = 1
x = [0] * n
y = [0] * n
for i in range(n):
    x[i], y[i] = map(int, input().split())
x.sort()
y.sort()
for i in range(1, n):
    if x[i] == x[0] or y[i] == y[0]:
        cost += 1

print(cost)

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

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

memo = False
ans = int(1e9+7)
for x, y in diff:
  if x == 0 or y == 0:
    continue
  cost = 1
  for X, Y in XY:
    if not memo:
      memo = (X, Y)
      continue
    if (X - x, Y - y) == memo:
      pass
    else:
      cost += 1
    memo = (X, Y)
  ans = min(cost, ans)
  memo = False
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)
	nai3 = gess4[(p,q)]


	tmp = max(nai, nai2, nai3)

	print(N-tmp)



if __name__ == "__main__":
	main()

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)))):
        ans.append(L.count(LL))
    print(n - max(ans))

Submission status: Wrong Answer

Solution code:
def main():
    num = int(input())
    data = [list(map(int, input().split())) for i in range(num)]


    ans = num
    for i in range(num):
        for j in range(num):
            if i == j:
                continue

            now_kyori = [data[i][0] - data[j][0], data[i][1] - data[j][1]]
            visit_list = [0 for i in range(num)]
            visit_list[i], visit_list[j] = 1, 1

            kari_num = 1

            for k in range(num):
                if visit_list[k]:
                    continue

                now_data = data[k]

                flg = 1
                for l in range(num):
                    if visit_list[l]:
                        a = data[l][0] - now_data[0]
                        b = data[l][1] - now_data[1]

                        if [a, b] == now_kyori or [-a, -b] == now_kyori:
                            flg = 0

                        # if now_kyori[0] == 0 and now_kyori[1] == 0:
                        #     if a == now_kyori[0] and b == now_kyori[0]:
                        #         flg = 0
                        # elif now_kyori[0] == 0:
                        #     if a == now_kyori[0] and b % now_kyori[1] == 0:
                        #         if b + now_kyori[1] == 0 or b - now_kyori[1] == 0:
                        #             flg = 0
                        # elif now_kyori[1] == 0:
                        #     if b == now_kyori[1] and a % now_kyori[0] == 0:
                        #         if a + now_kyori[0] == 0 or a - now_kyori[0] == 0:
                        #             flg = 0
                        # else:
                        #     if a % now_kyori[0] == 0 and b % now_kyori[1] == 0:
                        #         if a // now_kyori[0] == b // now_kyori[1]:
                        #             if a + now_kyori[0] == 0 or a - now_kyori[0] == 0:
                        #                 flg = 0
                        if flg == 0:
                            break

                if flg:
                    kari_num += 1
                visit_list[k] = 1


            ans = min(kari_num, ans)

    print(ans)






if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

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


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


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


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


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


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


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


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


def mt(f):
    import time

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

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

    return wrap


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

    ans = 0
    for _, v in c.items():
        tmp = set()
        for x, y in v:
            tmp.add(x)
            tmp.add(y)
        ans = max(ans, len(v))
        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()

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 abs(l[i][0])==abs(l[j][0]) and abs(l[i][1])==abs(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:
import bisect
from operator import itemgetter
import math
import collections
import functools
import itertools
import numpy as np
import sys
MAX_INT = int(10e10)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N = I()
xy = [IL() for i in range(N)]

if N == 1:
  print(0)
elif N == 2:
  print(1)
else:
  data = []
  cnt = 0
  for i in itertools.combinations(xy,2):
    rex,rey = i[0]
    x,y = i[1]
    if rex > x:
      rex,rey,x,y = x,y,rex,rey
    data.append(str(x-rex)+str(y-rey))
  else:
    d = collections.Counter(data)
    cnt = max(cnt,d.most_common()[0][1])
  
  print(N-cnt)

Submission status: Wrong Answer

Solution code:
import sys

N = int(input())

if N == 1:
    print(1)

coor = []
for i in range(N):
    (x,y) = (int(i) for i in input().split())
    coor.append((x,y))
    
diffs = []
for i in range(N-1):
    for j in range(i+1, N):
        diffs.append((coor[j][0]-coor[i][0], coor[j][1]-coor[i][1]))
    
m = 1

for i in range(N-1):
    times = 0
    for j in range(N-1):
        if diffs[i] == diffs[j]:
            times += 1
    if times > m:
        m = times

ans = N - 1 - m   

if N - 1 - m > 1:
    print(ans)
else:
    print(1)

Submission status: Wrong Answer

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

sabun_dict = {}

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

for i in range(1, n):
  for j in range(i):
    x = point_list[i][0] - point_list[j][0]
    y = point_list[i][1] - point_list[j][1]
    if (x, y) in sabun_dict:
      sabun_dict[(x, y)] = sabun_dict[(x, y)] + 1
    else:
      sabun_dict[(x, y)] = 1

max_v = max(sabun_dict.values())

print(n - max_v)

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

p, q = sorted(list(c(inclination).items()),
              key=lambda x: (x[1], -x[0][0]))[-1][0]

cnt_zero = 0
flag = [False]*N
for i in range(N):
    for j in range(i+1, N):
        if not flag[j] and XY[j][0] - XY[i][0] == p and XY[j][1] - XY[i][1] == q:
            cnt_zero += 1

print(N-cnt_zero)

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np

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

matrix = [input().split() for l in range(n)]
min_cost = 60

for i in range(n):
    count = 0
    # matrix[i][0] matrix[i][1] を通る
    slope_list = []
    for j in range(n):
        if i == j:
            count += 1
        elif matrix[i][0] == matrix[j][0]:
            slope_list.append(10^10)
        else:
            slope_list.append((int(matrix[i][1])-int(matrix[j][1]))/(int(matrix[i][0])-int(matrix[j][0])))
    # 同じ数のものをカウント
    len_list = len(slope_list)
    for x in list(set(slope_list)):
        tmp_slope_list = [a for a in slope_list if a != x]
        if len_list > len(tmp_slope_list):
            len_list = len(tmp_slope_list)
    count += len_list
    if min_cost > count:
        min_cost = count

print(count)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
N = int(input())
Xs = []
Ys = []
za = []


for i in range(N):
    x,y = list(map(int, input().split(" ")))
    Xs.append(x)
    Ys.append(y)
    za.append((x,y))
if N == 1:
    print(1)
    exit()
za.sort(key=lambda x:x[0])
dix = defaultdict(lambda :0)
diy = defaultdict(lambda :0)
for i,z in enumerate(za[1:]):
    x = z[0]
    before = za[i][0]
    tempx = x -before
    y = z[1]
    before = za[i][1]
    tempy =  y -before
    diy[(tempx,tempy)] += 1

ymax = max(diy.values())
cand = [N - ymax]


za.sort(key=lambda x:x[1])
dix = defaultdict(lambda :0)
diy = defaultdict(lambda :0)
for i,z in enumerate(za[1:]):
    x = z[0]
    before = za[i][0]
    tempx = x -before
    y = z[1]
    before = za[i][1]
    tempy =  y -before
    diy[(tempx,tempy)] += 1

ymax = max(diy.values())
cand.append(N - ymax)


print(min(cand))

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 = (-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:
# 何本の数直線上にあるかを求める　1<=ans<=n-1
n=int(input())
xy=[list(map(int,input().split())) for _ in range(n)]
# xy.sort(key=lambda x:x[0])
# print(xy)
if n==1:
    print(1)
else:
    diff=[]
    for i in range(n):
        for j in range(i):
            diff.append((xy[i][0]-xy[j][0],xy[i][1]-xy[j][1]))

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

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 == 0:
    print(N - 1)
else:
    print(N - ans + 1)