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())
balls = []
for i in range(N):
    x, y = map(int, input().split(' '))
    balls.append((x,y))

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

dic = {}
for i in range(N):
    px = balls[i][0]
    py = balls[i][1]
    for j in range(N-(i+1)):
        dx = balls[j][0] - px
        dy = balls[j][1] - py
        px = balls[j][0]
        py = balls[j][1]
        if (0>dx):
            dx *= -1
            dy *= -1
        if (dx,dy) not in dic.keys():
            dic[(dx,dy)] = 1
        else:
            dic[(dx,dy)] += 1

d_max = max(dic.values())
print(N - d_max)

Submission status: Wrong Answer

Solution code:
from itertools import combinations

n = int(input())
xy_array = [[int(x) for x in input().split()] for y in range(n)]
index_array = [x for x in range(n)]
comb_index = combinations(index_array, 2)
a_array = []
for before, after in comb_index:
    before_x, before_y = xy_array[before]
    after_x, after_y = xy_array[after]
    a_array.append([before_x - after_x, before_y - after_y])
    a_array.append([after_x - before_x, after_y - before_y])
res = n - 1
for ax, ay in a_array:
    # if ax == 0 or ay == 0:
    #     continue
    tmp_res = 0
    for i in range(n):
        for j in range(n):
            if i == j:
                continue
            diff_x = xy_array[i][0] - xy_array[j][0]
            diff_y = xy_array[i][1] - xy_array[j][1]
            if diff_x == ax and diff_y == ay:
                pass
            else:
                tmp_res += 1
    res = min(res, tmp_res)
print(n-res if n != 1 else 1)

Submission status: Wrong Answer

Solution code:
N = int(input())

xy = [[0,0] for i in range(N)]

for i in range(N):
    tmp_x, tmp_y = map(int, input().split())
    xy[i][0] = tmp_x
    xy[i][1] = tmp_y

#x座標でソート
xy = sorted(xy, key = lambda x: x[0])



ans = 9999
for i in range(N):
    for j in range(N):
        if i == j:
            continue
        else:
            p = xy[i][0] - xy[j][0]
            q = xy[i][1] - xy[j][1]
        tmp = 0
        for x in range(N):
            for y in range(N):
                if x == y:
                    continue
                else:
                    if  xy[x][0] - xy[y][0] == p and xy[x][1] - xy[y][1] == q:
                        tmp += 1
        ans = min(ans, N - tmp)
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from collections import deque
from string import ascii_uppercase
import sys, bisect, math, heapq

stdin = sys.stdin
read_int = lambda : list(map(int,stdin.readline().split()))
read_str = lambda : stdin.readline().rstrip()

N = read_int()[0]
xy = [read_int() for _ in range(N)]

def solve():
    pq = defaultdict(lambda: int())
    res = []
    M = 0
    for i in range(N):
        for j in range(N):
            if i >= j: continue
            p, q = xy[i][0] - xy[j][0], xy[i][1] - xy[j][1]
            count = 0
            for ii in range(N):
                for jj in range(N):
                    if ii >= jj: continue
                    if xy[ii][0] - xy[jj][0] == p and xy[ii][1] - xy[jj][1] == q:
                        count += 1
            res.append(count)
            M = max(M, count)
    ans = N - M
    return ans

if __name__ == "__main__":
    print(solve())

Submission status: Wrong Answer

Solution code:
from itertools import combinations

n = int(input())
xy_array = sorted([[int(x) for x in input().split()] for y in range(n)], key=lambda x: (x[0], x[1]))
index_array = [x for x in range(n)]
comb_index = combinations(index_array, 2)
a_array = []
for before, after in comb_index:
    before_x, before_y = xy_array[before]
    after_x, after_y = xy_array[after]
    a_array.append([before_x - after_x, before_y - after_y])
    a_array.append([after_x - before_x, after_y - before_y])
res = n
for ax, ay in a_array:
    if ax == 0 or ay == 0:
        continue
    now_x, now_y = xy_array[0]
    tmp_res = 1
    for x, y in xy_array[1:]:
        if x - ax == now_x and y - ay == now_y:
            pass
        else:
            tmp_res += 1
        now_x = x
        now_y = y
    res = min(res, tmp_res)
print(res)

Submission status: Wrong Answer

Solution code:
from collections import Counter
N = int(input())
xy = [tuple(map(int,input().split())) for i in range(N)]
ct = Counter()
for i in range(N):
  for j in range(i+1,N):
    dx = xy[i][0]-xy[j][0]
    dy = xy[i][1]-xy[j][1]
    ct[(dx,dy)] += 1
print(N-max(ct.values() if len(ct)>0 else [0]))

Submission status: Wrong Answer

Solution code:
n = int(input())
xy_array = [[int(x) for x in input().split()] for y in range(n)]
xy_array = sorted(xy_array, key=lambda x: (x[0], x[1]))

a_array = []
tmp_x, tmp_y = xy_array[0]
for x, y in xy_array[1:]:
    a_array.append([tmp_x-x, tmp_y-y])
    tmp_x, tmp_y = x, y

res = n
for ax, ay in a_array:
    if ax == 0 or ay == 0:
        continue
    tmp_res = 1
    now_x, now_y = xy_array[-1]
    for x, y in reversed(xy_array[:-1]):
        if now_x+ax == x and now_y+ay == y:
            pass
        else:
            tmp_res += 1
        now_x, now_y = x, y
    res = min(res, tmp_res)

xy_array = sorted(xy_array, key=lambda x: (x[1], x[0]))
a_array = []
tmp_x, tmp_y = xy_array[0]
for x, y in xy_array[1:]:
    a_array.append([tmp_x-x, tmp_y-y])
    tmp_x, tmp_y = x, y

for ax, ay in a_array:
    if ax == 0 or ay == 0:
        continue
    tmp_res = 1
    now_x, now_y = xy_array[-1]
    for x, y in reversed(xy_array[:-1]):
        if now_x+ax == x and now_y+ay == y:
            pass
        else:
            tmp_res += 1
        now_x, now_y = x, y
    res = min(res, tmp_res)
print(res)

Submission status: Wrong Answer

Solution code:
import statistics

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

delta = []
for i in range(N):
    for j in range(i+1,N):
        dx = p[j][0]-p[i][0]
        dy = p[j][1]-p[i][1]
        delta.append([dx,dy])
delta.sort()
best = [0,0]
bestc = 0
nowc = 0
for i in range(len(delta)):
    if i == 0:
        best = delta[i]
        bestc = 1
        nowc = 1
    else:
        if delta[i-1][0]==delta[i][0] and delta[i-1][1]==delta[i][1]:
            nowc += 1
            if nowc > bestc:
                best = delta[i]
                bestc = nowc
        else:
            nowc = 1
ans = 1+(N-1-bestc)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
N = int(input())
li = []
if N == 1:
    a = list(map(int,input().split()))
    print(1)
    sys.exit()   
 
for i in range(N):
    a = list(map(int,input().split()))
    li.append(a)
 
cross = []
 
##計算量に余裕があるので全探索します
for i in range(N):
    for j in range (i+1, N):
        a = [li[j][0]-li[i][0],li[j][1]-li[i][1]]
        if a[0] < 0 and a[1] <= 0:
            b = [abs(li[j][0]-li[i][0]),abs(li[j][1]-li[i][1])]
            cross.append(b)
        elif a[0] < 0 and a[1] >= 0:
            c = li[j][1]-li[i][1]
            b = [abs(li[j][0]-li[i][0]),-c]
            cross.append(b) ####
        else:
            cross.append(a) 
lencross = len(cross)
 
res = 0
ans = []
 
for i in range (lencross):
    res = 0
    for j in range (lencross):
        if cross[i] == cross[j]:
            res += 1
    ans.append(res)
reduce = max(ans)
 
print(N - reduce)

Submission status: Wrong Answer

Solution code:
import sys
N = int(input())
li = []
if N == 1:
    a = list(map(int,input().split()))
    print(1)
    sys.exit()   
 
for i in range(N):
    a = list(map(int,input().split()))
    li.append(a)
 
cross = []
 
##計算量に余裕があるので全探索します
for i in range(N):
    for j in range (i+1, N):
        a = [li[j][0]-li[i][0],li[j][1]-li[i][1]]
        if a[0] <= 0 and a[1] <= 0:
            b = [abs(li[j][0]-li[i][0]),abs(li[j][1]-li[i][1])]
            cross.append(b)
        elif a[0] <= 0 and a[1] > 0:
            c = li[j][1]-li[i][1]
            b = [abs(li[j][0]-li[i][0]),-c]
            cross.append(b) ####
        else:
            cross.append(a) 
lencross = len(cross)
 
res = 0
ans = []
 
for i in range (lencross):
    res = 0
    for j in range (lencross):
        if cross[i] == cross[j]:
            res += 1
    ans.append(res)
reduce = max(ans)
 
print(N - reduce)

Submission status: Wrong Answer

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

else:
    print(1)

Submission status: Wrong Answer

Solution code:
import sys
N = int(input())
li = []
if N == 1:
    a = list(map(int,input().split()))
    print(1)
    sys.exit()   
 
for i in range(N):
    a = list(map(int,input().split()))
    li.append(a)
 
cross = []
 
##計算量に余裕があるので全探索します
for i in range(N):
    for j in range (i+1, N):
        a = [li[j][0]-li[i][0],li[j][1]-li[i][1]]
        if a[0] < 0 and a[1] <= 0:
            b = [abs(li[j][0]-li[i][0]),abs(li[j][1]-li[i][1])]
            cross.append(b)
        elif a[0] < 0 and a[1] > 0:
            c = li[j][1]-li[i][1]
            b = [abs(li[j][0]-li[i][0]),-c]
            cross.append(b) ####
        else:
            cross.append(a) 
lencross = len(cross)
 
res = 0
ans = []
 
for i in range (lencross):
    res = 0
    for j in range (lencross):
        if cross[i] == cross[j]:
            res += 1
    ans.append(res)
reduce = max(ans)
 
print(N - reduce)

Submission status: Wrong Answer

Solution code:
###template###
import sys
def input(): return sys.stdin.readline().rstrip()
def mi(): return map(int, input().split())
###template###

#Union-Find ****0スタートなので注意！****
class UnionFind():
  # 作りたい要素数（ノードの数）nで初期化
  # 使用するインスタンス変数の初期化
  def __init__(self, n):
    self.n = n
    # root[x]<0ならそのノードが根かつその値が木の要素数
    # rootノードでその木の要素数を記録する
    self.root = [-1]*(n) #元々はn+1になっていたが、nに直した
    # 木をくっつける時にアンバランスにならないように調整する
    self.rnk = [0]*(n) #元々はn+1になっていたが、nに直した

  # ノードxのrootノードを見つける
  def Find_Root(self, x):
    if(self.root[x] < 0):
      return x
    else:
      # ついでに経路圧縮（調べた辺を根に直接つなぎ直す）をかけておく
      self.root[x] = self.Find_Root(self.root[x])
      return self.root[x]

  # 木の併合、入力は併合したい集合に属する各ノード
  def Unite(self, x, y):
    # 入力ノードのrootノードを見つける
    x = self.Find_Root(x)
    y = self.Find_Root(y)
    # すでに同じ木に属していた場合、何もしないで返す
    if(x == y):
      return
    # 違う木に属していた場合rnkを見てくっつける方を決める
    elif(self.rnk[x] > self.rnk[y]):
      self.root[x] += self.root[y] #要素数を足す(根のrootは"-要素数")
      self.root[y] = x #ノードyの親をx（新しい集合の根）とする
    else:
      self.root[y] += self.root[x] #要素数を足す
      self.root[x] = y
      # rnkが同じ（深さに差がない場合）は1増やす（根(rnk1)+繋げる集合のrnkということで、1増えることになる）
      if(self.rnk[x] == self.rnk[y]):
          self.rnk[y] += 1

  # xとyが同じグループに属するか判断
  def isSameGroup(self, x, y):
    return self.Find_Root(x) == self.Find_Root(y)

  # ノードxが属する木のサイズを返す（根ノードの.root[idx]を-符号を外して返すだけ
  def Count(self, x):
    return -self.root[self.Find_Root(x)] #-符号を外す

  # 木の数（＝集合の数）を返す（根の数=rootに-符号を持つものの数を返すだけ）
  def Count_Trees(self):
    treecnt = 0
    for eachroot in self.root:
      if eachroot < 0: treecnt += 1
    return treecnt
#------Union-Findおわり-------------#

import collections

N = int(input())
XYs = [tuple(mi()) for _ in range(N)]

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

sa_list = []
cmb_with_same_diff = collections.defaultdict(list)
import itertools
diffidx = 0
for a in range(0, N):
  for b in range(0, N):
    if a>=b: continue
    #ここでa, bは各ボールのidx
    ax, ay = XYs[a]
    bx, by = XYs[b]
    if ax-bx>=0: nowsa = (ax-bx,ay-by)
    elif ax-bx==0: nowsa = (ax-bx,abs(ay-by))
    elif ay-by==0: nowsa = (abs(ax-bx), ay-by)
    else: nowsa = (-(ax-bx),-(ay-by))
    sa_list.append(nowsa)
    cmb_with_same_diff[nowsa].append((a, b))

#print(sa_list)
#print(cmb_with_same_diff)

#最も多い差の個数（これ-1を短縮できるはず）
print(N-collections.Counter(sa_list).most_common()[0][1])

#[((x, y), 回数), ...]　多い順で入っている
#sa_sorted = collections.Counter(sa_list).most_common()

ans = N
for each_samesa_list in cmb_with_same_diff.values():
  UF = UnionFind(N) #ノード数はボールの数
#  print(each_samesa_list, 'における処理前の木の数は', UF.Count_Trees())
  for a, b in each_samesa_list:
    UF.Unite(a, b)
#  print(each_samesa_list, 'における処理後の木の数は', UF.Count_Trees())
  ans = min(ans, UF.Count_Trees())

#print(ans)

Submission status: Wrong Answer

Solution code:
###template###
import sys
def input(): return sys.stdin.readline().rstrip()
def mi(): return map(int, input().split())
###template###

#Union-Find ****0スタートなので注意！****
class UnionFind():
  # 作りたい要素数（ノードの数）nで初期化
  # 使用するインスタンス変数の初期化
  def __init__(self, n):
    self.n = n
    # root[x]<0ならそのノードが根かつその値が木の要素数
    # rootノードでその木の要素数を記録する
    self.root = [-1]*(n) #元々はn+1になっていたが、nに直した
    # 木をくっつける時にアンバランスにならないように調整する
    self.rnk = [0]*(n) #元々はn+1になっていたが、nに直した

  # ノードxのrootノードを見つける
  def Find_Root(self, x):
    if(self.root[x] < 0):
      return x
    else:
      # ついでに経路圧縮（調べた辺を根に直接つなぎ直す）をかけておく
      self.root[x] = self.Find_Root(self.root[x])
      return self.root[x]

  # 木の併合、入力は併合したい集合に属する各ノード
  def Unite(self, x, y):
    # 入力ノードのrootノードを見つける
    x = self.Find_Root(x)
    y = self.Find_Root(y)
    # すでに同じ木に属していた場合、何もしないで返す
    if(x == y):
      return
    # 違う木に属していた場合rnkを見てくっつける方を決める
    elif(self.rnk[x] > self.rnk[y]):
      self.root[x] += self.root[y] #要素数を足す(根のrootは"-要素数")
      self.root[y] = x #ノードyの親をx（新しい集合の根）とする
    else:
      self.root[y] += self.root[x] #要素数を足す
      self.root[x] = y
      # rnkが同じ（深さに差がない場合）は1増やす（根(rnk1)+繋げる集合のrnkということで、1増えることになる）
      if(self.rnk[x] == self.rnk[y]):
          self.rnk[y] += 1

  # xとyが同じグループに属するか判断
  def isSameGroup(self, x, y):
    return self.Find_Root(x) == self.Find_Root(y)

  # ノードxが属する木のサイズを返す（根ノードの.root[idx]を-符号を外して返すだけ
  def Count(self, x):
    return -self.root[self.Find_Root(x)] #-符号を外す

  # 木の数（＝集合の数）を返す（根の数=rootに-符号を持つものの数を返すだけ）
  def Count_Trees(self):
    treecnt = 0
    for eachroot in self.root:
      if eachroot < 0: treecnt += 1
    return treecnt
#------Union-Findおわり-------------#

import collections

N = int(input())
XYs = [tuple(mi()) for _ in range(N)]

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

sa_list = []
cmb_with_same_diff = collections.defaultdict(list)
import itertools
diffidx = 0
for a in range(0, N):
  for b in range(0, N):
    if a>=b: continue
    #ここでa, bは各ボールのidx
    ax, ay = XYs[a]
    bx, by = XYs[b]
    if ax-bx>=0: nowsa = (ax-bx,ay-by)
    elif ax-bx==0: nowsa = (ax-bx,abs(ay-by))
    else: nowsa = (-(ax-bx),-(ay-by))
    sa_list.append(nowsa)
    cmb_with_same_diff[nowsa].append((a, b))

#print(sa_list)
#print(cmb_with_same_diff)

#最も多い差の個数（これ-1を短縮できるはず）
print(N-collections.Counter(sa_list).most_common()[0][1])

#[((x, y), 回数), ...]　多い順で入っている
#sa_sorted = collections.Counter(sa_list).most_common()

ans = N
for each_samesa_list in cmb_with_same_diff.values():
  UF = UnionFind(N) #ノード数はボールの数
#  print(each_samesa_list, 'における処理前の木の数は', UF.Count_Trees())
  for a, b in each_samesa_list:
    UF.Unite(a, b)
#  print(each_samesa_list, 'における処理後の木の数は', UF.Count_Trees())
  ans = min(ans, UF.Count_Trees())

#print(ans)

Submission status: Wrong Answer

Solution code:
###template###
import sys
def input(): return sys.stdin.readline().rstrip()
def mi(): return map(int, input().split())
###template###

#Union-Find ****0スタートなので注意！****
class UnionFind():
  # 作りたい要素数（ノードの数）nで初期化
  # 使用するインスタンス変数の初期化
  def __init__(self, n):
    self.n = n
    # root[x]<0ならそのノードが根かつその値が木の要素数
    # rootノードでその木の要素数を記録する
    self.root = [-1]*(n) #元々はn+1になっていたが、nに直した
    # 木をくっつける時にアンバランスにならないように調整する
    self.rnk = [0]*(n) #元々はn+1になっていたが、nに直した

  # ノードxのrootノードを見つける
  def Find_Root(self, x):
    if(self.root[x] < 0):
      return x
    else:
      # ついでに経路圧縮（調べた辺を根に直接つなぎ直す）をかけておく
      self.root[x] = self.Find_Root(self.root[x])
      return self.root[x]

  # 木の併合、入力は併合したい集合に属する各ノード
  def Unite(self, x, y):
    # 入力ノードのrootノードを見つける
    x = self.Find_Root(x)
    y = self.Find_Root(y)
    # すでに同じ木に属していた場合、何もしないで返す
    if(x == y):
      return
    # 違う木に属していた場合rnkを見てくっつける方を決める
    elif(self.rnk[x] > self.rnk[y]):
      self.root[x] += self.root[y] #要素数を足す(根のrootは"-要素数")
      self.root[y] = x #ノードyの親をx（新しい集合の根）とする
    else:
      self.root[y] += self.root[x] #要素数を足す
      self.root[x] = y
      # rnkが同じ（深さに差がない場合）は1増やす（根(rnk1)+繋げる集合のrnkということで、1増えることになる）
      if(self.rnk[x] == self.rnk[y]):
          self.rnk[y] += 1

  # xとyが同じグループに属するか判断
  def isSameGroup(self, x, y):
    return self.Find_Root(x) == self.Find_Root(y)

  # ノードxが属する木のサイズを返す（根ノードの.root[idx]を-符号を外して返すだけ
  def Count(self, x):
    return -self.root[self.Find_Root(x)] #-符号を外す

  # 木の数（＝集合の数）を返す（根の数=rootに-符号を持つものの数を返すだけ）
  def Count_Trees(self):
    treecnt = 0
    for eachroot in self.root:
      if eachroot < 0: treecnt += 1
    return treecnt
#------Union-Findおわり-------------#

import collections

N = int(input())
XYs = [tuple(mi()) for _ in range(N)]

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

sa_list = []
cmb_with_same_diff = collections.defaultdict(list)
import itertools
diffidx = 0
for a in range(0, N):
  for b in range(0, N):
    if a>=b: continue
    #ここでa, bは各ボールのidx
    ax, ay = XYs[a]
    bx, by = XYs[b]
    nowsa = (ax-bx,ay-by) if ax-bx>=0 else (-(ax-bx),-(ay-by))
    sa_list.append(nowsa)
    cmb_with_same_diff[nowsa].append((a, b))

#print(sa_list)
#print(cmb_with_same_diff)

#最も多い差の個数（これ-1を短縮できるはず）
print(N-collections.Counter(sa_list).most_common()[0][1])

#[((x, y), 回数), ...]　多い順で入っている
#sa_sorted = collections.Counter(sa_list).most_common()

ans = N
for each_samesa_list in cmb_with_same_diff.values():
  UF = UnionFind(N) #ノード数はボールの数
#  print(each_samesa_list, 'における処理前の木の数は', UF.Count_Trees())
  for a, b in each_samesa_list:
    UF.Unite(a, b)
#  print(each_samesa_list, 'における処理後の木の数は', UF.Count_Trees())
  ans = min(ans, UF.Count_Trees())

#print(ans)

Submission status: Wrong Answer

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

A = Counter()
for (x1, y1), (x2, y2) in combinations(XY, 2):
        if x1 == x2 and y1 == y2:
            continue
        if x1 < x2:
            x1, x2 = x2, x1
            y1, y2 = y2, y1
        A[(x1-x2, y1-y2)] += 1
if N == 1:
    print(1)
else:
    print(N - max(A.values()))

Submission status: Wrong Answer

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

A = Counter()
for (x1, y1), (x2, y2) in combinations(XY, 2):
        if x1 == x2 and y1 == y2:
            continue
        if x1 < x2:
            x1, x2 = x2, x1
            y1, y2 = y2, y1
        A[(x1-x2, y1-y2)] += 1
print(A)
if N == 1:
    print(1)
else:
    print(N - max(A.values()))

Submission status: Wrong Answer

Solution code:
N = int(input())
xy = [list(map(int, input().split())) for _ in range(N)]
 
if N == 1:
  print(1)
  exit()
  
import itertools
hoges = {}
for i in itertools.combinations(xy, 2):
    if i[0][0] - i[1][0] >= 0:
        hoge = (i[0][0] - i[1][0], i[0][1] - i[1][1])
    else:
        hoge = (i[1][0] - i[0][0], i[1][1] - i[0][1])
    hoges.setdefault(hoge, 0)
    hoges[hoge] += 1
# print(hoges)
max_v = max(hoges.values())
print(N - max_v)

Submission status: Wrong Answer

Solution code:
###template###
import sys
def input(): return sys.stdin.readline().rstrip()
def mi(): return map(int, input().split())
###template###

#Union-Find ****0スタートなので注意！****
class UnionFind():
  # 作りたい要素数（ノードの数）nで初期化
  # 使用するインスタンス変数の初期化
  def __init__(self, n):
    self.n = n
    # root[x]<0ならそのノードが根かつその値が木の要素数
    # rootノードでその木の要素数を記録する
    self.root = [-1]*(n+1) #元々はn+1になっていたが、nに直した
    # 木をくっつける時にアンバランスにならないように調整する
    self.rnk = [0]*(n+1) #元々はn+1になっていたが、nに直した

  # ノードxのrootノードを見つける
  def Find_Root(self, x):
    if(self.root[x] < 0):
      return x
    else:
      # ついでに経路圧縮（調べた辺を根に直接つなぎ直す）をかけておく
      self.root[x] = self.Find_Root(self.root[x])
      return self.root[x]

  # 木の併合、入力は併合したい集合に属する各ノード
  def Unite(self, x, y):
    # 入力ノードのrootノードを見つける
    x = self.Find_Root(x)
    y = self.Find_Root(y)
    # すでに同じ木に属していた場合、何もしないで返す
    if(x == y):
      return
    # 違う木に属していた場合rnkを見てくっつける方を決める
    elif(self.rnk[x] > self.rnk[y]):
      self.root[x] += self.root[y] #要素数を足す(根のrootは"-要素数")
      self.root[y] = x #ノードyの親をx（新しい集合の根）とする
    else:
      self.root[y] += self.root[x] #要素数を足す
      self.root[x] = y
      # rnkが同じ（深さに差がない場合）は1増やす（根(rnk1)+繋げる集合のrnkということで、1増えることになる）
      if(self.rnk[x] == self.rnk[y]):
          self.rnk[y] += 1

  # xとyが同じグループに属するか判断
  def isSameGroup(self, x, y):
    return self.Find_Root(x) == self.Find_Root(y)

  # ノードxが属する木のサイズを返す（根ノードの.root[idx]を-符号を外して返すだけ
  def Count(self, x):
    return -self.root[self.Find_Root(x)] #-符号を外す

  # 木の数（＝集合の数）を返す（根の数=rootに-符号を持つものの数を返すだけ）
  def Count_Trees(self):
    treecnt = 0
    for eachroot in self.root:
      if eachroot < 0: treecnt += 1
    return treecnt
#------Union-Findおわり-------------#

import collections

N = int(input())
XYs = [tuple(mi()) for _ in range(N)]

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

sa_list = []
cmb_with_same_diff = collections.defaultdict(list)
import itertools
diffidx = 0
for a in range(0, N):
  for b in range(0, N):
    if a>=b: continue
    #ここでa, bは各ボールのidx
    ax, ay = XYs[a]
    bx, by = XYs[b]
    nowsa = (ax-bx,ay-by) if ax-bx>=0 else (-(ax-bx),-(ay-by))
    sa_list.append(nowsa)
    cmb_with_same_diff[nowsa].append((a, b))

#print(sa_list)
#print(cmb_with_same_diff)

#最も多い差の個数（これ-1を短縮できるはず）
#print(N-collections.Counter(sa_list).most_common()[0][1])

#[((x, y), 回数), ...]　多い順で入っている
sa_sorted = collections.Counter(sa_list).most_common()

ans = N
for each_samesa_list in cmb_with_same_diff.values():
  UF = UnionFind(N) #ノード数はボールの数
#  print(each_samesa_list, 'における処理前の木の数は', UF.Count_Trees())
  for a, b in each_samesa_list:
    UF.Unite(a, b)
#  print(each_samesa_list, 'における処理後の木の数は', UF.Count_Trees())
  ans = min(ans, UF.Count_Trees())

print(ans)

Submission status: Wrong Answer

Solution code:
###template###
import sys
def input(): return sys.stdin.readline().rstrip()
def mi(): return map(int, input().split())
###template###

#Union-Find ****0スタートなので注意！****
class UnionFind():
  # 作りたい要素数（ノードの数）nで初期化
  # 使用するインスタンス変数の初期化
  def __init__(self, n):
    self.n = n
    # root[x]<0ならそのノードが根かつその値が木の要素数
    # rootノードでその木の要素数を記録する
    self.root = [-1]*(n) #元々はn+1になっていたが、nに直した
    # 木をくっつける時にアンバランスにならないように調整する
    self.rnk = [0]*(n) #元々はn+1になっていたが、nに直した

  # ノードxのrootノードを見つける
  def Find_Root(self, x):
    if(self.root[x] < 0):
      return x
    else:
      # ついでに経路圧縮（調べた辺を根に直接つなぎ直す）をかけておく
      self.root[x] = self.Find_Root(self.root[x])
      return self.root[x]

  # 木の併合、入力は併合したい集合に属する各ノード
  def Unite(self, x, y):
    # 入力ノードのrootノードを見つける
    x = self.Find_Root(x)
    y = self.Find_Root(y)
    # すでに同じ木に属していた場合、何もしないで返す
    if(x == y):
      return
    # 違う木に属していた場合rnkを見てくっつける方を決める
    elif(self.rnk[x] > self.rnk[y]):
      self.root[x] += self.root[y] #要素数を足す(根のrootは"-要素数")
      self.root[y] = x #ノードyの親をx（新しい集合の根）とする
    else:
      self.root[y] += self.root[x] #要素数を足す
      self.root[x] = y
      # rnkが同じ（深さに差がない場合）は1増やす（根(rnk1)+繋げる集合のrnkということで、1増えることになる）
      if(self.rnk[x] == self.rnk[y]):
          self.rnk[y] += 1

  # xとyが同じグループに属するか判断
  def isSameGroup(self, x, y):
    return self.Find_Root(x) == self.Find_Root(y)

  # ノードxが属する木のサイズを返す（根ノードの.root[idx]を-符号を外して返すだけ
  def Count(self, x):
    return -self.root[self.Find_Root(x)] #-符号を外す

  # 木の数（＝集合の数）を返す（根の数=rootに-符号を持つものの数を返すだけ）
  def Count_Trees(self):
    treecnt = 0
    for eachroot in self.root:
      if eachroot < 0: treecnt += 1
    return treecnt
#------Union-Findおわり-------------#

import collections

N = int(input())
XYs = [tuple(mi()) for _ in range(N)]

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

sa_list = []
cmb_with_same_diff = collections.defaultdict(list)
import itertools
diffidx = 0
for a in range(0, N):
  for b in range(0, N):
    if a>=b: continue
    #ここでa, bは各ボールのidx
    ax, ay = XYs[a]
    bx, by = XYs[b]
    nowsa = (ax-bx,ay-by) if ax-bx>=0 else (-(ax-bx),-(ay-by))
    sa_list.append(nowsa)
    cmb_with_same_diff[nowsa].append((a, b))

#print(sa_list)
#print(cmb_with_same_diff)

#最も多い差の個数（これ-1を短縮できるはず）
#print(N-collections.Counter(sa_list).most_common()[0][1])

#[((x, y), 回数), ...]　多い順で入っている
sa_sorted = collections.Counter(sa_list).most_common()

ans = N
for each_samesa_list in cmb_with_same_diff.values():
  UF = UnionFind(N) #ノード数はボールの数
#  print(each_samesa_list, 'における処理前の木の数は', UF.Count_Trees())
  for a, b in each_samesa_list:
    UF.Unite(a, b)
#  print(each_samesa_list, 'における処理後の木の数は', UF.Count_Trees())
  ans = min(ans, UF.Count_Trees())

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
balls = [
    [int(s) for s in input().split(' ')]
    for i in range(N)
]
balls.sort(key=lambda p: p[1])
balls.sort(key=lambda p: p[0])
d = {}
d_max = -1
for i in range(N):
    for j in range(i + 1, N):
        p = balls[j][0] - balls[i][0]
        q = balls[j][1] - balls[i][1]
        if not p in d:
            d[p] = {}
        d[p][q] = (d[p][q] if q in d[p] else 0) + 1
        d_max = max([d_max, d[p][q]])
print(N - d_max)

Submission status: Wrong Answer

Solution code:
from itertools import combinations
from operator import itemgetter
N = int(input())
XY = [list(map(int, input().split())) for _ in range(N)]
X, Y = list(map(list, zip(*XY)))

P = [abs(x1 - x2) for x1, x2 in combinations(X, 2)]
P = set(P)
if 0 in P:
    P.remove(0)
P = list(P)
Q = [abs(y1 - y2) for y1, y2 in combinations(Y, 2)]
Q = set(Q)
if 0 in Q:
    Q.remove(0)
Q = list(Q)
ans = 10**10

XY.sort()
for p in P:
    S = set()
    la = 0
    for x, y in XY:
        if (x, y) not in S:
            la += 1
        S.add((x+p, y))
    ans = min(ans, la)
XY1 = XY[:]
XY1.sort(key = itemgetter(1))
for q in Q:
    S = set()
    la = 0
    for x, y in XY1:
        if (x, y) not in S:
            la += 1
        S.add((x, y+q))
    ans = min(ans, la)

for p in P:
    for q in Q:
        S = set()
        la = 0
        for x, y in XY:
            if (x, y) not in S:
                la += 1
            S.add((x+p, y+q))
        ans = min(ans, la)
        S = set()
        la = 0
        for x, y in XY:
            if (x, y) not in S:
                la += 1
            S.add((x+p, y-q))
        ans = min(ans, la)
print(ans)

Submission status: Wrong Answer

Solution code:
###template###
import sys
def input(): return sys.stdin.readline().rstrip()
def mi(): return map(int, input().split())
###template###

import collections

N = int(input())
XYs = [tuple(mi()) for _ in range(N)]

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

sa_list = []
import itertools
for (ax, ay), (bx, by) in itertools.combinations(XYs, 2):
  sa_list.append((ax-bx,ay-by) if ax-bx>=0 else (-(ax-bx),-(ay-by)))

#最も多い差の個数（これ-1を短縮できるはず）
#print(N-collections.Counter(sa_list).most_common()[0][1])

#[((x, y), 回数), ...]　多い順で入っている
sa_sorted = collections.Counter(sa_list).most_common()

ans = N
for eachsa in sa_sorted:
#  print(eachsa)
  cnt = 0
  tmpans = N #ここから引いていく
  #aとbの差がeachsa[0]と一致したらvisitedに入れる
  visited = [0] * N
  for a in range(0, N):
    tmpsame = 0 #今見ているaと差が同じものの数
    visitset = set()
    for b in range(0, N):
  #    print(a, b)
      if a>=b or visited[b]!=0: continue
      sa = sa_list[cnt]
      if sa == eachsa[0]:
  #      print('same', sa, a, b)
        tmpans -= 1
        visitset.add(b)
      cnt += 1
    visited[a] = 1
    for v in visitset:
      visited[v] = 1
  ans = min(ans, tmpans)

print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import combinations
N = int(input())
XY = [list(map(int, input().split())) for _ in range(N)]
X, Y = list(map(list, zip(*XY)))

P = [abs(x1 - x2) for x1, x2 in combinations(X, 2)]
P = list(set(P))
Q = [abs(y1 - y2) for y1, y2 in combinations(Y, 2)]
Q = list(set(Q))
ans = 10**10
XY.sort()
for p in P:
    for q in Q:
        S = set()
        la = 0
        for x, y in XY:
            if (x, y) not in S:
                la += 1
            S.add((x+p, y+q))
        ans = min(ans, la)
        S = set()
        la = 0
        for x, y in XY:
            if (x, y) not in S:
                la += 1
            S.add((x+p, y-q))
        ans = min(ans, la)
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import combinations
N = int(input())
XY = [list(map(int, input().split())) for _ in range(N)]
X, Y = list(map(list, zip(*XY)))

P = [abs(x1 - x2) for x1, x2 in combinations(X, 2)]
P = list(set(P))
Q = [abs(y1 - y2) for y1, y2 in combinations(Y, 2)]
Q = list(set(Q))
ans = 10**10
XY.sort()
for p in P:
    for q in Q:
        S = set()
        la = 0
        for x, y in XY:
            if (x, y) not in S:
                la += 1
            S.add((x+p, y+q))
        ans = min(ans, la)
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import combinations, product
N = int(input())
XY = [list(map(int, input().split())) for _ in range(N)]
X, Y = list(map(list, zip(*XY)))

P = [abs(x1 - x2) for x1, x2 in combinations(X, 2)]
P = set(P)
P = list(P)
Q = [abs(y1 - y2) for y1, y2 in combinations(Y, 2)]
Q = set(Q)
Q = list(Q)
ans = 10**10
XY.sort()
XYs = {(x, y) for x, y in XY}
for p, q in product(P, Q):
    S = set()
    la = 0
    for x, y in XY:
        if (x, y) not in S:
            la += 1
        S.add((x+p, y+q))
    ans = min(ans, la)

Submission status: Wrong Answer

Solution code:
N=int(input())
P=[tuple(map(int,input().split())) for i in range(N)]
ans=N-1
for i in range(N):
    for j in range(N):
        if i==j:
            continue
        p=P[i][0]-P[j][0]
        q=P[i][1]-P[j][1]
        if p==0 or q==0:
            continue
        cost=0
        for k in range(N):
            if (P[k][0]-p,P[k][1]-q) not in P:
                cost+=1
        ans=min(ans,cost)
print(ans)