Problem p03006 (python)

Fixed submission:
# https://atcoder.jp/contests/diverta2019-2/tasks/diverta2019_2_b


from itertools import combinations
from collections import defaultdict

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

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

# points.sort()  # 先にソートしておくと大小関係の処理が楽

cnts = defaultdict(lambda: 0)
for pa, pb in combinations(points, 2):
    dx = pa[0] - pb[0]
    dy = pa[1] - pb[1]
    if dx < 0:  # 事前にソートしておくとココらへんの処理がいらなくなるよ
        dx *= -1
        dy *= -1
    if dx == 0:
        dy = max(dy, -dy)
    if dy == 0:
        dx = max(dx, -dx)
    cnts[(dx, dy)] += 1

print(N - max(cnts.values()))

Buggy submission (verdict: Runtime Error):
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 ある点を選択
#        その点の+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))

print(N - max(Counter(PQcandi).values()))


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

Buggy submission (verdict: Runtime Error):
# https://atcoder.jp/contests/diverta2019-2/tasks/diverta2019_2_b
# 問題文はよく読もうね！

# 実際にボールを拾っていくシミュレーションをしていっても十分間に合う

from itertools import combinations
from collections import defaultdict
from operator import itemgetter

N = int(input())
points = [tuple(map(int, input().split())) for _ in range(N)]
ans = 0


def is_online(x0, y0, xa, ya, p, q):
    # x0,y0を通る直線がp,qで与えられたときに、xa,yaがその線上にあるか判別
    dx = xa - x0
    dy = ya - y0
    if dx == 0 and dy == 0:
        return True
    elif dx == 0 or dy == 0:
        return False
    # print(x0, y0, xa, ya, p, q)
    return (dy / dx) == (q / p)  # 傾きが同じならば線上にある


def pickballs(balls):
    # cnt most frequent p,q
    global ans

    # 最適なpq探索
    cnts = defaultdict(lambda: 0)
    for pa, pb in combinations(balls, 2):
        dx = pa[0] - pb[0]
        dy = pa[1] - pb[1]
        if dx == 0 or dy == 0:
            continue
        if dx < 0:
            dx *= -1
            dy *= -1
        cnts[(dx, dy)] += 1
    p, q = max(cnts.items(), key=itemgetter(1))[0]

    # 最適な最初のpickball探索
    cnts = defaultdict(lambda: 0)
    for p0 in balls:
        for p1 in balls:
            if p0 == p1:
                continue
            if is_online(p0[0], p0[1], p1[0], p1[1], p, q):
                cnts[p0] += 1
    x, y = max(cnts.items(), key=itemgetter(1))[0]

    # 実際にpickball
    ans += 1
    ret = []
    for p1 in balls:
        if is_online(x, y, p1[0], p1[1], p, q):
            continue
        ret.append(p1)
    return ret


while points:
    points = pickballs(points)
print(ans)

Buggy submission (verdict: Runtime Error):
# https://atcoder.jp/contests/diverta2019-2/tasks/diverta2019_2_b


from itertools import combinations
from collections import defaultdict, Counter

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

# cnts = defaultdict(lambda: 0)
dxy = []
for pa, pb in combinations(points, 2):
    dx = pa[0] - pb[0]
    dy = pa[1] - pb[1]
    if dx < 0:
        dx *= -1
        dy *= -1
    dxy.append((dx, dy))
    # cnts[(dx, dy)] += 1

print(N - max(Counter(dxy).values()))

# print(N - max(cnts.values()))

Buggy submission (verdict: Runtime Error):
# https://atcoder.jp/contests/diverta2019-2/tasks/diverta2019_2_b


from itertools import combinations
from collections import defaultdict

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

cnts = defaultdict(lambda: 0)
for pa, pb in combinations(points, 2):
    dx = pa[0] - pb[0]
    dy = pa[1] - pb[1]
    if dx < 0:
        dx *= -1
        dy *= -1
    cnts[(dx, dy)] += 1

print(N - max(cnts.values()))