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())
XY = [list(map(int,input().split())) for _ in range(N)]

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

        PQ = (x2-x1, y2-y1)

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

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

Submission status: Wrong Answer

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

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

        PQ = (x2-x1, y2-y1)

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

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

Submission status: Wrong Answer

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

if n == 1:
    print(0)
    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]))

ans = float("inf")
for p, q in pq:
    tmp = 0
    for i in range(n):
        for j in range(n):
            if i != j and (p, q) == (xy[i][0] - xy[j][0] ,xy[i][1] - xy[j][1]):
                tmp += 1
        ans = min(ans, n - tmp)
            
print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    a = [None]*n
    for i in range(n):
        x, y = map(int, input().split())
        a[i] = [x, y]
    p, q = 0, 0
    cnt = 0
    for i in range(n):
        for j in range(i+1, n):
            sp, sq = abs(a[i][0]-a[j][0]), abs(a[i][1]-a[j][1])
            scnt = 0
            for k in range(n):
                for l in range(k+1, n):
                    if abs(a[k][0]-a[l][0]) == sp and abs(a[k][1]-a[l][1]) == sq:
                        scnt += 1
            if scnt > cnt:
                cnt = scnt
                p = sp
                q = sq
    print(n-cnt)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import Counter
n= int(input())
xy=[[int(x) for x in input().split()] for _ in range(n)]
gr = [[[0,0]for _ in range(n)]for _ in range(n)]
for i in range(n):
  a,b = xy[i]
  for j in range(n):
    gr[i][j] = [xy[j][0]-a,xy[j][1]-b]
gr1 = []
for i in gr:
  for j in i:
    gr1.append(tuple(j))
#print(gr1)
c = Counter(gr1)
l,f = c.most_common()[0]
if l!=(0,0):
  print(n-f)

Submission status: Wrong Answer

Solution code:
from collections import Counter
n= int(input())
xy=[[int(x) for x in input().split()] for _ in range(n)]
gr = [[[0,0]for _ in range(n)]for _ in range(n)]
for i in range(n):
  a,b = xy[i]
  for j in range(n):
    gr[i][j] = [abs(xy[j][0]-a),abs(xy[j][1]-b)]
gr1 = []
for i in gr:
  for j in i:
    gr1.append(tuple(j))
#print(gr1)
c = Counter(gr1)
l,f = c.most_common()[0]
print(n-f//2)

Submission status: Wrong Answer

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
print(ans)

Submission status: Wrong Answer

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))}

    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: Wrong Answer

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(i+1,N):
                slope = (pos[i][0]-pos[j][0],pos[i][1]-pos[j][1])
                if slope[0]*slope[1] != 0:
                    d[slope] += 1
        if len(d) == 0:
            print(N)
        else:
            print(N-max(d.values()))

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.buffer.readline
from itertools import combinations

def main():
    N = int(input())
    pos = [list(map(int,input().split())) for _ in range(N)]
    prov = [i for i in range(N)]
    
    ans = N
    for x,y in combinations(prov,2):
        if (pos[x][0] == pos[y][0] or pos[x][1] == pos[y][1]):
            continue
        count = 0
        use = [False for _ in range(N)]
        for i in range(N):
            if not use[i]:
                count += 1
                use[i] = True
                for j in range(i+1,N):
                    if (pos[x][1]-pos[y][1])*(pos[i][0]-pos[j][0]) == (pos[x][0]-pos[y][0])*(pos[i][1]-pos[j][1]):
                        use[j] = True
        ans = min(ans,count)

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.buffer.readline
from itertools import combinations

def main():
    N = int(input())
    pos = [list(map(int,input().split())) for _ in range(N)]
    prov = [i for i in range(N)]
    
    ans = 10**2
    for x,y in combinations(prov,2):
        count = 0
        use = [False for _ in range(N)]
        for i in range(N):
            if not use[i]:
                count += 1
                use[i] = True
                for j in range(i+1,N):
                    if (pos[x][1]-pos[y][1])*(pos[i][0]-pos[j][0]) == (pos[x][0]-pos[y][0])*(pos[i][1]-pos[j][1]):
                        use[j] = True
        ans = min(ans,count)

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
l = [tuple(map(int, input().split())) for _ in range(N)]
l.sort()
m = []

for i in range(N-1):
    x1, y1 = l[i]
    x2, y2 = l[i+1]
    m.append((x1-x2, y1-y2))
    m.append((x2-x1, y2-y1))

ans = 10**10

for p, q in m:
    v = 1
    for i in range(N-1):
        a, b = l[i]
        x, y = l[i+1]
        if not (x==a-p and y==b-q):
            v += 1
    ans = min(ans, v)

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
l = [tuple(map(int, input().split())) for _ in range(N)]
l.sort()
m = []

for i in range(N-1):
    x1, y1 = l[i]
    x2, y2 = l[i+1]
    m.append((x1-x2, y1-y2))

ans = 10**10

for p, q in m:
    v = 1
    for i in range(N-1):
        a, b = l[i]
        x, y = l[i+1]
        if not (x==a-p and y==b-q):
            v += 1
    ans = min(ans, v)

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
l = [tuple(map(int, input().split())) for _ in range(N)]
m = []

for i in range(N-1):
    x1, y1 = l[i]
    x2, y2 = l[i+1]
    m.append((x1-x2, y1-y2))

ans = 10**10

for p, q in m:
    v = 1
    for i in range(N-1):
        a, b = l[i]
        x, y = l[i+1]
        if not (x==a-p and y==b-q):
            v += 1
    ans = min(ans, v)

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
l = [tuple(map(int, input().split())) for _ in range(N)]
m = []

for i in range(N-1):
    x1, y1 = l[i]
    x2, y2 = l[i+1]
    m.append((x1-x2, y1-y2))

ans = 10**10

for p, q in m:
    v = 0
    for i in range(N-1):
        if i==0:
            v += 1
            continue

        a, b = l[i]
        x, y = l[i+1]
        if not (x==a-p and y==b-q):
            v += 1
    ans = min(ans, v)

print(ans)

Submission status: Wrong Answer

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:
    if a>c:
      e=a-c
      f=b-d
    else:
      e=c-a
      f=d-b
    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//2)

Submission status: Wrong Answer

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)]

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: Wrong Answer

Solution code:
from sys import stdin
n = int(stdin.readline().rstrip())
li = [list(map(int,stdin.readline().rstrip().split())) for _ in range(n)]
x = []
y = []
for i,j in li:
    x.append(i)
    y.append(j)
x.sort()
y.sort()
x_sa = [x[i+1]-x[i] for i in range(n-1)]
y_sa = [y[i+1]-y[i] for i in range(n-1)]
mi = 10**10
li2 = sorted(li,key=lambda x:(x[0]))
li3 = sorted(li,key=lambda x:(x[1]))
for i in x_sa:
    for j in y_sa:
        if i == 0 and j == 0:
            continue
        point2 = 1
        point3 = 1
        for k in range(n-1):
            if li2[k+1][0]-li2[k][0] != i or li2[k+1][1]-li2[k][1] != j:
                point2 += 1
            if li3[k+1][0]-li3[k][0] != i or li3[k+1][1]-li3[k][1] != j:
                point3 += 1
        mi = min(mi,point2,point3)
print(mi)

Submission status: Wrong Answer

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])
        b = (-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 b not in diff:
            diff[b] = 1
        else:
            diff[b] += 1
if diff:
    maxv = max(diff.values())
    print(N-maxv)
else:
    print(N-1)

Submission status: Wrong Answer

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-1)

Submission status: Wrong Answer

Solution code:
N = int(input())
ab = [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-1)

Submission status: Wrong Answer

Solution code:
N = int(input())
ab = [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: Wrong Answer

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):
        dist = (x[i]-x[j],y[i]-y[j])
        d[dist] = d.get(dist,0) + 1

print(n-max(d.values()))

Submission status: Wrong Answer

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

set_cover = []
for i in range(n):
    for j in range(i+1, n):
        s = 0
        s |= 1 << i
        p = xyl[j][0] - xyl[i][0]
        q = xyl[j][1] - xyl[i][1]
        for k in range(n):
            if p == 0:
                if (xyl[k][1] - xyl[i][1]) % q == 0 and xyl[k][1] - xyl[i][1] > 0 and xyl[k][0] - xyl[i][0] == 0:
                    s |= 1 << k
            elif q == 0:
                if (xyl[k][0] - xyl[i][0]) % p == 0 and xyl[k][0] - xyl[i][0] > 0 and xyl[k][1] - xyl[i][1] == 0:
                    s |= 1 << k
            elif (xyl[k][0] - xyl[i][0]) % p == 0 and xyl[k][0] - xyl[i][0] > 0:
                m = (xyl[k][0] - xyl[i][0]) // p
                if m * q == (xyl[k][1] - xyl[i][1]):
                    s |= 1 << k
            else:
                continue
        set_cover.append(s)

from collections import defaultdict
dp = defaultdict(lambda : float("inf"))

from copy import deepcopy
dp[0] = 0
for s in set_cover:
    c_dp = deepcopy(dp)
    for i in c_dp:
        if i|s < 2**n:
            dp[i|s] = min(dp[i]+1, dp[i|s])
print(dp[2**n-1])

Submission status: Wrong Answer

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

set_cover = []
for i in range(n):
    for j in range(i+1, n):
        s = 0
        s |= 1 << i
        p = xyl[j][0] - xyl[i][0]
        q = xyl[j][1] - xyl[i][1]
        for k in range(n):
            if p == 0:
                if (xyl[k][1] - xyl[i][1]) % q == 0 and xyl[k][1] - xyl[i][1] > 0 and xyl[k][0] - xyl[i][0] == 0:
                    s |= 1 << k
            elif q == 0:
                if (xyl[k][0] - xyl[i][0]) % p == 0 and xyl[k][0] - xyl[i][0] > 0 and xyl[k][1] - xyl[i][1] == 0:
                    s |= 1 << k
            elif (xyl[k][0] - xyl[i][0]) % p == 0 and xyl[k][0] - xyl[i][0] > 0:
                m = (xyl[k][0] - xyl[i][0]) // p
                if m * q == (xyl[k][1] - xyl[i][1]):
                    s |= 1 << k
            else:
                continue
        set_cover.append(s)

dp = [float("inf") for i in range(2**n+1)]
dp[0] = 0
for s in set_cover:
    for i in range(2**n):
        dp[i|s] = min(dp[i]+1, dp[i|s])
print(dp[-2])

Submission status: Wrong Answer

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]])
m=len(a)
for k in range(m):
    ans=0
    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: Wrong Answer

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):
        a.append([l[i][0]-l[j][0],l[i][1]-l[j][1]])
a.sort()
b=[]
for i in range(n):
    if a[i]!=[0,0]:
        b.append(a[i])
if b:
    c=0
    d=1
    x=0
    for i in range(len(b)):
        if x==b[i]:
            d+=1
        elif x!=b[i]:
            x=b[i]
            c=max(c,d)
            d=1
    c=max(c,d)
    print(n-c)
else:
    print(n)

Submission status: Wrong Answer

Solution code:
n=int(input())
l=[list(map(int,input().split())) for i in range(n)]
l.sort()
a=[]
for i in range(n-1):
    a.append([l[i+1][0]-l[i][0],l[i+1][1]-l[i][1]])
a.sort()
aa=[]
for i in range(n-1):
    if a[i]!=[0,0]:
        aa.append(a[i])
c=0
d=1
x=0
for i in range(len(aa)):
    if x==aa[i]:
        d+=1
    elif x!=aa[i]:
        x=aa[i]
        c=max(c,d)
        d=1
c=max(c,d)
if aa:
    print(n-c)
else:
    print(n)

Submission status: Wrong Answer

Solution code:
n=int(input())
l=[list(map(int,input().split())) for i in range(n)]
l.sort()
a=[]
for i in range(n-1):
    a.append([l[i+1][0]-l[i][0],l[i+1][1]-l[i][1]])
a.sort()
aa=[]
for i in range(n-1):
    if a[i]!=[0,0]:
        aa.append(a[i])
c=0
d=1
x=0
for i in range(len(aa)):
    if x==aa[i]:
        d+=1
    elif x!=aa[i]:
        x=a[i]
        c=max(c,d)
        d=1
c=max(c,d)
if aa:
    print(n-c)
else:
    print(n)

Submission status: Wrong Answer

Solution code:
n=int(input())
l=[list(map(int,input().split())) for i in range(n)]
l.sort()
a=[]
for i in range(n-1):
    a.append([l[i+1][0]-l[i][0],l[i+1][1]-l[i][1]])
a.sort()
c=0
d=1
x=0
for i in range(n-1):
    if x==a[i]:
        d+=1
    elif x!=a[i]:
        x=a[i]
        c=max(c,d)
        d=1
c=max(c,d)
print(n-c)

Submission status: Wrong Answer

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: Wrong Answer

Solution code:
n = int(input())
lis = [list(map(int,input().split())) for i in range(n)]
lis.sort(key = lambda x:x[0])
ans = n
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: Wrong Answer

Solution code:
n = int(input())
lis = [list(map(int,input().split())) for i in range(n)]
lis.sort(key = lambda x:x[0])
ans = n
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 li and a[0]+p == li[0][0] and a[1]+q == li[0][1]:
                a = li.pop(0)
            cnt += 1
        ans = min(ans,cnt)
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
lis = [list(map(int,input().split())) for i in range(n)]
lis.sort(key = lambda x:x[0])
ans = n
for i in range(n-1):
    for j in range(i+1,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 li and a[0]+p == li[0][0] and a[1]+q == li[0][1]:
                a = li.pop(0)
            cnt += 1
        ans = min(ans,cnt)
print(ans)

Submission status: Wrong Answer

Solution code:



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

"""
・あるボールから（p,q）の移動で別のボールに移れるならコストが０、そうでなければ１
　→あるボールの位置(x,y) + (p,q) の位置にボールがあるかどうか、全てのボールについて確認する。なければコスト＋１
・p,qの選び方は、全ボールの間隔を試すと行けそう(N <= 50 なので間に合いそう)

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

pq = []
for i in range(N):
    for j in range(N):
        if i != j:
            # 同じ間隔（同じp,qのパターン）が起こりうるのでdictで管理するほうがいいかも
            pq.append((xy[i][0] - xy[j][0], xy[i][1] - xy[j][1]))

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

    ans = min(ans, cost)

print(cost)

Submission status: Wrong Answer

Solution code:



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

"""
・あるボールから（p,q）の移動で別のボールに移れるならコストが０、そうでなければ１
　→あるボールの位置(x,y) + (p,q) の位置にボールがあるかどうか、全てのボールについて確認する。なければコスト＋１
・p,qの選び方は、全ボールの間隔を試すと行けそう(N <= 50 なので間に合いそう)

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

pq = []
for i in range(N):
    for j in range(N):
        if i != j:
            # 同じ間隔（同じp,qのパターン）が起こりうるのでdictで管理するほうがいいかも
            pq.append((xy[i][0] - xy[j][0], xy[i][1] - xy[j][1]))

xy = set(xy)
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(cost)

Submission status: Wrong Answer

Solution code:



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

"""
・あるボールから（p,q）の移動で別のボールに移れるならコストが０、そうでなければ１
　→あるボールの位置(x,y) + (p,q) の位置にボールがあるかどうか、全てのボールについて確認する。なければコスト＋１
・p,qの選び方は、全ボールの間隔を試すと行けそう(N <= 50 なので間に合いそう)

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

pq = []
for i in range(N):
    for j in range(N):
        if i != j:
            # 同じ間隔（同じp,qのパターン）が起こりうるのでdictで管理するほうがいいかも
            pq.append((xy[i][0] - xy[j][0], xy[i][1] - xy[j][1]))

ans = 500
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(cost)

Submission status: Wrong Answer

Solution code:



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

"""
・あるボールから（p,q）の移動で別のボールに移れるならコストが０、そうでなければ１
　→あるボールの位置(x,y) + (p,q) の位置にボールがあるかどうか、全てのボールについて確認する。なければコスト＋１
・p,qの選び方は、全ボールの間隔を試すと行けそう(N <= 50 なので間に合いそう)

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

pq = []
for i in range(N):
    for j in range(N):
        if i != j:
            # 同じ間隔（同じp,qのパターン）が起こりうるのでdictで管理するほうがいいかも
            pq.append((xy[i][0] - xy[j][0], xy[i][1] - xy[j][1]))

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

    ans = min(ans, cost)

print(cost)

Submission status: Wrong Answer

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

PQ=[]
for a,b in permutations(A,2):
    if a!=b:
        PQ.append([a[0]-b[0],a[1]-b[1]])

cnt=50
for p,q in PQ:
    ans1=1
    for i in range(n-1):
        if [A[i][0]-A[i+1][0],A[i][1]-A[i+1][1]]==[p,q]:continue
        else:ans1 +=1
    ans2=1
    for i in reversed(range(1,n)):
        if [A[i][0]-A[i-1][0],A[i][1]-A[i-1][1]]==[p,q]:continue
        else:ans2 +=1
    cnt=min(cnt,ans1,ans2)

print(cnt if n!=1 else 1)

Submission status: Wrong Answer

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

PQ=[]
for a,b in permutations(A,2):
    if a!=b:
        PQ.append([a[0]-b[0],a[1]-b[1]])

cnt=50
for p,q in PQ:
    ans=1
    for i in range(n-1):
        if [A[i][0]-A[i+1][0],A[i][1]-A[i+1][1]]==[p,q]:continue
        else:ans +=1
    cnt=min(cnt,ans)

print(cnt if n!=1 else 1)

Submission status: Wrong Answer

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

PQ=[]
for a,b in permutations(A,2):
    if a!=b:
        PQ.append([a[0]-b[0],a[1]-b[1]])

cnt=50
for p,q in PQ:
    ans=1
    for i in range(n-1):
        if [A[i][0]-A[i+1][0],A[i][1]-A[i+1][1]]==[p,q]:continue
        else:ans +=1
    cnt=min(cnt,ans)

print(cnt)

Submission status: Wrong Answer

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

PQ=[]
for a,b in permutations(A,2):
    if a!=b:
        PQ.append([a[0]-b[0],a[1]-b[1]])

cnt=50
for p,q in PQ:
    ans=1
    for i in range(n-1):
        if [A[i][0]-A[i+1][0],A[i][1]-A[i+1][1]]==[p,q]:continue
        else:ans +=1
    cnt=min(cnt,ans)
print(cnt)

Submission status: Wrong Answer

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(ans2)

Submission status: Wrong Answer

Solution code:
# y = ax + b上に最も多く等間隔で並ぶもの以外にコストを支払う
# 適当に２つ選んだとき、残ったものがいくつその条件を満たすかを数え、最も多いものを採用

# とか考えたけど実装できず 解答を見る
# ケチケチせずに果敢にN^4で全探索するらしい

n = int(input())
xs, ys = [], []
for _ in range(n):
    x, y = map(int, input().split())
    xs.append(x)
    ys.append(y)
max_count = -1
for i in range(n):
    for j in range(i, n):
        if i == j or xs[i] == xs[j]:
            continue
        # 差はi-jとする
        p, q = xs[i] - xs[j], ys[i] - ys[j]
        # print("p, q = {} {}".format(p, q))
        count = 0
        # ここから全探索
        for k in range(n):
            for l in range(n):
                # print("p, q vs... {}, {}".format(xs[k] - xs[l], ys[k] - ys[l]))
                if p == xs[k] - xs[l] and q == ys[k] - ys[l]:
                    continue
                else:
                    # print("yay!!")
                    count += 1
        # print("count result = {}".format(count))
        max_count = max(max_count, count)
print(max(1, n - max_count))

Submission status: Wrong Answer

Solution code:
# y = ax + b上に最も多く等間隔で並ぶもの以外にコストを支払う
# 適当に２つ選んだとき、残ったものがいくつその条件を満たすかを数え、最も多いものを採用

# とか考えたけど実装できず 解答を見る
# ケチケチせずに果敢にN^4で全探索するらしい

n = int(input())
xs, ys = [], []
for _ in range(n):
    x, y = map(int, input().split())
    xs.append(x)
    ys.append(y)
max_count = -1
for i in range(n):
    for j in range(i, n):
        if i == j or xs[i] == xs[j]:
            continue
        # 差はi-jとする
        p, q = xs[i] - xs[j], ys[i] - ys[j]
        if p == 0 and q == 0:
            continue
        # print("p, q = {} {}".format(p, q))
        count = 0
        # ここから全探索
        for k in range(n):
            for l in range(n):
                # print("p, q vs... {}, {}".format(xs[k] - xs[l], ys[k] - ys[l]))
                if p == xs[k] - xs[l] and q == ys[k] - ys[l]:
                    # print("yay!!")
                    count += 1
        # print("count result = {}".format(count))
        max_count = max(max_count, count)
print(max(1, n - max_count))

Submission status: Wrong Answer

Solution code:
# y = ax + b上に最も多く等間隔で並ぶもの以外にコストを支払う
# 適当に２つ選んだとき、残ったものがいくつその条件を満たすかを数え、最も多いものを採用

# とか考えたけど実装できず 解答を見る
# ケチケチせずに果敢にN^4で全探索するらしい

n = int(input())
xs, ys = [], []
for _ in range(n):
    x, y = map(int, input().split())
    xs.append(x)
    ys.append(y)
max_count = -1
for i in range(n):
    for j in range(i, n):
        if i == j or xs[i] == xs[j]:
            continue
        # 差はi-jとする
        p, q = xs[i] - xs[j], ys[i] - ys[j]
        if p == 0 or q == 0:
            continue
        # print("p, q = {} {}".format(p, q))
        count = 0
        # ここから全探索
        for k in range(n):
            for l in range(n):
                # print("p, q vs... {}, {}".format(xs[k] - xs[l], ys[k] - ys[l]))
                if p == xs[k] - xs[l] and q == ys[k] - ys[l]:
                    # print("yay!!")
                    count += 1
        # print("count result = {}".format(count))
        max_count = max(max_count, count)
print(max(1, n - max_count))

Submission status: Wrong Answer

Solution code:
# y = ax + b上に最も多く等間隔で並ぶもの以外にコストを支払う
# 適当に２つ選んだとき、残ったものがいくつその条件を満たすかを数え、最も多いものを採用

# とか考えたけど実装できず 解答を見る
# ケチケチせずに果敢にN^4で全探索するらしい

n = int(input())
xs, ys = [], []
for _ in range(n):
    x, y = map(int, input().split())
    xs.append(x)
    ys.append(y)
max_count = -1
for i in range(n):
    for j in range(i, n):
        if i == j or xs[i] == xs[j]:
            continue
        # 差はi-jとする
        p, q = xs[i] - xs[j], ys[i] - ys[j]
        # print("p, q = {} {}".format(p, q))
        count = 0
        # ここから全探索
        for k in range(n):
            for l in range(n):
                # print("p, q vs... {}, {}".format(xs[k] - xs[l], ys[k] - ys[l]))
                if p == xs[k] - xs[l] and q == ys[k] - ys[l]:
                    # print("yay!!")
                    count += 1
        # print("count result = {}".format(count))
        max_count = max(max_count, count)
print(max(1, n - max_count))

Submission status: Wrong Answer

Solution code:
# y = ax + b上に最も多く等間隔で並ぶもの以外にコストを支払う
# 適当に２つ選んだとき、残ったものがいくつその条件を満たすかを数え、最も多いものを採用
n = int(input())
xs, ys = [], []
for _ in range(n):
    x, y = map(int, input().split())
    xs.append(x)
    ys.append(y)
max_count = -1
for i in range(n):
    for j in range(i, n):
        if i == j or xs[i] == xs[j]:
            continue
        # 差はi-jとする
        # print("[{},{}]と[{}, {}]を通る直線".format(xs[i], ys[i], xs[j], ys[j]))
        a = (ys[i] - ys[j]) / (xs[i] - xs[j])
        b = ys[i] - a * xs[i]
        # print("傾き {}: 切片 {}".format(a, b))
        count = 1  # 2座標点取るときの最低コストは1
        for k in range(n):
            if k == i or k == j or xs[i] == xs[k]:
                continue
            tmp_a = (ys[i] - ys[k]) / (xs[i] - xs[k])
            if a != tmp_a:
                continue
            tmp_b = ys[k] - tmp_a * xs[k]
            if b != tmp_b:
                continue
            count += 1
            # print("Yay!!!")
        max_count = max(max_count, count)
        # print("count = {}".format(count))
print(max(1, n - max_count - 1))