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())
P=[tuple(map(int,input().split())) for i in range(N)]
ans=N-1
for i in range(N):
    for j in range(N):
        if i==j:
            continue
        p=P[i][0]-P[j][0]
        q=P[i][1]-P[j][1]
        cost=0
        for k in range(N):
            if (P[k][0]-p,P[k][1]-q) not in P:
                cost+=1
        ans=min(ans,cost)
print(ans)

Submission status: Wrong Answer

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

D={}
for i in range(N):
    for j in range(N):
        if i!=j:
            if (L[i][0]-L[j][0],L[i][1]-L[j][1]) not in D:
                D[(L[i][0]-L[j][0],L[i][1]-L[j][1])]=1
#print(D)

ANS=100

for i in D.keys():
    S={}
    for j in L:
        if i[0]==0:
            if (j[0],0) not in S:
                S[(j[0],0)]=1
        else:
            if (0,j[1]-i[1]*(j[0]/i[0])) not in S:
                S[(0,int((j[1]*i[0]-i[1]*(j[0]))))]=1
    if ANS>len(S):
        ANS=len(S)
        #print(S)
print(ANS)

Submission status: Wrong Answer

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

D={}
for i in range(N):
    for j in range(N):
        if i!=j:
            if (L[i][0]-L[j][0],L[i][1]-L[j][1]) not in D:
                D[(L[i][0]-L[j][0],L[i][1]-L[j][1])]=1
#print(D)

ANS=100

for i in D.keys():
    S={}
    for j in L:
        if i[0]==0:
            if (j[0],0) not in S:
                S[(j[0],0)]=1
        else:
            if (0,j[1]-i[1]*(j[0]/i[0])) not in S:
                S[(0,int((j[1]*i[0]-i[1]*(j[0]))))]=1
    if ANS>len(S):
        ANS=len(S)
        print(S)
print(ANS)

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 or q != 0:
        sub = 0
        for b3, b4 in combinations(balls, 2):
            dx, dy = b3[0] - b4[0], b3[1] - b4[1]
            if dx == p and dy == q:
                sub += 1
        cost = min(cost, n - sub)

print(max(cost, 1))

Submission status: Wrong Answer

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

D={}
for i in range(N):
    for j in range(N):
        if i!=j:
            if (L[i][0]-L[j][0],L[i][1]-L[j][1]) not in D:
                D[(L[i][0]-L[j][0],L[i][1]-L[j][1])]=1
#print(D)

ANS=100

for i in D.keys():
    S={}
    for j in L:
        if i[0]==0:
            if (j[0],0) not in S:
                S[(j[0],0)]=1
        else:
            if (0,j[1]-i[1]*(j[0]/i[0])) not in S:
                S[(0,int((j[1]-i[1]*(j[0]/i[0]))*100000000000000))]=1
    if ANS>len(S):
        ANS=len(S)
        #print(S)
print(ANS)

Submission status: Wrong Answer

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

D={}
for i in range(N):
    for j in range(N):
        if i!=j:
            if (L[i][0]-L[j][0],L[i][1]-L[j][1]) not in D:
                D[(L[i][0]-L[j][0],L[i][1]-L[j][1])]=1
#print(D)

ANS=100

for i in D.keys():
    S={}
    for j in L:
        if i[0]==0:
            if (j[0],0) not in S:
                S[(j[0],0)]=1
        else:
            if (0,j[1]-i[1]*(j[0]/i[0])) not in S:
                S[(0,int((j[1]-i[1]*(j[0]/i[0]))*1000000000))]=1
    if ANS>len(S):
        ANS=len(S)
        #print(S)
print(ANS)

Submission status: Wrong Answer

Solution code:
def input_from_console():
    n = int(input())
    x_list = []
    y_list = []

    for i in range(n):
        x, y = map(int, input().split())
        x_list.append(x)
        y_list.append(y)
    return n, x_list, y_list


def solve(n, x_list, y_list):
    if n <= 2:
        return 1

    matrix_dict = {}
    for i in range(n):
        for j in range(i, n):
            if i != j:
                d_x = x_list[j] - x_list[i]
                d_y = y_list[j] - y_list[i]
                if d_x < 0:
                    d_x, d_y = -d_x, -d_y
                if matrix_dict.get((d_x, d_y), None):
                    matrix_dict[(d_x, d_y)] += 1
                else:
                    matrix_dict[(d_x, d_y)] = 1
    depth_list = sorted([matrix_dict[item] for item in matrix_dict], reverse=True)
    return n - depth_list[0]


def main():
    n, x_list, y_list = input_from_console()
    print(solve(n, x_list, y_list))


if __name__ == "__main__":
    import sys

    if sys.gettrace():  # Check if the python interpreter is in debug mode or not.
        check_cases()
    else:
        main()

Submission status: Wrong Answer

Solution code:


def input_from_console():
    n = int(input())
    x_list = []
    y_list = []

    for i in range(n):
        x, y = map(int, input().split())
        x_list.append(x)
        y_list.append(y)
    return n, x_list, y_list


def solve(n, x_list, y_list):
    if n < 2:
        return 1

    matrix_dict = {}
    for i in range(n):
        for j in range(i, n):
            if i != j:
                d_x = x_list[j] - x_list[i]
                d_y = y_list[j] - y_list[i]
                if d_x < 0:
                    d_x, d_y = -d_x, -d_y
                if matrix_dict.get((d_x, d_y), None):
                    matrix_dict[(d_x, d_y)] += 1
                else:
                    matrix_dict[(d_x, d_y)] = 1
    depth_list = sorted([matrix_dict[item] for item in matrix_dict], reverse=True)
    return n - depth_list[0]
    

def main():
    n, x_list, y_list = input_from_console()
    print(solve(n, x_list, y_list))


if __name__ == "__main__":
    import sys

    if sys.gettrace():  # Check if the python interpreter is in debug mode or not.
        check_cases()
    else:
        main()

Submission status: Wrong Answer

Solution code:
N=int(input())

XY = [list(map(int,input().split())) for _ in range(N)]

x=[]
y=[]

for X,Y in XY:
    x.append(X)
    y.append(Y)
    
l1=[]
c=0
for i in range(N):
    for j in range(N):
        a=x[i]-x[j]
        b=y[i]-y[j]
        """
        if a<=0 and b>=0:
            a=-a
            b=-b
        elif a<=0 and b<=0:
            a=-a
            b=-b
        """
        l1.append(str(a)+"_"+str(b))
        #l1.append([a,b])
v=set(l1)
c=[]
for i in v:
    c.append(l1.count(i))
#c = collections.Counter(l1)      
#values, counts = zip(*c.most_common())    
print(N-max(c))

Submission status: Wrong Answer

Solution code:

def input_from_console():
    n = int(input())
    x_list = []
    y_list = []

    for i in range(n):
        x, y = map(int, input().split())
        x_list.append(x)
        y_list.append(y)
    return n, x_list, y_list


def solve(n, x_list, y_list):
    if n <= 2:
        return 1

    matrix_dict = {}
    for i in range(n):
        t_y = y_list[i]
        t_x = x_list[i]
        for j in range(i, n):
            if i != j:
                diff_x = x_list[j] - t_x
                diff_y = y_list[j] - t_y
                if matrix_dict.get((diff_x, diff_y), None):
                    matrix_dict[(diff_x, diff_y)] += 1
                else:
                    matrix_dict[(diff_x, diff_y)] = 1
    depth_list = sorted([matrix_dict[item] for item in matrix_dict], reverse=True)
    if depth_list:
        return n - depth_list[0]
    else:
        return n



def main():
    n, x_list, y_list = input_from_console()
    print(solve(n, x_list, y_list))


if __name__ == "__main__":
    import sys

    if sys.gettrace():  # Check if the python interpreter is in debug mode or not.
        check_cases()
    else:
        main()

Submission status: Wrong Answer

Solution code:
import copy

n=int(input())
li=[list(map(int,input().split())) for _ in range(n)]

li=sorted(li,key=lambda x:(x[0],x[1]))
bl=[False for _ in range(n)]

def search(num,a,p,q):
  re=copy.deepcopy(a)
  for i in range(num,len(li)):
    if li[i][0]==re[0]+p and li[i][1]==re[1]+q:
      bl[i]=True
      re=[li[i][0],li[i][1]]
      
        
max_=n
for i in range(li[-1][0]):
  for j in range(li[-1][1]):
    count=0
    while(False in bl):
      count+=1
      for k in range(len(bl)):
        if bl[k]==False:
          bl[k]=True
          search(k,li[k],i,j)
          break
    max_=min(max_,count)
    bl=[False for _ in range(n)]
print(max_)

Submission status: Wrong Answer

Solution code:
class UnionFind:
    def __init__(self, size: int):
        self.__root = [-1] * size

    def find(self, x: int)->int:
        if self.__root[x] < 0:
            return x
        self.__root[x] = self.find(self.__root[x])
        return self.__root[x]

    def same(self, x: int, y: int)->bool:
        return self.find(x) == self.find(y)

    def unite(self, x: int, y: int)->bool:
        rx, ry = self.find(x), self.find(y)

        if rx == ry:
            return False

        if ry < rx:
            rx, ry = ry, rx

        self.__root[rx] += self.__root[ry]
        self.__root[ry] = rx

        return True


def picking_up(N: int, balls: list)->int:
    rev = {}  # rev[x][y] = (x, y) にあるボールのインデックス
    for i, (x, y) in enumerate(balls):
        rev.setdefault(x, {})
        rev[x][y] = i

    # (p, q) の候補
    candidates = [
        (x2-x1, y2-y1)
        for x1, y1 in balls
        for x2, y2 in balls
        if x1 != x2 or y1 != y2]

    ans = float('inf')
    for p, q in candidates:
        uf = UnionFind(N)
        score = N

        for i, (x, y) in enumerate(balls):
            if x+p not in rev:
                continue
            if y+q not in rev[x+p]:
                continue
            if uf.unite(i, rev[x+p][y+q]):
                score -= 1

        ans = min(ans, score)

    return ans


if __name__ == "__main__":
    N = int(input())
    balls = [tuple(map(int, input().split())) for _ in range(N)]

    ans = picking_up(N, balls)
    print(ans)

Submission status: Wrong Answer

Solution code:
class UnionFind:
    def __init__(self, size: int):
        self.__root = [-1] * size

    def find(self, x: int)->int:
        if self.__root[x] < 0:
            return x
        self.__root[x] = self.find(self.__root[x])
        return self.__root[x]

    def same(self, x: int, y: int)->bool:
        return self.find(x) == self.find(y)

    def unite(self, x: int, y: int)->bool:
        rx, ry = self.find(x), self.find(y)

        if rx == ry:
            return False

        if ry < rx:
            rx, ry = ry, rx

        self.__root[rx] += self.__root[ry]
        self.__root[ry] = rx

        return True


def picking_up(N: int, balls: list)->int:
    rev = {}  # rev[x][y] = (x, y) にあるボールのインデックス
    for i, (x, y) in enumerate(balls):
        rev.setdefault(x, {})
        rev[x][y] = i

    candidates = []  # (p, q) の候補
    for x1, y1 in balls:
        for x2, y2 in balls:
            if x1 == x2 and y1 == y2:
                continue
            candidates.append((x2-x1, y2-y1))

    ans = float('inf')
    for p, q in candidates:
        uf = UnionFind(N)
        score = N

        for i, (x, y) in enumerate(balls):
            if x+p not in rev:
                continue
            if y+q not in rev[x+p]:
                continue
            if uf.unite(i, rev[x+p][y+q]):
                score -= 1

        ans = min(ans, score)

    return ans


if __name__ == "__main__":
    N = int(input())
    balls = [tuple(map(int, input().split())) for _ in range(N)]

    ans = picking_up(N, balls)
    print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
INF = float("inf")


def solve(N: int, x: "List[int]", y: "List[int]"):
    x, y = zip(*sorted(list(zip(x, y))))
    p_cand = [x[j]-x[i] for i in range(N) for j in range(i+1, N)]
    q_cand = [y[j]-y[i] for i in range(N) for j in range(i+1, N)]

    minimum = INF
    for p, q in set(zip(p_cand, q_cand)):
        # print("(p, q) = ({}, {})".format(p, q))
        xy = list(zip(x, y))
        cost = 0
        while len(xy) > 0:
            xx, yy = xy.pop()
            cost += 1
            # print(xx, yy, xy, xx-p, yy-q)
            while (xx-p, yy-q) in xy:
                xy.remove((xx-p, yy-q))
                xx -= p
                yy -= q
        if minimum >= cost:
            minimum = cost
    print(minimum)

    return


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, collections
N = int(input())
XY = sorted([[int(_) for _ in input().split()] for _ in range(N)])
count = collections.defaultdict(int)
for i, j in itertools.combinations(range(N), 2):
    x1, y1 = XY[i]
    x2, y2 = XY[j]
    print(i, j, XY[i], XY[j])
    count[y2 - y1 + (x2 - x1) * 10**10] += 1
if count:
    print(N - max(count.values()))
else:
    print(1)

Submission status: Wrong Answer

Solution code:
import itertools, collections
N = int(input())
XY = [[int(_) for _ in input().split()] for _ in range(N)]
count = collections.defaultdict(int)
for i, j in itertools.combinations(range(N), 2):
    x1, y1 = XY[i]
    x2, y2 = XY[j]
    count[abs(x1 - x2) + abs(y1 - y2) * 10**10] += 1
if count:
    print(N - max(count.values()))
else:
    print(1)

Submission status: Wrong Answer

Solution code:
from collections import Counter
n = int(input())

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

l = []
pre = [x[0], y[0]]
for i in range(1, n):
    for j in range(1, n):
        if i == j:
            continue
        l.append("{}_{}".format(x[i] - pre[0], y[i] - pre[1]))
    pre = [x[i], y[i]]
if len(l) > 0:
    c = Counter(l)
    min_cost = 10**9
    for idx in range(len(c)):
        p, q = map(int, c.most_common()[idx][0].split("_"))

        cost = 1
        pre = [x[0], y[0]]
        for i in range(1, n):
            if not(pre[0] == x[i] - p and pre[1] == y[i] - q):
                cost += 1
            pre = [x[i], y[i]]
        min_cost = min(cost, min_cost)
    print(min_cost)
else:
    print(1)

Submission status: Wrong Answer

Solution code:
from collections import Counter
n = int(input())

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

l = []
pre = [x[0], y[0]]
for i in range(1, n):
    for j in range(1, n):
        if i == j:
            continue
        l.append("{}_{}".format(x[i] - pre[0], y[i] - pre[1]))
    pre = [x[i], y[i]]
if len(l) > 0:
    c = Counter(l)
    p, q = map(int, c.most_common()[0][0].split("_"))

    cost = 1
    pre = [x[0], y[0]]
    for i in range(1, n):
        if not(pre[0] == x[i] - p and pre[1] == y[i] - q):
            cost += 1
        pre = [x[i], y[i]]
    print(cost)
else:
    print(1)

Submission status: Wrong Answer

Solution code:
N = int(input())
xy = [list(map(int, input().split())) for _ in range(N)]
x, y = [], []
for i, j in xy:
    x += [i]
    y += [j]
memo = {}
for i in range(N):
    for j in range(N):
        if i == j:
            continue
        p = x[j] - x[i]
        q = y[j] - y[i]
        pq = str(i) + str(j) + '_' + str(p) + str(q)
        for k in range(N):
            for l in range(N):
                if k == l:
                    continue
                if (x[k] - x[l]) == p and (y[k] - y[l]) == q:
                    if pq in memo:
                        memo[pq] += 1
                    else:
                        memo[pq] = 1
if N != 1:
    print(N-max(memo.values()))
else:
    print('1')

Submission status: Wrong Answer

Solution code:
N = int(input())
xy = [list(map(int, input().split())) for _ in range(N)]
x, y = [], []
for i, j in xy:
    x += [i]
    y += [j]
memo = {}
for i in range(N):
    for j in range(N):
        if i == j:
            continue
        p = x[j] - x[i]
        q = y[j] - y[i]
        pq = str(i) + str(j) + str(p) + str(q)
        for k in range(N):
            for l in range(N):
                if k == l:
                    continue
                if (x[k] - x[l]) == p and (y[k] - y[l]) == q:
                    if pq in memo:
                        memo[pq] += 1
                    else:
                        memo[pq] = 1
if N != 1:
    print(N-max(memo.values()))
else:
    print('1')

Submission status: Wrong Answer

Solution code:
N = int(input())
xy = [list(map(int, input().split())) for _ in range(N)]
x, y = [], []
for i, j in xy:
    x += [i]
    y += [j]
memo = {}
for i in range(N):
    for j in range(N):
        if i == j:
            continue
        p = x[j] - x[i]
        q = y[j] - y[i]
        pq = str(i) + str(j) + str(p) + str(q)
        for k in range(N):
            for l in range(N):
                if (x[k] - x[l]) == p and (y[k] - y[l]) == q:
                    if pq in memo:
                        memo[pq] += 1
                    else:
                        memo[pq] = 1
if N != 1:
    print(N-max(memo.values()))
else:
    print('1')

Submission status: Wrong Answer

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

def xy_count(diff_XY,xy):
  count = 0
  for i in range(len(diff_XY)):
    if xy in diff_XY[i]:
      count += 1
  return count

XY.sort()
for i in range(N):
  XY.append(list([int(i) for i in input().split()]))

diff_XY = [[[0] * 2 for i in range(N)] for i in range(N)]
search_XY = []
ans = N

for i in range(N):
  for j in range(i+1,N):
    tmp = [XY[i][0]-XY[j][0],XY[i][1]-XY[j][1]]
    diff_XY[i][j] = tmp
    if tmp not in search_XY:
      search_XY.append(tmp)

ans_diff = 1
for xy in search_XY:
  ans_diff = max(ans_diff, xy_count(diff_XY,xy))

print(ans-ans_diff)

Submission status: Wrong Answer

Solution code:
N = int(input())
arr = [list(map(int, input().split())) for _ in range(N)]
cnt = {}
for i in range(N):
    for j in range(i+1,N):
        xy = (arr[j][0] - arr[i][0], arr[j][1] - arr[i][1])
        cnt.setdefault(xy, 0)
        cnt[xy] += 1
print(1 if cnt == {} else N - max(cnt.values()))

Submission status: Wrong Answer

Solution code:
import itertools
from collections import Counter


def main():
    N = int(input())
    data = []
    for _ in range(N):
        data.append( list(map(int, input().split())) )

    if N == 1:
        return 1
    else:
        common_data = []
        max_common_num = 0

        for obj in itertools.combinations(data, 2):
            # print(obj)
            common_data.append( str(obj[0][0] - obj[1][0]) + "_" + str(obj[0][1] - obj[1][1]) )

        # カウント
        counter = Counter(common_data)
        for word, cnt in counter.most_common():
            if cnt >= max_common_num:
                max_common_num = cnt

    return N - max_common_num
    # print(common_data)

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

Submission status: Wrong Answer

Solution code:
def b_picking_up(N, Positions):
    if N == 1:
        return 1  # 最初のボールに移動するのは必ずコスト1

    from collections import defaultdict
    difference_count = defaultdict(int)  # xの差分とyの差分の組について、現れた回数

    for i in range(N):
        for j in range(i + 1, N):
            # diff_x と diff_y がともに0となることは、入力の制約よりありえない
            diff_x = Positions[j][0] - Positions[i][0]
            diff_y = Positions[j][1] - Positions[i][1]
            difference_count[(diff_x, diff_y)] += 1
    return N - max(difference_count.values())  # 第2項はコスト0で移動できる座標の数

N = int(input())
Positions = [[int(i) for i in input().split()] for j in range(N)]
print(b_picking_up(N, Positions))

Submission status: Wrong Answer

Solution code:
import sys

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

    if n <= 2:
        print(1)
        sys.exit()

    w = [tuple(map(int,input().split())) for x in range(n)]
    w.sort(key=lambda x: x[0])

    pqs = {}
    for i in range(n):
        for j in range(i+1,n):
            x = w[j][0] - w[i][0]
            y = w[j][1] - w[i][1]
            if (x,y) not in pqs:
                pqs[(x,y)] = 1
            else:
                pqs[(x,y)] += 1

    print(n - max(pqs.values()))

if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
import itertools
from collections import Counter


def main():
    N = int(input())
    data = []
    for _ in range(N):
        data.append( list(map(int, input().split())) )

    if N == 1:
        return 1
    else:
        common_data = []
        max_common_num = 0

        for obj in itertools.combinations(data, 2):
            # print(obj)
            common_data.append( str(obj[0][0] - obj[1][0]) + "_" + str(obj[0][1] - obj[1][1]) )

        # カウント
        counter = Counter(common_data)
        for word, cnt in counter.most_common():
            if cnt >= max_common_num:
                max_common_num = cnt

    print(N - max_common_num)
    # print(common_data)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import numpy as np

def main():
    N = int(input())
    if N == 1:
        print(1)
        return
    ball = np.empty((N,2), int)
    for i in range(N):
        s = input().split()
        x = int(s[0])
        y = int(s[1])
        ball[i][0] = x
        ball[i][1] = y
    diffs = []
    for i in range(N-1):
        for j in range(i+1, N):
            x_diff = ball[i][0] - ball[j][0]
            y_diff = ball[i][1] - ball[j][1]
            ball_diff = [x_diff, y_diff]
            diffs.append(ball_diff)
    count_num = 0
    for diff in diffs:
        num = diffs.count(diff)
        if num > count_num:
            count_num = num
    print(N - count_num)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import itertools
from collections import Counter


def main():
    N = int(input())
    data = []
    for _ in range(N):
        data.append( list(map(int, input().split())) )

    if N == 1:
        return 1
    else:
        common_data = []
        max_common_num = 0

        for obj in itertools.combinations(data, 2):
            # print(obj)
            common_data.append( str(obj[0][0] - obj[1][0]) + "_" + str(obj[0][1] - obj[1][1]) )

        # カウント
        counter = Counter(common_data)
        for word, cnt in counter.most_common():
            max_common_num = cnt
            break

    print(N - max_common_num)
    # print(common_data)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def gcd(a, b):
    if b < 0:
        return gcd(a, -b)
    if b == 0:
        return a
    else:
        return gcd(b, a%b)

def solve():
    N = int(raw_input())
    xy = [None] * N
    for i in range(N):
        xi, yi = [int(_) for _ in raw_input().split()]
        xy[i] = (xi, yi)
    xy.sort()
    pq_dict = []
    def AddToPQDict(ele):
        pq, i, j, _gcd = ele
        added_flag = False
        for ind in range(0, len(pq_dict)):
            if pq_dict[ind][0] == pq:
                subdict_added = False
                for subdict in pq_dict[ind][1]:
                    if i in subdict.keys():
                        subdict.setdefault(j,  subdict[i] + _gcd)
                        subdict_added = True
                        break
                    elif j in subdict.keys():
                        subdict.setdefault(i, subdict[i] - _gcd)
                        subdict_added = True
                        break
                if not subdict_added:
                    tmp_dict = {i:0, j:_gcd}
                    pq_dict[ind][1].append(tmp_dict)
                added_flag = True
                break
            elif pq_dict[ind][0] > pq:
                tmp_dict = {i:0, j:_gcd}
                pq_dict.insert(ind, (pq, [tmp_dict]))
                added_flag = True
                break
        if not added_flag:
            tmp_dict = {i:0, j:_gcd}
            pq_dict.append((pq, [tmp_dict]))
        # print pq
        # print "i = " + str(i) + ", j = " + str(j)
        # print pq_dict

    for i in range(N):
        for j in range(i+1, N):
            p = xy[j][0] - xy[i][0]
            q = xy[j][1] - xy[i][1]
            _gcd = gcd(p,q)
            # print "i = " + str(i) + ", j = " + str(j)
            # print p, q, _gcd
            p = p / _gcd
            q = q / _gcd
            AddToPQDict(((p,q),i,j, _gcd))

    maxcntpq = 0
    # print pq_dict
    for i in range(len(pq_dict)):
        num_subdict = len(pq_dict[i][1])
        cnt = - num_subdict
        # Check if 1, 2, ...
        MinMod = 10**10
        MulPQ = []
        for subdict in pq_dict[i][1]:
            MulPQ += subdict.values()
            MinMod = min(MinMod, subdict.values()[1])
        MulPQ.sort()
        mulPQ_cnt = 2
        for ele in MulPQ:
            if ele == 0 or ele == MinMod:
                cnt += 1
            elif ele % MinMod == 0:
                tmp_mul = ele / MinMod
                if tmp_mul == mulPQ_cnt:
                    cnt += 1
                elif tmp_mul == mulPQ_cnt + 1:
                    cnt += 1
                else:
                    break
        # for subdict in pq_dict[i][1]:
        #     cnt += len(subdict)
        if cnt > maxcntpq:
            maxcntpq = cnt
    print N - maxcntpq

if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
from itertools import permutations

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

for b1, b2 in permutations(balls, 2):
    p, q = b1[0] - b2[0], b1[1] - b2[1]
    if p != 0 or q != 0:
        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:
                d, mod = None, None
                if p == 0:
                    mod = dy % q
                    d = dx
                else:
                    mod = dx % p
                    d = dy
                if mod == 0 and d == 0:
                    sub += 1
        cost = min(cost, n - sub)

print(max(cost, 1))

Submission status: Wrong Answer

Solution code:
import collections
N = int(input())
if N == 1:
  print(1)
elif N == 2:
  print(1)
else:
  ball = [tuple(map(int, input().split())) for _ in range(N)]
  diff = [tuple((ball[i][0] - ball[j][0], ball[i][1] - ball[j][1])) for i in range(N) for j in range(i + 1, N)]
  c = collections.Counter(diff)
  ans = c.most_common()[0][1]
  print(N - ans)

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 or q != 0:
        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:
                d, mod = None, None
                if p == 0:
                    mod = dy % q
                    d = dx
                else:
                    mod = dx % p
                    d = dy
                if mod == 0 and d == 0:
                    sub += 1
        cost = min(cost, n - sub)

print(max(cost, 1))

Submission status: Wrong Answer

Solution code:
def b_picking_up(N, Positions):
    if N == 1:
        return 1

    from collections import defaultdict
    difference_count = defaultdict(int)  # xの差分とyの差分の組について、現れた回数
    before_x, before_y = Positions[0]
    for x, y in Positions[1:]:
        # diff_x と diff_y がともに0となることは、入力の制約よりありえない
        diff_x, diff_y = x - before_x, y - before_y
        difference_count[(diff_x, diff_y)] += 1
        before_x, before_y = x, y
    # print(difference_count)
    difference_count = sorted(difference_count.items(), key=lambda x: x[1], reverse=True)
    # print(difference_count)
    p, q = difference_count[0][0]

    ans = 1
    before_x, before_y = Positions[0]
    for x, y in Positions[1:]:
        diff_x, diff_y = x - before_x, y - before_y
        if (diff_x, diff_y) != (p, q):
            ans += 1
        before_x, before_y = x, y
    return ans

N = int(input())
Positions = [[int(i) for i in input().split()] for j in range(N)]
print(b_picking_up(N, Positions))

Submission status: Wrong Answer

Solution code:
import numpy as np

def main():
    N = int(input())
    if N == 1:
        print(1)
        return
    ball = np.empty((N,2), int)
    for i in range(N):
        s = input().split()
        x = int(s[0])
        y = int(s[1])
        ball[i][0] = x
        ball[i][1] = y
    diffs = []
    for i in range(N-1):
        for j in range(i+1, N):
            x_diff = ball[i][0] - ball[j][0]
            y_diff = ball[i][1] - ball[j][1]
            ball_diff = [x_diff, y_diff]
            diffs.append(ball_diff)
    count_num = 0
    for diff in diffs:
        count = diffs.count(diff)
        if count > count_num:
            count_num = count
    print(N - count_num)

if __name__ == "__main__":
    main()

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 or q != 0:
        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)