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:
import numpy as np
N = int(input())
x = np.zeros(N)
y = np.zeros(N)

for i in range(N):
    x[i], y[i] = map(int, input().split())
for j in range(N-1):
    for k in range(N-1):
        if x[k] > x[k + 1]:
            x[k], y[k] = x[k + 1], y[k + 1]
        if x[k] == x[k + 1] and y[k] > y[k + 1]:
            x[k], y[k] = x[k + 1], y[k + 1]

ans = N
for m in range(N):
    for p in range(m):
        diff_x = x[m] - x[p]
        diff_y = y[m] - y[p]
        ans_kari = N
        for q in range(N):
            for r in range(q):
                if x[q] - x[r] == diff_x and y[q] - y[r] == diff_y:
                    ans_kari -= 1
        if ans_kari < ans:
            ans = ans_kari
if N == 2 or N == 1:
    ans = 1
print("{}".format(ans))

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()]
    pm = [-1*i for i in p]
    # print(p)
    # q = csy.most_common()[0][0]
    q = [i for i,v in csy.most_common()]
    qm = [-1*i for i in q]
    p = p + pm
    q = q + qm
    # print(p)

    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:
import numpy as np
 
N = int(input())
X = []
Y = []
for i in range(N):
  x,y = map(int, input().split())
  X.append(x)
  Y.append(y)
 
X2 = np.array(X)
Y2 = np.array(Y)
 
I = list(range(N))
 
 
for i in range(N):
  z = np.polyfit(X2, Y2, 1)
  YY = np.polyval(z, X2)
  D = (YY - Y2)
  j = np.argmax(np.abs(D))
  if (np.abs(D[j]) < 0.00001):
    break
  np.delete(X2, j)
  np.delete(Y2, j)

#print(z)
YY = np.polyval(z, np.array(X))
D = (YY - np.array(Y))
J = np.where(np.abs(D) >= 0.00001)
print(len(J[0]) + 1)

Submission status: Wrong Answer

Solution code:
from collections import Counter
n=int(input())
xy = sorted([list(map(int,input().split())) for i in range(n)])
A = Counter([xy[i+1][0]-xy[i][0] for i in range(0,len(xy)-1)]).keys()
B = Counter([xy[i+1][1]-xy[i][1] for i in range(0,len(xy)-1)]).keys()
final_ans=10**9
for a in A:
	if a==0:
		continue
	for b in B:
		if b==0:
			continue
		ans=0
		tmp0,tmp1 = xy[0]
		for i in range(1,len(xy)):
			ans += 0 if tmp0 == xy[i][0]-a  and tmp1 == xy[i][1]-b else 1
			tmp0=xy[i][0]
			tmp1=xy[i][1]
		tmp = ans
		ans=0
		for i in range(len(xy)-1,-1,-1):
			ans += 0 if tmp0 == xy[i][0]-a and tmp1 == xy[i][1]-b else 1
			tmp0=xy[i][0]
			tmp1=xy[i][1]
		tmp_ans = min(ans,tmp)
		final_ans = min(final_ans,tmp_ans)

print(final_ans+1 if final_ans==0 else final_ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
xy=list(list(map(int,input().split())) for _ in range(N))
L=[]
c=1
for i in range(N):
    for j in range(N):
        if i!=j:
            L.append(([xy[j][0]-xy[i][0],xy[j][1]-xy[i][1]]))
for l in L:
    c=max(c,L.count(l))
print(N-c)

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):
            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):
            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:
# -*- 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)]

	tmp = max(nai, nai2, nai3)

	print(N-tmp)



if __name__ == "__main__":
	main()

Submission status: Wrong Answer

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

ans = 0
while len(xy) > 2:
  p, q = xy[0][0] - xy[1][0], xy[0][1] - xy[1][1]
  tmp = []
  for l in xy:
    if p == 0 and (l[1] - xy[0][1]) % q == 0 or q == 0 and (xy[0][0] - xy[1][0]) % p == 0 or (xy[0][0] - xy[1][0]) % p == 0 and (xy[0][1] - xy[1][1]) % q == 0:
      tmp.append(l)
  if len(tmp) > 2:
    for t in tmp:
      xy.remove(t)
    ans += 1
  else:
    xy += tmp
if len(xy) > 0:
  ans += 1
print(ans)

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:
            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=list()
y=list()
for i in range(n):
  xt,yt = map(int,input().split())
  x.append(xt)
  y.append(yt)
  
z=1
t=[ 0 for i in range(n-1) ]
for i in range(n):
  k=0
  zz=0
  for j in range(n):
    if i != j:
      if x[i] == x[j]:
        t[k] = 0
        zz+=1
      else:
        t[k]=(y[j] - y[i])/(x[j] - x[i])
      k+=1
  #print(t,set(t))
  if zz > 0:
    zz-=1
  z=max(z,len(set(t))+zz)
  
print(z)

Submission status: Wrong Answer

Solution code:
N = int(input())

x = []
for _ in range(N):
  a,b = map(int,input().split())
  x.append([a,b])
  
x.sort(key=lambda x : (x[0],x[1]))

y = []
for i,j in zip(x,x[1:]):
  y.append((j[0]-i[0],j[1]-i[1]))

print(len(set(y)))

Submission status: Wrong Answer

Solution code:
import collections
n = int(input())
ans = 1
t_list = []
dif_list = []
a_list = []
xt = yt = 0
for i in range(n):
  x, y = map(int, input().split())
  dif = [x - xt, y - yt]
  t_list.append([x, y])
  dif_list.append(dif)
  xt = x
  yt = y

for dif in dif_list:
  if not dif in a_list:
    a_list.append(dif)
  else:
    a_list.remove(dif)

if len(a_list) == 0:
  print(1)
else:
  print(len(a_list))

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.add((-a, b))
            lines.add((a, -b))
            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())

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

lst = []

for i in range(n):
    for j in range(i+1,n):
        if a[j][0]-a[i][0] <= 0:
            lst.append([a[i][0]-a[j][0], a[i][1]-a[j][1]])
        else:
            lst.append([a[j][0]-a[i][0], a[j][1]-a[i][1]])

if n ==1:
    print(1)
else:
    x = 0
    for i in range(len(lst)):
        c = 1
        for j in range(i+1,len(lst)):
            if lst[i] == lst[j]:
                c += 1
        x = max(x,c)
    print(n-x)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Jun 15 20:54:29 2019

@author: Yamazaki Kenichi
"""

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

a = set()
for j in range(N):
    for i in range(j + 1,N):
        if (A[i][1] - A[j][1]) == 0 or (A[i][0] - A[j][0]) == 0:
            continue
        a1 = (A[i][1] - A[j][1]) / (A[i][0] - A[j][0])
        a.add(a1)

ans = []
for c in a:
    T = [A[0]]
    for i in range(1,N):
        flg = True
        for t in T:
#            print(abs(A[i][1] - t[1] - c * (A[i][0] - t[0])))
            if abs(A[i][1] - t[1] - c * (A[i][0] - t[0])) < 0.0000000001:
                flg = False
                break
        if flg:
            T.append(A[i])
    ans.append(len(T))
if len(a) == 0:
    ans.append(N)
print(min(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[0] == -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:
N = int(input())
xy = [[int(i) for i in input().split()] for i in range(N)]

#xy = list(map(list, set(map(tuple, xy))))

d = {}
m = 0
for i in range(N):
    for j in range(i+1, N):
        if (abs(xy[i][0]-xy[j][0]), abs(xy[i][1]-xy[j][1])) in d:
            d[abs(xy[i][0]-xy[j][0]), abs(xy[i][1]-xy[j][1])] += 1
        else:
            d[abs(xy[i][0]-xy[j][0]), abs(xy[i][1]-xy[j][1])] = 1

for val in d.values():
    m = max(m, val)
#print(d)
print(N-m)

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, q in set(zip(p_cand, q_cand)):
        # print("p: {}, q: {}".format(p, q))
        xy = list(zip(x, y))
        cost = 0
        while len(xy) > 0:
            # 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 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()
    if p == 0:
        for x,y in XY:
            result.add(x)
        return len(result)
    for x,y in XY:
        result.add(y - Fraction(x,p) * 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())
L = [list(map(int, input().split())) for _ in range(N)]

if N == 1:
    print(1)
    
else:
    B = sorted(L, key=lambda x: x[1], reverse=True)  
    B = sorted(B, key=lambda x: x[0])
    
    dic_x = {}
    dic_y = {}
    for i in range(N-1):
        if B[i+1][0] - B[i][0] in dic_x:
            dic_x[B[i+1][0] - B[i][0]] += 1

        else:
            dic_x[B[i+1][0] - B[i][0]] = 1


        if B[i+1][1] - B[i][1] in dic_y:
            dic_y[B[i+1][1] - B[i][1]] += 1

        else:
            dic_y[B[i+1][1] - B[i][1]] = 1


    tmp_x = max(dic_x.items(), key=lambda x:x[1])[0]
    tmp_y = max(dic_y.items(), key=lambda x:x[1])[0]
    ans_1 = 0
    for i in range(N-1):
        if B[i][0] + tmp_x == B[i+1][0] and B[i][1] + tmp_y == B[i+1][1]:
            pass
        else:
            ans_1 += 1

    B = sorted(L, key=lambda x: x[0], reverse=True)      
    B = sorted(B, key=lambda x: x[1])

    dic_x = {}
    dic_y = {}
    for i in range(N-1):
        if B[i+1][0] - B[i][0] in dic_x:
            dic_x[B[i+1][0] - B[i][0]] += 1

        else:
            dic_x[B[i+1][0] - B[i][0]] = 1


        if B[i+1][1] - B[i][1] in dic_y:
            dic_y[B[i+1][1] - B[i][1]] += 1

        else:
            dic_y[B[i+1][1] - B[i][1]] = 1


    tmp_x = max(dic_x.items(), key=lambda x:x[1])[0]
    tmp_y = max(dic_y.items(), key=lambda x:x[1])[0]
    ans_2 = 0
    for i in range(N-1):
        if B[i][0] + tmp_x == B[i+1][0] and B[i][1] + tmp_y == B[i+1][1]:
            pass
        else:
            ans_2 += 1

    print(min(ans_1, ans_2)+1)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(100000)

def intinput(): return map(int,sys.stdin.readline().split())


n=int(input())
p=[]
for _ in range(n):
    p.append(tuple(intinput()))
s={}
for x,y in p:
    for x1,y1 in p:
        if x==x1 and y==y1:
            break
        if (x-x1,y-y1) in s:
            s[(x-x1,y-y1)]+=1
        else:
            s[(x-x1,y-y1)]=1
if n==1:
    print(1)
else:
    print(n-max(s.values()))

Submission status: Wrong Answer

Solution code:
# coding: UTF-8
import sys
#sys.setrecursionlimit(n)
import heapq
import re
import bisect
import random
import math
import itertools
from collections import defaultdict, deque
from copy import deepcopy
from decimal import *

readl= lambda: list(map(int, sys.stdin.readline().split()))
readt= lambda: tuple(map(int, sys.stdin.readline().split()))
read = lambda: sys.stdin.readline().rstrip()
readi = lambda: int(read())
readmi = lambda: map(int, sys.stdin.readline().split())
readms = lambda: map(str, sys.stdin.readline().split())

n = readi()
a = []
b = []
if n == 1:
    print(1)
    exit()
for i in range(n):
    x, y = readmi()
    a.append([x,y])
    b.append([y,x])
a.sort()
b.sort()
aa = defaultdict(int)
bb = defaultdict(int)
old1 = 0
old2 = 0
flg = True
for i in range(n - 1):
    aa[(a[i + 1][0] - a[i][0], a[i + 1][1] - a[i][1])] += 1
    bb[(b[i + 1][0] - b[i][0], b[i + 1][1] - b[i][1])] += 1

aaa = sorted(aa.items(), key=lambda x:x[1], reverse=True)
bbb = sorted(bb.items(), key=lambda x:x[1], reverse=True)
ccc = defaultdict(int)

if aaa[0][1] >= bbb[0][1]:
    ccc = aaa[0]
else:
    ccc = bbb[0]
print(n - ccc[1])

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(N-cnt)

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
        elif dx==0 and dy<0:
            dy-=dy
        key="{},{}".format(dx,dy)
        if key in diffs:
            diffs[key]+=1
        else:
            diffs[key]=1

max=0
maxkey=""
for k,v in diffs.items():
    if v>max:
        max=v
        maxkey=k
        
print(n-max)

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 = (x2-x1), (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:
import numpy as np
import sys

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

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
#!/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:
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)

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 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 = (x2-x1), (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:
from itertools import permutations, product
import sys

N = int(input())
if N == 1:
  print(1)
  sys.exit()
  
balls = []
for i in range(N):
  balls.append(tuple(map(int, input().split())))
  
def cost(ball_before, ball_after, p, q):
  if ball_before == (ball_after[0] - p, ball_after[1] - q):
    return 0, ball_after
  else:
    return 1, ball_after
    
total_costs = []
p_q = (1, 1)
for scenario in permutations(balls):
  total_cost = 0
  ball_before = scenario[0]
  for next_ball in scenario:
    c, ball_before = cost(ball_before, next_ball, p_q[0], p_q[1])
    total_cost += c
    total_costs.append(total_cost)
print(min(total_costs))

Submission status: Wrong Answer

Solution code:
import math


def main():
    N = int(input())
    XY = [
        [int(a) for a in input().split()]
        for a in range(N)
    ]

    r = N
    for i in range(N):
        xy1 = XY[i]
        for j in range(i + 1, N):
            xy2 = XY[j]
            dx = xy1[0] - xy2[0]
            dy = xy1[1] - xy2[1]

            bs = set()
            if dx != 0:
                if dx < 0:
                    dx = -dx
                    dy = -dy

                for x, y in XY:
                    k = math.ceil(-x / dx)
                    while True:
                        if x + k * dx < 0:
                            k += 1
                        elif x + (k - 1) * dx >= 0:
                            k -= 1
                        else:
                            break

                    # while not x + k * dx>=0:

                    t = x + k * dx, y + k * dy
                    bs.add(t)
                # print(bs)
                r = min(len(bs), r)
            else:
                for x, y in XY:
                    bs.add(y)
                r = min(len(bs), r)

    print(r)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import Counter
N = int(input())
xy = [list(map(int, input().split())) for _ in range(N)]
xlist = []
for i, (x, y) in enumerate(xy):
    if i == 0:
        tmpx = x
        tmpy = y
        continue
    xlist.append((abs(tmpx-x), abs(tmpy-y)))
    tmpx = x
    tmpy = y

c = Counter(xlist)
m = 0
for (x, y) in c:
    m = max(m, c[(x, y)])
print(N-m)

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:
#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)
if N == 1:
    print(1)
else:
    print(N-most)