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
# -*- coding: utf-8 -*-
''' 
------------------------
author : iiou16
------------------------
'''

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

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

    sub_vals = {}
    for i in range(len(pos)):
        for j in range(len(pos)):
            if i > j:
                tmp = [pos[i][0] - pos[j][0], pos[i][1] - pos[j][1]]

                key = str(tmp[0]) + str(tmp[1])
                if key not in sub_vals:
                    sub_vals[key] = 1
                else:
                    sub_vals[key] += 1

    if len(sub_vals) == 0:
        max_val = 0
    else:
        max_val = max(sub_vals.values())
    print(sub_vals)
    print(N - max_val)

if __name__ == '__main__':
    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)]
    a = sorted(a, key=lambda x:x[0])

    x.sort()
    y.sort()

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

    from collections import Counter

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

    # p = csx.most_common()[0][0]
    p = [i for i,v in csx.most_common()]
    # print(p)
    # q = csy.most_common()[0][0]
    q = [i for i,v in csy.most_common()]

    ans = 10000000000
    for i in p:
        for j in q:
            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:
N = int(input())
XYi = [0] * N
for i in range(N):
    x, y = list(map(int, input().split()))
    XYi[i] = (x, y)
XYi = sorted(XYi, key=lambda t: t[0])

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 = 0
q = 0
maxv = 0
for i in dictX.keys():
    v = dictX[i]
    if v > maxv:
        maxv = v
        p = i

maxv = 0
for i in dictY.keys():
    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
print(cost)

Submission status: Wrong Answer

Solution code:
*D, = open(0)
n = int(D[0])
data = []
for i in range(n):
    x, y = D[i+1].split()
    data.append([int(x), int(y)])


table = {}
for i in range(0, len(data)):
    el = data[i]
    for j in range(i+1, len(data)):
        el2 = data[j]
        dis = '{},{}'.format(el[0]-el2[0], el[1]-el2[1])
#         print(i, j, dis)
        if dis in table.keys():
            table[dis].append([i, j])
        else:
            table[dis] = [[i, j]]

val = list(table.values())
val.sort(key=lambda x:len(x), reverse=True)


rest = list(range(len(data)))
cnt = 0
for it in val:
    cnt += 1
    for x, y in it:
        if x in rest and y in rest:
            if len(rest) == 2:
                rest.remove(x)
                rest.remove(y)
            else:
                rest.remove(x)
    if len(rest) == 0:
        break
    elif len(rest)==1:
        cnt += 1
        break

print(cnt)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env pypy
from __future__ import division, print_function

import os
import sys
from __builtin__ import xrange as range
from cStringIO import StringIO
from future_builtins import ascii, filter, hex, map, oct, zip
from io import IOBase

import __pypy__


def get_2dline(p1, p2):
    return p2[1] - p1[1], p1[0] - p2[0], p1[1] * p2[0] - p1[0] * p2[1]


def main():
    n = int(input())
    points = []
    for _ in range(n):
        points.append(tuple(map(int, input().split())))

    lines = set()
    for i in range(n):
        for j in range(n):
            a, b, c = get_2dline(points[i], points[j])
            lines.add((a, b))
    lines.discard((0, 0))

    res = n
    for p, q in lines:
        counter = set()
        for x, y in points:
            counter.add(p * x + q * y)
        res = min(res, len(counter))
    print(res)


# region fastio

BUFSIZE = 8192


class FastI(IOBase):
    def __init__(self, file):
        self._fd = file.fileno()
        self._buffer = StringIO()
        self.newlines = 0

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count("\n") + (not b)
            ptr = self._buffer.tell()
            self._buffer.seek(0, 2), self._buffer.write(b), self._buffer.seek(ptr)
        self.newlines -= 1
        return self._buffer.readline()


class FastO(IOBase):
    def __init__(self, file):
        self._fd = file.fileno()
        self._buffer = __pypy__.builders.StringBuilder()
        self.write = lambda s: self._buffer.append(s)

    def flush(self):
        os.write(self._fd, self._buffer.build())
        self._buffer = __pypy__.builders.StringBuilder()


def print(*args, **kwargs):
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


sys.stdin, sys.stdout = FastI(sys.stdin), FastO(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n=int(input())
w={}
d=[]
for i in range(n):
    x,y=map(int, input().split())
    d.append((x+y,x,y))

d.sort()
p=d[0][1]
q=d[0][2]
chk=0
for i in range(1,n):
    a=d[i][1]
    b=d[i][2]
    if (a-p,b-q) in w:
        w[(a-p,b-q)]+=1
    else:
        w[(a-p,b-q)]=1
    chk=max(chk,w[(a-p,b-q)])
    p=a
    q=b

print(1+(n-1-chk))

Submission status: Wrong Answer

Solution code:
n=int(input())
l=[]
if n==1 or n==2:
  print(1)
else:
  for iii in range(n):
    l.append(list(map(int,input().split())))
  dic={}
  for iii in range(n):
    for jjj in range(iii+1,n):
      if l[iii][0]-l[jjj][0]>=0:
        a=str(l[iii][0]-l[jjj][0])+"_"+str(l[iii][1]-l[jjj][1])
      else:
        a=str(l[jjj][0]-l[iii][0])+"_"+str(l[jjj][1]-l[iii][1])
      if a not in dic:
        dic[a]=0
      else:
        dic[a]+=1
  b=max(dic.values())
  print(n-b-1)

Submission status: Wrong Answer

Solution code:

N = int(input())
xy = [list(map(int, input().split())) for i in range(N)]
xy.sort(key=lambda x: x[0])
tilt_map = {}

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

    for i in range(N):
        for j in range(i+1, N):
            a = xy[i]
            b = xy[j]
            tilt_x = a[0] - b[0]
            tilt_y = a[1] - b[1]
            key = str(tilt_x) + ":" + str(tilt_y)
            if key in tilt_map:
                tilt_map[key] += 1
            else:
                tilt_map[key] = 1


    most_key = sorted(tilt_map.items(), key=lambda x: x[1], reverse=True)[0][0]

    idx = most_key.index(":")
    m_dx = int(most_key[:idx])
    m_dy = int(most_key[idx+1:])

    if m_dx == 0:
        if m_dy < 0:
            m_dy *= -1
        xy.sort(key=lambda x: x[1])
    else:
        if m_dx < 0:
            m_dx *= -1
            m_dy *= -1
        xy.sort(key=lambda x:x[0])

    pos = xy.pop(0)
    cost = 1

    while len(xy) > 0:
        next_x = pos[0] + m_dx
        next_y = pos[1] + m_dy
        for _xy in xy[::]:
            if _xy[0] == next_x and _xy[1] == next_y:
                xy.remove([next_x, next_y])
                pos = [next_x, next_y]
                break
        else:
            pos = xy.pop(0)
            cost += 1
    print(cost)

Submission status: Wrong Answer

Solution code:
n=int(input())

pts=[]
for i in range(n):
    pts.append(tuple(map(int,input().split())))

diffs={}
for i in range(n-1):
    for j in range(i+1,n):
        dx=pts[i][0]-pts[j][0]
        dy=pts[i][1]-pts[j][1]
        if dx<0 :
            dx=-dx
            dy=-dy
        key="{},{}".format(dx,dy)
        if key in diffs:
            diffs[key]+=1
        else:
            diffs[key]=1

max=1
maxkey=""
for k,v in diffs.items():
    if v>max:
        max=v
        maxkey=k

if max<2:
    print(n)
else:
    print(n-max)

Submission status: Wrong Answer

Solution code:
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())


def count_cost(xy: list, a: int):
    n = len(xy)
    done = [False]*n

    cnt = 0

    for i, (xi, yi) in enumerate(xy):
        if done[i]:
            continue

        done[i] = True
        for j, (xj, yj) in enumerate(xy):
            if j <= i:
                continue

            if xi == xj:
                continue

            elif (yi - yj) / (xi - xj) == a:
                done[j] = True

        cnt += 1


    return cnt


def count_cost_zero(xy: list):
    xuniq = set()
    for xi, _ in xy:
        xuniq.add(xi)

    return len(xuniq)




n = ni()
xy = [list(li()) for _ in range(n)]

ans = count_cost_zero(xy)
for i in range(n):
    for j in range(i+1, n):
        xi, yi = xy[i]
        xj, yj = xy[j]

        if xi == xj:
            continue

        a = (yi - yj) / (xi - xj)

        ans = min(ans, count_cost(xy, a))

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
# input = sys.stdin.readline
inf = 10 ** 18

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

x = [xi for xi, yi in xy]
y = [yi for xi, yi in xy]

ans = inf
for i in range(N - 1):
    xi, yi = xy[i]
    for j in range(i + 1, N):
        xj, yj = xy[j]
        #
        p = xj - xi
        q = yj - yi
        #
        ans_tmp = 0
        for n, (xn, yn) in enumerate(xy):
            xm = xn - p
            ym = yn - q
            # print("##", (xm, ym))
            if [xm, ym] not in xy: ans_tmp += 1
        #
        # print("#", xy, ans_tmp)
        if ans > ans_tmp: ans = ans_tmp

print(ans)

Submission status: Wrong Answer

Solution code:

def main():
    num = int(input())
    data = [list(map(int, input().split())) for i in range(num)]


    ans = num

    for i in range(num):
        for j in range(num):
            if i == j:
                continue

            now_kyori = [data[i][0] - data[j][0], data[i][1] - data[j][1]]
            visit_list = [0 for i in range(num)]
            visit_list[i], visit_list[j] = 1, 1

            kari_num = 1

            for k in range(num):
                if visit_list[k]:
                    continue

                now_data = data[k]

                flg = 1
                for l in range(num):
                    if visit_list[l]:
                        a = data[l][0] - now_data[0]
                        b = data[l][1] - now_data[1]

                        if now_kyori[0] == 0 and now_kyori[1] == 0:
                            if a == now_kyori[0] and b == now_kyori[0]:
                                flg = 0
                        elif now_kyori[0] == 0:
                            if a == now_kyori[0] and b % now_kyori[1] == 0:
                                if b // now_kyori[1] == 1 or b // now_kyori[1] == -1:
                                    flg = 0
                        elif now_kyori[1] == 0:
                            if b == now_kyori[1] and a % now_kyori[0] == 0:
                                if a // now_kyori[0] == 1 or a // now_kyori[0] == -1:
                                    flg = 0
                        else:
                            if a % now_kyori[0] == 0 and b % now_kyori[1] == 0:
                                if a // now_kyori[0] == b // now_kyori[1]:
                                    if a // now_kyori[0] == 1 or a // now_kyori[1] == -1:
                                        flg = 0
                        if flg == 0:
                            break

                if flg:
                    kari_num += 1
                visit_list[k] = 1


            ans = min(kari_num, ans)

    print(ans)






if __name__ == '__main__':
    main()

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_gap = [x_y[i+1][0]-x_y[i][0] for i in range(N-1)]
y_gap = [x_y[i+1][1]-x_y[i][1] for i in range(N-1)]
x_count = collections.Counter(x_gap)
y_count = collections.Counter(y_gap)
combination = [x_count.most_common()[0][0], y_count.most_common()[0][0]]

answer = 1
for i in range(len(x_gap)): 
  if x_gap[i] != combination[0] or y_gap[i] != combination[1]:
    answer+=1

print(answer)

Submission status: Wrong Answer

Solution code:
from collections import Counter
N = int(input())
l = []
pql = []
for i in range(N):
        x, y = map(int, input().split())
        l.append((x,y))
l.sort()
for i in range(N-1):
        p = int(l[i+1][0] - l[i][0])
        q = int(l[i+1][1] - l[i][1])
        pql.append((p,q))
pq = Counter(pql)
cntl = pq.most_common(1)
if N != 1:
        cnt = cntl[0][1]
        print(N - cnt)
else:
        print(1)

Submission status: Wrong Answer

Solution code:
from operator import itemgetter

n = int(input())
xy = sorted(sorted([list(map(int, input().split())) for i in range(n)], key=itemgetter(0)), key=itemgetter(1))
a = {}
last = []
for i in range(n):
    if i != 0:
        b = ",".join([str(xy[i][0] - last[0]), str(xy[i][1] - last[1])])
        if b not in a:
            a[b] = 1
        else:
            a[b] += 1
    last = xy[i]
ans = 0
for i in a.values():
    ans = max(ans, i)

xy = sorted(sorted(xy, key=itemgetter(1)), key=itemgetter(0))
a = {}
last = []
for i in range(n):
    if i != 0:
        b = ",".join([str(xy[i][0] - last[0]), str(xy[i][1] - last[1])])
        if b not in a:
            a[b] = 1
        else:
            a[b] += 1
    last = xy[i]
ans_ = 0
for i in a.values():
    ans_ = max(ans_, i)
print(n - max(ans, ans_))

Submission status: Wrong Answer

Solution code:
N = int(input())
xy = [list(map(int,input().split())) for i in range(N)]
cst = 1
xy.sort(key = lambda x:x[0])
keep = xy[0]
if N != 1:
    p = xy[1][0]-xy[0][0]
    q = xy[1][1]-xy[0][1]
    for i in range(1,N-1):
        if not(xy[i][0] == keep[0]+p and xy[i][1] == keep[1]+q):
            cst += 1
            p = xy[i+1][0] - xy[i][0]
            q = xy[i+1][1] - xy[i][1]
            keep = xy[i+1]
        else:
            keep = xy[i+1]
else:
    print(1)

print(cst)

Submission status: Wrong Answer

Solution code:
n = int(input())
xy_array = [[int(x) for x in input().split()] for y in range(n)]
xy_array = sorted(xy_array, key=lambda x: (x[0], x[1]))

a_array = []
tmp_x, tmp_y = xy_array[0]
for x, y in xy_array[1:]:
    a_array.append([tmp_x-x, tmp_y-y])
    tmp_x, tmp_y = x, y

res = float("inf")
for ax, ay in a_array:
    tmp_res = 1
    now_x, now_y = xy_array[-1]
    for x, y in reversed(xy_array[:-1]):
        if now_x+ax == x and now_y+ay == y:
            pass
        else:
            tmp_res += 1
        now_x, now_y = x, y
    res = min(res, tmp_res)

xy_array = sorted(xy_array, key=lambda x: (x[1], x[0]))
a_array = []
tmp_x, tmp_y = xy_array[0]
for x, y in xy_array[1:]:
    a_array.append([tmp_x-x, tmp_y-y])
    tmp_x, tmp_y = x, y

for ax, ay in a_array:
    tmp_res = 1
    now_x, now_y = xy_array[-1]
    for x, y in reversed(xy_array[:-1]):
        if now_x+ax == x and now_y+ay == y:
            pass
        else:
            tmp_res += 1
        now_x, now_y = x, y
    res = min(res, tmp_res)
print(res if n > 1 else 1)

Submission status: Wrong Answer

Solution code:
import sys

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

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

PQ = {}
for i in range(1, len(XY)):
    pq = XY[i][0] - XY[i-1][0], XY[i][1] - XY[i-1][1]
    if pq in PQ.keys():
        PQ[pq] += 1
    else:
        PQ[pq] = 1
pq = max(PQ, key=lambda x: PQ[x])
print(N - PQ[pq])

Submission status: Wrong Answer

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

from itertools import permutations

diff = []
for X, Y in XY:
  for X2, Y2 in XY[1:]:
    if (X2 - X, Y2 - Y) == (0, 0):
      continue
    diff.append((X2-X, Y2-Y))

memo = False
ans = 1e9+7
for x, y in diff:
  for per in permutations(XY):
    cost = 1
    for X, Y in per:
      if not memo:
        memo = (X, Y)
        continue
      if (X - x, Y - y) == memo:
        pass
      else:
        cost += 1
      memo = (X, Y)
    ans = min(cost, ans)
    memo = False
print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline


def read_int():
    return int(input())


def read_int_n():
    return tuple(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, XY):

    @lru_cache(maxsize=None)
    def f(i, v, x, y):
        ans = 0
        for j, u in enumerate(XY[i+1:]):
            if v[0] - u[0] == x and v[1] - u[1] == y:
                ans = max(ans, f(i+j+1, u, x, y) + 1)
            else:
                ans = max(ans, f(i+j+1, u, x, y))
        return ans

    ans = 0
    for i in range(N):
        for j in range(i+1, N):
            if XY[i][0]-XY[j][0] == 0 and XY[i][1]-XY[j][1] == 0:
                continue
            ans = max(ans, f(i, XY[i], XY[i][0]-XY[j][0], XY[i][1]-XY[j][1]))
    return N - ans


def main():
    N = read_int()
    XY = [read_int_n() for _ in range(N)]
    XY.sort()
    ans = slv(N, XY)
    XY.sort(key=lambda x: x[1])
    ans = min(ans, slv(N, XY))
    print(ans)

    # N = 50
    # XY = [(random.randint(1, 100), random.randint(1, 100)) for _ in range(N)]

    # XY.sort()
    # print(slv(N, XY))
    # XY.sort(key=lambda x: x[1])
    # print(slv(N, XY))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import itertools
n = int(input())
xy = list()
ans = list()

for _ in range(n):
  a, b = map(int, input().split())
  xy.append([a, b])

aa = itertools.permutations(xy, n)
for i in aa:
  ll = list()
  for j in range(n-1):
    k = [i[j+1][0]-i[j][0], i[j+1][1]-i[j][1]]
    ll.append(k)
  sett = set(map(tuple, ll))
  ans.append(len(sett))
  
print(min(ans))

Submission status: Wrong Answer

Solution code:
import collections

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

x_list = []
y_list = []

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

p_list = [x_list[i] - x_list[i+1] for i in range(N-1)]
q_list = [y_list[i] - y_list[i+1] for i in range(N-1)]

pq_list = sorted([(p_list[i],q_list[i]) for i in range(N-1)],reverse=True)

pq_qty = collections.Counter(pq_list).most_common()[0][1]

print(N-pq_qty)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [[int(s) for s in input().split()] for _ in range(N)]
cost = N
for x0, y0 in A:
    for x1, y1 in A:
        if not (x0 == x1 and y0 == y1):
            p = x0 - x1
            q = y0 - y1
            if p != 0 or q != 0:
                cost = min([cost, len(set([q * a[0] - p * a[1] for a in A]))])
print(cost)

Submission status: Wrong Answer

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

cood.sort()
cnt=0
diff=[]
for i in range(N-1):
    diff.append((cood[i+1][0]-cood[i][0],cood[i+1][1]-cood[i][1]))
    cnt=max(diff.count(diff[i]),cnt)
print(cnt)

Submission status: Wrong Answer

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

ans_li = []
rest = len(li)

for i in range(len(li)):
  for j in range(rest):
    x = li[i][0] - li[-j][0]
    y = li[i][1] - li[-j][1]
    ans_li.append([x,y])

  rest -= 1
  
max_a = 0
for i in ans_li:
  a = ans_li.count(i)
  if a > max_a:
    max_a = a
print(n - max_a)

Submission status: Wrong Answer

Solution code:
n=int(input())
xy=[]
for i in range(n):
    a=[int(j) for j in input().split()]
    xy.append(a)

if n==1:
    print(1)
    import sys
    sys.exit()
l=[]
ans=0
import itertools
for a,b in itertools.combinations(xy,2):
    p=abs(a[0]-b[0])
    q=abs(a[1]-b[1])
    if p!=0 or q!=0:
        l.append((p,q))

import collections
c=collections.Counter(l)
ans=c.most_common()


print(n-ans[0][1])

Submission status: Wrong Answer

Solution code:
from collections import Counter

N = int(raw_input())

points = [map(int, raw_input().split()) for _ in xrange(N)]

if N == 1:
    print 1
else:
    dist = lambda p1, p2: (p1[0]-p2[0], p1[1]-p2[1])

    vecs = []
    for i in xrange(N):
        for j in xrange(i+1, N):
            vecs.append(dist(points[i], points[j]))

    vecs_cnt = Counter(vecs)
    # print Counter(vecs)
    ans = max(vecs_cnt.values())

    print N-ans

Submission status: Wrong Answer

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

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

ans = float("inf")
for i in range(n - 1):
    for j in range(1, n - i):
        p = point[i + j][0] - point[i][0]
        q = point[i + j][1] - point[i][1]
        num = 1
        for k in range(n - 1):
            if k + j < n and point[k][0] + p == point[k + j][0] and point[k][1] + q == point[k + j][1]:
                num = num
            else:
                num += 1
        ans = min(ans, num)

point.sort(key=lambda x: x[1])
for i in range(n - 1):
    for j in range(1, n - i):
        p = point[i + j][0] - point[i][0]
        q = point[i + j][1] - point[i][1]
        num = 1
        for k in range(n - 1):
            if k + j < n and point[k][0] + p == point[k + j][0] and point[k][1] + q == point[k + j][1]:
                num = num
            else:
                num += 1
        ans = min(ans, num)
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import combinations
import sys

N = int(input())

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

X_Y = [0] * N

for i in range(N):
    X_Y[i] = tuple(map(int, input().split()))
    
combo = list(combinations(X_Y, 2))
diff = [0] * (len(combo))

for i, item in enumerate(combo):
    x_dif = item[0][0] - item[1][0]
    y_dif = item[0][1] - item[1][1]
    diff[i] = [x_dif, y_dif]

count_list = [0] * len(diff)
for k, d in enumerate(diff):
    p = d[0]
    q = d[1]
    count = 0
    for i in range(0, len(X_Y) - 1):
        if (X_Y[i][0] == X_Y[i + 1][0] + p) and X_Y[i][1] == X_Y[i + 1][1] + q:
            count += 0
        else:
            count += 1
    count_list[k] = count
print(min(count_list) + 1)

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]))
d1 = []
for i in range(1, N):
    x = xy[i-1][0] - xy[i][0]
    y = xy[i-1][1] - xy[i][1]
    d1.append((x, y))
P1 = 0
for D in d1:
    P1 = max(d1.count(D), P1)

xy.sort(key=lambda x:(x[1],x[0]))
d2 = []
for i in range(1, N):
    x = xy[i-1][0] - xy[i][0]
    y = xy[i-1][1] - xy[i][1]
    d2.append((x, y))
P2 = 0
for D in d2:
    P2 = max(d2.count(D), P2)

cut_P = max(P1, P2)
ans = N - cut_P
print(ans)

Submission status: Wrong Answer

Solution code:
#B問題
N = int(input())
XY = [list(map(int,input().split())) for i in range(N)]
edges = []
for i in range(N):
    x1,y1 = XY[i][0],XY[i][1]
    for j in range(N-i-1):
        J = i+j+1
        x2,y2 = XY[J][0],XY[J][1]
        dx = x2-x1
        dy = y2-y1
        if dx < 0:
            dx = -dx
            dy = -dy
        edges.append([dx,dy])

listcount = []
count = []
if N == 1:
    listcount.append([0,0])
    count.append(1)

for edge in edges:
    if edge == [0,0]:
        if [0,0] not in listcount:
            listcount.append([0,0])
            count.append(1)
    elif edge in listcount:
        count[listcount.index(edge)]+=1
    else:
        listcount.append(edge)
        count.append(1)
        
most = max(count)
print(N-most)

Submission status: Wrong Answer

Solution code:
from collections import Counter
N = int(input())
l = []
pql = []
for i in range(N):
        x, y = map(int, input().split())
        l.append((x,y))
l.sort()
for i in range(N-1):
        p = l[i+1][0] - l[i][0]
        q = l[i+1][1] - l[i][1]
        pql.append((p,q))
pq = Counter(pql)
cntl = pq.most_common(1)
if N != 1:
        cnt = cntl[0][1]
        print(N - cnt)
else:
        print(1)

Submission status: Wrong Answer

Solution code:
from copy import deepcopy
from itertools import combinations
N = int(input())
XY = [list(map(int, input().split())) for _ in range(N)]
ans = float("inf")
for (x1, y1), (x2, y2) in combinations(XY, 2):
    p, q = abs(x2-x1), abs(y2-y1)
    XY_ = deepcopy(XY)
    XY_.sort(key=lambda v: v[0]*q - v[1]*p)
    an = 0
    old = float("inf")
    for x, y in XY_:
        x *= q;
        y *= p
        new = x-y
        if new != old:
            an += 1
        else:
            pass
        old = new
    # if ans > an:
    #     print(p, q)
    ans = min(ans, an)
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 = [-abs(x[i]-x[j]) for i in range(N) for j in range(i+1, N)]
    q_cand = [-abs(y[i]-y[j]) for i in range(N) for j in range(i+1, N)]
    # p_cand = set([-x[i+1]+x[i] for i in range(N-1)])
    # q_cand = set([-y[i+1]+y[i] for i in range(N-1)])
    # print(p_cand, q_cand)

    minimum = INF
    for p in p_cand:
        for q in q_cand:
            # print("p: {}, q: {}".format(p, q))
            xy = list(zip(x, y))
            cost = 0
            while len(xy) > 0:
                # print(xy)
                xx, yy = xy.pop()
                cost += 1
                while (xx+p, yy+q) in xy:
                    xy.remove((xx+p, yy+q))
                    xx += p
                    yy += q
            # print("cost: {}".format(cost))
            if minimum >= cost:
                minimum = cost
                # print("P: {}, q: {}, cost: {}".format(p, q, 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:
from collections import Counter, defaultdict
import sys
N = int(input())
x = []
for i in range(N):
    a, b = map(int, input().split())
    x.append([a, b])
if N == 1:
    print(1)
    sys.exit()

y = x[:]
z = x[:]
sorted(y, key=lambda x: x[0])
sorted(z, key=lambda x: x[1])

a = y[0][0]
b = y[0][1]
ls1 = []
for i in y[1:]:
    p = i[0]
    q = i[1]
    ls1.append([a - p, b - q])
    a = p
    b = q
c = []
for i in ls1:
    c.append(ls1.count(i))
ans = N - max(c)

a = z[0][0]
b = z[0][1]
ls1 = []
for i in z[1:]:
    p = i[0]
    q = i[1]
    ls1.append([a - p, b - q])
    a = p
    b = q
c = []
for i in ls1:
    c.append(ls1.count(i))
ans = min(ans,N - max(c))
print(ans)

Submission status: Wrong Answer

Solution code:

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

from itertools import permutations

diff = []
for X, Y in XY:
  for X2, Y2 in XY[1:]:
    if (X2 - X, Y2 - Y) == (0, 0):
      continue
    diff.append((X2-X, Y2-Y))

memo = False
ans = 1e9+7
for x, y in diff:
  cost = 1
  for per in permutations(XY):
    for X, Y in per:
      if not memo:
        memo = (X, Y)
        continue
      if (X - x, Y - y) == memo:
        pass
      else:
        cost += 1
      memo = (X, Y)
    ans = min(cost, ans)
print(ans)