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 copy
import math

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

def dfs(parent, p, q):
    tosee.remove(parent)
    group[-1].append(parent)
    for el in tosee:
        x, y = el
        if x + p == parent[0] and y + q == parent[1] or \
                x - p == parent[0] and y - q == parent[1]:
            dfs(el,p,q)

m = N
for i in range(N - 1):
    for j in range(i + 1, N):
        p = xy[i][0] - xy[j][0]
        q = xy[i][1] - xy[j][1]

        group = []
        tosee = copy.copy(xy)
        while tosee:
            el = tosee[0]
            group.append([])
            dfs(el,p,q)
            # print(tosee)
        temp = len(group)
        m = min(temp, m)
        # print(p, q, group)
print(m)

Submission status: Wrong Answer

Solution code:
import collections

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

moves = collections.defaultdict(list)
mmax = -1
vmax = None
for i in range(N):
    for j in range(i):
        x1, y1 = balls[i]
        x2, y2 = balls[j]
        if y1 > y2 or (y1 == y2 and x1 > x2):
            x1, x2 = x2, x1
            y1, y2 = y2, y1
        moves[x2-x1, y2-y1].append((j, i))
        m = len(moves[x2-x1, y2-y1])
        if m > mmax:
            mmax = m
            vmax = (x2-x1, y2-y1)

print(N - mmax)

Submission status: Wrong Answer

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

count={}
ans=0
for i in range(n):
    
    for j in range(i+1,n):
   #     print(i,j)
        x=xy[i][0]-xy[j][0]
        y=xy[i][1]-xy[j][1]
        if (x,y) in count:
            count[x,y]+=1
        else:
            count[x,y]=1
#print(count)
for v in count.values():
    ans=max(ans,v)
print(n-ans)

Submission status: Wrong Answer

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

count={}
ans=0
for i in range(n):
    
    for j in range(i+1,n):
 #       print(i,j)
        x=xy[i][0]-xy[j][0]
        y=xy[i][1]-xy[j][1]
        if (x,y) in count:
            count[(x,y)]+=1
        else:
            count[(x,y)]=1
#print(count)
for v in count.values():
    ans=max(ans,v)
print(n-ans)

Submission status: Wrong Answer

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

count={}
ans=0
for i in range(n):
    for j in range(i+1,n):
        x=xy[i][0]-xy[j][0]
        y=xy[i][1]-xy[j][1]
        if (x,y) in count:
            count[(x,y)]+-1
        else:
            count[(x,y)]=1

for v in count.values():
    ans=max(ans,v)
print(n-ans)

Submission status: Wrong Answer

Solution code:
N,*L = map(int, open(0).read().split())
ls = [0]*N
for i,c in enumerate(zip(*[iter(L)]*2)):
  ls[i] = c
ls.sort()
pls = []
for i in range(N):
  for j in range(i+1,N):
    a,b = ls[i]
    x,y = ls[j]
    pls += [(x-a,y-b)]
ans = 10**10
for X,Y in pls:
  s = set()
  m = 0
  for x,y in ls:
    if (x-X, y-Y) not in s:
      m += 1
    s.add((x,y))
  ans = min(m,ans)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)

def get_par(x):
  if x == par_list[x]:
    return x
  else:
    par_list[x] = get_par(par_list[x])
    return par_list[x]

def merge(x,y):
  par_x = get_par(x)
  par_y = get_par(y)
  if par_x != par_y:
    par_list[par_y] = par_x

def is_same(x,y):
  return get_par(x) == get_par(y)

N=int(input())
if N<=2:
  print(1)
  sys.exit(0)

xylist=[]
for i in range(N):
  x,y=map(int,input().split())
  xylist.append((x,y))
xylist.sort()
#print(xylist)

pqset=set()
for i in range(N):
  x1,y1=xylist[i]
  for j in range(i+1,N):
    x2,y2=xylist[j]
    p=x2-x1
    q=y2-y1
    pqset.add((p,q))
#print(len(pqset))
    
answer=50
for p,q in pqset:
  par_list=list(range(N))
  for i in range(N):
    x1,y1=xylist[i]
    for j in range(i+1,N):
      x2,y2=xylist[j]
      dx=x2-x1
      dy=y2-y1
      
      if p==0 and dx==0 and dy%q==0:
        merge(i,j)
      elif q==0 and dy==0 and dx%p==0:
        merge(i,j)
      elif p!=0 and dx%p==0 and q!=0 and dy%q==0 and dx//p==dy//q:
        merge(i,j)
        
  #print(par_list)  
  comp_set=set()
  for i in range(N):
    comp_set.add(get_par(i))
  answer=min(answer,len(comp_set))
  #print(p,q,len(comp_set))
    
print(answer)

Submission status: Wrong Answer

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

if N<=2:
  print(1)
  sys.exit(0)

xylist=[]
for i in range(N):
  x,y=map(int,input().split())
  xylist.append((x,y))
xylist.sort()
#print(xylist)

answer=50
for i in range(N):
  x1,y1=xylist[i]
  for j in range(i+1,N):
    x2,y2=xylist[j]
    #ax+by+c=0
    a=y2-y1
    b=-x2+x1
    
    sep_set=set()
    for k in range(N):
      x3,y3=xylist[k]
      c=a*x3+b*y3
      sep_set.add(c)
    #print(sep_set)
    answer=min(answer,len(sep_set))
    
print(answer)

Submission status: Wrong Answer

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

vectors = set()
for i in range(n-1):
    for j in range(i+1, n):
        xi, yi = xy[i]
        xj, yj = xy[j]
        if xj-xi == 0 and yj-yi == 0:
            continue
        unit_vector = (xj-xi, yj-yi)
        vectors |= {unit_vector}
ans = n
for vector in vectors:
    cnt = 0
    for i in range(n-1):
        for j in range(i+1, n):
            xi, yi = xy[i]
            xj, yj = xy[j]
            if vector == (xj-xi, yj-yi):
                cnt += 1
    ans = min(ans, n-cnt)
print(ans)

Submission status: Wrong Answer

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

vectors = set()
for i in range(n-1):
    for j in range(i+1, n):
        xi, yi = xy[i]
        xj, yj = xy[j]
        if xj-xi == 0 or yj-yi == 0:
            continue
        unit_vector = (xj-xi, yj-yi)
        vectors |= {unit_vector}
ans = n
for vector in vectors:
    cnt = 0
    for i in range(n-1):
        for j in range(i+1, n):
            xi, yi = xy[i]
            xj, yj = xy[j]
            if vector == (xj-xi, yj-yi):
                cnt += 1
    ans = min(ans, n-cnt)
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import combinations
n = int(input())
pos = []
for i in range(n):
  pos.append(tuple(map(int,input().split())))
ans = 1e100
def cost(p,q):
  ret = 0
  for i,j in pos:
    ret += 1 - ((i+p,j+q) in pos)
  return ret
for a,b in combinations(pos, 2):
  ans = min(ans, cost(a[0]-b[0],a[1]-b[1]))
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import combinations
n = int(input())
pos = []
for i in range(n):
  pos.append(tuple(map(int,input().split())))
ans = 1e100
def cost(p,q):
  ret = 0
  for i,j in pos:
    ret += 1 - ((i+p,j+q) in pos)
  return ret
for a,b in combinations(pos, 2):
  ans = max(ans, cost(a[0]-b[0],a[1]-b[1]))
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
if n==1:
    print(1)
    exit()
elif n==2:
    x, y = map(int, input().split())
    a, b = map(int, input().split())
    if a/x == b/y:
        print(1)
    else:
        print(2)
    exit()
    
x,y=map(int,input().split())
li=[]
for i in range(n-1):
    a=x
    b=y
    x,y=map(int,input().split())
    li.append([x-a,y-b])
li=sorted(li, key=lambda x: x[0])
ans=0
cnt=1
for i in range(n-2):
    if li[i+1]==li[i]:
        cnt+=1
    else:
        ans=max(ans,cnt)
        cnt=1
ans=max(ans,cnt)
if ans==1:
  print(n)
else:
  print(n-ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
if n==1:
    print(1)
    exit()
elif n==2:
    x, y = map(int, input().split())
    a, b = map(int, input().split())
    if a/x == b/y:
        print(1)
    else:
        print(2)
    exit()
    
x,y=map(int,input().split())
li=[]
for i in range(n-1):
    a=x
    b=y
    x,y=map(int,input().split())
    li.append([x-a,y-b])
li=sorted(li, key=lambda x: x[0])
ans=0
cnt=1
for i in range(n-2):
    if li[i+1]==li[i]:
        cnt+=1
    else:
        ans=max(ans,cnt)
        cnt=1
print(n-ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
xy = [tuple(map(int, input().split())) for _ in range(n)]
s_xy = set(xy)

count = 0
for i in range(n-1):
    for j in range(i+1, n):
        ix, iy = xy[i]
        jx, jy = xy[j]
        p, q = jx - jy, jy - jx
        tc = sum((x-p,y-q) in s_xy for x, y in s_xy)

        count = max(count, tc)
            
print(n-count)

Submission status: Wrong Answer

Solution code:

import numpy as np
from functools import *
import sys
sys.setrecursionlimit(100000)
input = sys.stdin.readline




def acinput():
    return list(map(int, input().split(" ")))


def II():
    return int(input())

directions=np.array([[1,0],[0,1],[-1,0],[0,-1]])
directions = list(map(np.array, directions))

mod = 10**9+7


def factorial(n):
    fact = 1
    for integer in range(1, n + 1):
        fact *= integer
    return fact



def serch(x, count):
    #print("top", x, count)
            

    for d in directions:
        nx = d+x
        #print(nx)
        if np.all(0 <= nx) and np.all(nx < (H, W)):
            if field[nx[0]][nx[1]] == "E":
                count += 1 
                field[nx[0]][nx[1]] = "V"
                count = serch(nx, count)  
                continue
            if field[nx[0]][nx[1]] == "#":
                field[nx[0]][nx[1]] = "V"
                count = serch(nx, count)    
                 
    return count

N=int(input())

x= [np.array(acinput())for i in range(N)]
#x = [acinput() for i in range(N)]
#print(tmp)
#x=sorted(tmp)

import itertools as it

from collections import defaultdict
#es=10**10

#dc={}
dc=defaultdict(int)

for cb in it.combinations(x,2):
    d=cb[0]-cb[1]
    d=tuple(d)
    dc[d]+=1

#print(dc)    
if N==1:
    print(1)
else:
    print(N-max(dc.values()))

Submission status: Wrong Answer

Solution code:

import numpy as np
from functools import *
import sys
sys.setrecursionlimit(100000)
input = sys.stdin.readline




def acinput():
    return list(map(int, input().split(" ")))


def II():
    return int(input())

directions=np.array([[1,0],[0,1],[-1,0],[0,-1]])
directions = list(map(np.array, directions))

mod = 10**9+7


def factorial(n):
    fact = 1
    for integer in range(1, n + 1):
        fact *= integer
    return fact



def serch(x, count):
    #print("top", x, count)
            

    for d in directions:
        nx = d+x
        #print(nx)
        if np.all(0 <= nx) and np.all(nx < (H, W)):
            if field[nx[0]][nx[1]] == "E":
                count += 1 
                field[nx[0]][nx[1]] = "V"
                count = serch(nx, count)  
                continue
            if field[nx[0]][nx[1]] == "#":
                field[nx[0]][nx[1]] = "V"
                count = serch(nx, count)    
                 
    return count

N=int(input())

x= [np.array(acinput())for i in range(N)]
#print(tmp)
#x=sorted(tmp)

import itertools as it

res=10**10

for cb in it.combinations(x,2):
    d=cb[0]-cb[1]
    count=0
    for cb2 in it.combinations(x, 2):
        d2=cb2[0]-cb2[1]
        if np.all(d==d2):
            count+=1
    
    res=min(res,N-count)
    
print(res)

Submission status: Wrong Answer

Solution code:
from collections import *
from heapq import *
from itertools import *
from fractions import gcd
import sys
from decimal import *
input=lambda :sys.stdin.readline().rstrip()

N=int(input())
if N==1:
    print(1)
XY=[list(map(int,input().split())) for i in range(N)]
itelst=combinations(range(N),2)

alst=[]
for a,b in itelst:
    x1,y1=XY[a]
    x2,y2=XY[b]
    Y=y1-y2;X=x1-x2
    if X and Y:
        alst.append([X,Y])
    elif Y or X:
        alst.append([X,Y])



value=50
idlemax=10**18
for Xa,Ya in alst:
    n=set([x+idlemax*y for x,y in XY])

    count=0
    for x,y in XY:
        if x+idlemax*y in n:
            count+=1
            a=0;b=0
            A=x+Xa+a+idlemax*(y+Ya+b)
            while A in n:
                n.remove(A)
                a+=Xa;b+=Ya
                A=x+Xa+a+idlemax*(y+Ya+b)

            a=0;b=0
            A=x-Xa-a+idlemax*(y-Ya-b)
            while A in n:
                n.remove(A)
                a+=Xa;b+=Ya
                A=x-Xa-a+idlemax*(y-Ya-b)
    value=min(value,count)
print(value)

Submission status: Wrong Answer

Solution code:
from collections import *
from heapq import *
from itertools import *
from fractions import gcd
import sys
from decimal import *
input=lambda :sys.stdin.readline().rstrip()

N=int(input())
XY=[list(map(int,input().split())) for i in range(N)]
itelst=combinations(range(N),2)

alst=[]
for a,b in itelst:
    x1,y1=XY[a]
    x2,y2=XY[b]
    Y=y1-y2;X=x1-x2
    if X and Y:
        alst.append([X,Y])
    elif Y or X:
        alst.append([X,Y])



value=50
idlemax=10**18
for Xa,Ya in alst:
    n=set([x+idlemax*y for x,y in XY])

    count=0
    for x,y in XY:
        if x+idlemax*y in n:
            count+=1
            a=0;b=0
            A=x+Xa+a+idlemax*(y+Ya+b)
            while A in n:
                n.remove(A)
                a+=Xa;b+=Ya
                A=x+Xa+a+idlemax*(y+Ya+b)

            a=0;b=0
            A=x-Xa-a+idlemax*(y-Ya-b)
            while A in n:
                n.remove(A)
                a+=Xa;b+=Ya
                A=x-Xa-a+idlemax*(y-Ya-b)
    value=min(value,count)
print(value)

Submission status: Wrong Answer

Solution code:
from collections import *
from heapq import *
from itertools import *
from fractions import gcd
import sys
from decimal import *
input=lambda :sys.stdin.readline().rstrip()

N=int(input())
XY=[list(map(int,input().split())) for i in range(N)]
itelst=combinations(range(N),2)

alst=[]
for a,b in itelst:
    x1,y1=XY[a]
    x2,y2=XY[b]
    Y=y1-y2;X=x1-x2
    if X and Y:
        alst.append([X,Y])
    elif Y or X:
        alst.append([X,Y])



value=50
idlemax=10**18
for Xa,Ya in alst:
    n=set()
    count=0
    for x,y in XY:
        if x+Xa+idlemax*(y+Ya) in n or x-Xa+idlemax*(y-Ya) in n:
            pass
        else:
            count+=1
        n.add(x+idlemax*y)
    value=min(value,count)
print(value)

Submission status: Wrong Answer

Solution code:
from collections import *
from heapq import *
from itertools import *
from fractions import gcd
import sys
from decimal import *
input=lambda :sys.stdin.readline().rstrip()

N=int(input())
XY=[list(map(int,input().split())) for i in range(N)]
itelst=combinations(range(N),2)

alst=[]
for a,b in itelst:
    x1,y1=XY[a]
    x2,y2=XY[b]
    Y=y1-y2;X=x1-x2
    if X and Y:
        alst.append([X,Y])
    elif Y or X:
        alst.append([X,Y])



value=50
idlemax=10**18
for Xa,Ya in alst:
    n=set()
    for x,y in XY:
        if Xa and Ya:
            n.add(x%Xa+idlemax*(y-Ya*(x//Xa)))
        elif Xa:
            n.add(y)
        elif Ya:
            n.add(x)

    value=min(value,len(n))
print(value)

Submission status: Wrong Answer

Solution code:
from collections import *
from heapq import *
from itertools import *
from fractions import gcd
import sys
from decimal import *
input=lambda :sys.stdin.readline().rstrip()


N=int(input())
XY=[list(map(int,input().split())) for i in range(N)]
itelst=combinations(range(N),2)

alst=[]
for a,b in itelst:
    x1,y1=XY[a]
    x2,y2=XY[b]
    Y=y1-y2;X=x1-x2
    if X and Y:
        G=gcd(Y,X)
        alst.append([X//G,Y//G])
    elif Y or X:
        alst.append([X,Y])



value=50
idlemax=10**18
for Xa,Ya in alst:
    n=set()
    for x,y in XY:
        if Xa and Ya:
            n.add(x%Xa+idlemax*(y-Ya*(x//Xa)))
        elif Xa:
            n.add(y)
        elif Ya:
            n.add(x)

    value=min(value,len(n))
print(value)

Submission status: Wrong Answer

Solution code:
from collections import *
from heapq import *
from itertools import *
from fractions import gcd
import sys
from decimal import *
input=lambda :sys.stdin.readline().rstrip()


N=int(input())
XY=[list(map(int,input().split())) for i in range(N)]
itelst=combinations(range(N),2)

alst=[]
for a,b in itelst:
    flag=0
    x1,y1=XY[a]
    x2,y2=XY[b]

    Y=y1-y2;X=x1-x2
    if X:
        alst.append( Decimal(Y)/Decimal(X) )
    else:
        alst.append("tate")
#print (alst)

value=50

for a in alst:
    n=set()
    if a!="tate":
        for x,y in XY:
            y=Decimal(y-Decimal(x)*Decimal(a))
            n.add(y)
    else:
        for x,y in XY:
            n.add(x)
    value=min(value,len(n))
print(value)

Submission status: Wrong Answer

Solution code:
from collections import *
from heapq import *
from itertools import *
from fractions import gcd
import sys
from decimal import *
input=lambda :sys.stdin.readline().rstrip()


N=int(input())
XY=[list(map(int,input().split())) for i in range(N)]
itelst=combinations(range(N),2)

alst=[]
for a,b in itelst:
    flag=0
    x1,y1=XY[a]
    x2,y2=XY[b]

    Y=y1-y2;X=x1-x2
    if X:
        alst.append( Decimal(Y)/Decimal(X) )
    else:
        alst.append("tate")
#print (alst)

value=50

for a in alst:
    n=set()
    if a!="tate":
        for x,y in XY:
            y-=Decimal(x)*Decimal(a)
            n.add(y)
    else:
        for x,y in XY:
            n.add(x)
    value=min(value,len(n))
print(value)

Submission status: Wrong Answer

Solution code:
from collections import *
from heapq import *
from itertools import *
from fractions import gcd
import sys
from decimal import *
input=lambda :sys.stdin.readline().rstrip()


N=int(input())
XY=[list(map(int,input().split())) for i in range(N)]
itelst=combinations(range(N),2)

alst=[]
for a,b in itelst:
    flag=0
    x1,y1=XY[a]
    x2,y2=XY[b]

    Y=y1-y2;X=x1-x2
    if X:
        alst.append( Decimal(Y)/Decimal(X) )
    else:
        alst.append("tate")
#print (alst)

value=50

for a in alst:
    lst=set(list(range(N)))
    count=0
    while lst:
        count+=1
        n=lst.pop()
        x1,y1=XY[n]
        nlst=set()
        while lst:
            n=lst.pop()
            x2,y2=XY[n]
            Y=y1-y2;X=x1-x2
            if X and a== Decimal(Y)/Decimal(X) or X==0 and a == "tate":
                pass
            else:
                nlst.add(n)
        lst|=nlst
    value=min(value,count)
print(value)

Submission status: Wrong Answer

Solution code:
from collections import *
from heapq import *
from itertools import *
from fractions import gcd
import sys
from decimal import *
input=lambda :sys.stdin.readline().rstrip()


N=int(input())
XY=[list(map(int,input().split())) for i in range(N)]
itelst=combinations(range(N),2)

alst=[]
for a,b in itelst:
    flag=0
    x1,y1=XY[a]
    x2,y2=XY[b]

    Y=y1-y2;X=x1-x2
    if X:
        alst.append( Decimal(Y)/Decimal(X) )
#print (alst)

value=50

for a in alst:
    lst=set(list(range(N)))
    count=0
    while lst:
        count+=1
        n=lst.pop()
        x1,y1=XY[n]
        nlst=set()
        while lst:
            n=lst.pop()
            x2,y2=XY[n]
            Y=y1-y2;X=x1-x2
            if not (X and a== Decimal(Y)/Decimal(X)):
                nlst.add(n)
        lst|=nlst
    value=min(value,count)
print(value)

Submission status: Wrong Answer

Solution code:
from collections import Counter
N = int(input())
P = set(tuple(map(int, input().split())) for _ in range(N))

p_q_cand = []
for p in P:
    for q in P:
        if p == q:
            continue
        diff_p = p[0]-q[0]
        diff_q = p[1]-q[1]
        p_q_cand.append((abs(diff_p), abs(diff_q)))

if N == 1:
    print(1)
else:
    C = Counter(p_q_cand)
    ans = float('inf')
    for v, c in C.items():
        p = v[0]
        q = v[1]
        tmp = 0
        used = set()
        for a, b in sorted(list(P), key=lambda x: (x[0], x[1])):
            if (a-p, b-q) not in used:
                tmp += 1
            used.add((a, b))
        ans = min(ans, tmp)
    print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter
N = int(input())
P = set(tuple(map(int, input().split())) for _ in range(N))

p_q_cand = []
for p in P:
    for q in P:
        if p == q:
            continue
        diff_p = p[0]-q[0]
        diff_q = p[1]-q[1]
        p_q_cand.append((abs(diff_p), abs(diff_q)))

if N == 1:
    print(1)
else:
    C = Counter(p_q_cand)
    ans = float('inf')
    for v, c in C.items():
        p = v[0]
        q = v[1]
        tmp = 0
        used = set()
        for a, b in sorted(P):
            if (a-p, b-q) not in used:
                tmp += 1
            used.add((a, b))
        ans = min(ans, tmp)
    print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter
N = int(input())
P = set(tuple(map(int, input().split())) for _ in range(N))

p_q_cand = []
for p in P:
    for q in P:
        if p == q:
            continue
        diff_p = p[0]-q[0]
        diff_q = p[1]-q[1]
        p_q_cand.append((abs(diff_p), abs(diff_q)))

if N == 1:
    print(1)
else:
    C = Counter(p_q_cand)
    p, q = C.most_common()[0][0]
    ans = 0
    used = set()
    for a, b in sorted(P):
        if (a-p, b-q) not in used:
            ans += 1
        used.add((a, b))
    print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import combinations
from collections import Counter
N = int(input())
xy = [list(map(int, input().split())) for _ in range(N)]

count = []
for ((x1,x2),(x3,x4)) in combinations(xy, 2):
    count.append((x1-x3,x2-x4))
    
c = Counter(count)
m = 0
for i in c.values():
    m = max(m, i)

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

Submission status: Wrong Answer

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

def get_cnt(xy):
    diff = set()
    for i in range(1, len(xy)):
        x = xy[i][0]-xy[i-1][0]
        y = xy[i][1]-xy[i-1][1]
        diff.add((x,y))
    return len(diff)

asc = get_cnt(xy)
xy.sort(key=lambda x:x[1])
desc = get_cnt(xy)
m = min(asc, desc)
print(m)

Submission status: Wrong Answer

Solution code:
from collections import Counter
N = int(input())
xy = sorted([list(map(int, input().split())) for _ in range(N)])
def getCount(xy):
    diff = []
    for i in range(1, len(xy)):
        x = xy[i][0]-xy[i-1][0]
        y = xy[i][1]-xy[i-1][1]
        diff.append((x,y))
    return Counter(diff)

def getMax(c):
    xm = 0
    for i in c:
        xm = max(xm, c[i])
    return xm

ret = []
c = getCount(xy)
ret.append(getMax(c))
m = max(ret)
print(N-m)

Submission status: Wrong Answer

Solution code:
from collections import Counter
N = int(input())
xy = sorted([list(map(int, input().split())) for _ in range(N)])
def getCount(xy):
    diff = []
    for i in range(1, len(xy)):
        x = xy[i][0]-xy[i-1][0]
        y = xy[i][1]-xy[i-1][1]
        diff.append((x,y))
    return Counter(diff)

def getMax(c):
    xm = 0
    for i in c:
        xm = max(xm, c[i])
    return xm
ret = []
c = getCount(xy)
ret.append(getMax(c))
xy.sort(key=lambda x:x[1])
c = getCount(xy)
ret.append(getMax(c))
m = max(ret)
print(N-m)

Submission status: Wrong Answer

Solution code:
from collections import Counter
N = int(input())
xy = sorted([list(map(int, input().split())) for _ in range(N)])
def getCount(xy):
    diff = []
    for i in range(1, len(xy)):
        x = xy[i][0]-xy[i-1][0]
        y = xy[i][1]-xy[i-1][1]
        diff.append((x,y))
    return Counter(diff)

def getMax(c):
    xm = 0
    for i in c:
        xm = max(xm, c[i])
    return xm

def get_cnt(xy):
    diff = set()
    for i in range(1, len(xy)):
        x = xy[i][0]-xy[i-1][0]
        y = xy[i][1]-xy[i-1][1]
        diff.add((x,y))
    return len(diff)

ret = []
ret.append(get_cnt(xy))
xy.sort(key=lambda x:x[1])
ret.append(get_cnt(xy))
xy.sort(key=lambda x:x[0], reverse=True)
ret.append(get_cnt(xy))
xy.sort(key=lambda x:x[1], reverse=True)
ret.append(get_cnt(xy))
m = min(ret)
print(m)

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]*10**9 + x[1])

xset = set()
yset = set()

for i in range(N-1):
    xset.add(xy[i+1][0]-xy[i][0])
    yset.add(xy[i+1][0]-xy[i][0])

print(max(len(xset), len(yset)))

Submission status: Wrong Answer

Solution code:
import sys
from collections import Counter

readline = sys.stdin.readline
n = int(readline())
xy = [list(map(int, readline().split())) for _ in range(n)]

d = []
for i in range(n-1):
    for j in range(i+1, n):
        d.append((abs(xy[i][0] - xy[j][0]), abs(xy[i][1] - xy[j][1])))

if n > 1:
    ans = n - max(Counter(d).values())
else:
    ans = 1

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from collections import Counter

readline = sys.stdin.readline
n = int(readline())
xy = [list(map(int, readline().split())) for _ in range(n)]

d = []
for i in range(n-1):
    for j in range(i+1, n):
        d.append((abs(xy[i][0] - xy[j][0]), abs(xy[i][1] - xy[j][1])))
max_cnt = 0
max_pq = []
for pq, cnt in Counter(d).items():
    if max_cnt < cnt:
        max_cnt = cnt
        max_pq = [pq]
    elif max_cnt == cnt:
        max_pq.append(pq)
ans = n
for p, q in max_pq:
    cost = n
    for i in range(n-1):
        for j in range(i+1, n):
            if abs(xy[i][0] - xy[j][0]) == p and abs(xy[i][1] - xy[j][1]) == q:
                cost -= 1
    if ans > cost:
        ans = cost

print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    balls = int(input())
    coordinates = []
    answer = 1
    count_delta = {}
    for _ in range(balls):
        coordinates.append(tuple(map(int, input().split())))
    if balls > 1:
        for i in range(balls):
            for j in range(i + 1, balls):
                d = (coordinates[j][0] - coordinates[i][0], coordinates[j][1] - coordinates[i][1])
                if d in count_delta:
                    count_delta[d] += 1
                else:
                    count_delta[d] = 1
        answer = balls - max(count_delta.values())
    print(answer)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    balls = int(input())
    coordinates = []
    answer = float("inf")
    dxy = []
    for _ in range(balls):
        coordinates.append(tuple(map(int, input().split())))
    if balls > 1:
        for i in range(2):
            coordinates.sort(key=lambda x: x[i % 2])
            count_delta = {}
            for j in range(1, balls):
                delta = (coordinates[j][0] - coordinates[j - 1][0], coordinates[j][1] - coordinates[j - 1][1])
                if delta in count_delta:
                    count_delta[delta] += 1
                else:
                    count_delta[delta] = 1
            count_delta = sorted(count_delta.items(), key=lambda x: x[1])
            dxy.append(count_delta[-1][1])
        for i in range(2):
            answer = min(answer, balls - dxy[i])
    print(answer)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    balls = int(input())
    coordinates = []
    answer = float("inf")
    dxy = []
    for _ in range(balls):
        coordinates.append(tuple(map(int, input().split())))
    coordinates.sort(key=lambda x: x[0])
    if balls > 1:
        for i in range(2):
            coordinates.sort(key=lambda x: x[i % 2])
            count_delta = {}
            for j in range(1, balls):
                delta = (coordinates[j][0] - coordinates[j - 1][0], coordinates[j][1] - coordinates[j - 1][1])
                if delta in count_delta:
                    count_delta[delta] += 1
                else:
                    count_delta[delta] = 1
            count_delta = sorted(count_delta.items(), key=lambda x: x[1])
            dxy.append(list(count_delta[-1][0]))
        for i in range(2):
            dx, dy = dxy[i]
            result = 1
            for j in range(1, balls):
                if coordinates[j - 1][0] + dx != coordinates[j][0] or coordinates[j - 1][1] + dy != coordinates[j][1]:
                    result += 1
            answer = min(answer, result)
    print(answer)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    balls = int(input())
    coordinates = []
    count_delta = {}
    answer = 1
    for _ in range(balls):
        coordinates.append(tuple(map(int, input().split())))
    coordinates.sort(key=lambda x: x[0])
    if balls > 1:
        for i in range(1, balls):
            delta = (coordinates[i][0] - coordinates[i - 1][0], coordinates[i][1] - coordinates[i - 1][1])
            if delta in count_delta:
                count_delta[delta] += 1
            else:
                count_delta[delta] = 1
        count_delta = sorted(count_delta.items(), key=lambda x: x[1])
        dx, dy = count_delta[-1][0]
        for i in range(1, balls):
            if coordinates[i - 1][0] + dx != coordinates[i][0] or coordinates[i - 1][1] + dy != coordinates[i][1]:
                answer += 1
    print(answer)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

li = {}
for i in range(N):
    for j in range(N):
        if i!=j:
            continue

        x1,y1 = XY[i][0],XY[i][1]
        x2,y2 = XY[j][0],XY[j][1]

        mm1 = x2-x1
        mm2 = y2-y1
        if mm1<0 and mm2<0:
            mm1 *= -1
            mm2 *= -1
        PQ = (mm1, mm2)

        if PQ in li:
            li[PQ] += 1
        else:
            li[PQ] = 1

mm = 0
for i in li:
    mm = max(mm,li[i])
print(N-mm)

Submission status: Wrong Answer

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

li = {}
for i in range(N-1):
    for j in range(i+1,N):
        x1,y1 = XY[i][0],XY[i][1]
        x2,y2 = XY[j][0],XY[j][1]

        mm1 = x2-x1
        mm2 = y2-y1
        if mm1<0 and mm2<0:
            mm1 *= -1
            mm2 *= -1
        PQ = (mm1, mm2)

        if PQ in li:
            li[PQ] += 1
        else:
            li[PQ] = 1

mm = 0
for i in li:
    mm = max(mm,li[i])
print(N-mm)

Submission status: Wrong Answer

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

li = {}
for i in range(N-1):
    for j in range(i+1,N):
        x1,y1 = XY[i][0],XY[i][1]
        x2,y2 = XY[j][0],XY[j][1]

        mm1 = x2-x1
        mm2 = y2-y1
        if mm1<0:
            mm1 *= -1
            mm2 *= -1
        PQ = (mm1, mm2)

        if PQ in li:
            li[PQ] += 1
        else:
            li[PQ] = 1

mm = 0
for i in li:
    mm = max(mm,li[i])
print(N-mm)