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: Accepted

Solution code:
def main():
    import sys
    input=sys.stdin.readline   
    sys.setrecursionlimit(100000000)

    n=int(input())
    point=[tuple(map(int,input().split())) for _ in range(n)]
    dic={i:j for i,j in zip(point,range(n))}
    
    if n==1:
        print(1)
        exit()
        
    ans=10**9
    for i in range(n-1):
        for j in range(i+1,n):
            p=point[j][0]-point[i][0]
            q=point[j][1]-point[i][1]
            cnt=0
            visited=[True]*n

            def dfs(x,y):
                if (x+p,y+q) in dic:
                    idx=dic[(x+p,y+q)]
                    if visited[idx]:
                        visited[idx]=False
                        dfs(x+p,y+q)
                if (x-p,y-q) in dic:
                    idx=dic[(x-p,y-q)]
                    if visited[idx]:
                        visited[idx]=False
                        dfs(x-p,y-q)

            for k in range(n):
                if visited[k]:
                    visited[k]=False
                    cnt+=1
                    dfs(point[k][0],point[k][1])      
        
            ans=min(ans,cnt)  
    print(ans)

if __name__=='__main__':
    main()

Submission status: Accepted

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

def main():
    N = int(input())
    pos = [list(map(int,input().split())) for _ in range(N)]
    if N == 1:
        print(1)
    else:
        d = defaultdict(int)
        for i in range(N):
            for j in range(N):
                slope = (pos[i][0]-pos[j][0],pos[i][1]-pos[j][1])
                if slope[0] != 0 or slope[1] != 0:
                    d[slope] += 1
        if len(d) == 0:
            print(N)
        else:
            print(N-max(d.values()))

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N=int(input())
if N==1:
  print(1)
  exit()
  
A=[list(map(int,input().split())) for i in range(N)]
B={}
for a,b in A:
  for c,d in A:
    e=a-c
    f=b-d
    if e!=0 or f!=0:
      if (e,f) in B:
        B[(e,f)]+=1
      else:
        B[(e,f)]=1
a=max(B.values())
print(N-a)

Submission status: Accepted

Solution code:
import itertools
from collections import Counter
n = int(input())
xy = [[int(x) for x in input().split()] for _ in range(n)]
vectors = []
for xy1, xy2 in itertools.combinations(xy,2):
    p = xy2[0] - xy1[0]
    q = xy2[1] - xy1[1]
    vectors.append((p, q))
    vectors.append((-p, -q))
c = Counter(vectors)
if n>=2:
    x = max(c.values())
    res = n - x
else:
    res = 1
print(res)

Submission status: Accepted

Solution code:
from collections import Counter
N=int(input())
XY=[tuple(map(int, input().split())) for _ in range(N)]
PQ=[(x1-x2,y1-y2) for x1,y1 in XY for x2,y2 in XY if x1!=x2 or y1!=y2]
C=Counter(PQ)
print(N-C.most_common(1)[0][1] if N!=1 else 1)

Submission status: Accepted

Solution code:
import itertools
import collections

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

count = collections.defaultdict(int)
for i in itertools.combinations(x_y, 2):
    count[(i[0][0]-i[1][0], i[0][1]-i[1][1])] += 1
    count[(i[1][0]-i[0][0], i[1][1]-i[0][1])] += 1
if not count:
    print(N)
else:
    print(N-max(count.values()))

Submission status: Accepted

Solution code:
from collections import Counter
N = int(input())
X = []
for i in range(N):
    x,y = map(int,input().split())
    X.append((x,y))
kouho = []
for i in range(N):
    for j in range(N):
        if i==j:continue
        kouho.append((X[i][0]-X[j][0],X[i][1]-X[j][1]))
C = Counter(kouho)
if len(C)==0:print(1)
else:print(N-max(C.values()))

Submission status: Accepted

Solution code:
from collections import defaultdict
N = int(input())
if N == 1:
    print(1)
    exit()
X, Y = [], []
for _ in range(N):
    x, y = map(int, input().split())
    X.append(x)
    Y.append(y)
d = defaultdict(int)
for i in range(N):
    for j in range(N):
        if i == j:
            continue
        p = X[i] - X[j]
        q = Y[i] - Y[j]
        d[(p, q)] += 1
print(N - max(d.values()))

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
n = int(readline())
lst1 = [list(map(int,readline().split())) for i in range(n)]
lst1.sort()
cost = 1
if n == 1:
    print(cost)
    exit()
#同じベクトルでつなげる要素を最大化する。全点対象にベクトルを求め、多数決。
dic1 = dict()

for i in range(n-1):
    for j in range(i+1,n):
        x,y = lst1[i][0] - lst1[j][0] , lst1[i][1] - lst1[j][1]
        """
        if x < 0 and y < 0:
            x,y = -x,-y
        elif x < 0 and y >= 0:
            x,y = -x,-y"""
        if (x,y) in dic1:
            dic1[(x,y)] += 1
        else:
            dic1[(x,y)] = 1

#線分は頂点-1個。そのうち同ベクトル数が免除される。
cost += n-1
cost -= max(dic1.values())

print(cost)

Submission status: Accepted

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

if len(l) == 1:
    print(1)
    exit()


from collections import defaultdict
d = defaultdict(int)

for i in range(len(l)):
    for j in range(len(l)):
        difx = l[i][0] - l[j][0]
        dify = l[i][1] - l[j][1]
        if difx!=0 or dify!=0:
            dif = str(difx) + "_" + str(dify)
            d[dif] += 1

p_q = max((v,k) for (k,v) in d.items())[1]
p,q = p_q.split("_")

ans=0
for i in range(len(l)):
    found=False
    for j in range(len(l)):
        difx = l[i][0] - l[j][0]
        dify = l[i][1] - l[j][1]
        if difx==int(p) and dify==int(q):
            found=True
            break
    if not found:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
n = int(input())
if n == 1:
  print(1)
else:
  XY = tuple(tuple(map(int, input().split())) for _ in range(n))
  L = []
  for i in range(n-1):
    for j in range(i+1, n):
      x1, y1 = XY[i]
      x2, y2 = XY[j]
      L.append((x1-x2, y1-y2))
      L.append((x2-x1, y2-y1))
  C = Counter(L)
  ans = n - C.most_common()[0][1]
  print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
from itertools import combinations
from collections import Counter
n = int(stdin.readline().rstrip())
li = [list(map(int,stdin.readline().rstrip().split())) for _ in range(n)]
lin = list(combinations(li,2))
sa = []
for i,j in lin:
    p = i[0]-j[0]
    q = i[1]-j[1]
    sa.append((p,q))
    sa.append((-p,-q))
san = Counter(sa)
if n >= 2:
    print(n-max(san.values()))
else:
    print(1)

Submission status: Accepted

Solution code:
N = int(input())
ab = sorted([list(map(int,input().split())) for i in range(N)])
diff = {}
for i in range(N-1):
    for j in range(i+1,N):
        a = (ab[i][0]-ab[j][0],ab[i][1]-ab[j][1])
        if a not in diff:
            diff[a] = 1
        else:
            diff[a] += 1
if diff:
    maxv = max(diff.values())
    print(N-maxv)
else:
    print(N)

Submission status: Accepted

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

d = {(0,0):0}
for i in range(n):
    for j in range(n):
        if i == j: continue
        dx = x[i]-x[j]
        dy = y[i]-y[j]
        d[(dx,dy)] = d.get((dx,dy),0) + 1
        
print(n-max(d.values()))

Submission status: Accepted

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

d = {(0,0):0}
for i in range(n-1):
    for j in range(i+1,n):
        dx = x[i]-x[j]
        dy = y[i]-y[j]
        d[(dx,dy)] = d.get((dx,dy),0) + 1
        d[(-dx,-dy)] = d.get((-dx,-dy),0) + 1
        
print(n-max(d.values()))

Submission status: Accepted

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

ans = n
set_cover = []
for i in range(n):
    for j in range(i+1, n):
        p = xyl[j][0] - xyl[i][0]
        q = xyl[j][1] - xyl[i][1]
        tmp = n
        for k in range(n):
            for l in range(n):
                x = xyl[l][0] - xyl[k][0]
                y = xyl[l][1] - xyl[k][1]
                if p == x and q == y:
                    tmp -= 1
        ans = min(ans, tmp)
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
n=int(input())
b=[tuple(map(int,input().split())) for _ in range(n)]
r=[(x[0]-y[0],x[1]-y[1]) for x in b for y in b if x!=y]
c=Counter(r).most_common(1)
print(n-c[0][1] if c else n)

Submission status: Accepted

Solution code:
n=int(input())
l=[list(map(int,input().split())) for i in range(n)]
a=[]
for i in range(n):
    for j in range(n):
        if i!=j:
            a.append([l[i][0]-l[j][0],l[i][1]-l[j][1]])
#print(a)
m=len(a)
ans=0
for k in range(m):
    c=0
    p=a[k][0]
    q=a[k][1]
    for i in range(n):
        for j in range(n):
            if i!=j and [l[i][0]-l[j][0],l[i][1]-l[j][1]]==[p,q]:
                c+=1
    ans=max(ans,c)
if n==1:
    print(1)
else:
    print(n-ans)

Submission status: Accepted

Solution code:
from collections import Counter

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

pq = []

for x, y in A:
    for i, j in A:
        if x == i and y == j:
            continue
        pq.append(str(i-x)+str(j-y))

ans = Counter(pq).most_common()

if ans == []:
    print(1)
else:
    print(N - ans[0][1])

Submission status: Accepted

Solution code:
import collections
import sys

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

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

pq = []
for i in range(N):
    for j in range(N):
        if i != j:
            pq.append((xy[i][0]-xy[j][0], xy[i][1]-xy[j][1]))
#print(pq)
pqc = collections.Counter(pq)
x = pqc.most_common()[0][1]
print(N-x)

Submission status: Accepted

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

dic = {}

for i in range(n):
    for j in range(n):
        if i != j:
            coordinate = str((balls[i][0] - balls[j][0], balls[i][1] - balls[j][1]))
            if coordinate in dic:
                dic[coordinate] += 1
            else:
                dic[coordinate] = 1

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

Submission status: Accepted

Solution code:
n = int(input())
lis = [list(map(int,input().split())) for i in range(n)]
lis.sort(key = lambda x:x[1])
lis.sort(key = lambda x:x[0])
ans = 10 ** 8
for i in range(n):
    for j in range(i,n):
        p = lis[j][0]-lis[i][0]
        q = lis[j][1]-lis[i][1]
        li = lis.copy()
        cnt = 0
        while li:
            a = li.pop(0)
            while [a[0]+p,a[1]+q] in li:
                a = li.pop(li.index([a[0]+p,a[1]+q]))
            cnt += 1
        ans = min(ans,cnt)
print(ans)

Submission status: Accepted

Solution code:


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

pq = []
for i in range(N):
    for j in range(N):
        if i != j:
            pq.append((xy[i][0] - xy[j][0], xy[i][1] - xy[j][1]))


ans = N
for p,q in pq:
    cost = 0
    for x,y in xy:
        if  (x+p, y+q) not in xy:
            cost += 1

    ans = min(ans, cost)

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
from itertools import permutations
n=int(input())
if n==1:print(1);exit()
A=[list(map(int,input().split())) for i in range(n)]
B=[(a[0]-b[0],a[1]-b[1]) for a,b in permutations(A,2)]
most=max(Counter(B).values())
print(n-most)

Submission status: Accepted

Solution code:
from collections import Counter
n=int(input())
A=[list(map(int,input().split())) for i in range(n)]
Per=[(a[0]-b[0],a[1]-b[1]) for a in A for b in A if a!=b]
print(n-Counter(Per).most_common(1)[0][1] if n!=1 else 1)

Submission status: Accepted

Solution code:
import collections
N = int(input())
xy = [0] * N
for i in range(N):
  xy[i] = list(map(int, input().split()))
#print(xy)

ans = [[0, 0] for i in range(N ** 2)]
x = [1] * (N ** 2)
y = 0
for i in range(N):
  for j in range(N):
    if i != j:
      p = xy[i][0] - xy[j][0]
      q = xy[i][1] - xy[j][1]
      if [p, q] not in ans:
        ans[y][0], ans[y][1] = p, q 
        y += 1
      else:
        lnum = ans.index([p, q])
        x[lnum] += 1
        
x_max = x.index(max(x))
pq = ans[x_max]
#print(pq)

ans2 = N - max(x)
print(max(ans2, 1))

Submission status: Accepted

Solution code:
import itertools
import collections as c
N = int(input())
XY = [list(map(int, input().split())) for _ in range(N)]
vectors = []
for xy1,xy2 in itertools.combinations(XY,2):
	p = xy2[0] - xy1[0]
	q = xy2[1] - xy1[1]

	vectors.append((p,q))
	vectors.append((-p,-q))

V = c.Counter(vectors)
if N >= 2:
	x = max(V.values())
	ans = N-x
else:
	ans = 1

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

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

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

points.sort(key=lambda p: p[1])
points.sort(key=lambda p: p[0])
d = defaultdict(int)
max_count = 0
max_f = None
for i in range(N):
    for j in range(i + 1, N):
        xi, yi = points[i]
        xj, yj = points[j]
        key = (xj - xi, yj - yi)
        d[key] += 1
        if d[key] > max_count:
            max_count = d[key]
            max_f = key


class UnionFind(object):

    def __init__(self, N):
        self.tree = [i for i in range(N)]
        self.rank = [0] * (N + 1)

    def find(self, x):
        if self.tree[x] == x:
            return x
        else:
            self.tree[x] = self.find(self.tree[x])  # 経路圧縮
            return self.tree[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)

        # ランクを考慮しない場合はどちらが親になっても良い
        if self.rank[x] < self.rank[y]:
            self.tree[x] = y
        else:
            self.tree[y] = x

        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1

    def has_same_parent(self, x, y):
        return self.find(x) == self.find(y)


p, q = max_f
uf = UnionFind(N)
for i in range(N):
    for j in range(i + 1, N):
        xi, yi = points[i]
        xj, yj = points[j]
        if xj - xi == p and yj - yi == q:
            uf.unite(i, j)

print(len(set(uf.tree)))

Submission status: Accepted

Solution code:
def main():
    from collections import Counter, namedtuple

    pt = namedtuple('pt', 'x y')

    def delta(a: pt, b: pt) -> pt:
        x = a.x - b.x
        y = a.y - b.y
        if (x < 0) or (x == 0 and y < 0):
            x = -x
            y = -y
        return pt(x=x, y=y)

    n = int(input())
    if n == 1:
        # deltaが計算できないので、
        # 別処理する
        print(1)
        return

    ps = [pt(*map(int, input().split())) for _ in range(n)]

    c = Counter(
        delta(a, b)
        for i, a in enumerate(ps)
        for j, b in enumerate(ps)
        if i < j
    )

    ma = max(c.values())

    print(n - ma)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n=int(input())
xy=[list(map(int,input().split())) for _ in range(n)]
d=[]
if n==1:
    print(1)
else:
    for i in range(n):
        for j in range(n):
            if i!=j:
                d.append([xy[i][0]-xy[j][0],xy[i][1]-xy[j][1]])
    d.sort()
    res = 1
    tres = 1
    for i in range(len(d)-1):
        if d[i] == d[i+1]:
            tres += 1
        else:
            tres = 1
        res = max(res,tres)
    print(n-res)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict, deque
import bisect
from heapq import *
from math import factorial, ceil, floor
sys.setrecursionlimit(200000)
input = sys.stdin.readline

# N, M, = map(int, input().split())
# N = int(input())
# L = [int(v) for v in input().split()]
# L = [[int(v) for v in input().split()] for _ in range(N)]
# L = [int(input()) for _ in range(N)]
# L = [list(input().strip())  for _ in range(N)]
# S = input().strip()

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

m = {}
for i in range(N):
    for j in range(N):
        if i != j:
            x, y = L[i]
            x2, y2 = L[j]

            key = (x - x2, y - y2)

            if m.get(key) == None:
                m[key] = 0
            m[key] += 1

if m == {}:
    print(1)
    exit()
print(N - max(m.values()))

Submission status: Accepted

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

# B = [[[0, 0] for i in range(n)] for j in range(n)]
if n == 1:
    print(1)
else:

    D = {}
    for i in range(n):
        for j in range(n):
            if i != j:
                dy = A[i][1] - A[j][1]
                dx = A[i][0] - A[j][0]
                try:
                    D[(dx, dy)] += 1
                except:
                    D[(dx, dy)] = 1
    # print(D)
    ans = n - max(list(D.values()))
    print(ans)

Submission status: Accepted

Solution code:
n = int(input())

points = [list(map(int, input().split(" "))) for _ in range(n)]
X = 0
Y = 1
ans = 10 ** 14
for i in range(n):
    for j in range(n):
        if i == j:
            continue
        x1, y1 = points[i]
        x2, y2 = points[j]
        p = x1 - x2
        q = y1 - y2
        cost = n
        for point1 in points:  # そのpointからcost0で遷移できる先があるかどうか
            fromx, fromy = point1
            for point2 in points:
                tox, toy = point2
                if fromx - tox == p and fromy - toy == q:
                    cost -= 1
                    break
        if ans > cost:
            ans = cost
if n == 1:
    print(1)
else:
    print(ans)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/diverta2019-2/tasks/diverta2019_2_b


from itertools import combinations
from collections import defaultdict

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

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

# points.sort()  # 先にソートしておくと大小関係の処理が楽

cnts = defaultdict(lambda: 0)
for pa, pb in combinations(points, 2):
    dx = pa[0] - pb[0]
    dy = pa[1] - pb[1]
    if dx < 0:  # 事前にソートしておくとココらへんの処理がいらなくなるよ
        dx *= -1
        dy *= -1
    if dx == 0:
        dy = max(dy, -dy)
    if dy == 0:
        dx = max(dx, -dx)
    cnts[(dx, dy)] += 1

print(N - max(cnts.values()))

Submission status: Accepted

Solution code:
import collections

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

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

pq = []
for i in range(N):
  xi, yi = xy[i][0], xy[i][1]
  for j in range(i + 1, N):
    xj, yj = xy[j][0], xy[j][1]
    p, q = xj - xi, yj - yi
    pq.append((p, q))
#print(pq)

c = list(collections.Counter(pq).values())
c.sort()
print(N - c[-1])

Submission status: Accepted

Solution code:
from bisect import bisect_left
N=int(input())
xy=[list(map(int,input().split())) for i in range(N)]
xy.sort()
inf=float("inf")
ans=inf
for i in range(N-1):
    for j in range(i+1,N):
        p=xy[j][0]-xy[i][0]
        q=xy[j][1]-xy[i][1]
        flag=[0]*N
        cnt=0
        for k in range(N):
            if flag[k]==0:
                flag[k]=1
                cnt+=1
                nx,ny=xy[k][0]+p,xy[k][1]+q
                b=bisect_left(xy,[nx,ny])
                while b<N and xy[b]==[nx,ny]:
                    flag[b]=1
                    nx,ny=nx+p,ny+q
                    b=bisect_left(xy,[nx,ny])
        ans=min(ans,cnt)
if N==1:
    print(1)
else:
    print(ans)

Submission status: Accepted

Solution code:
#各操作でコストゼロになるボールは一意
n = int(input())
x = []
y = []
for i in range(n):
    xi,yi =map(int, input().split( ))
    x.append(xi)
    y.append(yi)

cnt = {}

for i in range(n):
    for j in range(i):
        d1 = x[i]-x[j]
        d2 = y[i]-y[j]
        if (d1,d2) in cnt:
            cnt[(d1,d2)] += 1
        else:
            cnt[(d1,d2)] = 1
        if (-d1,-d2) in cnt:#こっちもいる
            cnt[(-d1,-d2)] += 1
        else:
            cnt[(-d1,-d2)] = 1

tmp = 0

for k in cnt:
    tmp = max(tmp, cnt[k])

print(n-tmp)

Submission status: Accepted

Solution code:
from collections import Counter
N=int(input())
B=[tuple(map(int, input().split())) for _ in range(N)]
R=[(x[0]-y[0],x[1]-y[1]) for x in B for y in B if x!=y]
C=Counter(R).most_common(1)
print(N-C[0][1] if C else N)

Submission status: Accepted

Solution code:
from collections import Counter
N=int(input())
B=[tuple(map(int, input().split())) for _ in range(N)]
R=[(x[0]-y[0],x[1]-y[1]) for x in B for y in B if x!=y]
C=Counter(R).most_common(1)
print(N-C[0][1] if C else N)

Submission status: Accepted

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

#2ボールの相対座標をぜんぶ調べる
R=[(x[0]-y[0],x[1]-y[1]) for x in balls for y in balls]
C=Counter(R).most_common()

#いちばん多い相対座標を(p,q)とする
#C[0]は(0,0)なので除外
if len(C)<=1:
    print(N)
else:
    print(N-(C[1][1]))

Submission status: Accepted

Solution code:
import collections
N=int(input())
xy=[tuple(map(int,input().split())) for i in range(N)]
table=collections.defaultdict(int)

for x,y in xy:
  for x2,y2 in xy:
    if x==x2 and y==y2:
      continue
    else:
      table[(x-x2,y-y2)]+=1
ans=0
for x in table:
  ans=max(ans,table[x])
print(N-ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
n = int(input())
xy = [list(map(int, input().split())) for _ in range(n)]

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

def cost(p,q):
    e = 0
    for i in range(n):
        for j in range(n):
            v = xy[i]
            u = xy[j]
            if p==u[0]-v[0] and q==u[1]-v[1]:
                e += 1
                break
    return n-e

d = {}
for i in range(n):
    for j in range(n):
        if i==j:
            continue
        v = xy[i]
        u = xy[j]
        p = v[0]-u[0]
        q = v[1]-u[1]
        if (p,q) not in d:
            d[(p,q,)] = 0
        d[(p,q)] += 1

c = 0
for k in d:
    if d[k]>c:
        c = d[k]
        p,q = k

print(cost(p,q))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
n = int(input())
xy = [list(map(int, input().split())) for _ in range(n)]

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

def cost(p,q):
    e = 0
    for i in range(n):
        for j in range(n):
            v = xy[i]
            u = xy[j]
            if p==u[0]-v[0] and q==u[1]-v[1]:
                e += 1
                break
    return n-e

res = 10**9
for i in range(n):
    for j in range(n):
        if i==j:
            continue
        v = xy[i]
        u = xy[j]
        res = min(res, cost(v[0]-u[0], v[1]-u[1]))

print(res)

Submission status: Accepted

Solution code:
import itertools
from collections import defaultdict


def main():
    N = int(input())
    if N == 1:
        print(1)

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

        dd = defaultdict(int)

        for xy1, xy2 in itertools.combinations(XY, 2):
            a = (xy2[0] - xy1[0], xy2[1] - xy1[1])
            b = (-a[0], -a[1])
            dd[a] += 1
            dd[b] += 1

        print(N - max(dd.values()))


main()

Submission status: Accepted

Solution code:
import sys
from collections import Counter
n = int(input())
ls = []
if n == 1:
    print(1)
else:
    for i in range(n):
        x, y = [int(i) for i in sys.stdin.readline().split()]
        ls.append((x, y))
    res = []
    for i in range(n - 1):
        for j in range(i+1, n):
            res.append((ls[j][0] - ls[i][0], ls[j][1] - ls[i][1]))
            res.append((- ls[j][0] + ls[i][0], - ls[j][1] + ls[i][1]))
    ct = Counter(res)
    print(n - max(ct.values()))

Submission status: Accepted

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

for i in range(N):
    for j in range(N):
        if(i==j):continue
        LIST[i*N+j][0]=X[i]-X[j]
        LIST[i*N+j][1]=Y[i]-Y[j]

LIST=sorted(LIST,key=lambda x: (x[0],x[1]))

t=[0,0]
m=0
c=0
for i in range(len(LIST)):
    if(LIST[i]==[0,0]):continue
    elif(LIST[i]!=t):
        c=1
        t=LIST[i]
    else:c+=1
    m=max(c,m)

print(N-m)

Submission status: Accepted

Solution code:
import sys
from collections import Counter
input = sys.stdin.readline
N = int(input())
xy = [tuple([int(i) for i in input().split()]) for _ in range(N)]
ary = []
if N == 1:
    print(1)
    exit()
for i, t in enumerate(xy[:-1]):
    x = t[0]
    y = t[1]
    for x2, y2 in xy[i+1:]:
        ary.append((x2-x, y2-y))
        ary.append((x-x2, y-y2))
c = dict(Counter(ary))
print(N-max(c.values()))

Submission status: Accepted

Solution code:
import sys
from itertools import combinations
from collections import Counter
read = sys.stdin.read

N, *xy = map(int, read().split())

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

pq = []
for (a1, b1), (a2, b2) in combinations(zip(*[iter(xy)] * 2), 2):
    p = a1 - a2
    q = b1 - b2
    pq.append((p, q))
    pq.append((-p, -q))

print(N - Counter(pq).most_common()[0][1])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline


def main():
    N = int(input())
    A = []
    for _ in range(N):
        x, y = map(int, input().split())
        A.append((x, y))
    if N == 1:
        print(1)
        return

    A.sort()
    import collections
    D = collections.defaultdict(int)
    import itertools
    for a, b in itertools.combinations(A, 2):
        p = a[0] - b[0]
        q = a[1] - b[1]
        D[(p, q)] += 1
    d = sorted(D.values())
    print(N - d[-1])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict
d = defaultdict(int)
n = int(input())
xy = [tuple(map(int, input().split())) for _ in range(n)]
xy.sort()

for i in range(n - 1):
    xa, ya = xy[i]
    for j in range(i + 1, n):
        xb, yb = xy[j]
        p = xb - xa
        q = yb - ya
        d[(p, q)] += 1

ans = n
for k, v in d.items():
    ans = min(ans, n - v)
if n == 1:
    ans = 1

print(ans)

Submission status: Accepted

Solution code:
def examB():
    N = I()
    X = [0]*N; Y = [0]*N
    for i in range(N):
        X[i],Y[i] = LI()
    pq = defaultdict(int)
    for i in range(N):
        for j in range(i+1,N):
            curx = X[j]-X[i]
            cury = Y[j]-Y[i]
            pq[curx,cury] +=1
            pq[-curx, -cury] += 1
    if N>1:
        ans = N - max(pq.values())
    else:
        ans = 1
    print(ans)

from string import digits
import sys,copy,bisect,itertools,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examB()

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    def size(self, x):
        return -self.parents[self.find(x)]
    def same(self, x, y):
        return self.find(x) == self.find(y)
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]
    def group_count(self):
        return len(self.roots())

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

ans = 10**10

for i in range(N):
    for j in range(N):

        if i==j:
            continue

        p = B[i][0]-B[j][0]
        q = B[i][1]-B[j][1]
        uf = UnionFind(N)

        for k in range(N):
            for l in range(N):

                if k==l:
                    continue

                if B[k][0]-B[l][0] == p and B[k][1]-B[l][1] == q:
                    uf.union(k,l)

        ans = min(ans,uf.group_count())

print(ans if N != 1 else 1)

Submission status: Accepted

Solution code:
N = int(input())
xy = [list(map(int,input().split())) for _ in range(N)]
if N == 1:
  print(1)
  exit()
d = []
for i in range(N):
  for j in range(N):
    if i == j:
      continue
    X = xy[i][0] - xy[j][0]
    Y = xy[i][1] - xy[j][1]
    d.append([X,Y])
d.sort()
#print(d)
cnt = 1
tmp = 1
std = d[0]
for i in range(1,len(d)):
  if d[i] == std:
    tmp += 1
  else:
    tmp = 1
  std = d[i]
  cnt = max(cnt,tmp)
print(N - cnt)

Submission status: Accepted

Solution code:
import copy

N = int(input())
XY = [tuple(map(int, input().split())) for _ in range(N)]
ans = 10**10
for i in range(N-1):
  x_begin, y_begin = XY[i]
  for j in range(i+1, N):
    p = XY[j][0]-XY[i][0]
    q = XY[j][1]-XY[i][1]
    c = 0
    for k in range(N-1):
      for l in range(k+1, N):
        dx = XY[k][0]-XY[l][0]
        dy = XY[k][1]-XY[l][1]
        if dx == p and dy == q or dx == -p and dy == -q:
          c += 1
    ans = min(ans, N-c)
print(ans if N > 2 else 1)

Submission status: Accepted

Solution code:
n = int(input())
xy = [tuple(map(int, input().split())) for _ in range(n)]
pq = []
for i in range(n):
	for j in range(i+1,n):
		if i==j:
			continue
		xi, yi = xy[i]
		xj, yj = xy[j]
		pq.append((xi - xj, yi - yj))
ans = n
for p, q in pq:
	cost = 0
	for x, y in xy:
		if (x + p, y + q) in xy:
			pass
		else:
			cost += 1
	ans = min(ans, cost)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
xy = [tuple(map(int, input().split())) for _ in range(n)]
pq = []
for i in range(n):
	for j in range(n):
		if i==j:
			continue
		xi, yi = xy[i]
		xj, yj = xy[j]
		pq.append((xi - xj, yi - yj))
ans = 1e9 if n>1 else 1
for p, q in pq:
	cost = 0
	for x, y in xy:
		if (x + p, y + q) in xy:
			pass
		else:
			cost += 1
	ans = min(ans, cost)
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
import itertools as it

N=int(input())
l=[]
for i in range(N):
    l.append(tuple(map(int,input().split())))
l.sort()

if N==1:
    ans=1
else:
    d=[(c[1][0]-c[0][0],c[1][1]-c[0][1]) for c in it.combinations(l,2)]
    ans=N-max(dict(Counter(d)).values())

print(ans)