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

from sys import stdout
from bisect import bisect_left as binl
from copy import copy, deepcopy
from collections import defaultdict
import math


mod = 1


def intin():
    input_tuple = input().split()
    if len(input_tuple) <= 1:
        return int(input_tuple[0])
    return tuple(map(int, input_tuple))


def intina():
    return [int(i) for i in input().split()]


def intinl(count):
    return [intin() for _ in range(count)]


def modadd(x, y):
    global mod
    return (x + y) % mod


def modmlt(x, y):
    global mod
    return (x * y) % mod


def mod_inv(x):
    # available only when mod is prime
    global mod
    return pow(x, mod - 2, mod)


def gcm(x, y):
    while y != 0:
        z = x % y
        x = y
        y = z
    return x


def combination(x, y):
    assert(x >= y)

    ret = math.factorial(x)
    ret = ret // (math.factorial(x - y) * math.factorial(y))

    return ret


def get_divisors(x):
    retlist = []
    for i in range(1, int(x**0.5) + 3):
        if x % i == 0:
            retlist.append(i)
            retlist.append(x // i)
    return retlist


def get_factors(x):
    retlist = []
    for i in range(2, int(x**0.5) + 3):
        while x % i == 0:
            retlist.append(i)
            x = x // i
    retlist.append(x)
    return retlist


def make_linklist(xylist):
    linklist = {}
    for a, b in xylist:
        linklist.setdefault(a, [])
        linklist.setdefault(b, [])
        linklist[a].append(b)
        linklist[b].append(a)
    return linklist


def calc_longest_distance(linklist, v=1):
    distance_list = {}
    distance_count = 0
    distance = 0
    vlist_previous = []
    vlist = [v]
    nodecount = len(linklist)

    while distance_count < nodecount:
        vlist_next = []
        for v in vlist:
            distance_list[v] = distance
            distance_count += 1
            vlist_next.extend(linklist[v])
        distance += 1
        vlist_to_del = vlist_previous
        vlist_previous = vlist
        vlist = list(set(vlist_next) - set(vlist_to_del))

    max_distance = -1
    max_v = None
    for v, distance in distance_list.items():
        if distance > max_distance:
            max_distance = distance
            max_v = v

    return (max_distance, max_v)


def calc_tree_diameter(linklist, v=1):
    _, u = calc_longest_distance(linklist, v)
    distance, _ = calc_longest_distance(linklist, u)
    return distance


class UnionFind:

    def __init__(self, n):
        self.parent = [i for i in range(n)]

    def root(self, i):
        if self.parent[i] == i:
            return i
        self.parent[i] = self.root(self.parent[i])
        return self.parent[i]

    def unite(self, i, j):
        rooti = self.root(i)
        rootj = self.root(j)
        if rooti == rootj:
            return
        if rooti < rootj:
            self.parent[rootj] = rooti
        else:
            self.parent[rooti] = rootj

    def same(self, i, j):
        return self.root(i) == self.root(j)


###############################################################################


def main():
    n = intin()
    xylist = intinl(n)

    pqtoij = defaultdict(list)

    for i in range(n):
        for j in range(n):
            if i == j:
                continue
            ansl = 1
            x1, y1 = xylist[i]
            x2, y2 = xylist[j]

            p = abs(x1 - x2)
            q = abs(y1 - y2)

            pqtoij[(p, q)].append((min(i, j), max(i, j)))

    maxcount = 0

    for (p, q), ijlist in pqtoij.items():
        checked = []
        count = 0
        for i, j in ijlist:
            if (i, j) in checked:
                continue
            count += 1
            checked.append((i, j))
        maxcount = max(maxcount, count)

    print(n - maxcount)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n=int(input())
arr=[list(map(int,input().split())) for _ in range(n)]
ans=n
for i in range(n):
  for j in range(i+1,n):
    p,q=arr[j][0]-arr[i][0],arr[j][1]-arr[i][1]
    cnt=0
    flag=[0]*n
    for k in range(n):
      if flag[k]==1:
        continue
      flag[k]=1
      a,b=arr[k][0],arr[k][1]
      while 1:
        for l in range(n):
          if flag[l]==1:
            continue
          if a+p==arr[l][0] and b+q==arr[l][1]:
            flag[l]=1
            a=arr[l][0]
            b=arr[l][1]
            break
        else:
          break
      cnt+=1
    ans=min(ans,cnt)
print(ans)

Submission status: Wrong Answer

Solution code:
#XY = [[1,2],[1,1],[2,2],[2,1]]
N=int(input())
XY =  [list(map(int, input().split())) for _ in range(N)]
cnt = 1
n=0
for i in range(N-1):
    xy = XY.pop(n)
    #print(XY)
    flag = False
    for k in range(len(XY)):
        if xy[0] != XY[k][0] and xy[1] != XY[k][1]:
            n = k
            #print("aa")
            flag=True
            break
    if flag ==False:
        #print("bb")
        cnt +=1
        n=0
print(cnt)

Submission status: Wrong Answer

Solution code:
N = int(input())

ball_position = []
for _ in range(N):
    i, j = map(int, input().split())
    ball_position.append((i, j))

def tuple_inverse(a):
    ai, aj = a
    if ai < 0:
        return (-ai, -aj)
    return(ai, aj)

def tup2_diff(a, b):
    ai, aj = a
    bi, bj = b
    return tuple_inverse((ai - bi , aj - bj))

calculation_list = []
for i in range(len(ball_position)):
    for j in range(i + 1, len(ball_position)):
        calculation_list.append(tup2_diff(ball_position[i], ball_position[j]))
        
import collections
c = collections.Counter(calculation_list).most_common(1)

if N == 1:
    print(1)
else:
    print(N - calculation_list.count(c[0][0]))

Submission status: Wrong Answer

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

cost=n
ma=0

for i in range(n-1):
    for j in range(i+1,n):
        che=0
        p=x[j]-x[i]
        q=y[j]-y[i]

        for c in range(n-1):
            for d in range(c+1,n): 
                if x[d]-x[c]==p and y[d]-y[c]==q:
                    che=che+1
        ma=max(ma,che)

print(cost-ma)

Submission status: Wrong Answer

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left, bisect_right
from copy import copy
inf=float('inf')
mod = 10**9+7
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N = I()
    XY = LLIN(N)
    if N == 1:
        print(1)
        exit()
    ans = inf
    for i in range(N):
        for j in range(N):
            if i == j:
                continue
            p = XY[i][0] - XY[j][0]
            q = XY[i][1] - XY[j][1]
            pre_exist = set()
            pre_exist.add((XY[i][0], XY[i][1]))
            mini_ans = 1
            for (x, y) in XY:
                found = False
                for (px, py) in pre_exist.copy():
                    dx = px - x
                    dy = py - y
                    if p == 0 and q == 0:
                        found = True
                        break
                    else:
                        if p == 0:
                            if dy / q == dy // q and dx==0:
                                found = True
                                break
                            continue
                        elif q == 0:
                            if dx / p == dx // p and dy==0:
                                found = True
                                break
                            continue
                    if dx / p == dy / q:
                        if dx/p == dx//p :
                            found = True
                            break
                    else:
                        continue
                if not found:
                    pre_exist.add((x,y))
                    mini_ans += 1
                        
            ans = min(ans, mini_ans)
    print(ans)
if __name__ == '__main__':
    main()

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
        isNext = False
        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]
                isNext = True
                break
        if not isNext:
            pos = xy.pop(0)
            cost += 1
    print(cost)

Submission status: Wrong Answer

Solution code:
from collections import Counter
from operator import itemgetter
n = int(input())
xy = [tuple([int(i) for i in input().split()]) for i in range(n)]

def sub(l):
    li = []
    for i in range(1,n):
        li.append((abs(l[i-1][0]-l[i][0]),abs(l[i-1][1]-l[i][1])))
    return li

def judgepq(l):
    cnt,p,q = 0,0,0
    for k,v in Counter(l).items():
        if cnt < v:
            cnt = v
            p,q = k
    return p,q

def judge(t,li):
    ans = 1
    p,q = t
    #print(li,p,q)
    for i in range(1,n):
        if (li[i][0]-p,li[i][1]-q) != (li[i-1][0],li[i-1][1]):
            ans += 1
    return ans

a = sorted(xy,key=itemgetter(0))
b = sorted(xy,key=itemgetter(1))
#print(judgepq(sub(a)))
print(min(judge(judgepq(sub(a)),a),judge(judgepq(sub(b)),b)))

Submission status: Wrong Answer

Solution code:
N = int(input())


def solve():

    initial_cost = 1

    # (x,y) list
    xy_list = []
    for i in range(N):
        x, y = map(int, input().split())
        xy_list.append((x, y))
    xy_list_sorted = sorted(xy_list, key=lambda a: a[0])

    if N == 1:
        return 1

    xy_sub_dic = {}
    for i in range(N):
        for j in range(i+1, N):
            xs = xy_list_sorted[j][0] - xy_list_sorted[i][0]
            ys = xy_list_sorted[j][1] - xy_list_sorted[i][1]
            if xy_sub_dic.get((xs, ys)) is None:
                xy_sub_dic[(xs, ys)] = 1
            else:
                xy_sub_dic[(xs, ys)] += 1
    xy_sub_dic_sorted = sorted(xy_sub_dic.items(), key=lambda a: a[1], reverse=True)

    return initial_cost + (N - 1) - xy_sub_dic_sorted[0][1]
print(solve())

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 + 1, n):
            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)
    steps = n - 1
    total = 0
    # print("stepts", steps)
    # print(depth_list)
    for item in depth_list:
        steps -= item
        total += 1
        if steps <= 0:
            return total


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 sys

N = int(input())

if N == 1:
    print(1)

coor = []
for i in range(N):
    (x,y) = (int(i) for i in input().split())
    coor.append((x,y))
    
diffs = []
for i in range(N-1):
    diffs.append((coor[i+1][0]-coor[i][0], coor[i+1][1]-coor[i][1]))
    
m = 0

for i in range(N-1):
    times = 0
    for j in range(N-1):
        if diffs[i] == diffs[j]:
            times += 1
    if times > m:
        m = times

ans = N - m   

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

n = int(input())

A = []

for i in range(n):
    A.append(list(map(int, input().split())))

A = np.array(A)

X = np.eye(n, k = 1, dtype = int)
X[n-1, 0] = 1

B = []
a = np.copy(A)

for i in range(n-1):
    a = np.dot(X, a)
    B.append(A - a)

B = np.array(B)

B = np.reshape(B, (-1, 2))

B = B[np.argsort(B[:, 0])]
B = B[np.argsort(B[:, 0])]

c = 1
max_cont = 0
for i in range(1, B.shape[0]):
    if B[i][0] == B[i-1][0] and B[i][1] == B[i-1][1]:
        c += 1
    elif c > max_cont:
        max_cont = c
        c = 1
    else:
        c =1

print(n - max_cont)

Submission status: Wrong Answer

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

import copy

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

result = float('inf')

for i in range(N):
    for j in range(N-i):
        p = List[i+j][0] - List[i][0]
        q = List[i+j][1] - List[i][1]
        if p == 0:
            p = 1
        if q == 0:
            q = 1
        tmp_list = copy.deepcopy(List)
        cost = 0
        
        for k in range(N):
            if [tmp_list[0][0] + p, tmp_list[0][1] + q] in List:
                tmp_cost = 0
            else:
                tmp_cost = 1
            cost += tmp_cost
            del tmp_list[0]
            
        if result > cost:
            result = cost
                    
print(result)

Submission status: Wrong Answer

Solution code:
str = input()
N = int(str.split()[0])

x = []
y = []
t = []
for i in range(N) :
	str = input()
	sStr = str.split()
	x.append(int(sStr[0]))
	y.append(int(sStr[1]))
	t.append(i)
for i in range(N) :
	for j in range(i, N) :
		if (x[i] < x[j]) :
			x[i], x[j] = x[j], x[i]
			y[i], y[j] = y[j], y[i]
			t[i], t[j] = t[j], t[i]

for i in range(N) :
	for j in range(i, N) :
		if (x[i] == x[j]) :
			if (y[i] < y[j]) :
				x[i], x[j] = x[j], x[i]
				y[i], y[j] = y[j], y[i]
				t[i], t[j] = t[j], t[i]

a = []

for i in range(N - 1) :
	tuple = (x[i] - x[i+1], y[i] - y[i+1])
	a.append(tuple)

for i in range(N) :
	for j in range(i, N) :
		if (y[i] == y[j]) :
			if (x[i] < x[j]) :
				x[i], x[j] = x[j], x[i]
				y[i], y[j] = y[j], y[i]
				t[i], t[j] = t[j], t[i]

for i in range(N - 1) :
	tuple = (x[i] - x[i+1], y[i] - y[i+1])
	a.append(tuple)

ab = 0
for tu in a :
	co = 1
	for i in range(N - 1) :
		tuple = (x[i] - x[i+1], y[i] - y[i+1])
		if (tuple != tu) :
			co = co + 1
	if (ab == 0) :
		ab = co
	if (ab > co) :
		ab = co

print(ab)

Submission status: Wrong Answer

Solution code:
from collections import deque
import statistics
import math
from collections import Counter
N=int(input())
x=[]
y=[]
for a in range(N):
    b,c=(int(x) for x in input().split())
    x.append(b)
    y.append(c)
sa=deque([[0,0]])
if N>1:
    for a in range(N):
        for b in range(N-a-1):
            sx=abs(x[a]-x[a+b+1])
            sy=abs(y[a]-y[a+b+1])
            sa.append([sx,sy])
    sa.remove([0,0])
    ans=[]
    nagasa=len(sa)
    for a in range(nagasa):
        xx,yy=sa.pop()
        ss=sa.count([xx,yy])
        ss=ss+1
        ans.append(ss)
        if len(sa)==0:
            break
    kotae=max(ans)
    print(N-kotae)

else:
    print(1)

Submission status: Wrong Answer

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

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

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

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

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

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

def main():

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

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

	xy.sort()
	gess = {}
	xm = 0
	ym = 0

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

	for i, val in enumerate(xy):
		if i == 0:
			x,y = val
			xm = x
			ym = y
			continue
		x, y = val
		p = x - xm
		q = y - ym
		if (p,q) in gess:
			gess[(p, q)] += 1
		else:
			gess[(p, q)] = 1
		xm = x
		ym = y

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

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

	for i, val in enumerate(xy):
		if i == 0:
			x,y = val
			xm = x
			ym = y
			continue
		x, y = val
		p = x - xm
		q = y - ym
		if (p,q) in gess2:
			gess2[(p, q)] += 1
		else:
			gess2[(p, q)] = 1
		xm = x
		ym = y

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

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

	for i, val in enumerate(xy):
		if i == 0:
			x,y = val
			xm = x
			ym = y
			continue
		x, y = val
		p = x - xm
		q = y - ym
		if (p,q) in gess3:
			gess3[(p, q)] += 1
		else:
			gess3[(p, q)] = 1
		xm = x
		ym = y

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

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

	for i, val in enumerate(xy):
		if i == 0:
			x,y = val
			xm = x
			ym = y
			continue
		x, y = val
		p = x - xm
		q = y - ym
		if (p,q) in gess4:
			gess4[(p, q)] += 1
		else:
			gess4[(p, q)] = 1
		xm = x
		ym = y

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

	tmp = max(nai, nai2, nai3, nai4)

	print(N-tmp)



if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
 
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

import collections

n = ni()

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

balls = []
dis = []

for i in range(n):
    x,y = na()
    for b in balls:
        k = '_1' if (b[0]-x)*(b[1]-y) > 0 else '_0'
        dis.append(str(abs(b[0]-x))+'_'+str(abs(b[1]-y))+k)
    balls.append([x,y])

c = collections.Counter(dis)
m = c.most_common()

if len(m) == 1:
    print(1)
    exit()

u = m[0][1]
if u == 1:
    u = 0

print(n-u)

Submission status: Wrong Answer

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left, bisect_right
from copy import copy
inf=float('inf')
mod = 10**9+7
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N = I()
    XY = LLIN(N)
    if N == 1:
        print(1)
        exit()
    ans = inf
    for i in range(N):
        for j in range(N):
            if i == j:
                continue
            p = XY[i][0] - XY[j][0]
            q = XY[i][1] - XY[j][1]
            pre_exist = set()
            pre_exist.add((XY[i][0], XY[i][1]))
            mini_ans = 1
            for (x, y) in XY:
                found = False
                print((x,y),pre_exist,mini_ans)
                for (px, py) in pre_exist.copy():
                    dx = px - x
                    dy = py - y
                    print("d",dx,dy ,p,q)
                    if p == 0 and q == 0:
                        found = True
                        break
                    else:
                        if p == 0:
                            if dy / q == dy // q and dx==0:
                                found = True
                                break
                            continue
                        elif q == 0:
                            print("a")
                            if dx / p == dx // p and dy==0:
                                found = True
                                break
                            continue
                    if dx / p == dy / q:
                        if dx/p == dx//p :
                            found = True
                            break
                    else:
                        continue
                if not found:
                    pre_exist.add((x,y))
                    mini_ans += 1
                        
            print(pre_exist,mini_ans)
            ans = min(ans, mini_ans)
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
from itertools import combinations

def main():
    input = sys.stdin.readline
    N = int(input())
    cord = []
    for _ in range(N):
        x, y = map(int, input().split())
        cord.append((x, y))

    ans = 50
    for a in combinations(cord, 2):
        x1, y1 = a[0]
        x2, y2 = a[1]

        if x1 == x2 or y1 == y2:
            p = 0
            q = 1
        else:
            p = x2 - x1
            q = y2 - y1

        b = set()
        for x, y  in cord:
            b.add(y * p  - q  * x)

        ans = min(ans, len(b))

    return ans


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

Submission status: Wrong Answer

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

xy.sort()
cost_temp=[]
for j in range(n-1):
    if not([xy[j+1][0]-xy[j][0],xy[j+1][1]-xy[j][1]] in cost_temp):
        cost_temp.append([xy[j+1][0]-xy[j][0],xy[j+1][1]-xy[j][1]])

print(len(cost_temp))

Submission status: Wrong Answer

Solution code:
import sys
import collections
input = sys.stdin.readline
n = int(input())
xy = []
for i in range(n):
    _a,_b = map(int,input().split())
    xy.append([_a,_b])
sxy = sorted(xy)
sxy2 = []
sxy2.append((sxy[0][0]**2)+sxy[0][1])
for i in range(1,n):
    sxy2.append(((sxy[i][0]-sxy[i-1][0])**2)+((sxy[i][1]-sxy[i-1][1])**2))
c = collections.Counter(sxy2)
ans = len(sxy2)-max(c.values())
print(ans) if ans != 0 else print(1)

Submission status: Wrong Answer

Solution code:
import sys
N=int(input())
# N=50

p = []
for n in range(N):
    x,y = map(int,input().split())
    # x,y = n,n
    p.append( (x,y) )

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

diffs = set()
for i,pi in enumerate(p):
    for j,pj in enumerate(p):
        diff = (pi[0]-pj[0],pi[1]-pj[1])
        diffs.add(diff)

max_cost = sys.float_info.max
for d in diffs:
    #空のリストを用意
    e = set()  #部分最小木
    av = set()  #部分最小木に含まれる頂点
    pv = set(p)  #その他の頂点
    used = {}
    for pp in p:
        used[pp] = 1
    used[p[0]] += 1
    #始点は任意
    av.add(p[0])
    pv.remove(p[0])
    costs = 0
    while 1:
        #比較のための初期値として十分大きい数を用意
        shortestlen = sys.float_info.max
        #部分最小木に追加する辺を為す2点の初期化
        kav = None  #部分最小木に含まれる頂点からの候補
        kpv = None  #その他の頂点からの候補
        for v1 in av:
            for v2 in pv:
                #重みの計算（ここでは距離）
                dist = 0 if (v1[0]-d[0] ==v2[0] and v1[1]-d[1] == v2[1]) else 1
                # dist = math.sqrt(  (v1[0]-v2[0])**2 + ( v1[1]-v2[1] )**2 )
                if shortestlen > dist and used[v1] > 0:
                    shortestlen = dist
                    #候補の更新
                    kav = v1
                    kpv = v2
        if shortestlen >= 0:
            #部分最小木に追加
            costs += shortestlen
            e.add((kav , kpv))
            used[kav] -= 1
        #確定した頂点を移す
        av.add(kpv)
        pv.remove(kpv)
        #全頂点に対する判定を終えたら終了
        if len(pv) == 0:
            break
    # print(costs)
    max_cost = min(max_cost,costs+1)

print(max_cost)

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)]
  ball.sort(key=lambda x:(x[0], x[1]))
  diff = [tuple((ball[i][0] - ball[i-1][0], ball[i][1] - ball[i-1][1])) for i in range(1,N)]
  c = collections.Counter(diff)
  ans = c.most_common()[0][1]
  print(N - ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
coords = []
dist = {}
prev = []
for i in range(n):
    a, b = (int(_) for _ in input().split())
    if [a, b] not in coords:
        for coord in coords:
            x = abs(coord[0] - a)
            y = abs(coord[1] - b)
            if (x,y) not in dist:
                dist[(x,y)] = 1
            else:
                dist[(x,y)] = dist[(x,y)] + 1
        coords.append([a,b])
    else:
        if (0, 0) not in dist:
            dist[(0,0)] = 1
        else:
            dist[(0,0)] = dist[(0,0)] + 1
        prev = [a,b]
if n == 1 or n == 2:
    print(1)
else:
    ans = 0
    for distance in dist:
        if dist[distance] > ans:
            ans = dist[distance]
            #print(distance)
    if ans == n:
        print(1)
    else:
        print(n - ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter





if __name__ == "__main__":
    #入力取得
    N = int(input())

    p = []


    results = [[] for i in range(N)]

    for row in results:
        for i in range(N):
            row.append('')

    tmp = []



    for i in range(N):
        l = list(map(int, input().split()))
        p.append(l)


    for i in range(len(p)):
        for j in range(len(p)):

            if p[i][0] == p[j][0]:
                r = N*N
            else:
                r = (p[i][1]-p[j][1])/(p[i][0]-p[j][0])

            results[i][j] = r

            tmp.append(r)




    counter = Counter(tmp)
    max_r = counter.most_common()[0][0]

    results2 = [0]*N


    for i in range(len(results)):
        for j in range(i+1,len(results)):
            if results[i][j] == max_r:
                results2[i] += 1




    tmp_ans = N - (max(results2) + 1)
    if tmp_ans == 0:
        print(1)
    else:
        print(tmp_ans)

Submission status: Wrong Answer

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

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


def calc(p,q):
    result = set()
    for x,y in XY:
        result.add(y*p - x * q)
    # print(p,q,result)
    return len(result)

ans = 5000

for i in range(N-1):
    for j in range(i,N):
        p = XY[i][0] - XY[j][0]
        q = XY[i][1] - XY[j][1]
        ans = min(ans,calc(p,q))

if ans == 5000:
    raise ValueError
print(ans)

Submission status: Wrong Answer

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

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


# 普通にやると1250の組み合わせを求める必要がある
Div_list = []

for i in range(N):
    x_i, y_i = XY[i]
    for j in range(i+1, N):
        x_j, y_j = XY[j]
        Div_list.append((abs(x_i - x_j), abs(y_i - y_j)))


Div_list_sorted = sorted(Div_list)

Div_list_len = len(Div_list_sorted)

count_max = 0
if Div_list_len == 1:
    count_max = 1
else:

    skip = 0

    for i in range(Div_list_len):
        count = 1
        if skip > 0:
            skip -= 1
            continue

        s_i = Div_list_sorted[i]
        for j in range(i+1, Div_list_len):
            s_j = Div_list_sorted[j]
            if s_i == s_j:
                count += 1

        skip = (count - 1)
        if count > count_max:
            count_max = count


print(N - count_max)

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]
        else:
            keep = xy[i]
    if not(xy[N-1][0] == keep[0]+p and xy[N-1][1] == keep[1]+q):
        cst += 1
else:
    print(1)

print(cst)