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())
pos = []
for _ in range(n):
    p = list(map(int, input().split()))
    pos.append(p)

ans = 0
for i in range(n-1):
    for j in range(i+1, n):
        dpos = [pos[i][0] - pos[j][0], pos[i][1] - pos[j][1]]
        cnt = 0
        for k in range(n - 1):
            for l in range(k+1, n):
                tmp = [pos[k][0] - pos[l][0], pos[k][1] - pos[l][1]]
                if dpos[0] == tmp[0] and dpos[1] == tmp[1]:
                    cnt += 1
        print(dpos, cnt)
        ans = max(cnt, ans)

print(n-ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
l=[]
if n==1:
    print(1)
    exit()
else:
    for i in range(n):
        x,y=map(int,input().split())
        l.append((x,y))
    x={}
    for i in l:
        for j in l:
            if i!=j:
                t=(i[0]-j[0],i[1]-j[1])
                if t in x:
                    x[t]+=1
                else:
                    x[t]=1
    print(max(x.values()))

Submission status: Wrong Answer

Solution code:
n=int(input())

xy=[tuple(map(int,input().split())) for i in range(n)]
pq=[]
for i in range(n):
  for j in range(n):
    if i==j:continue
    x1,y1=xy[i]
    x2,y2=xy[j]
    pq.append((x2-x1,y2-y1))

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

ans=n
for p,q in pq:
  t=0
  for x,y in xy:
    if (x+p,y+q) in xy:
      continue
    t+=1
  ans=min(ans,t)
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
xy=[tuple(map(int,input().split())) for i in range(n)]
pq=[]
for i in range(n):
  for j in range(n):
    if i==j:continue
    x1,y1=xy[i]
    x2,y2=xy[j]
    pq.append((x2-x1,y2-y1))

ans=50
for p,q in pq:
  t=0
  for x,y in xy:
    if (x+p,y+q) in xy:
      continue
    t+=1
  ans=min(ans,t)
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
xy=[tuple(map(int,input().split())) for i in range(n)]
pq=[]
for i in range(n):
  for j in range(n):
    if i==j:continue
    x1,y1=xy[i]
    x2,y2=xy[j]
    pq.append((x2-x1,y2-y1))

ans=10**18
for p,q in pq:
  t=0
  for x,y in xy:
    if (x+p,y+q) in xy:
      continue
    t+=1
  ans=min(ans,t)
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
xy=[]
for i in range(n):
  a,b=map(int,input().split())
  xy.append([a,b])
if n==1:
  print(0)
  exit(0)
from collections import Counter
c=[]
for i,xy1 in enumerate(xy):
  for j,xy2 in enumerate(xy):
    if i==j:continue
    tx,ty=xy1[0]-xy2[0],xy1[1]-xy2[1]
    key_str=""
    key_str=str(tx)+":"+str(ty)
    c.append(key_str)
c=Counter(c)

mid_str=""
ans=10**18
for k,v in c.items():
  mid_str=k
  p,q=mid_str.split(":")
  p=int(p)
  q=int(q)
  prex,prey=10**18,10**18
  t=0
  for i in range(n):
    if xy[i][0]-p==prex and xy[i][1]-q==prey:
      prex=xy[i][0]
      prey=xy[i][1]
      continue
    t+=1
    prex=xy[i][0]
    prey=xy[i][1]
  ans=min(ans,t)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys

stdin = sys.stdin
inf = 1 << 60
mod = 1000000007

sys.setrecursionlimit(10**7)

ni = lambda: int(ns())
nin = lambda y: [ni() for _ in range(y)]
na = lambda: list(map(int, stdin.readline().split()))
nan = lambda y: [na() for _ in range(y)]
nf = lambda: float(ns())
nfn = lambda y: [nf() for _ in range(y)]
nfa = lambda: list(map(float, stdin.readline().split()))
nfan = lambda y: [nfa() for _ in range(y)]
ns = lambda: stdin.readline().rstrip()
nsn = lambda y: [ns() for _ in range(y)]
ncl = lambda y: [list(ns()) for _ in range(y)]
nas = lambda: stdin.readline().split()

from collections import defaultdict

n = ni()
xy = nan(n)

dic = defaultdict(int)
for i in range(n):
    cx, cy = xy[i]
    for j in range(i + 1, n):
        nx, ny = xy[j]
        dic[(abs(nx - cx), abs(ny - cy))] += 1

m = 0
for k, v in dic.items():
    m = max(v, m)

ans = n - m
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 fractions import gcd
from itertools import combinations # (string,3) 3回
from collections import deque
from collections import defaultdict
import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7

def readInts():
  return list(map(int,input().split()))
def main():
    n = int(input())
    dic = defaultdict(int)
    x = [0] * n;y = [0]*n;
    for i in range(n):
        x[i],y[i] = map(int,input().split())
    for i in range(n-1):
        a = abs(x[i+1] - x[i])
        b = abs(y[i+1] - y[i])
        dic[str(a)+"_"+str(b)] += 1
    maxv = -1
    for k,v in dic.items():
        maxv = max(maxv,v)
    print(n-1 - maxv + 1)
if __name__ == '__main__':
  main()

Submission status: Wrong Answer

Solution code:
import sys
from collections import Counter
from math import ceil
def input():
    return sys.stdin.readline()[:-1]
def gcd(a,b):
    if b == 0:
        return a
    return gcd(b,a%b)
def main():
    N = int(input())
    P = []
    for _ in range(N):
        P.append(list(map(int,input().split())))
    K = []
    if N == 1:
        print(1)
        exit(0)
    for k in range(N-1):
        for l in range(k+1,N):
            a, b, c, d = P[k][0], P[k][1], P[l][0], P[l][1]
            if [a,b] != [c,d]:
                e = c-a
                f = d-b
                while gcd(e,f) != 1:
                    t = gcd(e,f)
                    e //= t
                    f //= t
                K.append((e,f))
    C = Counter(K).most_common()
    F = [0]*N
    for k in range(N-1):
        for l in range(k+1,N):
            a, b, c, d = P[k][0], P[k][1], P[l][0], P[l][1]
            if [a,b] != [c,d]:
                e = c-a
                f = d-b
                while gcd(e,f) != 1:
                    t = gcd(e,f)
                    e //= t
                    f //= t
            if (e,f) == C[0][0]:
                F[k] = 1
    print(F.count(0))
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque
N=int(input())
point=[list(map(int,input().split())) for _ in range(N)]
ans=float("inf")
for i in range(N):
    for j in range(i+1,N):
        x1,y1=point[i]
        x2,y2=point[j]
        vec=[x1-x2,y1-y2]
        tree=[[] for _ in range(N)]
        col=[-1]*N
        for k in range(N):
            for l in range(k+1,N):
                xa, ya = point[k]
                xb, yb = point[l]
                if ((vec[0]==xa-xb)and(vec[1]==ya-yb))or((-vec[0]==xa-xb)and(-vec[1]==ya-yb)):
                    tree[k-1].append(l-1)
                    tree[l-1].append(k-1)
        for k in range(N):
            d=deque()
            if col[k]==-1:
                d.append(k)
            while len(d)>0:
                v=d.popleft()
                col[v]=k
                for l in tree[v]:
                    if col[l]==-1:
                        d.append(l)
        #print(col)
        #print(set(col))
        ans=min(ans,len(set(col)))
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

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

d = defaultdict(int)
for i, (xi, yi) in enumerate(xy):
  for j in range(i+1, N):
    xj, yj = xy[j]
    p, q = xi - xj, yi - yj
    d[(p, q)] += 1

ans = N
for k in d:
  ans = min(ans, N-d[k])

print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import combinations
from collections import Counter

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

if N != 1:
    delta = []
    for i, j in combinations(list(range(N)), 2):
        if xy[i][0] < xy[j][0]:
            p0 = xy[i][:]
            p1 = xy[j][:]
        else:
            p0 = xy[j][:]
            p1 = xy[i][:]
        delta.append((p1[0] - p0[0], p1[1] - p0[1]))
    cnt = Counter(delta)
    dlt = cnt.most_common()
    
def calc(dd):
    visited =set()
    c = 0
    for i in range(N):
        if xy[i] in visited:continue
        c += 1
        temp = [[xy[i], c]]
        while temp:
            q = temp.pop()
            for n in [1, -1]:
                x1, y1 = q[0][0] + n * dd[0], q[0][1] + n * dd[1]
                if not (x1, y1) in visited and (x1, y1) in xy:
                    temp.append([(x1, y1), q[1]])
                    visited.add((x1, y1))
    return c

if N == 1: print(1)
else:
    ans = []
    pre = dlt[0][1]
    for lst in dlt:
        if lst[1] == pre:
            ans.append(calc(lst[0]))
    print(min(ans))

Submission status: Wrong Answer

Solution code:
from itertools import combinations
from collections import Counter

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

if N != 1:
    delta = []
    for i, j in combinations(list(range(N)), 2):
        if xy[i][0] < xy[j][0]:
            p0 = xy[i][:]
            p1 = xy[j][:]
        else:
            p0 = xy[j][:]
            p1 = xy[i][:]
        delta.append((p1[0] - p0[0], p1[1] - p0[1]))
    cnt = Counter(delta)
    dlt = cnt.most_common()
    
def calc(dd):
    visited =set()
    c = 0
    for i in range(N):
        if xy[i] in visited:continue
        c += 1
        temp = [[xy[i], c]]
        while temp:
            q = temp.pop()
            for n in [1, -1]:
                x1, y1 = q[0][0] + n * dd[0], q[0][1] + n * dd[1]
                if not (x1, y1) in visited and (x1, y1) in xy:
                    temp.append([(x1, y1), q[1]])
                    visited.add((x1, y1))
    return c

if N == 1: print(1)
else:
    ans = []
    pre = dlt[0][1]
    for lst in dlt:
        if lst[1] == pre:
            ans.append(calc(lst[0]))
    print(max(ans))

Submission status: Wrong Answer

Solution code:
n = int(input())
xy = []
for _ in range(n):
    x, y = map(int, input().split())
    xy.append((x, y))
dxdy = {}
for i in range(n-1):
    for j in range(i+1, n):
        dx = xy[i][0] - xy[j][0]
        dy = xy[i][1] - xy[j][1]
        if dx<0:
            dx, dy = -dx, -dy
        if (dx, dy) in dxdy:
            dxdy[(dx, dy)] += 1
        else:
            dxdy[(dx, dy)] = 1
# print(n-max(dxdy.values()))

Submission status: Wrong Answer

Solution code:
n = int(input())
dat = []
for i in range(n):
    a,b = map(int, input().split())
    dat.append([a,b])
dat2 = []
if n == 1:
    print(0)
else:
    for i in range(n):
        x1, y1 = dat[i]
        for j in range(n):
            if i == j:
                continue
            x2, y2 = dat[j]
            dat2.append( (x1-x2, y1-y2) )
    import collections
    c = collections.Counter(dat2)
    #print(c)
    ta, tb = c.most_common(1)[0][0]
    res = 0
    for i in range(n):
        canwarp = False
        x1, y1 = dat[i]
        for j in range(n):
            if i == j:
                continue
            x2, y2 = dat[j]
            if x1-x2 == ta and  y1-y2 == tb:
                canwarp = True
        if canwarp:
            continue
        else:
            res += 1
    print(res)

Submission status: Wrong Answer

Solution code:
n = int(input())
dat = []
for i in range(n):
    a,b = map(int, input().split())
    dat.append([a,b])
dat2 = []
if n == 1:
    print(0)
else:
    for i in range(n):
        x1, y1 = dat[i]
        for j in range(i+1, n):
            x2, y2 = dat[j]
            dat2.append( (x1-x2, y1-y2) )
    import collections
    c = collections.Counter(dat2)
    #print(c)
    ta, tb = c.most_common(1)[0][0]
    res = 0
    for i in range(n):
        canwarp = False
        x1, y1 = dat[i]
        for j in range(i+1, n):
            x2, y2 = dat[j]
            if x1-x2 == ta and  y1-y2 == tb:
                canwarp = True
        if canwarp:
            continue
        else:
            res += 1
    print(res)

Submission status: Wrong Answer

Solution code:
n = int(input())
dat = []
for i in range(n):
    a,b = map(int, input().split())
    dat.append([a,b])
dat2 = []
if n == 1:
    print(0)
else:
    for i in range(n):
        x1, y1 = dat[i]
        for j in range(i+1, n):
            x2, y2 = dat[j]
            dat2.append( (x1-x2, y1-y2) )
    import collections
    c = collections.Counter(dat2)
    #print(c)
    print(n - c.most_common(1)[0][1])

Submission status: Wrong Answer

Solution code:
from collections import Counter 
INF = 10**20

N = int(input())
ball = []
for i in range(N):
    ball.append(tuple(map(int, input().split())))
    
div = set()
div_c = []
for i in range(N-1):
    a = ball[i+1][0]-ball[i][0]
    b = ball[i+1][1]-ball[i][1]
    
    if((a, b) not in div):
        div.add((a, b))
        div_c.append(tuple((a, b)))
ans = 1
c = Counter(div_c)
cs = sorted(c.items(), key=lambda x:x[1], reverse=True)
for i in range(1, len(cs)):
    ans += cs[i][1]

print(ans)

Submission status: Wrong Answer

Solution code:
ans=float("INF")
n=int(input())
l=[list(map(int,input().split())) for i in range(n)]
for i in range(n):
    for j in range(n):
        if i==j:continue
        p,q=l[i][0]-l[j][0],l[i][1]-l[j][1]
        ret=0
        pre=sorted(l,reverse=1,key=lambda x:p*x[0]+q*x[1])
        while pre:
            ret+=1
            x,y=pre.pop()
            while  [x+p,y+q] in pre:
                pre.remove([x+p,y+q])
                x,y=[x+p,y+q]
        ans=min(ans,ret)
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
x=[0]*n
y=[0]*n

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

p_=set([])
q_=set([])

for i in range(n):
    for j in range(n):
        if i!=j:
            p_.add(x[i]-x[j])
            q_.add(y[i]-y[j])


P=list(p_)
Q=list(q_)

cost=float('inf')

for p in P:
    for q in Q:
        if p!=0 or q!=0:
            cnt=0
            for i in range(n):
                for j in range(n):
                    if i!=j :
                        if x[i]-x[j]==p and y[i]-y[j]==q:
                            cnt+=1
            cost=min(cost,n-cnt)
            if cost == 0: cost += 1

print(cost)

Submission status: Wrong Answer

Solution code:
n=int(input())
x=[]
y=[]

for i in range(n):
    a,b=map(int,input().split())
    x.append(a)
    y.append(b)

p_=set([])
q_=set([])

for i in range(n):
    for j in range(n):
        if i!=j:
            p_.add(x[i]-x[j])
            q_.add(y[i]-y[j])


P=list(p_)
Q=list(q_)

cost=float('inf')

for p in P:
    for q in Q:
        if p!=0 or q!=0:
            cnt=0
            for i in range(n):
                for j in range(n):
                    if i!=j :
                        if x[i]-x[j]==p and y[i]-y[j]==q:
                            cnt+=1
            cost=min(cost,n-cnt)
if cost==0: cost+=1
print(cost)

Submission status: Wrong Answer

Solution code:
n=int(input())
x=[]
y=[]

for i in range(n):
    a,b=map(int,input().split())
    x.append(a)
    y.append(b)

p_=set([])
q_=set([])

for i in range(n):
    for j in range(n):
        if i!=j:
            p_.add(x[i]-x[j])
            q_.add(y[i]-y[j])


P=list(p_)
Q=list(q_)

cost=float('inf')

for p in P:
    for q in Q:
        if p!=0 or q!=0:
            cnt=0
            for i in range(n):
                for j in range(n):
                    if i!=j :
                        if x[i]-x[j]==p and y[i]-y[j]==q:
                            cnt+=1
            cost=min(cost,n-cnt)

print(cost)

Submission status: Wrong Answer

Solution code:
n=int(input())
x=[]
y=[]

for i in range(n):
    a,b=map(int,input().split())
    x.append(a)
    y.append(b)

p_=set([])
q_=set([])

for i in range(n):
    for j in range(n):
        if i!=j:
            p_.add(x[i]-x[j])
            q_.add(y[i]-y[j])


P=list(p_)
Q=list(q_)

cost=float('inf')

for p in P:
    for q in Q:
        if p!=0 and q!=0:
            cnt=0
            for i in range(n):
                for j in range(n):
                    if i!=j :
                        if x[i]-x[j]==p and y[i]-y[j]==q:
                            cnt+=1
            cost=min(cost,n-cnt)

print(cost)

Submission status: Wrong Answer

Solution code:
n=int(input())
x=[]
y=[]

for i in range(n):
    a,b=map(int,input().split())
    x.append(a)
    y.append(b)

p_=set([])
q_=set([])

for i in range(n):
    for j in range(n):
        if i!=j:
            p_.add(x[i]-x[j])
            q_.add(y[i]-y[j])


P=list(p_)
Q=list(q_)

cost=float('inf')

for p in P:
    for q in Q:
        cnt=0
        for i in range(n):
            for j in range(n):
                if i!=j :
                    if x[i]-x[j]==p and y[i]-y[j]==q:
                        cnt+=1
        cost=min(cost,n-cnt)

print(cost)

Submission status: Wrong Answer

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
from itertools import combinations
from collections import Counter
def main():
    n=int(input())
    if n==1:
        print(1)
        sys.exit()
    XY=[tuple(map(int,input().split())) for i in range(n)]
    lis=list(combinations(XY,2))
    PQ=[]
    for l in lis:
        if l[0][0]<l[1][0]:
            PQ.append((l[1][0]-l[0][0],l[1][1]-l[0][1]))
        else:
            PQ.append((l[0][0]-l[1][0],l[0][1]-l[1][1])) 
    x=Counter(PQ).most_common(1)[0][1]
    print(n-x)

if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque
n=int(input())
ans=10**18
xy=[list(map(int,input().split())) for _ in range(n)]
d=dict()
for i in range(n):
    a,b=xy[i]
    d[(a,b)]=i
def bfs(s,p,q,visited):
    queue=deque([s])
    visited[s]=1
    while queue:
        x=queue.popleft()
        a,b=xy[x]
        if (a+p,b+q) in d:
            idx=d[(a+p,b+q)]
            if visited[idx]==0:
                visited[idx]=1
                queue.append(idx)
        if (a-p,b-q) in d:
            idx=d[(a-p,b-q)]
            if visited[idx]==0:
                visited[idx]=1
                queue.append(idx)
for i in range(n-1):
    ai,bi=xy[i]
    for j in range(i+1,n):
        aj,bj=xy[j]
        p,q=ai-aj,bi-bj
        cnt=0
        visited=[0]*n
        for k in range(n):
            if visited[k]==0:
                bfs(k,p,q,visited)
                cnt+=1
        ans=min(ans,cnt)
print(ans)
#print(d)

Submission status: Wrong Answer

Solution code:
n=int(input())
xys=[list(map(int,input().split())) for _ in range(n)]
vec = []
pqs = []
for i in range(n):
    for j in range(i+1,n):
        pqs.append([abs(xys[i][0]-xys[j][0]),abs(xys[i][1]-xys[j][1])])
pqs.sort()
import collections

cnt = 1
cntMax = 0
for i in range(1,len(pqs)+1):
    if i == len(pqs):
        cntMax = max(cntMax,cnt)
    elif pqs[i] == pqs[i-1]:
        cnt += 1
    else:
        cntMax = max(cntMax,cnt)
        cnt = 1
print(n-cntMax)

Submission status: Wrong Answer

Solution code:
n=int(input())
ab = []
for _ in range(n):
    a, b = (int(x) for x in input().split())
    ab.append([a, b])

ab.sort()
#print(ab)

sa = []

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

ans = 10000000000

for x,y in ab:
    for c , d in sa:
        memo = 1
        for k in range(n-1):
            x += c
            y += d
            if [x,y] not in ab:
                memo += 1
        ans = min(memo, ans)
        
print(ans)

Submission status: Wrong Answer

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

n = int(input())
X, Y = [], []
for _ in range(n):
    xi, yi = map(int, input().split())
    X.append(xi)
    Y.append(yi)
# print(X)
# print(Y)

# PQをバラすとだめ？
posPQ = []
score = int(1e18)
for i in range(n):
    xi, yi = X[i], Y[i]
    for j in range(n):
        if i == j:
            continue
        xj, yj = X[j], Y[j]
        p = xj - xi
        q = yj - yi

        # posPQ.append((dx, dy))
        count = n
        for k in range(n):
            for l in range(n):
                if X[l] - X[k] == p and Y[l] - Y[k] == q:
                    count -= 1
        # print(p, q, count)
        score = min(score, count)
print(score)

Submission status: Wrong Answer

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

n = int(input())
X, Y = [], []
for _ in range(n):
    xi, yi = map(int, input().split())
    X.append(xi)
    Y.append(yi)
# print(X)
# print(Y)

posPQ = []

for i in range(n):
    xi, yi = X[i], Y[i]
    for j in range(n):
        if i == j:
            continue
        xj, yj = X[j], Y[j]
        dx = xj - xi
        dy = yj - yi

        if (dx, dy) not in posPQ:
            posPQ.append((dx, dy))

score = int(1e18)
for p, q in posPQ:
    count = n
    for i in range(n):
        for j in range(n):
            if X[i] - X[j] == p and Y[i] - Y[j] == q:
                count -= 1
    # print(p, q, count)
    score = min(score, count)
print(score)

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    from collections import defaultdict
    input = sys.stdin.readline
    N = int(input())
    if N == 1:
        print(1)
        exit()
    XY = [0] * N
    for i, (x, y) in enumerate([[int(x) for x in input().strip().split()] for _ in range(N)]):
        XY[i] = (x, y)
    XY.sort(key=lambda x:(x[0], x[1]))
    print(XY)
    for i in range(len(XY)-1):
        print(XY[i+1][0]-XY[i][0], XY[i+1][1]-XY[i][1])
    dic = defaultdict(int)
    for d in range(1, N):
        for i in range(N-d):
            dic[(XY[i+d][0]-XY[i][0], XY[i+d][1]-XY[i][1])] += 1
            dic[(XY[i][0]-XY[i+d][0], XY[i][1]-XY[i+d][1])] += 1

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

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    from collections import defaultdict
    input = sys.stdin.readline
    N = int(input())
    if N == 1:
        print(1)
        exit()
    XY = [0] * N
    for i, (x, y) in enumerate([[int(x) for x in input().strip().split()] for _ in range(N)]):
        XY[i] = (x, y)
    XY.sort(key=lambda x:(x[0], x[1]))
    dic = defaultdict(int)
    for d in range(1, N):
        for i in range(N-d):
            if (XY[i+d][1] >= XY[i][1] and XY[i+d][0] > XY[i][0]) or (XY[i+d][1] > XY[i][1] and XY[i+d][0] >= XY[i][0]):
                t = 1
            else:
                t = 0
            dic[(XY[i+d][0]-XY[i][0], XY[i+d][1]-XY[i][1])] += t
            
    print(N-max(dic.values()))

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    from collections import defaultdict
    input = sys.stdin.readline
    N = int(input())
    if N == 1:
        print(1)
        exit()
    XY = [0] * N
    for i, (x, y) in enumerate([[int(x) for x in input().strip().split()] for _ in range(N)]):
        XY[i] = (x, y)

    dic = defaultdict(int)
    for d in range(1, N):
        for i in range(N-d):
            if (XY[i+d][1] >= XY[i][1] and XY[i+d][0] > XY[i][0]) or (XY[i+d][1] > XY[i][1] and XY[i+d][0] >= XY[i][0]):
                t = 1
            else:
                t = 0
            dic[(XY[i+d][0]-XY[i][0], XY[i+d][1]-XY[i][1])] += t
            
    print(N-max(dic.values()))

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    from collections import defaultdict
    input = sys.stdin.readline
    N = int(input())
    if N == 1:
        print(1)
        exit()
    XY = [0] * N
    for i, (x, y) in enumerate([[int(x) for x in input().strip().split()] for _ in range(N)]):
        XY[i] = (x, y)

    dic = defaultdict(int)
    for d in range(1, N):
        for i in range(N-d):
            if XY[i+d][1] > XY[i][1]:
                t = 1
            else:
                t = 0
            dic[(XY[i+d][0]-XY[i][0], XY[i+d][1]-XY[i][1])] += t
            
    print(N-max(dic.values()))

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    from collections import defaultdict
    input = sys.stdin.readline
    N = int(input())
    if N == 1:
        print(1)
        exit()
    XY = sorted([tuple([int(x) for x in input().strip().split()]) for _ in range(N)], key=lambda x: x[0])
    dic = defaultdict(int)
    for d in range(1, N):
        for i in range(N-d):
            if XY[i+d][1] > XY[i][1] and XY[i][0] != XY[i+d][0]:
                t = 1
            else:
                t = 0
            dic[(XY[i+d][0]-XY[i][0], XY[i+d][1]-XY[i][1])] += 1
            
    print(N-max(dic.values()))

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    from collections import defaultdict
    input = sys.stdin.readline
    N = int(input())
    if N == 1:
        print(1)
        exit()
    XY = sorted([tuple([int(x) for x in input().strip().split()]) for _ in range(N)], key=lambda x: x[0])
    dic = defaultdict(int)
    for d in range(1, N):
        for i in range(N-d):
            if XY[i+d][1] > XY[i][1]:
                t = 1
            else:
                t = 0
            dic[(XY[i+d][0]-XY[i][0], XY[i+d][1]-XY[i][1])] += 1
            
    print(N-max(dic.values()))

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import collections

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

div = []
    
for i in range(1, N):
    div.append(tuple((X[i-1][0]-X[i][0], X[i-1][1]-X[i][1])))
c = collections.Counter(div)
c_s = sorted(c.items(), key=lambda x:x[1], reverse = True)

ans = 1
for i in range(1, len(c_s)):
    ans += c_s[i][1]
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
INF = 114514191981036436433-4
xy = []
for i in range(n):
    x,y = map(int,input().split())
    xy.append((x,y))
    
a = INF
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]
        ans = n
        
        for k in range(n):
            for l in range(n):
                xx,yy = xy[k][0] - xy[l][0] , xy[k][1] - xy[l][1]
                if xx == p and yy == q:
                    ans -= 1
                    
        a = min(a,ans)
        
print(a)

Submission status: Wrong Answer

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

    d = {}
    for i in range(N):
        tmp = set()
        for j in range(N):
            if i == j:
                continue
            dx = xy[i][0] - xy[j][0]
            dy = xy[i][1] - xy[j][1]

            if (dx, dy) in tmp:
                continue
            if (dx, dy) not in d:
                d[(dx, dy)] = 1
            else:
                d[(dx, dy)] += 1
            tmp.add((dx, dy))

    d = sorted(d.items(), key=lambda x: x[1], reverse=True)
    cnt = d[0][1]
    print(N - cnt)

Submission status: Wrong Answer

Solution code:
import sys


def input():
    return sys.stdin.readline().strip()


sys.setrecursionlimit(10 ** 9)


def main():
    N = int(input())
    XY = [list(map(int, input().split())) for _ in range(N)]
    P = []
    Q = []
    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]
            P.append(p)
            Q.append(q)
    ans = float("inf")

    for p, q in zip(P, Q):
        a = N
        for i in range(N):
            x, y = XY[i][0], XY[i][1]
            if [x + p, y + q] in XY:
                a -= 1
        if a < ans:
            ans = a
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import Counter

if __name__ == "__main__":
    n = int(input())
    pos = list()
    for i in range(n):
        pos.append(list(map(int, input().split())))

    # まず1個のボールを最初選びそこから次のボールを選んだときの距離をp,qとして
    # それぞれの組み合わせの最汎値を求める
    dist = list()
    for i in range(n):
        for j in range(n):
            if i < j:
                tmp = (pos[j][0] - pos[i][0], pos[j][1]-pos[i][1])
                dist.append(tmp)

    # most_comon(n)とすると、最も出現回数が多い順からn要素を抽出する
    pq = Counter(dist).most_common(1)

    print(n - pq[0][1] if n != 1 else 1)

Submission status: Wrong Answer

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

#pq=[[0]*n for _ in range(n)]

#初期値が0の辞書
from collections import defaultdict
pq_x = defaultdict(lambda: set([])) 
pq_y = defaultdict(lambda: set([])) 

for i,from_xy in enumerate(zahyou):
    for j,to_xy in enumerate(zahyou[i+1:]):
        #print(i,j+i+1)
        pq_x[(from_xy[0]-to_xy[0],from_xy[1]-to_xy[1])].add((i))
        pq_y[(from_xy[0]-to_xy[0],from_xy[1]-to_xy[1])].add((j+i+1))

result=10**9
for item in pq_x.keys():
    len_x=len(list(pq_x[item]))
    len_y=len(list(pq_y[item]))
    min_xy=min(len_x,len_y)
    temp=max(n-min_xy,1)

    result=min(result,temp)

print(result)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
N = int(input())
d = defaultdict(int)
X, Y = [0]*N, [0]*N
for i in range(N):
  X[i], Y[i] = map(int, input().split())
for i in range(N):
  for j in range(i):
    d[(X[i] - X[j], Y[i] - Y[j])] += 1
print(N - max(d.values(), default=0))

Submission status: Wrong Answer

Solution code:
n = int(input())
xy = sorted([tuple(map(int,input().split())) for i in range(n)])
if n==1:
    print(1)
    exit()
dif = []
for i in range(n-1):
    dif.append(tuple([xy[i+1][0]-xy[i][0],xy[i+1][1]-xy[i][1]]))
from collections import Counter
c = Counter(dif)
print(n-c[list(c)[0]])

Submission status: Wrong Answer

Solution code:
import copy
import math

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

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

m = N
for i in range(N - 1):
    for j in range(i + 1, N):
        p = xy[i][0] - xy[j][0]
        q = xy[i][1] - xy[j][1]
        cnt = 0
        tosee = copy.copy(xy)
        while tosee:
            el = tosee[0]
            dfs(el,p,q)
            cnt += 1
            # print(tosee)
        m = min(cnt, m)
        # print(p, q, group)
print(m)