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

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

visited = set()
for b1, b2 in combinations(balls, 2):
    p, q = b1[0] - b2[0], b1[1] - b2[1]
    if p != 0 or q != 0:
        if (p, q) in visited:
            continue
        visited.add((p, q))
        sub = 0
        for ball in balls:
            bx, by = ball
            dx, dy = bx - b2[0], by - b2[1]
            if p != 0 and q != 0:
                if dx % p == 0 and dy % q == 0 and dx // p == dy // q:
                    sub += 1
            else:
                div, mod = None, None
                if p == 0:
                    div, mod = dy // q, dy % q
                else:
                    div, mod = dx // p, dx % p
                if div > 0 and mod == 0:
                    sub += 1
        if n - sub <= 1:
            sub -= 1
        cost = min(cost, n - sub)

print(cost)

Submission status: Wrong Answer

Solution code:
# Picking Up
# グラフ,有向グラフ,ベクトル, ２次元、コスト,

import itertools

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

candidates = itertools.permutations(S, 2)
for e in candidates:
    t_vec_x1 = e[1][0] - e[0][0]
    t_vec_y1 = e[1][1] - e[0][0]
    edge = 0
    for l,le in enumerate(S):
        for m, me in enumerate(S):
            if l == m:
                continue
            vec_x = me[0] - le[0]
            vec_y = me[1] - le[1]
            if t_vec_x1 == vec_x and t_vec_y1 == vec_y:
                edge += 1
    cost = min(cost, N - edge)

print(cost)

Submission status: Wrong Answer

Solution code:
import itertools
n=int(input())
ball=[]
for i in range(n):
    ball.append([int(i) for i in input().split()])

ball.sort()

# p,qの候補取得
pq_cand=set()
for v in itertools.combinations(ball,2):
    xdiff=v[0][0]-v[1][0]
    ydiff=v[0][1]-v[1][1]
    pq_cand.add((xdiff,ydiff))
    
cost=n-1
for pq in pq_cand:
    cost_tmp=0
    for point in ball:
        if [point[0]+pq[0],point[1]+pq[1]] not in ball:
            cost_tmp+=1
    cost=min(cost,cost_tmp)
print(cost)

Submission status: Wrong Answer

Solution code:
import itertools
n=int(input())
ball=[]
for i in range(n):
    ball.append([int(i) for i in input().split()])

ball.sort()

# p,qの候補取得
pq_cand=set()
for v in itertools.combinations(ball,2):
    xdiff=v[0][0]-v[1][0]
    ydiff=v[0][1]-v[1][1]
    pq_cand.add((xdiff,ydiff))
    
cost=n-1
for pq in pq_cand:
    cost_tmp=0
    for point in ball:
        if [point[0]+pq[0],point[1]+pq[1]] not in ball:
            cost_tmp+=1
    if cost_tmp>0:
        cost=min(cost,cost_tmp)
print(cost)

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
    if vec[0]<0:
      vec[0] = (-1)*vec[0]
      vec[1] = (-1)*vec[1]
    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)
print(N-m)

Submission status: Wrong Answer

Solution code:
from collections import deque
from collections import defaultdict
from copy import copy
N = int(input())
XY = list(sorted([tuple(map(int, input().split())) for _ in range(N)]))
PQ = []
for i in range(N-1):
    for j in range(i, N):
        PQ.append((XY[j][0]-XY[i][0], XY[j][1]-XY[i][1]))
PQ = list(set(PQ))
ans = N
for p, q in PQ:
    tmp1 = 1
    check = dict()
    T = deque(copy(XY))
    for x, y in T:
        check[(x, y)] = 0
    x, y = T.popleft()
    cnt = 1
    while cnt < N:
        tmp2 = 1
        for s, t in T:
            if check[(s, t)]:
                continue
            else:
                if s - p == x and t - q == y:
                    check[(s, t)] += 1
                    tmp2 = 0
                    break
        if tmp2:
            x, y = T.popleft()
        else:
            x, y = s, t
        tmp1 += tmp2
        cnt += 1      
    ans = min(ans, tmp1)
print(ans)

Submission status: Wrong Answer

Solution code:
# 未完成
import numpy as np
import sys
N = int(input())
x = np.zeros(N)
y = np.zeros(N)
kouholist = []
ans = N
if N == 1:
    print(1)
    sys.exit()

for i in range(N):
    x[i], y[i] = map(int, input().split())
for m in range(N):
    for p in range(N):
        if m == p:
            continue
        diff_x = x[m] - x[p]
        diff_y = y[m] - y[p]
        ans_kari = N
        for r in range(N):
            for q in range(N):
                if x[q] - x[r] == diff_x and y[q] - y[r] == diff_y:
                    ans_kari += 1
        if ans_kari < ans:
            ans = ans_kari

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

Submission status: Wrong Answer

Solution code:
n = int(input())
point = []
for i in range(n):
    x_, y_ = map(int, input().split())
    point.append([x_, y_])

point.sort(key=lambda x: x[0])
ans = 0
x = []
y = []
for i in range(n):
    x.append(point[i][0])
    y.append(point[i][1])

if n == 1:
    print(1)
    exit()
for i in range(n):
    for j in range(i+1, n):
        count = 0
        p = x[j] - x[i]
        q = y[j] - y[i]
        for k in range(n):
            for l in range(k+1, n):
                if (x[l] - x[k] == p) and (y[l] - y[k] == q):
                    count += 1
        ans = max(ans, count)

print(n - ans)

Submission status: Wrong Answer

Solution code:
import itertools
n=int(input())
ball=[]
for i in range(n):
    ball.append([int(i) for i in input().split()])

ball.sort()
    
# p,qの候補取得
pq_cand=set()
for v in itertools.combinations(ball,2):
    xdiff=abs(v[0][0]-v[1][0])
    ydiff=abs(v[0][1]-v[1][1])
    pq_cand.add((xdiff,ydiff))
    
connect=0
for pq in pq_cand:
    con=0
    for point in ball:
        if [point[0]+pq[0],point[1]+pq[1]] in ball:
            con+=1
    connect=max(connect,con)
print(n-connect)

Submission status: Wrong Answer

Solution code:
import itertools
n=int(input())
ball=[]
for i in range(n):
    ball.append([int(i) for i in input().split()])

ball.sort()
    
# p,qの候補取得
pq_cand=set()
for v in itertools.combinations(ball,2):
    xdiff=abs(v[0][0]-v[1][0])
    ydiff=abs(v[0][1]-v[1][1])
    pq_cand.add((xdiff,ydiff))
    
connect=0
for pq in pq_cand:
    con=0
    for point in ball:
        if [point[0]-pq[0],point[1]-pq[1]] in ball:
            con+=1
    connect=max(connect,con)
print(n-connect)

Submission status: Wrong Answer

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left, bisect_right
from copy import copy
inf=float('inf')
mod = 10**9+7
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():

    N = I()
    XY = LLIN(N)
    if N == 1:
        print(1)
        exit()

    count = defaultdict(int)
    for i, (x1, y1) in enumerate(XY):
        for j, (x2, y2) in enumerate(XY[i+1:]):
            dx, dy = x1 - x2, y1 - y2
            if dx < 0:
                dx *= -1
                dy *= -1
            count[(dx, dy)] += 1
    maxim = -inf
    for v in count.values():
        maxim=max(maxim,v)
    print(N - maxim)
    
    
                        
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
point = []
for i in range(n):
    x_, y_ = map(int, input().split())
    point.append([x_, y_])

point.sort(key=lambda x: x[0])
ans = 0
x = []
y = []
for i in range(n):
    x.append(point[i][0])
    y.append(point[i][1])

for i in range(n):
    for j in range(i+1, n):
        count = 0
        p = x[j] - x[i]
        q = y[j] - y[i]
        for k in range(n):
            for l in range(k+1, n):
                if (x[l] - x[k] == p) and (y[l] - y[k] == q):
                    count += 1
        ans = max(ans, count)

print(n - ans)

Submission status: Wrong Answer

Solution code:
import itertools
n=int(input())
ball=[]
for i in range(n):
    ball.append([int(i) for i in input().split()])

# p,qの候補取得
pq_cand=set()
for v in itertools.combinations(ball,2):
    xdiff=abs(v[0][0]-v[1][0])
    ydiff=abs(v[0][1]-v[1][1])
    pq_cand.add((xdiff,ydiff))
    
connect=0
for pq in pq_cand:
    con=0
    for point in ball:
        if [point[0]-pq[0],point[1]-pq[1]] in ball:
            con+=1
    connect=max(connect,con)
print(n-connect)

Submission status: Wrong Answer

Solution code:
import itertools
import collections
n=int(input())
s=[list(map(int, input().split())) for i in range(n)]
ans=[]
x=list(itertools.permutations(s))

if n==1:
    print(n)
else:
    v=[]
    r=[]
    for i in range(len(x)):
        e=[]
        v=[]
        for j in range(n-1):
            a=x[i][j][0]
            b=x[i][j+1][0]
            c=x[i][j][1]
            d=x[i][j+1][1]
            v.append(b-a)
            v.append(d-c) 
        q=[v[i:i+2] for i in range(0,len(v),2)]
        for i in range(len(q)):
            e.append(q.count(q[i]))
        r.append(max(e))
    print(n-max(r))
    print(r)

Submission status: Wrong Answer

Solution code:
# 未完成
import numpy as np
import sys
N = int(input())
x = np.zeros(N)
y = np.zeros(N)
kouholist = []
ans = []
if N == 1:
    print(1)
    sys.exit()

for i in range(N):
    x[i], y[i] = map(int, input().split())
for m in range(N):
    for p in range(N):
        if m == p:
            continue
        diff_x = x[m] - x[p]
        diff_y = y[m] - y[p]
        if (diff_x, diff_y) not in kouholist:
            kouholist.append((diff_x, diff_y))

for list_i in kouholist:
    ans_kari = 0
    for r in range(N):
        for q in range(N):
            if x[q] - x[r] == list_i[0] and y[q] - y[r] == list_i[1]:
                ans_kari += 1
    ans.append(ans_kari)

    print("{}".format(N-max(ans)))

Submission status: Wrong Answer

Solution code:
N=int(input())
po=[]
for i in range(N):
  po.append([int(i) for i in input().split()])
ds=[]
d2={}

for i in range(N):
  for j in range(i+1,N):
    ds.append(str(abs(po[i][0]-po[j][0]))+" "+str(abs(po[i][1]-po[j][1])))
if ds==[]:
	print(1)
else:
	for d in ds:
		if d in d2:
			d2[d]=d2[d]+1
		else:
			d2[d]=1
	d3=sorted(d2.values())[-1]
	print(N-d3)

Submission status: Wrong Answer

Solution code:
# 未完成
import numpy as np
import sys
N = int(input())
x = np.zeros(N)
y = np.zeros(N)
kouholist = []
ans = []
if N == 1:
    print(1)
    sys.exit

for i in range(N):
    x[i], y[i] = map(int, input().split())
for m in range(N):
    for p in range(N):
        if m == p:
            continue
        diff_x = x[m] - x[p]
        diff_y = y[m] - y[p]
        if (diff_x, diff_y) not in kouholist:
            kouholist.append((diff_x, diff_y))

for list_i in kouholist:
    ans_kari = 0
    for r in range(N):
        for q in range(N):
            if x[q] - x[r] == list_i[0] and y[q] - y[r] == list_i[1]:
                ans_kari += 1
    ans.append(ans_kari)

    print("{}".format(N-max(ans)))

Submission status: Wrong Answer

Solution code:
N = int(input())
x = []
y = []
for i in range(N):
    x1,y1=[int(i) for i in input().split()]
    x.append(x1)
    y.append(y1)
    
max_yuko = 0
for p in range(N+1):
    for q in range(N+1):
        yuko = 0
        for i in range(N):
            for j in range(N):
                if i != j:
                    sp = x[i] - x[j]
                    sq = y[i] - y[j]
                    if (sp == p and sq == q):
                        yuko += 1
        if max_yuko < yuko:
            max_yuko = yuko
            
print(N-max_yuko)

Submission status: Wrong Answer

Solution code:
#-------------------------------------------------------------------
import sys
def p(*a):
  s=" ".join(map(str,a))
  #print(s)
  sys.stderr.write(s+"\n")
#-------------------------------------------------------------------

N = int(input())						# 5

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

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

#print(P)


from itertools import permutations
from itertools import combinations
L = list(combinations(P, 2))
#print( L )
#print( len(L) )

A=[]

for l in L:
	a=l[1][0]-l[0][0]
	b=l[1][1]-l[0][1]
	if a<0:
		a,b=-a,-b
	A.append((a,b))

#print(A)


# 各朝食メニューの回数を調べる
from collections import defaultdict

d = defaultdict(int)
for b in A:
	d[b] += 1

#print("dict(d)", dict(d))
# => {'pan': 2, 'kome': 4, 'cereal': 1}

# Value降順
B=[]
for k, v in sorted(d.items(), key=lambda x: -x[1]):
	#print(str(k) + ": " + str(v))
	break

#print("k,v", k,v)

print(N-v)

Submission status: Wrong Answer

Solution code:
#-------------------------------------------------------------------
import sys
def p(*a):
  s=" ".join(map(str,a))
  #print(s)
  sys.stderr.write(s+"\n")
#-------------------------------------------------------------------

N = int(input())						# 5

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

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

#print(P)


from itertools import permutations
from itertools import combinations
L = list(combinations(P, 2))
#print( L )
#print( len(L) )

A=[]

for l in L:
	a=l[1][0]-l[0][0]
	b=l[1][1]-l[0][1]
	A.append((a,b))

#print(A)


# 各朝食メニューの回数を調べる
from collections import defaultdict

d = defaultdict(int)
for b in A:
	d[b] += 1

#print("dict(d)", dict(d))
# => {'pan': 2, 'kome': 4, 'cereal': 1}

# Value降順
B=[]
for k, v in sorted(d.items(), key=lambda x: -x[1]):
	#print(str(k) + ": " + str(v))
	break

#print("k,v", k,v)

print(N-v)

Submission status: Wrong Answer

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

ans = 0
for i in range(n):
    for j in range(i+1, n):
        count = 0
        p = x[j] - x[i]
        q = y[j] - y[i]
        for k in range(n):
            for l in range(k+1, n):
                if (x[l] - x[k] == p) and (y[l] - y[k] == q):
                    count += 1
        ans = max(ans, count)

print(n - ans)

Submission status: Wrong Answer

Solution code:
# Picking Up
# グラフ,有向グラフ,ベクトル, ２次元、コスト,

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

for i in range(1, len(S)-1):
    t_vec_x = S[i][0]-S[i-1][0]
    t_vec_y = S[i][1]-S[i-1][1]
    edge=1
    for l in range(1, len(S)-1):
        vec_x = S[l][0]-S[l-1][0]
        vec_y = S[l][1]-S[l-1][1]
        if t_vec_x == vec_x and t_vec_y==vec_y:
            edge += 1
    point = N - edge
    if point < cost:
        cost = point
print(cost)

Submission status: Wrong Answer

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

ans = 0
for i in range(n):
    for j in range(i+1, n):
        count = 0
        p = x[j] - x[i]
        q = y[j] - y[i]
        for k in range(n):
            for l in range(k+1, n):
                if (x[j] - x[i] == p) and (y[j] - y[i] == q):
                    count += 1
        ans = max(ans, count)

print(n - ans)

Submission status: Wrong Answer

Solution code:
import collections
import sys
n = int(input())
if n == 1:
	print(1)
	sys.exit()
tmp = []
for _ in range(n):
	x, y = map(int,input().split())
	tmp.append([x,y])
ball_axis = sorted(tmp)

diff = []
for i in range(1,n):
	diff.append(str(ball_axis[i][0]-ball_axis[i-1][0])+','+str(ball_axis[i][1]-ball_axis[i-1][1]))

max_diff_count = collections.Counter(diff).most_common()[0][1]
print(n-max_diff_count)

Submission status: Wrong Answer

Solution code:
from collections import  Counter
n=int(input())
xy = sorted([list(map(int,input().split())) for i in range(n)])
A = Counter([xy[i+1][0]-xy[i][0] for i in range(n-1)]).keys()
B = Counter([xy[i+1][1]-xy[i][1] for i in range(n-1)]).keys()

ans=0
final_ans=10**9
for a in A:
	for b in B:
		if a==b==0:
			continue
		tmp0,tmp1 = xy[0]
		for i in range(1,len(xy)):
			ans += 0 if tmp0 == xy[i][0]-a  and tmp1 == xy[i][1]-b else 1
			tmp0=xy[i][0]
			tmp1=xy[i][1]
		tmp = ans
		ans=0
		for i in range(len(xy)-1,-1,-1):
			ans += 0 if tmp0 == xy[i][0]-a and tmp1 == xy[i][1]-b else 1
			tmp0=xy[i][0]
			tmp1=xy[i][1]
		tmp_ans = min(ans,tmp)
		final_ans = min(final_ans,tmp_ans)

print(final_ans+1)

Submission status: Wrong Answer

Solution code:
from itertools import combinations

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

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

print(cost)

Submission status: Wrong Answer

Solution code:
N = int(input())
x = []
y = []
for i in range(N):
    x1,y1=[int(i) for i in input().split()]
    x.append(x1)
    y.append(y1)
    
max_yuko = 0
for p in range(N):
    for q in range(N):
        yuko = 0
        for i in range(N):
            for j in range(N):
                if i != j:
                    sp = x[i] - x[j]
                    sq = y[i] - y[j]
                    if (sp == p and sq == q):
                        yuko += 1
        if max_yuko < yuko:
            max_yuko = yuko
            
print(N-max_yuko)

Submission status: Wrong Answer

Solution code:
from fractions import Fraction


class PickingUp:
    def __init__(self):
        self.N = int(input())
        self.points = []
        for n in range(self.N):
            self.points.append([int(n) for n in input().split()])

    def main(self):
        pattern_list = []
        slope_list = []
        for s in range(self.N):
            for e in range(s + 1, self.N):
                slope = self.__cal_slope(self.points[s], self.points[e])
                if slope not in slope_list:
                    slope_list.append(slope)

        for sl in slope_list:
            section_list = []
            for i in range(self.N):
                section = self.__cal_section(sl, self.points[i])
                if section not in section_list:
                    section_list.append(section)
            pattern_list.append(len(section_list))

        if len(pattern_list) == 0:
            pattern_list.append(1)

        print(min(pattern_list))

    def __cal_slope(self, s, e):
        if s[0] != e[0]:
            return Fraction((s[1] - e[1]), (s[0] - e[0]))
        else:
            return None

    def __cal_section(self, slope, point):
        if slope is not None:
            return point[1] - slope * point[0]
        else:
            return point[0]


pickingUp = PickingUp()
pickingUp.main()

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)
print(N-m)

Submission status: Wrong Answer

Solution code:
N = int(input())

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

y = []
for _ in range(N):
  c,d = map(int,input().split())
  y.append((c,d))

z = []
for i in range(N):
  for j in range(i+1,N):
    z.append(((y[j][0]-y[i][0],y[j][1]-y[i][1])))
    
for j in set(z):
  if j in z:
    z.remove(j)
       
print(len(z))

Submission status: Wrong Answer

Solution code:
N = int(input())
xy = [list(map(int, input().split())) for _ in range(N)]
memo = {}
pq = [[[0, 0]] * N for _ in range(N)]
for i in range(N-1):
    for j in range(N):
        pq[i][j] = [xy[j][0]-xy[i][0], xy[j][1]-xy[i][1]]
for i, t in enumerate(pq):
    for p, q in t:
        index = str(i) + str(p) + str(q)
        if index in memo:
            pass
        else:
            memo[index] = 1
memo2 = {}
for i in memo:
    i = i[1:]
    if i =='00':
        continue
    if i in memo2:
        memo2[i] += 1
    else:
        memo2[i] = 1
if N != 1:
    print(N-max(memo2.values()))
else:
    print('1')

Submission status: Wrong Answer

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

ans = float("inf")

for i in range(N):
  if N < 3:
    ans = 1
    break

  x, y = xy[i][0], xy[i][1]
  for j in range(N):
    if i == j:
      break
    p, q = xy[j][0] - x, xy[j][1] - y
    cnt = 0
    for k in range(N):
      xk, yk = xy[k][0], xy[k][1]
      for l in range(N):
        if k == l:
          break
        if xy[l][0] - xk == p and xy[l][1] - yk == q:
          cnt += 1
    ans = min(ans, N - cnt)
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
n=int(input())
balls=[[int(i) for i in input().split()] for _ in range(n)]
diff=deque()
for i in balls:
    for j in balls:
        if i!=j:
            diff.append((j[0]-i[0],j[1]-i[1]))
ans=100000000000
for p,q in set(diff):
    cnt=n
    for i in balls:
        for j in balls:
            if i!=j and j[0]-i[0]==p and j[1]-i[1]==q:
                cnt-=1
    if cnt<ans:
        ans=cnt
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
if n==1:
    print(1)
    exit()
    
xys=[list(map(int,input().split())) for _ in range(n)]
li = [[0,0] for i in range(n*(n-1)//2)]
cnt = 0
for i in range(n):
    for j in range(i+1,n):
        li[cnt][0] = xys[i][0] - xys[j][0]
        li[cnt][1] = xys[i][1] - xys[j][1]
        cnt += 1

li.sort()
ans = 0
cnt = 1
for i in range(len(li)-1):
    if li[i][0] == li[i+1][0] and li[i][1] == li[i+1][1]:
        cnt += 1
    else:
        ans = max(ans,cnt)
        cnt =1
ans = max(ans,cnt)
print(n-ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
xy = [list(map(int, input().split())) for _ in range(N)]
memo = {}
pq = [[[0, 0]] * N for _ in range(N)]
for i in range(N-1):
    for j in range(i+1,N):
        pq[i][j] = [xy[j][0]-xy[i][0], xy[j][1]-xy[i][1]]
for i, t in enumerate(pq):
    for p, q in t:
        index = str(i) + str(p) + str(q)
        if index in memo:
            pass
        else:
            memo[index] = 1
memo2 = {}
for i in memo:
    i = i[1:]
    if i =='00':
        continue
    if i in memo2:
        memo2[i] += 1
    else:
        memo2[i] = 1
if N != 1:
    print(N-max(memo2.values()))
else:
    print('1')

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 = 1
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

if n == 1:
    print(1)
else:
    print(n - max_cont)

Submission status: Wrong Answer

Solution code:
# div2019-2B - Picking Up
from collections import defaultdict

n = int(input())
arr = sorted([list(map(int, input().rstrip().split())) for _ in range(n)])
cnt = defaultdict(int)
for i in range(n):
    for j in range(i + 1, n):
        dif = (arr[j][0] - arr[i][0], arr[j][1] - arr[i][1])
        cnt[dif] += 1
print(cnt)
print(n - max(cnt.values(), default=0))

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)
#'''
N = int(input())
x, y = [0] * N, [0] * N

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

pq = []
m = 1

if N == 1:
	print(1)
else:	
	for i in range(N - 1):
		for j in range(i + 1, N):
			p, q = x[j] - x[i], y[j] - y[i]
			pq.append([p, q])
			
	for i in range(len(pq) - 1):
		n = 1
		for j in range(i + 1, len(pq)):
			if pq[i] == pq[j]:
				n += 1
				
		if n > m:
			m = n
			
	cost = N - m
	print(cost)

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):
    for k in range(N-1):
        if x[k] > x[k + 1]:
            x[k], y[k] = x[k + 1], y[k + 1]
        elif x[k] == x[k + 1] and y[k] > y[k + 1]:
            x[k], y[k] = x[k + 1], y[k + 1]

ans = 0
for p in range(N-1):
    for m in range(p+1, N):
        diff_x = x[m] - x[p]
        diff_y = y[m] - y[p]
        ans_kari = 0
        for r in range(N-1):
            for q in range(r+1, N):
                if x[q] - x[r] == diff_x and y[q] - y[r] == diff_y:
                    ans_kari += 1
        if ans_kari > ans:
            ans = ans_kari

print("{}".format(int(N-ans)))

Submission status: Wrong Answer

Solution code:
n=int(input())
if n==1:
    print(1)
    exit()
xys=[list(map(int,input().split())) for _ in range(n)]
li = [[0,0] for i in range(n*(n-1)//2)]
cnt = 0
for i in range(n):
    for j in range(i+1,n):
        li[cnt][0] = xys[i][0] - xys[j][0]
        li[cnt][1] = xys[i][1] - xys[j][1]
        cnt += 1

li.sort()
ans = 0
cnt = 1
for i in range(len(li)-1):
    if li[i][0] == li[i+1][0] and li[i][1] == li[i+1][1]:
        cnt += 1
    else:
        ans = max(ans,cnt)
        cnt =1
ans = max(ans,cnt)
print(n-ans)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque  # 双方向キュー
from collections import defaultdict  # 初期化済み辞書
from heapq import heapify, heappush, heappop, heappushpop  # プライオリティキュー
from bisect import bisect_left, bisect_right  # 二分探索
#import numpy as np  # 1.8.2
#import scipy  # 0.13.3

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in ss]
ss2nnn = lambda ss: [s2nn(s) for s in ss]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline().rstrip() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

def main():
    N = i2n()
    xy = ii2nnn(N)
    dicx = defaultdict(lambda: 0)
    xy.sort(key=lambda v: v[0]*1e+10+v[1])
    for i in range(1, len(xy)):
        dx = xy[i][0] - xy[i-1][0]
        dy = xy[i][1] - xy[i-1][1]
        if dx == 0 and dy == 0:
            continue
        key = '%d %d' % (dx, dy)
        dicx[key] += 1
    dicy = defaultdict(lambda: 0)
    xy.sort(key=lambda v: v[1]*1e+10+v[0])
    for i in range(1, len(xy)):
        dx = xy[i][0] - xy[i-1][0]
        dy = xy[i][1] - xy[i-1][1]
        if dx == 0 and dy == 0:
            continue
        key = '%d %d' % (dx, dy)
        dicy[key] += 1
    nm = 0
    for v in dicx.values():
        if nm < v:
            nm = v
    for v in dicy.values():
        if nm < v:
            nm = v
    print(N - nm)

main()

Submission status: Wrong Answer

Solution code:
from fractions import Fraction
n = int(input())

li = []

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

li.sort()

def cal(li):
    n = len(li)
    Route = []
    for s in range(n-1):
        x1, y1 = li[s]
        route = {}
        for i in range(n):
            xi, yi = li[i]
            if i != s:
                if i < s:
                    xA = x1; yA = y1
                    xB = xi; yB = yi
                else:
                    xA = x1; yA = y1
                    xB = xi; yB = yi
                     
                if xB != xA:
                    diff = Fraction((yB - yA),(xB - xA))
                else:
                    diff = 10e10

                if diff in route.keys():
                    route[diff].append([xi, yi])
                else:
                    route[diff] = [[x1,y1], [xi, yi]]

        Route.extend(route.values())
    return Route

cost = 0
route = cal(li)

def check(A,B):
    for a in A:
        if a not in B:
            return False
    
    return True

def max_cal(route, li):
    n = len(li)
    l_max = 0
    max_li = []
    for r in route:
        if check(r,li):
            l = len(r)
            if l > l_max:
                 max_li = r
                 l_max = l
    return l_max, max_li

while True:
    l, cand = max_cal(route, li)
    if l == 0:
        cost += len(li)
        break
    else:
        route.remove(cand)
        for c in cand:
            li.remove(c)
        cost += 1
    if len(li) == 0:
        break

print(cost)