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:
n=int(input())
l=[]
if n==1:
  print(1)
else:
  for i in range(n):
    x,y=map(int,input().split())
    l.append([x,y])

  dic={}
  for i in range(n):
    for j in range(i+1,n):
      dx,dy = l[j][0]-l[i][0],l[j][1]-l[i][1]
      if (dx,dy) not in dic:
        dic[dx,dy]=1
      else:
        dic[dx,dy]+=1

  dic=sorted(dic.items(),key=lambda x:x[1],reverse=True)
  print(n-dic[0][1])

Submission status: Wrong Answer

Solution code:
import sys, math, re
from itertools import accumulate
sys.setrecursionlimit(10**9)

def input():
    return sys.stdin.readline()[:-1]

def mi():
    return map(int, input().split())

def ii():
    return int(input())

def i2(n):
    tmp = [list(mi()) for i in range(n)]
    return [list(i) for i in zip(*tmp)]

def main():
    N = ii()
    x, y = i2(N)
    ans = -1

    s = set()
    for i in range(N):
        for j in range(N):
            if i != j:
                s.add((x[i]-x[j], y[i]-y[j]))

    for p, q in s:
        cnt = 0
        for i in range(N):
            for j in range(N):
                if i == j:
                    continue
                if x[i]-x[j] == p and y[i]-y[j] == q:
                    cnt += 1
        ans = max(ans, cnt)

    print(N-ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import itertools
n = int(input())
xy = []

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


a,b = [],[]
for v in itertools.combinations(xy,2):
  x = abs(v[1][0]-v[0][0])
  y = abs(v[1][1]-v[0][1])
  a.append([x,y])
  if [x,y] in b:
    continue
  b.append([x,y])

c = 0
for i in b:
  c = max(c,a.count(i))
print (n-c)

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

a = []
b = []
for i in range(n-1):
  x1,y1 = xy1[i][0],xy1[i][1]
  x2,y2 = xy1[i+1][0],xy1[i+1][1]
  x,y = x2-x1,y2-y1
  a.append([x,y])
  if [x,y] in b:
    continue
  b.append([x,y])
c = 0
for i in b:
  c = max(c,a.count(i))

xy2 = sorted(xy,key=lambda x:x[1],reverse=True)
xy1 = sorted(xy2,key=lambda x:x[0])
a,b=[],[]
for i in range(n-1):
  x1,y1 = xy1[i][0],xy1[i][1]
  x2,y2 = xy1[i+1][0],xy1[i+1][1]
  x,y = x2-x1,y2-y1
  a.append([x,y])
  if [x,y] in b:
    continue
  b.append([x,y])
d = 0
for i in b:
  d = max(d,a.count(i))
print (n-max(c,d))

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

a = []
b = []
for i in range(n-1):
  x1,y1 = xy1[i][0],xy1[i][1]
  x2,y2 = xy1[i+1][0],xy1[i+1][1]
  x,y = x2-x1,y2-y1
  a.append([x,y])
  if [x,y] in b:
    continue
  b.append([x,y])
c = 0
for i in b:
  c = max(c,a.count(i))
print (n-c)

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

a = []
for i in range(n-1):
  x1,y1 = xy1[i][0],xy1[i][1]
  x2,y2 = xy1[i+1][0],xy1[i+1][1]
  x,y = x2-x1,y2-y1
  if [x,y] in a:
    continue
  a.append([x,y])
xy2 = sorted(xy1,key=lambda x:x[1])
b = []
for i in range(n-1):
  x1,y1 = xy2[i][0],xy2[i][1]
  x2,y2 = xy2[i+1][0],xy2[i+1][1]
  x,y = x2-x1,y2-y1
  if [x,y] in b:
    continue
  b.append([x,y])
print (min(len(a),len(b)))

Submission status: Wrong Answer

Solution code:
n = int(input())
ls = [list(map(int,input().split())) for _ in range(n)]
di = []
ans = n - 1 
for i in ls:
    for j in ls:
        if i != j:
            a = i[0]-j[0]
            b = i[1]-j[1]
            if (a,b) not in di and (-a,-b) not in di:
                di.append((a,b))
for k in di:
    fi = ls[:]
    cnt = 0
    num = len(fi)
    while num > 0:
        nw = fi[0]
        fi = [p for p in fi if k[0]*(p[1]-nw[1]) != k[1]*(p[0]-nw[0])]
        num = len(fi)
        cnt += 1
    if cnt < ans:
        ans = cnt
print(max(ans,1))

Submission status: Wrong Answer

Solution code:
n = int(input())
ls = [list(map(int,input().split())) for _ in range(n)]
di = []
ans = n
for i in ls:
    for j in ls:
        if i != j:
            a = i[0]-j[0]
            b = i[1]-j[1]
            if (a,b) not in di and (-a,-b) not in di:
                di.append((a,b))
for k in di:
    fi = ls[:]
    cnt = 0
    num = len(fi)
    while num > 0:
        nw = fi[0]
        fi = [p for p in fi if k[0]*(p[1]-nw[1]) != k[1]*(p[0]-nw[0])]
        num = len(fi)
        cnt += 1
    if cnt < ans:
        ans = cnt
print(max(ans,1))

Submission status: Wrong Answer

Solution code:
n = int(input())
ls = [list(map(int,input().split())) for _ in range(n)]
di = []
ans = n
for i in ls:
    for j in ls:
        if i != j:
            a = i[0]-j[0]
            b = i[1]-j[1]
            if (a,b) not in di and (-a,-b) not in di:
                di.append((a,b))
for k in di:
    fi = ls[:]
    cnt = 0
    num = len(fi)
    while num > 0:
        nw = fi[0]
        fi = [p for p in fi if k[0]*(p[1]-nw[1]) != k[1]*(p[0]-nw[0])]
        num = len(fi)
        cnt += 1
    if cnt < ans:
        ans = cnt
print(ans)

Submission status: Wrong Answer

Solution code:
#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from math import gcd
from itertools import combinations,permutations,accumulate, product # (string,3) 3回
#from collections import deque
from collections import deque,defaultdict,Counter
import decimal
import re
import math
import bisect
import heapq
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#
# my_round_int = lambda x:np.round((x*2 + 1)//2)
# 四捨五入g
#
# インデックス系
# int min_y = max(0, i - 2), max_y = min(h - 1, i + 2);
# int min_x = max(0, j - 2), max_x = min(w - 1, j + 2);
#
#
import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7
#mod = 9982443453
#mod = 998244353
INF = float('inf')
from sys import stdin
readline = stdin.readline
def readInts():
  return list(map(int,readline().split()))
def readTuples():
    return tuple(map(int,readline().split()))
def I():
    return int(readline())
n = I()
if n == 2:
  print('NO')
  exit()
A = [tuple(readInts()) for i in range(n)]
PQ = []
for i in range(n):
    for j in range(n):
        if i == j:
            continue
        x0,y0 = A[i]
        x1,y1 = A[j]
        PQ.append((x1-x0, y1-y0))
pos = set(A)
ans = n
for p,q in PQ:
    nya = 0
    for x,y in A:
        if (x+p,y+q) not in pos:
            nya += 1
    ans = min(ans, nya)
print(ans)

Submission status: Wrong Answer

Solution code:
#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from math import gcd
from itertools import combinations,permutations,accumulate, product # (string,3) 3回
#from collections import deque
from collections import deque,defaultdict,Counter
import decimal
import re
import math
import bisect
import heapq
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#
# my_round_int = lambda x:np.round((x*2 + 1)//2)
# 四捨五入g
#
# インデックス系
# int min_y = max(0, i - 2), max_y = min(h - 1, i + 2);
# int min_x = max(0, j - 2), max_x = min(w - 1, j + 2);
#
#
import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7
#mod = 9982443453
#mod = 998244353
INF = float('inf')
from sys import stdin
readline = stdin.readline
def readInts():
  return list(map(int,readline().split()))
def readTuples():
    return tuple(map(int,readline().split()))
def I():
    return int(readline())
n = I()
dic = defaultdict(int)
A = [readInts() for _ in range(n)]
for i in range(n-1):
    for j in range(i+1,n):
        div = tuple([A[i][0]-A[j][0], A[i][1]-A[j][1]])
        dic[div] += 1
a = INF
for k,v in dic.items():
    nya = 1
    ak,bk = k
    for i in range(1,n):
        sak,sbk = A[i-1]
        eak,ebk = A[i]
        if sak - eak == ak and sbk - ebk == bk:
            pass
        else:
            nya += 1
    a = min(a,nya)
print(a)

Submission status: Wrong Answer

Solution code:
#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from math import gcd
from itertools import combinations,permutations,accumulate, product # (string,3) 3回
#from collections import deque
from collections import deque,defaultdict,Counter
import decimal
import re
import math
import bisect
import heapq
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#
# my_round_int = lambda x:np.round((x*2 + 1)//2)
# 四捨五入g
#
# インデックス系
# int min_y = max(0, i - 2), max_y = min(h - 1, i + 2);
# int min_x = max(0, j - 2), max_x = min(w - 1, j + 2);
#
#
import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7
#mod = 9982443453
#mod = 998244353
INF = float('inf')
from sys import stdin
readline = stdin.readline
def readInts():
  return list(map(int,readline().split()))
def readTuples():
    return tuple(map(int,readline().split()))
def I():
    return int(readline())
n = I()
dic = defaultdict(int)
A = [readInts() for _ in range(n)]
for i in range(n-1):
    for j in range(i+1,n):
        div = tuple([A[i][0]-A[j][0], A[i][1]-A[j][1]])
        dic[div] += 1
a = 1
for k,v in dic.items():
    a = max(a,v)
print(n-a)

Submission status: Wrong Answer

Solution code:
def main():
  n = int(input())
  ball = [tuple(map(int, input().split())) for i in range(n)]
  
  already = [False]*n
  
  ball.sort()
  ans = 0
  for i in range(n):
    if already[i]:
      continue
    already[i] = True
    ans += 1
    now = []
    for j in range(i+1, n):
      if already[j]:
        continue
      sub = [j]
      p, q = ball[j][0] - ball[i][0], ball[j][1] - ball[i][1]
      x, y = ball[j][0], ball[j][1]
      for k in range(j+1, n):
        if already[k]:
          continue
        if ball[k] == (x + p, y + q):
          sub.append(k)
          x, y = ball[k]
      if len(now) < len(sub):
        now = sub[:]
    for index in now:
      already[index] = True
    
  print(ans)

  
main()

Submission status: Wrong Answer

Solution code:
import sys
#import numpy as np
import math
#from fractions import Fraction
import itertools
from collections import deque
from collections import Counter
import heapq
from fractions  import gcd
#input=sys.stdin.readline
#import bisect
class UnionFind(): #集合の取り扱い、辺に重み、階層を意識するときは使えない
    def __init__(self,n):
        self.n=n
        self.par = [-1]*n
    def find(self,x):
        if self.par[x] <0: #負なら親、要素数
            return x
        else: #正なら親の番号
            self.par[x]=self.find(self.par[x]) #一回調べたら根を繋ぎ変える、経路圧縮
            return self.par[x]
    def union(self,x,y):
        x=self.find(x) #x,yの親
        y=self.find(y)

        if x==y: #親が同じなら何もしない
            return 
        if self.par[x]>self.par[y]: #要素数が大きい方をxにする
            x,y=y,x
        self.par[x]+=self.par[y] #xがある集合にyが入った集合をくっつける
        self.par[y]=x

    def size(self,x):
        return -self.par[self.find(x)] #親のサイズ
    
    def same(self,x,y): #親が同じ、すなわち同じ集合か
        return self.find(x)==self.find(y)

    def member(self,x): #同じ木（集合）にある要素全部リストで返す
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i)==root ]
    
    def roots(self): #集合の根になってる要素をリストで返す
        return [i for i , x in enumerate(self.par) if x<0]
    
    def group_count(self): #集合の数、木の数
        return len(self.roots())

    def all_member(self): #辞書型で返す
        return {r: self.member(r) for r in self.roots()}
    def __str__(self):
        return "\n".join('{}:{}'.format(r,self.member(r)) for r in self.roots)

n=int(input())
xy=[list(map(int,input().split()))  for _ in range(n)]
xy=sorted(xy,key=lambda x: x[0])

ans=2*n
for i in range(1,n):
    x,y=xy[i]
    p=x-xy[0][0]
    q=y-xy[0][1]
    tree=UnionFind(n)
    res={}
    cnt=1
    res[(xy[0][0],xy[0][1])]=1
    for j in range(1,n):
        s,t=xy[j]
        if (s-p,t-q) not in res and (s+p,t+q) not in res:
           cnt+=1
        res[(s,t)]=1
    c=cnt
    ans=min(ans,c)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
#import numpy as np
import math
#from fractions import Fraction
import itertools
from collections import deque
from collections import Counter
import heapq
from fractions  import gcd
#input=sys.stdin.readline
#import bisect
class UnionFind(): #集合の取り扱い、辺に重み、階層を意識するときは使えない
    def __init__(self,n):
        self.n=n
        self.par = [-1]*n
    def find(self,x):
        if self.par[x] <0: #負なら親、要素数
            return x
        else: #正なら親の番号
            self.par[x]=self.find(self.par[x]) #一回調べたら根を繋ぎ変える、経路圧縮
            return self.par[x]
    def union(self,x,y):
        x=self.find(x) #x,yの親
        y=self.find(y)

        if x==y: #親が同じなら何もしない
            return 
        if self.par[x]>self.par[y]: #要素数が大きい方をxにする
            x,y=y,x
        self.par[x]+=self.par[y] #xがある集合にyが入った集合をくっつける
        self.par[y]=x

    def size(self,x):
        return -self.par[self.find(x)] #親のサイズ
    
    def same(self,x,y): #親が同じ、すなわち同じ集合か
        return self.find(x)==self.find(y)

    def member(self,x): #同じ木（集合）にある要素全部リストで返す
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i)==root ]
    
    def roots(self): #集合の根になってる要素をリストで返す
        return [i for i , x in enumerate(self.par) if x<0]
    
    def group_count(self): #集合の数、木の数
        return len(self.roots())

    def all_member(self): #辞書型で返す
        return {r: self.member(r) for r in self.roots()}
    def __str__(self):
        return "\n".join('{}:{}'.format(r,self.member(r)) for r in self.roots)

n=int(input())
xy=[list(map(int,input().split()))  for _ in range(n)]
xy=sorted(xy,key=lambda x: x[0])

ans=2*n
for i in range(1,n):
    x,y=xy[i]
    p=x-xy[0][0]
    q=y-xy[0][1]
    res={}
    cnt=1
    res[(xy[0][0],xy[0][1])]=1
    for j in range(1,n):
        s,t=xy[j]
        if (s-p,t-q) not in res:
           cnt+=1
        res[(s,t)]=1
    c=cnt
    ans=min(ans,c)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
#import numpy as np
import math
#from fractions import Fraction
import itertools
from collections import deque
from collections import Counter
import heapq
from fractions  import gcd
#input=sys.stdin.readline
#import bisect
class UnionFind(): #集合の取り扱い、辺に重み、階層を意識するときは使えない
    def __init__(self,n):
        self.n=n
        self.par = [-1]*n
    def find(self,x):
        if self.par[x] <0: #負なら親、要素数
            return x
        else: #正なら親の番号
            self.par[x]=self.find(self.par[x]) #一回調べたら根を繋ぎ変える、経路圧縮
            return self.par[x]
    def union(self,x,y):
        x=self.find(x) #x,yの親
        y=self.find(y)

        if x==y: #親が同じなら何もしない
            return 
        if self.par[x]>self.par[y]: #要素数が大きい方をxにする
            x,y=y,x
        self.par[x]+=self.par[y] #xがある集合にyが入った集合をくっつける
        self.par[y]=x

    def size(self,x):
        return -self.par[self.find(x)] #親のサイズ
    
    def same(self,x,y): #親が同じ、すなわち同じ集合か
        return self.find(x)==self.find(y)

    def member(self,x): #同じ木（集合）にある要素全部リストで返す
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i)==root ]
    
    def roots(self): #集合の根になってる要素をリストで返す
        return [i for i , x in enumerate(self.par) if x<0]
    
    def group_count(self): #集合の数、木の数
        return len(self.roots())

    def all_member(self): #辞書型で返す
        return {r: self.member(r) for r in self.roots()}
    def __str__(self):
        return "\n".join('{}:{}'.format(r,self.member(r)) for r in self.roots)

n=int(input())
xy=[list(map(int,input().split()))  for _ in range(n)]
xy=sorted(xy,key=lambda x: x[0])

ans=2*n
for i in range(1,n):
    x,y=xy[i]
    p=x-xy[0][0]
    q=y-xy[0][1]
    tree=UnionFind(n)
    res={}
    res[(xy[0][0],xy[0][1])]=1
    for j in range(1,n):
        s,t=xy[j]
        
        for k in tree.all_member():
            if (s-p,t-q) in res:
                tree.union(k,j)
                break
        res[(s,t)]=1
    c=tree.group_count()
    ans=min(ans,c)
print(ans)

Submission status: Wrong Answer

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

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

dis = {}

for i in range(N):
    for j in range(N):
        if i == j:
            continue
        X = XY[j][0]-XY[i][0]
        Y = XY[j][1]-XY[i][1]
        if (X,Y) in dis:
            dis[(X,Y)] += 1
        else:
            dis[(X,Y)] = 1
print(N-max(dis.values()))

Submission status: Wrong Answer

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

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

dis = {}

for i in range(N-1):
    for j in range(i+1,N):
        X = XY[j][0]-XY[i][0]
        Y = XY[j][1]-XY[i][1]
        if (X,Y) in dis:
            dis[(X,Y)] += 1
        else:
            dis[(X,Y)] = 1
print(N-max(dis.values()))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from typing import Counter

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

ans = 0

for i in range(N):
    for j in range(i+1, N):
        a = XY[i][0]-XY[j][0]
        b = XY[i][1]-XY[j][1]
        cnt[a][b] += 1
        ans = max(cnt[a][b], ans)

print(N-ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from typing import Counter

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

ans = 0

for i in range(N):
    for j in range(i+1, N):
        a = abs(XY[i][0]-XY[j][0])
        b = abs(XY[i][1]-XY[j][1])
        cnt[a][b] += 1
        ans = max(cnt[a][b], ans)

print(N-ans)

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])
l.sort()

ans = 0
while len(l) > 0:
  tmp = []
  for i in range(len(l)-1):
    for j in range(i+1, len(l)):
      a, b = l[i][0]-l[j][0], l[i][1]-l[j][1]
      t = [i, j]
      for k in range(j+1, len(l)):
        for m in range(len(t)):
          if (l[m][0]-l[k][0]==a) and (l[m][1]-l[k][1]==b):
            t.append(k)
            break
          elif (l[k][0]-l[m][0]==a) and (l[k][1]-l[m][1]==b):
            t.append(k)
            break
      if len(tmp) < len(t):
        tmp = t
  ans += 1
  tmp.sort(reverse=True)
  for i in range(len(tmp)):
    l.pop(tmp[i])
  if len(l) == 1:
    ans += 1
    break
print(ans)

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])
l.sort()

ans = 0
while len(l) > 0:
  tmp = []
  for i in range(len(l)-1):
    for j in range(i+1, len(l)):
      a, b = l[i][0]-l[j][0], l[i][1]-l[j][1]
      t = [i, j]
      for k in range(j+1, len(l)):
        for m in range(len(t)):
          if (l[m][0]-l[k][0]==a) and (l[m][1]-l[k][1]==b):
            t.append(k)
            break
          elif (l[k][0]-l[m][0]==a) and (l[k][1]-l[m][1]==b):
            t.append(k)
            break
      if len(tmp) < len(t):
        tmp = t
  ans += 1
  n = 0
  for i in range(len(tmp)):
    l.pop(tmp[i]-n)
    n += 1
  if len(l) == 1:
    ans += 1
    break
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def MS(): return input().split()
def LS(): return list(input())
def LLS(rows_number): return [LS() for _ in range(rows_number)]
def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')
# from math import ceil, floor, log2
from collections import deque, defaultdict
# from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
# from heapq import heapify, heappop, heappush
# import numpy as np    # cumsum
# from bisect import bisect_left, bisect_right

def solve():
    N = II()
    X = [0] * N
    Y = [0] * N
    for i in range(N):
        x, y = MI()
        X[i], Y[i] = x, y

    dct = defaultdict(int)
    for i in range(N):
        for j in range(N):
            if i == j: continue
            xi, yi = X[i], Y[i]
            xj, yj = X[j], Y[j]

            dct[(xi-xj, yi-yj)] += 1
    # print(dct)
    # print(N - max(dct.values()))


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
N = int(input())

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

from collections import defaultdict

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

cnt = defaultdict(int)
for pi in range(N):
    for pj in range(pi+1, N):
        if pi == pj:
            continue
        # x
        dx = P[pi][0] - P[pj][0]

        # y
        dy = P[pi][1] - P[pj][1]

        cnt[(dx, dy)] += 1

ans = N-max(cnt.values())
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())

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

from collections import defaultdict

if N == 1:
    print(1)
    exit(0)
    
cnt = defaultdict(int)
for pi in range(N):
    for pj in range(pi+1, N):
        if pi == pj:
            continue
        # x
        dx = abs(P[pi][0] - P[pj][0])

        # y
        dy = abs(P[pi][1] - P[pj][1])

        cnt[(dx, dy)] += 1

ans = N-max(cnt.values())
print(ans)

Submission status: Wrong Answer

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

c=[set() for i in range(n)]
for i in range(n):
  for j in range(i+1,n):
    c[i].add((p[i][0]-p[j][0],p[i][1]-p[j][1]))
mn=100
for i in range(n):
  for j in range(i+1,n):
    cnt=0
    pq=(p[i][0]-p[j][0],p[i][1]-p[j][1])
    for k in range(n):
      if not(pq in c[k]):
        cnt+=1
    mn=min(mn,cnt)
print(mn)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

class UnionFind():
    def __init__(self, n=0):
        self.d = [-1]*n
    
    def find(self, x):
        if self.d[x] < 0: return x
        self.d[x] = self.find(self.d[x])
        return self.d[x]

    def unite(self, x, y):
        x,y=self.find(x),self.find(y)
        if x==y:return False
        if self.d[x] > self.d[y]: x,y=y,x
        self.d[x] += self.d[y]
        self.d[y] = x
        return True

    def same(self, x,y): return self.find(x)==self.find(y)
    def size(self,x): return -self.d[self.find(x)]

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

if N in (1,2):
  print(1)
  exit()

def gcd(a,b):
  if b==0:return a
  return gcd(b,a%b)

count=defaultdict(list)
for i in range(N-1):
  x1,y1 = xy[i]
  for j in range(i+1,N):
    x2,y2=xy[j]
    (x1,y1),(x2,y2)=sorted(((x1,y1),(x2,y2)))
    dx,dy = x2-x1,y2-y1
    #dx,dy = dx//gcd(dx,dy),dy//gcd(dx,dy)
    count[(dx,dy)].append((i,j))

MAX=0
argmax=-1
for k in count.keys():
  uf = UnionFind(N)
  for v1,v2 in count[k]:
    uf.unite(v1,v2)
  res=0
  for i in range(N):
    if uf.d[i]<-1:
      res += 1
  if MAX<res:
    MAX=res
    argmax = k

member=set()
for v1,v2 in count[argmax]:
  member.add(v1)
  member.add(v2)
print(MAX+N-len(member))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

class UnionFind():
    def __init__(self, n=0):
        self.d = [-1]*n
    
    def find(self, x):
        if self.d[x] < 0: return x
        self.d[x] = self.find(self.d[x])
        return self.d[x]

    def unite(self, x, y):
        x,y=self.find(x),self.find(y)
        if x==y:return False
        if self.d[x] > self.d[y]: x,y=y,x
        self.d[x] += self.d[y]
        self.d[y] = x
        return True

    def same(self, x,y): return self.find(x)==self.find(y)
    def size(self,x): return -self.d[self.find(x)]

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

if N in (1,2):
  print(1)
  exit()

def gcd(a,b):
  if b==0:return a
  return gcd(b,a%b)

count=defaultdict(list)
for i in range(N-1):
  x1,y1 = xy[i]
  for j in range(i+1,N):
    x2,y2=xy[j]
    (x1,y1),(x2,y2)=sorted(((x1,y1),(x2,y2)))
    dx,dy = x2-x1,y2-y1
    dx,dy = dx//gcd(dx,dy),dy//gcd(dx,dy)
    count[(dx,dy)].append((i,j))

MAX=0
argmax=-1
for k in count.keys():
  uf = UnionFind(N)
  for v1,v2 in count[k]:
    uf.unite(v1,v2)
  res=0
  for i in range(N):
    if uf.d[i]<-1:
      res += 1
  if MAX<res:
    MAX=res
    argmax = k

member=set()
for v1,v2 in count[argmax]:
  member.add(v1)
  member.add(v2)
print(MAX+N-len(member))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

class UnionFind():
    def __init__(self, n=0):
        self.d = [-1]*n
    
    def find(self, x):
        if self.d[x] < 0: return x
        self.d[x] = self.find(self.d[x])
        return self.d[x]

    def unite(self, x, y):
        x,y=self.find(x),self.find(y)
        if x==y:return False
        if self.d[x] > self.d[y]: x,y=y,x
        self.d[x] += self.d[y]
        self.d[y] = x
        return True

    def same(self, x,y): return self.find(x)==self.find(y)
    def size(self,x): return -self.d[self.find(x)]

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

def gcd(a,b):
  if b==0:return a
  return gcd(b,a%b)

count=defaultdict(list)
for i in range(N-1):
  x1,y1 = xy[i]
  for j in range(i+1,N):
    x2,y2=xy[j]
    (x1,y1),(x2,y2)=sorted(((x1,y1),(x2,y2)))
    dx,dy = x2-x1,y2-y1
    dx,dy = dx//gcd(dx,dy),dy//gcd(dx,dy)
    count[(dx,dy)].append((i,j))

MAX=0
for k in count.keys():
  uf = UnionFind(N)
  for v1,v2 in count[k]:
    uf.unite(v1,v2)
  MAX = max(MAX,-min(uf.d))
  
print(max(1,N-MAX))

Submission status: Wrong Answer

Solution code:
import sys
import itertools

input = sys.stdin.readline


def main():
    N = int(input())
    balls = [tuple(map(int, input().split())) for _ in range(N)]
    comb = list(itertools.combinations(balls, 2))
    ans = 1
    for c in comb:
        a, b = c
        p = b[0] - a[0]
        q = b[1] - a[1]
        ans_i = 0
        for d in balls:
            e = (d[0] + p, d[1] + q)
            if e in balls:
                ans_i += 1
        ans = max(ans, ans_i)
    print(N - ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

ans=100

def my_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return -1

for i in range(n):
    for j in range(i+1,n):
        x1,y1=pts[i]
        x2,y2=pts[j]

        p=x1-x2
        q=y1-y2

        visit=[0]*n
        
        cur=0
        for k in range(n):
            if visit[k]==1:
                continue
            cur+=1
            x3,y3=pts[k]
            cx=x3
            cy=y3
            while my_index(pts,[cx,cy])>=0:
                visit[my_index(pts,[cx,cy])]=1
                cx+=p
                cy+=q
            cx=x3
            cy=y3
            while my_index(pts,[cx,cy])>=0:
                visit[my_index(pts,[cx,cy])]=1
                cx-=p
                cy-=q
        
        ans=min(ans,cur)
    
print(ans)

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])
l.sort()


def main(l):
  li = []
  for i in range(len(l)-1):
    for j in range(i+1, len(l)):
      tmp = [l[i], l[j]]
      s = [l[j][0]-l[i][0], l[j][1]-l[j][0]]
      for k in range(j+1, len(l)):
        if (l[k][0]-tmp[-1][0]==s[0]) and (l[k][1]-tmp[-1][1]==s[1]):
          tmp.append(l[k])
      if len(li) < len(tmp):
        li = tmp
  return li

ans = 0
if len(l) == 1:
  ans = 1
else:
  while len(l) > 0:
    result = main(l)
    ans += 1
    for n in result:
      l.remove(n)
    if len(l) == 1:
      l = []
      ans += 1
print(ans)

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])
l.sort()


def main(l):
  li = []
  for i in range(len(l)-1):
    for j in range(i+1, len(l)):
      tmp = [l[i], l[j]]
      s = [l[j][0]-l[i][0], l[j][1]-l[j][0]]
      for k in range(j+1, len(l)):
        if (l[k][0]-tmp[-1][0]==s[0]) and (l[k][1]-tmp[-1][1]==s[1]):
          tmp.append(l[k])
      if len(li) < len(tmp):
        li = tmp
  return li

ans = 0
while len(l) > 0:
  result = main(l)
  ans += 1
  for n in result:
    l.remove(n)
  if len(l) == 1:
    l = []
print(ans)

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])
l.sort()


def main(l):
  li = []
  for i in range(len(l)-1):
    for j in range(i+1, len(l)):
      tmp = [l[i], l[j]]
      s = [l[j][0]-l[i][0], l[j][1]-l[j][0]]
      for k in range(j+1, len(l)):
        if (l[k][0]-tmp[-1][0]==s[0]) and (l[k][1]-tmp[-1][1]==s[1]):
          tmp.append(l[k])
      if len(li) < len(tmp):
        li = tmp
  return li

ans = 0
while len(l) > 0:
  result = main(l)
  ans += 1
  for n in result:
    l.remove(n)
  if len(l) == 1:
    l = []
    ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from collections import defaultdict


def read():
    N = int(input().strip())
    XY = []
    for i in range(N):
        x, y = map(int, input().strip().split())
        XY.append((x, y))
    return N, XY


def solve(N, XY):
    if N == 1:
        return 1

    min_cost = 1000000
    for j in range(N):
        for i in range(j):
            rdict = defaultdict(list)
            x0, y0 = XY[i]
            x1, y1 = XY[j]
            p, q = abs(x1-x0), abs(y1-y0)
            for k in range(N):
                x, y = XY[k]
                rdict[q * x - p * y].append((x, y))
            cost = 0
            for v in rdict.values():
                vs = list(sorted(v))
                x0, y0 = vs[0]
                for x1, y1 in vs:
                    if abs(x1 - x0) != p or abs(y1 - y0) != q:
                        cost += 1
                    x0, y0 = x1, y1
            min_cost = min(min_cost, cost)
    return min_cost


if __name__ == '__main__':
    inputs = read()
    print(solve(*inputs))