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
import sys
from collections.abc import Iterable
from math import *
from itertools import *
from collections import *
from functools import *
from operator import *
try:
    from math import gcd
except Exception:
    from fractions import gcd


def solve(N: int, x: "List[int]", y: "List[int]"):
    rem = {}
    for i in range(N):
        for j in range(i + 1, N):
            dx = x[i] - x[j]
            dy = y[i] - y[j]

            found = False
            for dx2, dy2  in rem.keys():
                if dx * dy2 == dy * dx2:
                    rem[(dx2, dy2)].add(j)
                    found = True
            if not found:
                rem[(dx, dy)] = set()
                rem[(dx, dy)].add(j)
    
    return N #- max([len(v) for k, v in rem.items()])


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))
    result = solve(N, x, y)
    print(result)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

ans = float("inf")
for i in range(1, N):
  if N == 1 or N == 2:
    ans = 1
    break

  xy_copy = xy.copy()
  p, q = xy[i][0] - xy[0][0], xy[i][1] - xy[0][1]
  cnt = 0
  while len(xy_copy) > 0:
    x, y = xy_copy[0][0], xy_copy[0][1]
    rem_list = []
    for j in range(1, len(xy_copy)):
      if p == 0 and xy_copy[j][0] == x or q == 0 and xy_copy[j][1] == y:
        rem_list.append(xy_copy[j])
      elif p * q != 0 and (xy_copy[j][0] - x) * p * (xy_copy[j][1] - y) * q > 0 and (xy_copy[j][0] - x) % p == 0 and (xy_copy[j][1] - y) % q == 0:
        rem_list.append(xy_copy[j])
    for r in rem_list:
      xy_copy.remove(r)
    del xy_copy[0]
    cnt += 1
  ans = min(ans, cnt)
print(ans)

Submission status: Wrong Answer

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

pq = []
for i in range(N) :        
    for j in range(i+1, N) :
        p = xy[j][0] - xy[i][0]
        q = xy[j][1] - xy[i][1]
        pq.append((p, q))
        
pq = list(set(pq))

ret = float('inf')
for p, q in pq :
    tmp = 0
    visited = [0] * N
    for i in range(N) :
        if visited[i] :
            continue
            
        visited[i] = 1
        
        queue = [i]
        while queue :
            que = queue.pop()
            for j in range(N) :
                if visited[j] :
                    continue
                dx = xy[j][0] - xy[que][0]
                dy = xy[j][1] - xy[que][1]
                if (dx == p and dy == q) or (dx == -p and dy == -q) :
                    queue.append(j)
                    visited[j] = 1
    
        tmp += 1
        
    ret = min(tmp, ret)
    
print(ret)

Submission status: Wrong Answer

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

if n <= 2:
    print(1)

else:
    L_sort = sorted(L, key=lambda x:(x[0]+x[1]))
    L_dict = {}
    for i in range(n-1):
        tmp0 = L_sort[i+1][0] - L_sort[i][0]
        tmp1 = L_sort[i+1][1] - L_sort[i][1]
        if (tmp0, tmp1) in L_dict:
            L_dict[(tmp0, tmp1)] += 1
        else:
            L_dict[(tmp0, tmp1)] = 1
    print(L_dict)
    ans = n - max(L_dict.values())
    print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
x = [0] * N
y = [0] * N
X = []
Y = []
Z = []
ans = 0
for i in range(N):
    x[i], y[i] = map(int, input().split())

for k in range(N-1):
    for i in range (N-k-1): 
        X.append(x[k]-x[k+i+1])

for k in range(N-1):
    for i in range (N-k-1): 
        Y.append(y[k]-y[k+i+1])

for i in range(len(X)):
    Z.append([X[i], Y[i]])

for i in range(len(Z)):
    if ans < Z.count(Z[i]):
        ans = Z.count(Z[i])

print(N-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
import random
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))

	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]))
	gess1 = {}
	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 gess1:
			gess1[(p, q)] += 1
		else:
			gess1[(p, q)] = 1
		xm = x
		ym = y

	p, q = max(gess1, key=gess1.get)
	nai1 = gess1[(p,q)]

	#########
	xy = sorted(xy, key=lambda x:(-x[0]))
	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)]

	#########
	xy = sorted(xy, key=lambda x:(x[0],-x[1]))
	gess5 = {}
	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 gess5:
			gess5[(p, q)] += 1
		else:
			gess5[(p, q)] = 1
		xm = x
		ym = y

	p, q = max(gess5, key=gess5.get)
	nai5 = gess5[(p,q)]

	#########
	random.shuffle(xy)
	gess6 = {}
	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 gess6:
			gess6[(p, q)] += 1
		else:
			gess6[(p, q)] = 1
		xm = x
		ym = y

	p, q = max(gess6, key=gess6.get)
	nai6 = gess6[(p,q)]

	#########
	random.shuffle(xy)
	gess7 = {}
	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 gess7:
			gess7[(p, q)] += 1
		else:
			gess7[(p, q)] = 1
		xm = x
		ym = y

	p, q = max(gess7, key=gess7.get)
	nai7 = gess7[(p,q)]
		#########
	xy = sorted(xy, key=lambda x:(x[1],x[0]))
	gess8 = {}
	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 gess8:
			gess8[(p, q)] += 1
		else:
			gess8[(p, q)] = 1
		xm = x
		ym = y

	p, q = max(gess8, key=gess8.get)
	nai8 = gess8[(p,q)]

		#########
	ans = -1

	for _ in range(10000):
		random.shuffle(xy)
		gess9 = {}
		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 gess9:
				gess9[(p, q)] += 1
			else:
				gess9[(p, q)] = 1
			xm = x
			ym = y

		p, q = max(gess9, key=gess9.get)
		nai9 = gess9[(p,q)]

		if nai9 > ans:
			ans = nai9

	tmp = max(nai, nai2, nai3,nai4, nai5,nai6,nai1,nai7,nai8,ans)

	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)]
XY.sort(key = lambda x: (-x[0], -x[1]))
cxy = sorted(XY, key = lambda x: (x[0], x[1]))
if N == 1:
  print(1)
  exit()

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

pre = []
ans = []
arr=XY[:]
for p, q in diff:
  if p < 0 and q < 0:
    arr = cxy[:]
  cost = 1
  for a, b in arr:
    if not pre:
      pre = (a, b)
      continue
    if (a - p, b - q) == pre:
      pass
    else:
      cost += 1
    pre = (a, b)
  ans.append(cost)
  pre = []
print(min(ans))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
from collections.abc import Iterable
from math import *
from itertools import *
from collections import *
from functools import *
from operator import *
try:
    from math import gcd
except Exception:
    from fractions import gcd


def solve(N: int, x: "List[int]", y: "List[int]"):
    rem = {}
    for i in range(N):
        for j in range(i + 1, N):
            dx = x[i] - x[j]
            dy = y[i] - y[j]

            found = False
            for dx2, dy2  in rem.keys():
                if dx * dy2 == dy * dx2:
                    rem[(dx2, dy2)].add(j)
                    found = True

    return 0
#            if not found:
#                rem[(dx, dy)] = set()
#                rem[(dx, dy)].add(j)
#    
#    return N - max([len(v) for k, v in rem.items()])


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))
    result = solve(N, x, y)
    print(result)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def calc(XYi, pq):
    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

    ps = []
    qs = []
    maxv = 0
    maxv = 0
    
    for i in dictX.keys():
        if i == 0 and pq:
            continue
        v = dictX[i]
        if v > maxv:
            maxv = v
    for i in dictX.keys():
        v = dictX[i]
        if v == maxv:
            ps.append(i)

    maxv = 0
    for i in dictY.keys():
        if i == 0 and not pq:
            continue
        v = dictY[i]
        if v > maxv:
            maxv = v
    for i in dictY.keys():
        v = dictY[i]
        if v == maxv:
            qs.append(i)

    min_cost = 99999
    for p in ps:
        for q in qs:
            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
            if cost < min_cost:
                min_cost = cost
    return min_cost


N = int(input())
XYi = [0] * N
for i in range(N):
    x, y = list(map(int, input().split()))
    XYi[i] = (x, y)

for i in range(N):
    for k in range(N):
        if i < k:
            if XYi[i][0] > XYi[k][0]:
                t = XYi[i]
                XYi[i] = XYi[k]
                XYi[k] = t
            elif XYi[i][0] == XYi[k][0]:
                if XYi[i][1] > XYi[k][1]:
                    t = XYi[i]
                    XYi[i] = XYi[k]
                    XYi[k] = t
costX = min(calc(XYi, True), calc(XYi, False))

for i in range(N):
    for k in range(N):
        if i < k:
            if XYi[i][1] > XYi[k][1]:
                t = XYi[i]
                XYi[i] = XYi[k]
                XYi[k] = t
            elif XYi[i][1] == XYi[k][1]:
                if XYi[i][0] > XYi[k][0]:
                    t = XYi[i]
                    XYi[i] = XYi[k]
                    XYi[k] = t

costY = min(calc(XYi, True), calc(XYi, False))

print(min(costX, costY))

Submission status: Wrong Answer

Solution code:
n=int(input())
r=[]
a=[]
for i in range(n):
  b,c=(int(j) for j in input().split())
  for k in range(i):
    d=a[k][0]-b
    e=a[k][1]-c
    if d<0:
      d=-d
      e=-e
    r.append([d,e])
  a.append([b,c])
r.sort()
if n>1:
  p=r[0]
x=1
z=1
t=0
q=[]
for i in range(len(r)-1):
  if r[i]==r[i+1]:
    x=x+1
  else:
    if x>z:
      p=r[i]
      z=x
    x=1
if n==1:
  print(1)
else:
  for i in range(n):
    if a[i] not in q:
      t=t+1
    q.append([a[i][0]+p[0],a[i][1]+p[1]])
    q.append([a[i][0]-p[0],a[i][1]-p[1]])
  print(t)

Submission status: Wrong Answer

Solution code:
N = int(input())
ball = []
dif = [[] for i in range(N-1)]
for i in range(N):
    x,y = map(int,input().split())
    ball += [[x,y]]
ball = sorted(ball)

for i in range(N-1):
    for j in range(N-i-1):
        dif[i].append([ball[j+1+i][0] - ball[i][0], ball[j+1+i][1] - ball[i][1]])

ans = 0
for i in range(N-1):
    for j in range(N-i-1):
        base = dif[i][j]
        point = 0
        for k in range(i+1,N-1):
            for l in range(N-k-1):
                if base == dif[k][l]:
                    point += 1
                    break
        if ans < point: ans = point

if N != 1:
    if ans == 0:    print(N-1)
    else:   print(N-ans)
else:   print(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]))
cxy = sorted(XY, key = lambda x: (x[0], x[1]))
if N == 1:
  print(1)
  exit()

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

pre = []
ans = []
arr=XY[:]
for p, q in diff:
  if p <= 0 or q <= 0:
    arr = cxy[:]
  cost = 1
  for a, b in arr:
    if not pre:
      pre = (a, b)
      continue
    if (a - p, b - q) == pre:
      pass
    else:
      cost += 1
    pre = (a, b)
  ans.append(cost)
  pre = []
print(min(ans))

Submission status: Wrong Answer

Solution code:
def gcd(a, b):
    if b < 0:
        return gcd(a, -b)
    if b == 0:
        return a
    else:
        return gcd(b, a%b)

def solve():
    N = int(raw_input())
    xy = [None] * N
    for i in range(N):
        xi, yi = [int(_) for _ in raw_input().split()]
        xy[i] = (xi, yi)
    xy.sort(key = lambda x: x[0])
    pq_set = []
    def AddToPQSet(ele):
        pq, i, j = ele
        # if len(pq_set) == 0 or pq_set[0][0] > pq:
        #     pq_set.insert(0, (pq, set()))
        #     pq_set[0][1].add(i)
        #     pq_set[0][1].add(j)
        added_flag = False
        for ind in range(0, len(pq_set)):
            if pq_set[ind][0] == pq:
                subset_added = False
                for subset in pq_set[ind][1]:
                    if i in subset:
                        subset.add(j)
                        subset_added = True
                        break
                    elif j in subset:
                        subset.add(i)
                        subset_added = True
                        break
                if not subset_added:
                    tmp_set = set()
                    tmp_set.add(i)
                    tmp_set.add(j)
                    pq_set[ind][1].append(tmp_set)
                added_flag = True
                break
            elif pq_set[ind][0] > pq:
                tmp_set = set()
                tmp_set.add(i)
                tmp_set.add(j)
                pq_set.insert(ind, (pq, [tmp_set]))
                added_flag = True
                break
        if not added_flag:
            tmp_set = set()
            tmp_set.add(i)
            tmp_set.add(j)
            pq_set.append((pq, [tmp_set]))
        # print pq
        # print "i = " + str(i) + ", j = " + str(j)
        # print pq_set

    for i in range(N):
        for j in range(i+1, N):
            p = xy[j][0] - xy[i][0]
            q = xy[j][1] - xy[i][1]
            _gcd = gcd(p,q)
            # print "i = " + str(i) + ", j = " + str(j)
            # print p, q, _gcd
            p = p / _gcd
            q = q / _gcd
            AddToPQSet(((p,q),i,j))

    maxcntpq = 0
    # print pq_set
    for i in range(len(pq_set)):
        if len(pq_set[i][1]) > maxcntpq:
            num_subset = len(pq_set[i][1])
            cnt = 0
            for subset in pq_set[i][1]:
                cnt += len(subset)
            cnt -= num_subset
            if cnt > maxcntpq:
                maxcntpq = cnt
    print N - maxcntpq

if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
import copy
import sys
input = sys.stdin.readline
'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)
#'''
N = int(input())
x, y = [0] * N, [0] * N

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

ans = 10 ** 18
	
for i in range(N):
	for j in range(N):
		if i == j:
			continue
			
		p, q = x[j] - x[i], y[j] - y[i]
		cost = 0
		n = 0
		flag = 1
		next_x = x[i] + p
		next_y = y[i] + q
		tmp_x = copy.copy(x)
		tmp_y = copy.copy(y)
		tmp_x.pop(i)
		tmp_y.pop(i)
		
		while n < N:
			cost += 1
			n += 1
			flag = 1
			while flag == 1:
				flag = 0
				
				for l in range(len(tmp_x)):
					if tmp_x[l] == next_x and tmp_y[l] == next_y:
						flag = 1
						n += 1
						next_x += p
						next_y += q
						tmp_x.pop(l)
						tmp_y.pop(l)
						break
			if len(tmp_x) > 0:			
				next_x = tmp_x[0] + p
				next_y = tmp_y[0] + q
		
		if cost < ans:
			ans = cost
			
print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

import sys
from itertools import combinations
from collections import Counter

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N=INT()

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

xy=[]
for i in range(N):
    x,y=MAP()
    xy.append((x, y))

C=Counter()
for comb in combinations(xy, 2):
    a,b=comb
    C[(abs(a[0]-b[0]), abs(a[1]-b[1]))]+=1

mx=max(C.values())
print(N-mx)

Submission status: Wrong Answer

Solution code:
n=int(input())
d=[list(map(int,input().split()))for _ in range(n)]
def c(p,q,a):
  global n
  s=n
  for i in a:
    if [i[0]-p,i[1]-q]in a:s-=1
  return s
ans=50
for i in range(n):
  for j in range(n):
    p,q=d[j][0]-d[i][0],d[j][1]-d[i][1]
    if not(p==q==0):ans=min(ans,c(p,q,d))
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
from collections.abc import Iterable
from math import *
from itertools import *
from collections import *
from functools import *
from operator import *
try:
    from math import gcd
except Exception:
    from fractions import gcd


def solve(N: int, x: "List[int]", y: "List[int]"):
    rem = {}
    for i in range(N):
        for j in range(i + 1, N):
            dx = x[i] - x[j]
            dy = y[i] - y[j]

    return 0
#            found = False
#            for dx2, dy2  in rem.keys():
#                if dx * dy2 == dy * dx2:
#                    rem[(dx2, dy2)].add(j)
#                    found = True
#            if not found:
#                rem[(dx, dy)] = set()
#                rem[(dx, dy)].add(j)
#    
#    return N - max([len(v) for k, v in rem.items()])


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))
    result = solve(N, x, y)
    print(result)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

pqs = {}

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

        if p == 0 or q == 0:
            continue

        p = max(p, -p)
        q = max(q, -q)

        string = str(p) + " " + str(q)
        if string not in pqs:
            pqs[string] = 0

        pqs[string] += 1


# p, q = map(int, max(pqs.items(), key=lambda x: x[1])[0].split())

print(max(n - max(pqs.values()), 1) if len(pqs) != 0 else n)

Submission status: Wrong Answer

Solution code:
import numpy as np
N=int(input())
x = [0] * N
y = [0] * N
ans = N

for i in range(N):
  x[i], y[i] = map(int, input().split())
  
for i in range(N):
  cost = N
  for j in range(i+1,N):
    p = x[i] - x[j]
    q = y[i] - y[j]
    if p == 0 and q==0:
      cost = N*2
    diffx = np.diff(x)
    diffy = np.diff(y)
    for k in range(N-1):
      if diffx[k] == p and diffy[k] == q:
        cost = cost - 1
      if diffx[k] == -p and diffy[k] == -q:
        cost = cost - 1
  ans = min(ans,cost)

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
x = [0]*n
y = [0]*n
x_y_sum = [0]*n
total = []
p_q = []
for i in range(n):
    x[i], y[i] = map(int, input().split())
total.append([0, x[0], y[0]])
for i in range(1, n):
    total.append([x[i]-x[i-1]+y[i]-y[i-1], x[i], y[i]])
total.sort()
cnt = 1
for i in range(1, n):
    p_q.append([total[i][1]-total[i-1][1], total[i][2]-total[i-1][2]])
p_q.sort()
new = []
for i in range(1, len(p_q)):
    new.append(list(set(p_q[i])-set(p_q[i-1])))
for i in range(len(new)):
    if new[i] != []:
        cnt += 1
print(cnt)

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

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

    x.sort()
    y.sort()

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

    from collections import Counter

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

    p = [i for i,v in csx.most_common()] + [-1*i for i,v in csx.most_common()]
    q = [i for i,v in csy.most_common()] + [-1*i for i,v in csy.most_common()]
    p.sort()
    q.sort()
    # print(p)

    if(len(p) == 0):
        p.append(0)

    if(len(q) == 0):
        q.append(0)

    a = sorted(a, key=lambda x:(x[1],x[0]), reverse=True)
    ans = 10000000000
    for i in p:
        for j in q:
            if(i == 0 and j == 0):
                continue
            
            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)

    a = sorted(a, key=lambda x:(x[0],x[1]), reverse=True)
    for i in p:
        for j in q:
            if(i == 0 and j == 0):
                continue
            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()