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

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

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

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

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

print(ans)

Submission status: Wrong Answer

Solution code:
from fractions import gcd
from collections import defaultdict
N = int(input())
B = [[0, 0] for i in range(N)]
D = [[[0, 0] for j in range(N)] for i in range(N)]
G = defaultdict(lambda:defaultdict(int))
for i in range(N):
  B[i] = [int(x) for x in input().split()]
B.sort()
for i in range(N):
  for j in range(i, N):
    if i == j:
      continue
    grad = gcd(abs(B[j][0] - B[i][0]), abs(B[j][1] - B[i][1]))
    D[i][j] = [(B[j][0] - B[i][0]) // grad, (B[j][1] - B[i][1]) // grad]
    D[j][i] = [-D[i][j][0], -D[i][j][1]]
for i in range(N):
  for j in range(i, N):
    if i == j:
      continue
    if G[str(D[i][j])][j] == 0:
      G[str(D[i][j])][j] = i + 1
    if G[str(D[i][j])][i] == 0:
      G[str(D[i][j])][i] = i + 1
ans = N
for p in G.keys():
  v = N - len(G[p].keys()) + len(list(set(G[p].values())))
  ans = min(ans, v)
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
d=[list(map(int,input().split()))[::-1]for _ in range(n)]
d.sort()
for i in range(n):d[i]=d[i][::-1]
d.sort()
def c(p,q,a):#p,qのときのスコア算出（多少おそくてもよし）
  global n
  s=n
  for i in a:
    if [i[0]-p,i[1]-q]in a:s-=1
  return s
ans=50
for i in range(n-1):
  for j in range(1+i,n):
    p,q=d[j][0]-d[i][0],d[j][1]-d[i][1]
    ans=min(ans,c(p,q,d[::-1]))
print(ans)

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 = 1
    q = 1
    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:
import numpy as np
N=int(input())
x = [0] * N
y = [0] * N
ans = N

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

for i in range(N-1):
  cost = N
  for j in range(i+1,N):
    p = x[i] - x[j]
    q = y[i] - y[j]
    if p == 0 and q==0:
      cost = N*2
    diffx = np.diff(x)
    diffy = np.diff(y)
    for k in range(N-1):
      if diffx[k] == p and diffy[k] == q:
        cost = cost - 1
      if diffx[k] == -p and diffy[k] == -q:
        cost = cost - 1
  ans = min(ans,cost)

print(ans)

Submission status: Wrong Answer

Solution code:
import collections

n = int(input())

xy = []
for i in range(n):
	xi,yi = map(int,input().split())
	xy.append([xi,yi])

xy.sort()

pi = []
qi = []

for i in range(n-1):
	pi.append(xy[i][0] - xy[i+1][0])
	qi.append(xy[i][1] - xy[i+1][1])

pc = collections.Counter(pi)
qc = collections.Counter(qi)

lpc = len(pc.keys())
lqc = len(pc.keys())

if lpc == lqc:
	print(lpc)
else:
	print(lpc+lqc)

Submission status: Wrong Answer

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


    min_cost = float('inf')
    for i in range(n):
        x,y = coords[i][0],coords[i][1]
        for j in range(n):
            if i == j:
                continue
            visited = set()
            visited.add((x,y))
            moves = 1
            x1,y1 = coords[j][0],coords[j][1]
            p,q = x1-x,y1-y
            visited.add((x1,y1))
            while len(visited) != n:
                if (x1+p,y1+q) in coords:
                    visited.add((x1+p,y1+q))
                    x1 += p
                    y1 += q
                else:
                    moves += 1
                    for k in range(n):
                        if (coords[k][0],coords[k][1]) not in visited:
                            x1,y1 = coords[k][0],coords[k][1]
                            visited.add((x1,y1))
                            break
            min_cost = min(min_cost,moves)

    print(min_cost)
            


main()

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

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

    x.sort()
    y.sort()

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

    from collections import Counter

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

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

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

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


    print(ans)

    return


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

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import itertools

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

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

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

print(ans)

Submission status: Wrong Answer

Solution code:
# div2019-2B - Picking Up
import sys
input = sys.stdin.readline

n = int(input())
arr = sorted([list(map(int, input().rstrip().split())) for _ in range(n)])
x_set, y_set = {i[0] for i in arr}, {i[1] for i in arr}
for i in range(1, n):
    x = arr[i][0] - arr[i - 1][0]
    y = arr[i][1] - arr[i - 1][1]
    x_set.add(x)
    y_set.add(y)

ans = float("inf")
for p in x_set:
    for q in y_set:
        cnt = 1
        for i in range(1, n):
            if (arr[i - 1][0], arr[i - 1][1]) != (arr[i][0] - p, arr[i][1] - q):
                cnt += 1
        ans = min(ans, cnt)
print(ans)

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
mincst_p = float("inf")
mincst_q = float("inf")
xy.sort(key = lambda x:x[0])
keep = xy[0]
if N != 1:
    for j in range(N-1):
        p = xy[j+1][0]-xy[j][0]
        q = xy[j+1][1]-xy[j][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
        if mincst_p > cst_p:
            mincst_p = cst_p
            cst_p = 1 
else:
    print(1)
    exit()
 
xy.sort(key = lambda x:x[1])
keep = xy[0]
if N != 1:
    for j in range(N-1):
        p = xy[j+1][0]-xy[j][0]
        q = xy[j+1][1]-xy[j][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
        if mincst_q > cst_q:
            mincst_q = cst_q
            cst_q = 1
else:
    print(1)
    exit()
 
print(min(mincst_p,mincst_q))

Submission status: Wrong Answer

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

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

diff = []
for X, Y in XY:
  for X2, Y2 in XY:
    p = X2-X
    q = Y2-Y
    k = X-X2
    l = Y-Y2
    if (p, q) == (0, 0) or (p, q) in diff:
      continue
    diff.append((p, q))
    if (k, l) == (0, 0) or (k, l) in diff:
      continue
    diff.append((k, l))
    
pre = []
ans = []
for p, q in diff:
  cost = 1
  for a, b in XY:
    if not pre:
      pre = (a, b)
      continue
    if (a - p, b - q) == pre:
      pass
    else:
      cost += 1
    pre = (a, b)
  ans.append(cost)
  pre = []
print(min(ans))

Submission status: Wrong Answer

Solution code:
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
    acnt=0
    bcnt=0
    tmp=0
    for j in range(len(l)):
        if l[i][0]==0:
            tmp=l[i][1]
            if l[i][0]==l[j][0] and l[i][1]==l[j][1] and i!=j or l[i][0]==-l[j][0] and l[i][1]==-l[j][1] and i!=j:
                if tmp==l[j][1]:
                    acnt+=1
                    if acnt>m:
                        m=acnt
        if l[i][1]==0:
            tmp=l[i][0]
            if l[i][0]==l[j][0] and l[i][1]==l[j][1] and i!=j or l[i][0]==-l[j][0] and l[i][1]==-l[j][1] and i!=j:
                if tmp ==l[j][0]:
                    bcnt+=1
                    if bcnt>m:
                        m=bcnt
        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())
xy = [list(map(int, input().split())) for _ in range(n)]

sa = []
for i, j in xy:
    for k, l in xy:
        sa.append([i - k, j - l])

#sa1
xy.sort()
xy = xy[::-1]
ans = 10000000000000000000
i = 0
while True:
    if i >= len(sa):
        break
    if sa[i] == [0, 0]:
        del sa[i]
        i -= 1
    i += 1


if len(sa) == 0 and n != 1:
    sa = [[1, 1]]

for p, q in sa:
    tmp = 1
    for i in range(1, n):
        x = xy[i][0]
        y = xy[i][1]
        if xy[i - 1][0] == x - p and xy[i - 1][1] == y - q:
            1
        else:
            tmp += 1
    ans = min(ans, tmp)
xy.sort(key=lambda x:x[1])

for p, q in sa:
    tmp = 1
    for i in range(1, n):
        x = xy[i][0]
        y = xy[i][1]
        if xy[i - 1][0] == x - p and xy[i - 1][1] == y - q:
            1
        else:
            tmp += 1
    ans = min(ans, tmp)
if len(xy) == 1:
    ans = 1
print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import random
input = sys.stdin.readline

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

def main():

	N = int(input())
	#N, K = map(int, input().split(" "))

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

	gess = {}
	xm = 0
	ym = 0

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

	for i, val in enumerate(xy):
		if i == 0:
			x,y = val
			xm = x
			ym = y
			continue
		x, y = val

		p = x - xm
		q = y - ym
		if (p,q) in gess:
			gess[(p, q)] += 1
		else:
			gess[(p, q)] = 1
		xm = x
		ym = y

	p, q = max(gess, key=gess.get)
	nai = gess[(p,q)]

	#########
	xy = sorted(xy, key=lambda x:(x[0]))
	gess1 = {}
	xm = 0
	ym = 0

	for i, val in enumerate(xy):
		if i == 0:
			x,y = val
			xm = x
			ym = y
			continue
		x, y = val

		p = x - xm
		q = y - ym
		if (p,q) in gess1:
			gess1[(p, q)] += 1
		else:
			gess1[(p, q)] = 1
		xm = x
		ym = y

	p, q = max(gess1, key=gess1.get)
	nai1 = gess1[(p,q)]

	#########
	xy = sorted(xy, key=lambda x:(-x[0]))
	gess2 = {}
	xm = 0
	ym = 0

	for i, val in enumerate(xy):
		if i == 0:
			x,y = val
			xm = x
			ym = y
			continue
		x, y = val

		p = x - xm
		q = y - ym
		if (p,q) in gess2:
			gess2[(p, q)] += 1
		else:
			gess2[(p, q)] = 1
		xm = x
		ym = y

	p, q = max(gess2, key=gess2.get)
	nai2 = gess2[(p,q)]

	#########
	xy = sorted(xy, key=lambda x:(x[1]))
	gess3 = {}
	xm = 0
	ym = 0

	for i, val in enumerate(xy):
		if i == 0:
			x,y = val
			xm = x
			ym = y
			continue
		x, y = val

		p = x - xm
		q = y - ym
		if (p,q) in gess3:
			gess3[(p, q)] += 1
		else:
			gess3[(p, q)] = 1
		xm = x
		ym = y

	p, q = max(gess3, key=gess3.get)
	nai3 = gess3[(p,q)]

	#########
	xy = sorted(xy, key=lambda x:(-x[1]))
	gess4 = {}
	xm = 0
	ym = 0

	for i, val in enumerate(xy):
		if i == 0:
			x,y = val
			xm = x
			ym = y
			continue
		x, y = val

		p = x - xm
		q = y - ym
		if (p,q) in gess4:
			gess4[(p, q)] += 1
		else:
			gess4[(p, q)] = 1
		xm = x
		ym = y

	p, q = max(gess4, key=gess4.get)
	nai4 = gess4[(p,q)]

	#########
	xy = sorted(xy, key=lambda x:(x[0],-x[1]))
	gess5 = {}
	xm = 0
	ym = 0

	for i, val in enumerate(xy):
		if i == 0:
			x,y = val
			xm = x
			ym = y
			continue
		x, y = val

		p = x - xm
		q = y - ym
		if (p,q) in gess5:
			gess5[(p, q)] += 1
		else:
			gess5[(p, q)] = 1
		xm = x
		ym = y

	p, q = max(gess5, key=gess5.get)
	nai5 = gess5[(p,q)]

	#########
	random.shuffle(xy)
	gess6 = {}
	xm = 0
	ym = 0

	for i, val in enumerate(xy):
		if i == 0:
			x,y = val
			xm = x
			ym = y
			continue
		x, y = val

		p = x - xm
		q = y - ym
		if (p,q) in gess6:
			gess6[(p, q)] += 1
		else:
			gess6[(p, q)] = 1
		xm = x
		ym = y

	p, q = max(gess6, key=gess6.get)
	nai6 = gess6[(p,q)]

	#########
	random.shuffle(xy)
	gess7 = {}
	xm = 0
	ym = 0

	for i, val in enumerate(xy):
		if i == 0:
			x,y = val
			xm = x
			ym = y
			continue
		x, y = val

		p = x - xm
		q = y - ym
		if (p,q) in gess7:
			gess7[(p, q)] += 1
		else:
			gess7[(p, q)] = 1
		xm = x
		ym = y

	p, q = max(gess7, key=gess7.get)
	nai7 = gess7[(p,q)]
		#########
	random.shuffle(xy)
	gess8 = {}
	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 gess8:
			gess8[(p, q)] += 1
		else:
			gess8[(p, q)] = 1
		xm = x
		ym = y

	p, q = max(gess8, key=gess8.get)
	nai8 = gess8[(p,q)]

		#########
	random.shuffle(xy)
	gess9 = {}
	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 gess9:
			gess9[(p, q)] += 1
		else:
			gess9[(p, q)] = 1
		xm = x
		ym = y

	p, q = max(gess9, key=gess9.get)
	nai9 = gess9[(p,q)]

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

	print(N-tmp)



if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
from collections import Counter
N = int(input())
xy = sorted([list(map(int, input().split())) for _ in range(N)])
diff = []
for i in range(1, len(xy)):
    x = xy[i][0]-xy[i-1][0]
    y = xy[i][1]-xy[i-1][1]
    diff.append((x,y))

c = Counter(diff)
xm = 0
for i in c:
    xm = max(xm, c[i])

xy.sort(key=lambda x:x[1])
diff = []
for i in range(1, len(xy)):
    x = xy[i][0]-xy[i-1][0]
    y = xy[i][1]-xy[i-1][1]
    diff.append((x,y))

c = Counter(diff)
ym = 0
for i in c:
    ym = max(ym, c[i])
m = max(xm,ym)
print(N-m)

Submission status: Wrong Answer

Solution code:
N = int(input())
XY = []
for n in range(N):
    XY.append([int(i) for i in input().split()])
cnt = {}
for n in range(N):
    for nn in range(n+1,N): 
        dist = [XY[n][0]-XY[nn][0],XY[n][1]-XY[nn][1]]
        if str(dist) in cnt:
            cnt[str(dist)] += 1
        else:
            cnt[str(dist)] = 1
if N == 1:
    print(1)
else:
	print(N - max(cnt.values()))

Submission status: Wrong Answer

Solution code:
from copy import deepcopy

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

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

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

        ans = min(ans, cos)

print(ans)

Submission status: Wrong Answer

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

if len(AB_list) ==1:
    print(1)
    exit(0)

AB_list = sorted(AB_list,key=lambda a:a[0])
kouho_list = []
for i, AB in enumerate(AB_list):
    for j,ab in enumerate(AB_list[i+1:]):
        kouho_list.append((AB[0]-ab[0] ,AB[1]-ab[1]))

from collections import Counter
kouho_counter = Counter(kouho_list).most_common()
pq = list(kouho_counter[0][0])

onaji_list = []
#print(pq)

result = []
for i,ab in enumerate(AB_list):
    for j,ab2 in enumerate(AB_list):
        if i == j:
            continue
        if ab[0] + pq[0] == ab2[0] and ab[1] + pq[1] == ab2[1]:
            result.append(ab2)
            continue
        #if ab[0] - pq[0] == ab2[0] and ab[1] - pq[1] == ab2[1]:
            #result.append(ab2)



#print(onaji_list)
#print(result)
print(len(AB_list)-len(result))





'''
候補は49 + 48 + 47 + ...
この候補の中で、一番えらばれているものをp,qとして設定する
その後、ループを回して、実際にコストを計算する

'''


#print(AB_list)

Submission status: Wrong Answer

Solution code:
import collections

n = int(input())

xy = []
for i in range(n):
	xi,yi = map(int,input().split())
	xy.append([xi,yi])

xy.sort()

pi = []
qi = []

for i in range(n-1):
	pi.append(xy[i][0] - xy[i+1][0])
	qi.append(xy[i][1] - xy[i+1][1])

pc = collections.Counter(pi)
qc = collections.Counter(qi)

lpc = len(pc.keys())
lqc = len(pc.keys())

if lpc == lqc:
	print(lpc)
else:
	print(max(lpc,lqc))

Submission status: Wrong Answer

Solution code:


from collections import Counter

data = [[1, 1], [1, 2], [2, 1], [2, 2]]
N = len(data)
# data = []
# N = int(input())
# for i in range(N):
# 	data.extend([list(map(int, input().split(' ')))])
x = []

for e_set in data:
    for sub_set in data:
        x.append((e_set[0] - sub_set[0], e_set[1] - sub_set[1]))

val = Counter(x)
commons = val.most_common()[1][1]

if commons == 1:
    commons = 0
ans = N - commons

if ans == 0:
    print(1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from operator import sub

def main():
    N = int(input())
    balls = [tuple(map(int,input().split())) for _ in range(N)]
    d = defaultdict(int)
    for i in range(N):
        for j in range(N):
            if i == j:
                continue
            d[tuple(map(sub, balls[i], balls[j]))] += 1
    try:
        mmax = max(d.values())
        mmax = int(N - mmax)
        print(mmax)
    except:
        print(100)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import numpy as np
n = int(input())
xy = []
for i in range(n):
    a = list(input().split())
    xy.append(a)

#print(xy)
s = n
for i in range(n-1):
    if xy[i][0] !="a":
        for j in range(i+1,n):
            if xy[j][0] !="a":
                p = int(xy[i][0])-int(xy[j][0])
                q = int(xy[i][1])-int(xy[j][1])
                m = n
                #print(p)
                #print(q)
                for c in range(n-1):
                    if xy[c][0] !="a":
                        for b in range(c+1,n):
                            #print(int(xy[c][0])-int(xy[b][0]))
                            if xy[b][0] != "a":
                                if abs(p) == abs(int(xy[c][0])-int(xy[b][0])) and abs(q) == abs(int(xy[c][1])-int(xy[b][1])):
                                    m -= 1
                                    xy[b][0] = "a"
                #print(m)
                if s>m:
                    s = m
                    #print("s"+ str(s))

print(s)

Submission status: Wrong Answer

Solution code:
import collections

N = int(input())
x_y = [[int(i) for i in input().split()] for _ in range(N)]

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

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

x_y_gap = [[x_y[i+1][0]-x_y[i][0], x_y[i+1][1]-x_y[i][1]] for i in range(N-1)]

x_y_count = 0
combination = [10**10, 10**10]
for i in x_y_gap:
  if x_y_gap.count(i) > x_y_count:
    combination = i 
    x_y_count = x_y_gap.count(i)

answer = 1
for gap in x_y_gap: 
  if gap[0] != combination[0] or gap[1] != combination[1]:
    answer+=1

print(answer)

Submission status: Wrong Answer

Solution code:
import itertools
n = int(input())
xy = [list(map(int, input().split())) for i in range(n)]
xy.sort(key=lambda x:(x[0],x[1]))
b = []
aa,bb = xy[0][0],xy[0][1]
for i in xy[1:]:
    x,y = i[0],i[1]
    b.append([x-aa,y-bb])
    aa,bb = x,y
ans = n
nowx,nowy = xy[0][0],xy[0][1]
d = []
for i in list(itertools.combinations(xy,2)):
    d.append([abs(i[0][0]-i[1][0]),abs(i[0][1]-i[1][1])])
for i in d:
    cost = n
    p,q = i[0], i[1]
    for j in b:
        if j[0] == p and j[1] == q:
            cost -= 1
    ans = min(ans,cost)
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
xy = [[int(x) for x in input().split()] for i in range(N)]
xy = sorted(xy)
ans = 1
if N <= 2:
  print(ans)
else:
  list_xypq = [[xy[0][0],xy[0][1],xy[1][0]-xy[0][0],xy[1][1]-xy[0][1]]]
  for i in range(2,N):
    x = int(xy[i][0])
    y = int(xy[i][1])
    for j in range(len(list_xypq)):
      x_tmp = int(list_xypq[j][0])
      y_tmp = int(list_xypq[j][1])
      p_tmp = int(list_xypq[j][2])
      q_tmp = int(list_xypq[j][3])
      if p_tmp == 10e10 and q_tmp == 10e10:
        list_xypq[j][2] = x-x_tmp
        list_xypq[j][3] = y-y_tmp
        break
      if p_tmp == 0 and q_tmp != 0:
        if x-x_tmp == 0 and (y-y_tmp)%q_tmp == 0:
          break
      elif p_tmp != 0 and q_tmp == 0:
        if (x-x_tmp)%p_tmp == 0 and y-y_tmp == 0:
          break
      elif p_tmp == 0 and q_tmp == 0:
        if x-x_tmp == 0 and y-y_tmp == 0:
          break
      else:
        if (x-x_tmp)%p_tmp == 0 and (y-y_tmp)%q_tmp == 0:
          break
    else:
      list_xypq.append([x,y,10e10,10e10])
      ans += 1
  print(ans)

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

Solution code:
import copy
N = int(input())
C = [[int(i) for i in input().split()] for i in range(N)]
pq_list = []
min_score = N
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(len(pq_list)):
    score = N
    p = pq_list[i][0]
    q = pq_list[i][1]
    if(p >= 0):
        C.sort(key=lambda x: x[0], reverse=False)
    else:
        C.sort(key=lambda x: x[0], reverse=True)
    for j in range(N-1):
        for k in range(j+1, N):
            if(C[j][0] == C[k][0] + p and C[j][1] == C[k][1] + q):
                score -= 1
                break
    min_score = min(min_score, score)
    
print(min_score)

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

Solution code:
from copy import deepcopy

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

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

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

print(ans)