Problem:


Score : 300 points

Problem Statement

There are N balls in a two-dimensional plane. The i-th ball is at coordinates (x_i, y_i).

We will collect all of these balls, by choosing two integers p and q such that p \neq 0 or q \neq 0 and then repeating the following operation:

Choose a ball remaining in the plane and collect it. Let (a, b) be the coordinates of this ball. If we collected a ball at coordinates (a - p, b - q) in the previous operation, the cost of this operation is 0. Otherwise, including when this is the first time to do this operation, the cost of this operation is 1.

Find the minimum total cost required to collect all the balls when we optimally choose p and q.

Constraints

1 \leq N \leq 50

|x_i|, |y_i| \leq 10^9

If i \neq j, x_i \neq x_j or y_i \neq y_j.

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
x_1 y_1
:
x_N y_N

Output

Print the minimum total cost required to collect all the balls.

Sample Input 1

2
1 1
2 2

Sample Output 1

1

If we choose p = 1, q = 1, we can collect all the balls at a cost of 1 by collecting them in the order (1, 1), (2, 2).

Sample Input 2

3
1 4
4 6
7 8

Sample Output 2

1

If we choose p = -3, q = -2, we can collect all the balls at a cost of 1 by collecting them in the order (7, 8), (4, 6), (1, 4).

Sample Input 3

4
1 1
1 2
2 1
2 2

Sample Output 3

2



Sample input:
2
1 1
2 2


Sample output:
1

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
def main():
    N = int(input())
    if N == 1:print(1);exit();
    x = [None] * N
    y = [None] * N
    for i in range(N):
        x[i], y[i] = map(int, input().split())
    
    diff = []
    nums = []
    for i in range(N-1):
        for j in range(i+1,N):
            if (x[j]-x[i],y[j]-y[i]) in diff:
                nums[diff.index((x[j]-x[i],y[j]-y[i]))] += 1
            else:
                diff.append((x[j]-x[i],y[j]-y[i]))
                nums.append(1)
    # print(diff)
    # print(nums)
    print(N-max(nums))

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from itertools import combinations
N = int(input())
d = [list(map(int, input().split())) for _ in range(N)]

dd = dict()
t = 0
ans = 0

for n ,m in combinations(d, 2):
    if n[0] != m[0] and n[1] != m[1]:
        a = (m[1]-n[1])/(m[0]-n[0])
        if a in dd:
            dd[a] += 1
        else:
            dd.setdefault(a, 1)
    else:
        ans += 1

print(ans + len(dd.values()))

Submission status: Wrong Answer

Solution code:
from itertools import combinations
N = int(input())
d = [list(map(int, input().split())) for _ in range(N)]

dd = dict()
t = 0

for n ,m in combinations(d, 2):
    if n[0] != m[0] and n[1] != m[1]:
        a = (m[1]-n[1])/(m[0]-n[0])
        if a in dd:
            dd[a] += 1
        else:
            dd.setdefault(a, 1)

print(len(dd.values()))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))
# 受け渡されたすべての要素からsubだけ引く.リストを*をつけて展開しておくこと


def a_int(): return int(read())


def ints(): return list(map(int, read().split()))


def read_col(H):
    '''H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


def read_tuple(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_matrix(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    # return [list(map(int, read().split())) for _ in range(H)] # 内包表記はpypyでは遅いため


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter, xor, add
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  # , insort_left, insort_right
from functools import reduce
from math import gcd


def lcm(a, b):
    # 最小公倍数
    g = gcd(a, b)
    return a // g * b


# https://atcoder.jp/contests/diverta2019-2/tasks/diverta2019_2_b
N = a_int()
XY = read_tuple(N)
if N == 1:
    print(1)
    exit()
# q,pは何通りありえる？N**2//2通りぐらい
# p,qを決定したらあとは直線に乗っているか確かめれば良い
# 点に当たるたびにO(N)かけて調べれば良い
# 以下のO(n**4)のプログラムが可能
# for q,p全通り
#     while ある点を選択
#        その点の+p+qを見てボールを消す
#     コストをmin
# と思ったけど、ただ単純にp,qで拾えるボールの個数を数えればいいかも

PQcandi = []
for po1, po2 in combinations(XY, r=2):
    dx = po1[0] - po2[0]
    dy = po1[1] - po2[1]
    if dx < 0:
        dx *= -1
        dy *= -1
    elif dx == 0:
        dy = abs(dy)

    PQcandi.append((dx, dy))


def del_ball(p, q, XYtmp):
    ret = []
    # x軸にソートしてあるので左から拾っていく
    x, y = XYtmp[0]
    for xx, yy in XYtmp[1:]:
        if xx == x + p and yy == y + q:
            x += p
            y += q
        else:
            ret.append((xx, yy))

    return ret


from copy import deepcopy
ans = INF
for p, q in PQcandi:
    XYtmp = deepcopy(XY)
    anstmp = 0
    while XYtmp:
        anstmp += 1
        XYtmp = del_ball(p, q, XYtmp)
    # print(p, q, anstmp)
    ans = min(ans, anstmp)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))
# 受け渡されたすべての要素からsubだけ引く.リストを*をつけて展開しておくこと


def a_int(): return int(read())


def ints(): return list(map(int, read().split()))


def read_col(H):
    '''H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


def read_tuple(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_matrix(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    # return [list(map(int, read().split())) for _ in range(H)] # 内包表記はpypyでは遅いため


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter, xor, add
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  # , insort_left, insort_right
from functools import reduce
from math import gcd


def lcm(a, b):
    # 最小公倍数
    g = gcd(a, b)
    return a // g * b


# https://atcoder.jp/contests/diverta2019-2/tasks/diverta2019_2_b
N = a_int()
XY = read_tuple(N)
if N == 1:
    print(1)
    exit()
# q,pは何通りありえる？N**2//2通りぐらい
# p,qを決定したらあとは直線に乗っているか確かめれば良い
# 点に当たるたびにO(N)かけて調べれば良い
# 以下のO(n**4)のプログラムが可能
# for q,p全通り
#     while ある点を選択
#        その点の+p+qを見てボールを消す
#     コストをmin
# と思ったけど、ただ単純にp,qで拾えるボールの個数を数えればいいかも

PQcandi = []
for po1, po2 in combinations(XY, r=2):
    dx = po1[0] - po2[0]
    dy = po1[1] - po2[1]
    if dx < 0:
        dx *= -1
        dy *= -1
    elif dx == 0:
        dy = abs(dy)

    PQcandi.append((dx, dy))


def del_ball(p, q, XYtmp):
    ret = []
    # x軸にソートしてあるので左から拾っていく
    x, y = XYtmp[0]
    for xxyy in XYtmp[1:]:
        if xxyy == (x + p, y + q):
            x += p
            y += q
        else:
            ret.append(xxyy)

    return ret


from copy import deepcopy
ans = INF
for p, q in PQcandi:
    XYtmp = deepcopy(XY)
    anstmp = 0
    while XYtmp:
        anstmp += 1
        XYtmp = del_ball(p, q, XYtmp)
    # print(p, q, anstmp)
    ans = min(ans, anstmp)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))
# 受け渡されたすべての要素からsubだけ引く.リストを*をつけて展開しておくこと


def a_int(): return int(read())


def ints(): return list(map(int, read().split()))


def read_col(H):
    '''H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


def read_tuple(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_matrix(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    # return [list(map(int, read().split())) for _ in range(H)] # 内包表記はpypyでは遅いため


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter, xor, add
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  # , insort_left, insort_right
from functools import reduce
from math import gcd


def lcm(a, b):
    # 最小公倍数
    g = gcd(a, b)
    return a // g * b


# https://atcoder.jp/contests/diverta2019-2/tasks/diverta2019_2_b
N = a_int()
XY = read_tuple(N)
# q,pは何通りありえる？N**2//2通りぐらい
# p,qを決定したらあとは直線に乗っているか確かめれば良い
# 点に当たるたびにO(N)かけて調べれば良い
# 以下のO(n**4)のプログラムが可能
# for q,p全通り
#     while ある点を選択
#        ある点とその直線状のボールを削除

PQcandi = set()
for po1, po2 in combinations(XY, r=2):
    dx = po1[0] - po2[0]
    dy = po1[1] - po2[1]
    if dx < 0:
        dx *= -1
        dy *= -1
    elif dx == 0:
        dy = abs(dy)

    PQcandi.add((dx, dy))


def del_ball(p, q, XYtmp):
    ret = []
    # x軸にソートしてあるので左から拾っていく
    x, y = XYtmp[0]
    for xxyy in XYtmp[1:]:
        if xxyy == (x + p, y + q):
            x += p
            y += q
        else:
            ret.append(xxyy)

    return ret


from copy import deepcopy
ans = INF
for p, q in PQcandi:
    XYtmp = deepcopy(XY)
    anstmp = 0
    while XYtmp:
        anstmp += 1
        XYtmp = del_ball(p, q, XYtmp)
    # print(p, q, anstmp)
    ans = min(ans, anstmp)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))
# 受け渡されたすべての要素からsubだけ引く.リストを*をつけて展開しておくこと


def a_int(): return int(read())


def ints(): return list(map(int, read().split()))


def read_col(H):
    '''H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


def read_tuple(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_matrix(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    # return [list(map(int, read().split())) for _ in range(H)] # 内包表記はpypyでは遅いため


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter, xor, add
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  # , insort_left, insort_right
from functools import reduce
from math import gcd


def lcm(a, b):
    # 最小公倍数
    g = gcd(a, b)
    return a // g * b


# https://atcoder.jp/contests/diverta2019-2/tasks/diverta2019_2_b
N = a_int()
XY = read_tuple(N)
# q,pは何通りありえる？N**2//2通りぐらい
# p,qを決定したらあとは直線に乗っているか確かめれば良い
# 点に当たるたびにO(N)かけて調べれば良い
# 以下のO(n**4)のプログラムが可能
# for q,p全通り
#     while ある点を選択
#        ある点とその直線状のボールを削除

PQcandi = set()
for po1, po2 in combinations(XY, r=2):
    dx = po1[0] - po2[0]
    dy = po1[1] - po2[1]
    if dx < 0:
        dx *= -1
        dy *= -1
    elif dx == 0:
        dy = abs(dy)

    PQcandi.add((dx, dy))


def del_ball(p, q, XYtmp):
    ret = []
    # x軸にソートしてあるので左から拾っていく
    x, y = XYtmp[0]
    for xxyy in XYtmp[1:]:
        if xxyy == (x + p, y + q):
            x += p
            y += q
        else:
            ret.append(xxyy)

    return ret


ans = INF
for p, q in PQcandi:
    XYtmp = XY.copy()
    anstmp = 0
    while XYtmp:
        anstmp += 1
        XYtmp = del_ball(p, q, XYtmp)
    # print(p, q, anstmp)
    ans = min(ans, anstmp)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))
# 受け渡されたすべての要素からsubだけ引く.リストを*をつけて展開しておくこと


def a_int(): return int(read())


def ints(): return list(map(int, read().split()))


def read_col(H):
    '''H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


def read_tuple(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_matrix(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    # return [list(map(int, read().split())) for _ in range(H)] # 内包表記はpypyでは遅いため


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter, xor, add
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  # , insort_left, insort_right
from functools import reduce
from math import gcd


def lcm(a, b):
    # 最小公倍数
    g = gcd(a, b)
    return a // g * b


# https://atcoder.jp/contests/diverta2019-2/tasks/diverta2019_2_b
N = a_int()
XY = read_tuple(N)
# q,pは何通りありえる？N**2//2通りぐらい
# p,qを決定したらあとは直線に乗っているか確かめれば良い
# 点に当たるたびにO(N)かけて調べれば良い
# 以下のO(n**4)のプログラムが可能
# for q,p全通り
#     while ある点を選択
#        ある点とその直線状のボールを削除

PQcandi = set()
for po1, po2 in combinations(XY, r=2):
    dx = po1[0] - po2[0]
    dy = po1[1] - po2[1]
    if dx < 0:
        dx *= -1
        dy *= -1
    PQcandi.add((dx, dy))


def del_ball(p, q, XYtmp):
    ret = []
    # x軸にソートしてあるので左から拾っていく
    x, y = XYtmp[0][0], XYtmp[0][1]
    for xxyy in XYtmp[1:]:
        if xxyy == (x + p, y + q):
            x += p
            y += q
        else:
            ret.append(xxyy)

    return ret


ans = INF
for p, q in PQcandi:
    XYtmp = XY.copy()
    anstmp = 0
    while XYtmp:
        anstmp += 1
        XYtmp = del_ball(p, q, XYtmp)
    # print(p, q, anstmp)
    ans = min(ans, anstmp)
print(ans)

Submission status: Wrong Answer

Solution code:
from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))

n=int(input())
xy=[lnii() for i in range(n)]
xy.sort(key=lambda x:x[0])

ans=n

pq=[]
for i in range(n-1):
  for j in range(i+1,n):
    t_p=xy[j][0]-xy[i][0]
    t_q=xy[j][1]-xy[i][1]
    pq.append([t_p,t_q])

for p,q in pq:
  cnt=0
#  for x,y in xy:
#    if [x+p,y+q] in xy:
  for i in range(n):
    for j in range(i+1,n):
        x1,y1=xy[i]
        x2,y2=xy[j]
        if (x2-x1)==p and (y2-y1)==q:
          cnt+=1
  ans=min(ans,n-cnt)

print(ans)

Submission status: Wrong Answer

Solution code:
from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))

n=int(input())
xy=[lnii() for i in range(n)]
xy.sort(key=lambda x:x[0])

ans=n

pq=[]
for i in range(n-1):
  for j in range(1,n):
    t_p=xy[j][0]-xy[i][0]
    t_q=xy[j][1]-xy[i][1]
    pq.append([t_p,t_q])

for p,q in pq:
  cnt=0
  for x,y in xy:
    if [x+p,y+q] in xy:
        cnt+=1
  ans=min(ans,n-cnt)

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))
# 受け渡されたすべての要素からsubだけ引く.リストを*をつけて展開しておくこと


def a_int(): return int(read())


def ints(): return list(map(int, read().split()))


def read_col(H):
    '''H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


def read_tuple(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_matrix(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    # return [list(map(int, read().split())) for _ in range(H)] # 内包表記はpypyでは遅いため


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter, xor, add
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  # , insort_left, insort_right
from functools import reduce
from math import gcd


def lcm(a, b):
    # 最小公倍数
    g = gcd(a, b)
    return a // g * b


# https://atcoder.jp/contests/diverta2019-2/tasks/diverta2019_2_b
N = a_int()
XY = read_tuple(N)
# q,pは何通りありえる？N**2//2通りぐらい
# p,qを決定したらあとは直線に乗っているか確かめれば良い
# 点に当たるたびにO(N)かけて調べれば良い
# 以下のO(n**4)のプログラムが可能
# for q,p全通り
#     while ある点を選択
#        ある点とその直線状のボールを削除

PQcandi = set()
for po1, po2 in combinations(XY, r=2):
    dx = po1[0] - po2[0]
    dy = po1[1] - po2[1]
    if dx < 0:
        dx *= -1
        dy *= -1
    PQcandi.add((dx, dy))


def del_ball(p, q, x, y, XYtmp):
    ret = []
    if p != 0 and q != 0:
        for xx, yy in XYtmp:
            # x座標について条件をクリアするか？
            if not((x - xx) * q == (y - yy) * p and (y - yy) // q * q == (y - yy)):
                # if (x - xx) // p != (x - xx) / p or (y - yy) // q != (y - yy) / q:
                ret.append((xx, yy))

    if p == 0:
        # y座標だけ一致するか確認
        for xx, yy in XYtmp:
            # x座標について条件をクリアするか？
            # x座標が一致しててもy座標が条件を満たしてほしい
            if x - xx != 0 or (y - yy) // q * q != (y - yy):
                ret.append((xx, yy))

    if q == 0:
        for xx, yy in XYtmp:
            # x座標について条件をクリアするか？
            if y - yy != 0 or (x - xx) // p * p != (x - xx):
                ret.append((xx, yy))
    # print(ret)
    return ret


ans = INF
for p, q in PQcandi:
    XYtmp = XY.copy()
    anstmp = 0
    while XYtmp:
        anstmp += 1
        x, y = XYtmp.pop()
        XYtmp = del_ball(p, q, x, y, XYtmp)
    # print(p, q, anstmp)
    ans = min(ans, anstmp)
print(ans)

Submission status: Wrong Answer

Solution code:
from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))

n=int(input())
xy=[lnii() for i in range(n)]
xy.sort(key=lambda x:x[0])

ans=n

pq=[]
for i in range(n):
  for j in range(n):
    if i==j:
      continue
    t_p=xy[j][0]-xy[i][0]
    t_q=xy[j][1]-xy[i][1]
    pq.append([t_p,t_q])

for p,q in pq:
  cnt=0
  for j in range(n-1):
    for k in range(j+1,n):
      x1,y1=xy[j]
      x2,y2=xy[k]
      if x2-x1==p and y2-y1==q:
        cnt+=1
  ans=min(ans,n-cnt)

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))
# 受け渡されたすべての要素からsubだけ引く.リストを*をつけて展開しておくこと


def a_int(): return int(read())


def ints(): return list(map(int, read().split()))


def read_col(H):
    '''H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


def read_tuple(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_matrix(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    # return [list(map(int, read().split())) for _ in range(H)] # 内包表記はpypyでは遅いため


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter, xor, add
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  # , insort_left, insort_right
from functools import reduce
from math import gcd


def lcm(a, b):
    # 最小公倍数
    g = gcd(a, b)
    return a // g * b


# https://atcoder.jp/contests/diverta2019-2/tasks/diverta2019_2_b
N = a_int()
XY = read_tuple(N)
# q,pは何通りありえる？N**2//2通りぐらい
# p,qを決定したらあとは直線に乗っているか確かめれば良い
# 点に当たるたびにO(N)かけて調べれば良い
# 以下のO(n**4)のプログラムが可能
# for q,p全通り
#     while ある点を選択
#        ある点とその直線状のボールを削除

PQcandi = set()
for po1, po2 in combinations(XY, r=2):
    dx = po1[0] - po2[0]
    dy = po1[1] - po2[1]
    if dx < 0:
        dx *= -1
        dy *= -1
    PQcandi.add((dx, dy))


def del_ball(p, q, x, y, XYtmp):
    ret = []
    if p != 0 and q != 0:
        for xx, yy in XYtmp:
            # x座標について条件をクリアするか？
            if not((x - xx) / p == (y - yy) / q and (y - yy) // q == (y - yy) / q):
                # if (x - xx) // p != (x - xx) / p or (y - yy) // q != (y - yy) / q:
                ret.append((xx, yy))

    if p == 0:
        # y座標だけ一致するか確認
        for xx, yy in XYtmp:
            # x座標について条件をクリアするか？
            if x - xx != 0 or (y - yy) // q != (y - yy) / q:  # x座標が一致しててもy座標が条件を満たしてほしい
                ret.append((xx, yy))

    if q == 0:
        for xx, yy in XYtmp:
            # x座標について条件をクリアするか？
            if y - yy != 0 or (x - xx) // p != (x - xx) / p:
                ret.append((xx, yy))
    # print(ret)
    return ret


ans = INF
for p, q in PQcandi:
    XYtmp = XY.copy()
    anstmp = 0
    while XYtmp:
        anstmp += 1
        x, y = XYtmp.pop()
        XYtmp = del_ball(p, q, x, y, XYtmp)
    # print(p, q, anstmp)
    ans = min(ans, anstmp)
print(ans)

Submission status: Wrong Answer

Solution code:
from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))

n=int(input())
xy=[lnii() for i in range(n)]
xy.sort(key=lambda x:x[0])

ans=n

pq=[]
for i in range(n-1):
  for j in range(1,n):
    t_p=xy[j][0]-xy[i][0]
    t_q=xy[j][1]-xy[i][1]
    pq.append([t_p,t_q])

for p,q in pq:
  cnt=0
  for j in range(n-1):
    for k in range(1,n):
      x1,y1=xy[j]
      x2,y2=xy[k]
      if x2-x1==p and y2-y1==q:
        cnt+=1
  ans=min(ans,n-cnt)

print(ans)

Submission status: Wrong Answer

Solution code:
from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))

n=int(input())
xy=[lnii() for i in range(n)]
xy.sort(key=lambda x:x[0])

ans=n

pq=[]
for i in range(n-1):
  for j in range(1,n):
    t_p=xy[j][0]-xy[i][0]
    t_q=xy[j][1]-xy[i][1]
    pq.append([t_p,t_q])

for p,q in pq:
  cnt=0
  for j in range(n-1):
    for k in range(j+1,n):
      x1,y1=xy[j]
      x2,y2=xy[k]
      if x2-x1==p and y2-y1==q:
        cnt+=1
  ans=min(ans,n-cnt)

print(ans)

Submission status: Wrong Answer

Solution code:
from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))

n=int(input())
xy=[lnii() for i in range(n)]
xy.sort(key=lambda x:x[0])

ans=n

pq=[]
for i in range(n-1):
  for j in range(1,n):
    t_p=xy[j][0]-xy[i][0]
    t_q=xy[j][1]-xy[i][1]
    pq.append([t_p,t_q])

for p,q in pq:
  cnt=0
  for j in range(n-1):
    for k in range(j+1,n):
      x1,y1=xy[j]
      x2,y2=xy[k]
      if x2-x1==p and y2-y1==q:
        cnt+=1
  ans=min(ans,ans-cnt)

print(ans)

Submission status: Wrong Answer

Solution code:
from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))

n=int(input())
xy=[lnii() for i in range(n)]
xy.sort(key=lambda x:x[0])

ans=n

pq=[]
for i in range(n-1):
  for j in range(1,n):
    t_p=xy[j][0]-xy[i][0]
    t_q=xy[j][1]-xy[i][1]
    pq.append([t_p,t_q])

for p,q in pq:
  cnt=0
  for j in range(n-1):
    for k in range(1,n):
      x1,y1=xy[j]
      x2,y2=xy[k]
      if x2-x1==p and y2-y1==q:
        cnt+=1
  ans=min(ans,ans-cnt)

print(ans)

Submission status: Wrong Answer

Solution code:
from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))

n=int(input())
xy=[lnii() for i in range(n)]
xy.sort(key=lambda x:x[0])

ans=10**18

pq=[]
for i in range(n-1):
  for j in range(1,n):
    t_p=xy[j][0]-xy[i][0]
    t_q=xy[j][1]-xy[i][1]
    pq.append([t_p,t_q])

#for i in range(n-1):
#  p=xy[i+1][0]-xy[i][0]
#  q=xy[i+1][1]-xy[i][1]

for p,q in pq:
  t_ans=1
  for j in range(1,n):
      x1,y1=xy[j-1]
      x2,y2=xy[j]
      if x2-x1==p and y2-y1==q:
        t_ans+=0
      else:
        t_ans+=1
  ans=min(ans,t_ans)

print(ans)

Submission status: Wrong Answer

Solution code:
from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))

n=int(input())
xy=[lnii() for i in range(n)]
xy.sort(key=lambda x:x[0])

ans=10**18
for i in range(n-1):
  p=xy[i+1][0]-xy[i][0]
  q=xy[i+1][1]-xy[i][1]
  t_ans=1
  for j in range(1,n):
      x1,y1=xy[j-1]
      x2,y2=xy[j]
      if x2-x1==p and y2-y1==q:
        t_ans+=0
      else:
        t_ans+=1
  ans=min(ans,t_ans)

print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import combinations
N = int(input())
X = [list(map(int,input().split())) for _ in range(N)]
if N==1:
    print(1)
else:
    C = {}
    for z in combinations(X,2):
        x1,x2 = z
        a = x1[0]-x2[0]
        b = x1[1]-x2[1]
        if a>=0 and b>=0:
            if (a,b) not in C:
                C[(a,b)] = 0
            C[(a,b)] += 1
        elif a>=0 and b<0:
            if (a,b) not in C:
                C[(a,b)] = 0
            C[(a,b)] += 1
        elif a<0 and b>=0:
            if (-a,-b) not in C:
                C[(-a,-b)] = 0
            C[(-a,-b)] += 1
        elif a<0 and b<0:
            if (-a,-b) not in C:
                C[(-a,-b)] = 0
            C[(-a,-b)] += 1
    C = sorted(list(C.items()),key=lambda x:x[1],reverse=True)
    k = C[0][1]
    print(N-k)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
dic = defaultdict(int) #初期化する関数。

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

for i in range(N):
  for j in range(i+1,N):
    p = X[i][0] - X[j][0]
    q = X[i][1] - X[j][1]
    if p <0:
      p = -p;q=-q
    dic[(p,q)] +=1

path = max(dic.values())
ans = N-path
#print(dic)
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

from collections import Counter

def main():
    N = int(input())
    S = [tuple(map(int,input().split())) for _ in range(N)]

    if N == 1:
        print(1)
    else:
        cnt = []
        for i in range(N-1):
            xi, yi = S[i]
            for j in range(i+1,N):
                xj, yj = S[j]
                if xj<xi:
                    cnt.append((xi-xj, yi-yj))
                else:
                    cnt.append((xj-xi, yj-yi))
        A = Counter(cnt)
        ll = max(A.values())
        print(N-ll)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N, *XY = map(int, open(0).read().split())
X = XY[::2]
Y = XY[1::2]
ans = N
for i in range(N - 1):
    for j in range(N):
        if i == j:
            continue
        p = X[i] - X[j]
        q = Y[i] - Y[j]
        cnt = 0
        for k in range(N - 1):
            for l in range(N):
                if k == l:
                    continue
                if X[k] - X[l] == p and Y[k] - Y[l] == q:
                    cnt += 1
        ans = min(ans, N - cnt)
print(ans)