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 = []
for i in range(N):
    tmpx, tmpy = map(int, input().split())
    xy.append([tmpx, tmpy])



def search(xy):
    sub = []
    for i in range(1, N):
        subx = xy[i][0] - xy[i-1][0]
        suby = xy[i][1] - xy[i-1][1]
        sub.append([subx, suby])

    tmpli = []
    count = []
    for i in range(len(sub)):
        if sub[i] not in tmpli:
            tmpli.append(sub[i])
            cnt = sub.count(sub[i])
            count.append(cnt)

    count.sort(reverse=True)
    ans = 0
    for i in range(1, len(count)):
        ans += count[i]

    return ans

ans = search(xy)
xy1 = sorted(xy, key=lambda x:x[0])
ans1 = search(xy1)
xy2 = sorted(xy, key=lambda x:x[1])
ans2 = search(xy2)
print(min(ans, ans1, ans2)+1)

Submission status: Wrong Answer

Solution code:
N=int(input())
x=[]
y=[]
if N==1:
    print(1)
xy=[]
for i in range(N):
    X,Y=map(int,input().split())
    x.append(X)
    y.append(Y)
    xy.append((X,Y))
c=[]
for i in range(N):
    for j in range(i+1,N):
        c.append((x[i]-x[j],y[i]-y[j]))
        c.append((x[j]-x[i],y[j]-y[i]))
ans=100
for p,q in c:
    s=0
    for i in range(N):
        if (x[i]-p,y[i]-q) in xy:
            pass
        else:
            s+=1
    ans=min(ans,s)
print(ans)

Submission status: Wrong Answer

Solution code:

N = int(input())
XY = [list(map(int,input().split())) for _ in range(N)]
#XY.sort(key = lambda x: (-x[0], -x[1]))

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

diff = []
for X, Y in XY:
  for X2, Y2 in XY:
    p = X2-X
    q = Y2-Y
    if (p, q) == (0, 0) or (p, q) in diff:
      continue
    diff.append((p, q))

pre = []
ans = []
for p, q in diff:
  cost = 1
  for a, b in XY:
    if not pre:
      pre = (a, b)
      continue
    if (a - p, b - q) == pre:
      pass
    else:
      cost += 1
    pre = (a, b)
  ans.append(cost)
  pre = []
print(min(ans))

Submission status: Wrong Answer

Solution code:
# div2019-2B - Picking Up
import sys
input = sys.stdin.readline

n = int(input())
arr = sorted([list(map(int, input().rstrip().split())) for _ in range(n)])
x_set, y_set = {i[0] for i in arr}, {i[1] for i in arr}
for i, j in arr:
    for k, l in arr:
        x_set.add(i - k)
        y_set.add(j - l)

ans = float("inf")
for p in x_set:
    for q in y_set:
        cnt = 1
        for i in range(1, n):
            if (arr[i - 1][0], arr[i - 1][1]) != (arr[i][0] - p, arr[i][1] - q):
                cnt += 1
        ans = min(ans, cnt)
print(ans)

Submission status: Wrong Answer

Solution code:
from copy import deepcopy

N = int(input())
Z = [[] for i in range(N)]
for i in range(N):
    x, y = map(int, input().split())
    Z[i] = [x, y]

# p, qが決まっている場合のコスト
def cost(p, q):
    reduction = 0
    W = deepcopy(Z)
    for i in range(N-1):
        x, y = W[i]
        if x == 10**10:
            pass
        else:
            for j in range(i+1, N):
                if p != 0 and q != 0:
                    if W[j] != [10**10, 10**10] and W[j][0] - x ==  p and W[j][1] - y == q:
                        reduction += 1
                        W[j] = [10**10, 10**10]
                elif p == 0:
                    if W[j] != [10**10, 10**10] and W[j][0] == x and W[j][1] - y == q:
                        reduction += 1
                        W[j] = [10**10, 10**10]
                else:
                    if W[j] != [10**10, 10**10] and (W[j][0] - x) == p and W[j][1] == y:
                        reduction += 1
                        W[j] = [10**10, 10**10]
    return N - reduction

ans = N
for i in range(N-1):
    for j in range(i+1, N):
        p = Z[j][0] - Z[i][0]
        q = Z[j][1] - Z[i][1]
        cos = cost(p, q)

        ans = min(ans, cos)

print(ans)

Submission status: Wrong Answer

Solution code:
import copy
N = int(input())
C = [[int(i) for i in input().split()] for i in range(N)]
pq_list = []
min_score = N
for i in range(N):
    for j in range(N):
        if(i == j):
            continue
        p = C[i][0] - C[j][0]
        q = C[i][1] - C[j][1]
        pq_list.append([p, q])

for i in range(len(pq_list)):
    score = N
    p = pq_list[i][0]
    q = pq_list[i][1]
    if(p >= 0):
        C.sort(key=lambda x: x[0], reverse=True)
    else:
        C.sort(key=lambda x: x[0], reverse=False)
    for j in range(N-1):
        for k in range(j+1, N):
            if((C[j][0] == C[k][0] + p) and (C[j][1] == C[k][1] + q)):
                score += -1
                break
    min_score = min(min_score, score)
    
print(min_score)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
import itertools
N = int(input())
balls = []
for i in range(N):
    l = list(map(int,input().split()))	
    balls.append(l)

d = list(itertools.permutations(balls, 2))

#print(d)

dic = {}

for i in range(len(d)):
   p = d[i][1][0] - d[i][0][0]
   q = d[i][1][1] - d[i][0][1]
   dic[str(p) + "," + str(q)] = 0
   
for i in range(len(d)):
   p = d[i][1][0] - d[i][0][0]
   q = d[i][1][1] - d[i][0][1]
   
   dic[str(p) + "," + str(q)] += 1

dic[str(0) + "," + str(0)] = -1
max_num = max(dic.values())
#p_q = max(dic.items(), key = lambda x:x[1])[0]

#p,q = map(int,p_q.split(","))

#print(max_num)

ans = N - max_num
print(ans)

Submission status: Wrong Answer

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


    min_cost = float('inf')
    for i in range(n):
        x,y = coords[i][0],coords[i][1]
        for j in range(n):
            if i == j:
                continue
            visited = set()
            visited.add((x,y))
            moves = 1
            x1,y1 = coords[j][0],coords[j][1]
            p,q = x1-x,y1-y
            if p == 0 and q == 0:
                continue
            visited.add((x1,y1))
            while len(visited) != n:
                if (x1+p,y1+q) in coords and (x1+p,y1+q) not in visited:
                    visited.add((x1+p,y1+q))
                    x1 += p
                    y1 += q
                else:
                    moves += 1
                    for k in range(n):
                        if (coords[k][0],coords[k][1]) not in visited:
                            x1,y1 = coords[k][0],coords[k][1]
                            visited.add((x1,y1))
                            break
            min_cost = min(min_cost,moves)

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

main()

Submission status: Wrong Answer

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


for i in range(n):
    for j in range(i+1,n):
        l.append([p[j][0]-p[i][0],p[j][1]-p[i][1],p[i][0],p[i][1]])

m=0
for i in range(len(l)):
    cnt=0
    acnt=0
    bcnt=0
    tmp=0
    for j in range(len(l)):
        if l[i][0]==0:
            tmp=l[i][3]
            if l[i][0]==l[j][0] and l[i][1]==l[j][1] and i!=j or l[i][0]==-l[j][0] and l[i][1]==-l[j][1] and i!=j:
                if tmp==l[j][3]:
                    acnt+=1
                    if acnt>m:
                        m=acnt
        if l[i][1]==0:
            tmp=l[i][2]
            if l[i][0]==l[j][0] and l[i][1]==l[j][1] and i!=j or l[i][0]==-l[j][0] and l[i][1]==-l[j][1] and i!=j:
                if tmp ==l[j][2]:
                    bcnt+=1
                    if bcnt>m:
                        m=bcnt
        if l[i][0]==l[j][0] and l[i][1]==l[j][1] and i!=j or l[i][0]==-l[j][0] and l[i][1]==-l[j][1] and i!=j:
            cnt+=1
            if cnt>m:
                m=cnt
        
ans=n
if m!=0:
    ans=n-m-1
if n==2:
    ans=1
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
xlist = []
ylist = []
pqlist = []
pqcount = {}
for i in range(N):
  x, y = map(int, input().split(" "))
  xlist.append(x)
  ylist.append(y)

for i in range(N):
  for j in range(i+1, N):
    p = xlist[i] - xlist[j]
    q = ylist[i] - ylist[j]
    tuple_pq = (p, q,)
    if not (tuple_pq in pqlist):
      pqlist.append(tuple_pq)
      pqcount[tuple_pq] = 1
    else:
      pqcount[tuple_pq] += 1

if N == 1:
  print(1)
else:
  print(N - max(pqcount.values()))

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7

def LI(): return list(map(int,input().split()))
def I(): return int(input())
def LS(): return input().split()
def S(): return input()

def main():
  n=I()
  l=[]

  for i in range(n):
    l.append(LI())

  # if n==2:
  #   return 1

  l2=[]
  for i in range(n):
    l3=[]
    for j in range(n):
      if i!=j:
        l3.append([l[j][0]-l[i][0],l[j][1]-l[i][1]])
    l2.append(l3)

  mx=0
  for i in range(n):
    _x=l2[i]

    for x in _x:
      for j in range(n):
        if i!=j:
          _y=l2[j]
          sm=0
          for y in _y:
            if x==y:
              sm+=1
          mx=max(mx,sm)

  return n-mx-1

print(main())

Submission status: Wrong Answer

Solution code:
import collections

n = int(input())

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

xy.sort()

pi = []
qi = []

for i in range(n-1):
	pi.append(xy[i][0] - xy[i+1][0])
	qi.append(xy[i][1] - xy[i+1][1])

pc = collections.Counter(pi)
qc = collections.Counter(qi)

lpc = len(pc.keys())
lqc = len(qc.keys())

if lpc == lqc:
	print(lpc)
else:
	print(max(lpc,lqc))

Submission status: Wrong Answer

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

li.sort(key = lambda x:x[0])
li2 = []

for i in range(n):
    for j in range(i):
        a = [li[i][0]-li[j][0],li[i][1]-li[j][1]]
        li2.append(a)

for i in li2:
    if i[0] < 0:
        i[0] = -i[0]
        i[1] = -i[1]

ans = 0

for i in li2:
    ans = max(ans,li2.count(i))

print(n-ans)

Submission status: Wrong Answer

Solution code:
# 何本の数直線上にあるかを求める　1<=ans<=n-1
# 少なくとも2点を通る直線のみ調べれば良い
n=int(input())
xy=[list(map(int,input().split())) for _ in range(n)]
xy.sort(key=lambda x:x[0])
# print(xy)
if n<=2:
    print(1)
else:
    diff=[]
    for i in range(n):
        for j in range(i):
            diff.append((xy[i][0]-xy[j][0],xy[i][1]-xy[j][1]))

    ans=[]
    # print(set(diff))
    for p,q in set(diff):
        intercepts=[]
        for i in range(n):
            qxHIKUpy=q*xy[i][0]-p*xy[i][1]
            intercepts.append(qxHIKUpy)
        # print(q,'x-',p,'y=',intercepts)
        ans.append(len(set(intercepts)))
    # print(ans)
    print(min(ans))

Submission status: Wrong Answer

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

li.sort(key = lambda x:x[0])
li2 = []

for i in range(n):
    for j in range(i):
        a = [li[i][0]-li[j][0],li[i][1]-li[j][1]]
        li2.append(a)

for i in li2:
    if i[0] < 0:
        i[0] = -i[0]
        i[1] = -i[1]

ans = 0

print(li2)
for i in li2:
    ans = max(ans,li2.count(i))

print(n-ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from operator import sub

def main():
    N = int(input())
    balls = [tuple(map(int,input().split())) for _ in range(N)]
    d = defaultdict(int)
    for i in range(N):
        for j in range(N):
            if i == j:
                continue
            d[tuple(map(sub, balls[i], balls[j]))] += 1
    try:
        mmax = max(d.values())
        mmax = int(N - mmax)
        print(mmax)
    except ValueError:
        print(100)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import collections

n = int(input())

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

xy.sort()

pi = []
qi = []

for i in range(n-1):
	pi.append(xy[i][0] - xy[i+1][0])
	qi.append(xy[i][1] - xy[i+1][1])

pc = collections.Counter(pi)
qc = collections.Counter(qi)

print(pc)
print(qc)

lpc = len(pc.keys())
lqc = len(qc.keys())

if lpc == lqc:
	print(lpc)
else:
	print(max(lpc,lqc))

Submission status: Wrong Answer

Solution code:
N = int(input())
XY = [list(map(int,input().split())) for _ in range(N)]
XY.sort(key = lambda x: (-x[0], -x[1]))

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

diff = []
for X, Y in XY:
  for X2, Y2 in XY:
    p = X2-X
    q = Y2-Y
    k = X-X2
    l = Y-Y2
    if (p, q) == (0, 0) or (p, q) in diff:
      continue
    diff.append((p, q))
    if (k, l) == (0, 0) or (k, l) in diff:
      continue
    diff.append((k, l))
    if (p, l) == (0, 0) or (p, l) in diff:
      continue
    diff.append((p, l))
    if (k, q) == (0, 0) or (k, q) in diff:
      continue
    diff.append((k, q))
    
pre = []
ans = []
for p, q in diff:
  cost = 1
  for a, b in XY:
    if not pre:
      pre = (a, b)
      continue
    if (a - p, b - q) == pre:
      pass
    else:
      cost += 1
    pre = (a, b)
  ans.append(cost)
  pre = []
print(min(ans))

Submission status: Wrong Answer

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


mincost = 10000000

for j,a in enumerate(xy): #O(N)
    for k, b in enumerate(xy[j:]):
        p = a[0]-b[0]
        q = a[1]-b[1]
        prev = a
        check = [0]*N
        check[j] = 1
        check[k] = 1
        cost = 1
        flag = True
        while flag:
            for i, c in enumerate(xy):
                if ([prev[0]-p,prev[1]-q]==c):
                    check[i] = 1
                    prev = c

            for i in range(N):
                if (not check[i]):
                    prev = xy[i]
                    check[i] = 1
                    cost += 1
                    break
                flag = False
        mincost = min(cost, mincost)   

print(mincost)

Submission status: Wrong Answer

Solution code:
import math

N = int(input())

ball = [0] * N

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

ans = N - 1

# p,q の組
for i in range(N) :
    for j in range(N) :
        p = ball[j][0] - ball[i][0]
        q = ball[j][1] - ball[i][1]

        if p == 0 and q == 0 :
            continue

        group = []

        if p == 0 :
            if q < 0 :
                q = -q
            for k in range(N) : # xがゼロ以下になるまで引き，切片を求める
                if ball[k][1] >= 0 :
                    mul = math.ceil(ball[k][1] / q)
                    b = ball[k][1] - q * mul
                else :
                    mul = math.ceil(-ball[k][1] / q) - 1
                    b = ball[k][1] + q * mul
                x = ball[k][0]
                group.append((x,b))
        else :
            if p < 0 :
                p = -p
                q = -q
            for k in range(N) :
                if ball[k][0] >= 0 :
                    mul = math.ceil(ball[k][0] / p)
                    b = ball[k][1] - q * mul
                    x = ball[k][0] - p * mul
                else :
                    mul = math.ceil(-ball[k][0] / p) - 1
                    b = ball[k][1] + q * mul
                    x = ball[k][0] + p * mul
                group.append((x,b))
        count = set(group)
        if len(count) <= 0 :
            continue
        ans = min(ans,len(count))

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
lx = []
ly = []
count = 1
for i in range(n):
    x,y=map(int,input().split())
    lx.append(x)
    ly.append(y)
kx=lx[n-1]-lx[n-2]
ky=ly[n-1]-ly[n-2]

for j in range(n-1):
    if lx[j+1]-lx[j]==kx and ly[j+1]-ly[j]==ky:
        count=count
    else:
        count+=1
print(count)

Submission status: Wrong Answer

Solution code:
N = int(input())
XY = []
for n in range(N):
    XY.append([int(i) for i in input().split()])
cnt = {}
for n in range(N):
    for nn in range(n+1,N): 
        dist = [XY[n][0]-XY[nn][0],XY[n][1]-XY[nn][1]]
        if str(dist) in cnt:
            cnt[str(dist)] += 1
        else:
            cnt[str(dist)] = 1
if N == 1:
    print(1)
else:
    print(N - max(cnt.values()))

Submission status: Wrong Answer

Solution code:
import numpy as np
N = int(input())
x = np.zeros(N)
y = np.zeros(N)

for i in range(N):
    x[i], y[i] = map(int, input().split())
for j in range(N):
    for k in range(N-1):
        if x[k] > x[k + 1]:
            x[k], y[k] = x[k + 1], y[k + 1]
        elif x[k] == x[k + 1] and y[k] > y[k + 1]:
            x[k], y[k] = x[k + 1], y[k + 1]

ans = np.full(N * N, N)
ite = 0
for m in range(N):
    for p in range(m):
        diff_x = x[m] - x[p]
        diff_y = y[m] - y[p]
        for r in range(N-1):
            for q in range(r+1,N):
                if x[q] - x[r] == diff_x and y[q] - y[r] == diff_y:
                    ans[ite] -= 1
        ite += 1
ans_min = ans[0]
for z in range(ite):
    if ans_min > ans[z]:
        ans_min = ans[z]

print("{}".format(int(ans_min)))

Submission status: Wrong Answer

Solution code:
n = int(input())

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

a = x[0]
b = y[0]

minCost =100000000000000
for p in range(n):
  for q in range(n):
      cost = 0
      chokuzenX = 0
      chokuzenY = 0
      for i in range(n):
          if n==1:
              chokuzenX = x[i]
              chokuzenY = y[i]
              cost = cost+1
      else:
          if a-p == chokuzenX and b-q == chokuzenY:
              cost =cost +0
          else:
              cost = cost+1
      if minCost < cost:
          minCost = minCost
      else:
          minCost = cost

print(minCost)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import random
input = sys.stdin.readline

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

def main():

	N = int(input())
	#N, K = map(int, input().split(" "))

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

	gess = {}
	xm = 0
	ym = 0

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

	for i, val in enumerate(xy):
		if i == 0:
			x,y = val
			xm = x
			ym = y
			continue
		x, y = val

		p = x - xm
		q = y - ym
		if (p,q) in gess:
			gess[(p, q)] += 1
		else:
			gess[(p, q)] = 1
		xm = x
		ym = y

	p, q = max(gess, key=gess.get)
	nai = gess[(p,q)]

	#########
	xy = sorted(xy, key=lambda x:(x[0]))
	gess1 = {}
	xm = 0
	ym = 0

	for i, val in enumerate(xy):
		if i == 0:
			x,y = val
			xm = x
			ym = y
			continue
		x, y = val

		p = x - xm
		q = y - ym
		if (p,q) in gess1:
			gess1[(p, q)] += 1
		else:
			gess1[(p, q)] = 1
		xm = x
		ym = y

	p, q = max(gess1, key=gess1.get)
	nai1 = gess1[(p,q)]

	#########
	xy = sorted(xy, key=lambda x:(-x[0]))
	gess2 = {}
	xm = 0
	ym = 0

	for i, val in enumerate(xy):
		if i == 0:
			x,y = val
			xm = x
			ym = y
			continue
		x, y = val

		p = x - xm
		q = y - ym
		if (p,q) in gess2:
			gess2[(p, q)] += 1
		else:
			gess2[(p, q)] = 1
		xm = x
		ym = y

	p, q = max(gess2, key=gess2.get)
	nai2 = gess2[(p,q)]

	#########
	xy = sorted(xy, key=lambda x:(x[1]))
	gess3 = {}
	xm = 0
	ym = 0

	for i, val in enumerate(xy):
		if i == 0:
			x,y = val
			xm = x
			ym = y
			continue
		x, y = val

		p = x - xm
		q = y - ym
		if (p,q) in gess3:
			gess3[(p, q)] += 1
		else:
			gess3[(p, q)] = 1
		xm = x
		ym = y

	p, q = max(gess3, key=gess3.get)
	nai3 = gess3[(p,q)]

	#########
	xy = sorted(xy, key=lambda x:(-x[1]))
	gess4 = {}
	xm = 0
	ym = 0

	for i, val in enumerate(xy):
		if i == 0:
			x,y = val
			xm = x
			ym = y
			continue
		x, y = val

		p = x - xm
		q = y - ym
		if (p,q) in gess4:
			gess4[(p, q)] += 1
		else:
			gess4[(p, q)] = 1
		xm = x
		ym = y

	p, q = max(gess4, key=gess4.get)
	nai4 = gess4[(p,q)]

	#########
	xy = sorted(xy, key=lambda x:(x[0],-x[1]))
	gess5 = {}
	xm = 0
	ym = 0

	for i, val in enumerate(xy):
		if i == 0:
			x,y = val
			xm = x
			ym = y
			continue
		x, y = val

		p = x - xm
		q = y - ym
		if (p,q) in gess5:
			gess5[(p, q)] += 1
		else:
			gess5[(p, q)] = 1
		xm = x
		ym = y

	p, q = max(gess5, key=gess5.get)
	nai5 = gess5[(p,q)]

	#########
	random.shuffle(xy)
	gess6 = {}
	xm = 0
	ym = 0

	for i, val in enumerate(xy):
		if i == 0:
			x,y = val
			xm = x
			ym = y
			continue
		x, y = val

		p = x - xm
		q = y - ym
		if (p,q) in gess6:
			gess6[(p, q)] += 1
		else:
			gess6[(p, q)] = 1
		xm = x
		ym = y

	p, q = max(gess6, key=gess6.get)
	nai6 = gess6[(p,q)]

	#########
	random.shuffle(xy)
	gess7 = {}
	xm = 0
	ym = 0

	for i, val in enumerate(xy):
		if i == 0:
			x,y = val
			xm = x
			ym = y
			continue
		x, y = val

		p = x - xm
		q = y - ym
		if (p,q) in gess7:
			gess7[(p, q)] += 1
		else:
			gess7[(p, q)] = 1
		xm = x
		ym = y

	p, q = max(gess7, key=gess7.get)
	nai7 = gess7[(p,q)]
		#########
	random.shuffle(xy)
	gess8 = {}
	xm = 0
	ym = 0

	for i, val in enumerate(xy):
		if i == 0:
			x,y = val
			xm = x
			ym = y
			continue
		x, y = val

		p = x - xm
		q = y - ym
		if (p,q) in gess8:
			gess8[(p, q)] += 1
		else:
			gess8[(p, q)] = 1
		xm = x
		ym = y

	p, q = max(gess8, key=gess8.get)
	nai8 = gess8[(p,q)]

		#########
	ans = -1

	for _ in range(1000):
		random.shuffle(xy)
		gess9 = {}
		xm = 0
		ym = 0
		for i, val in enumerate(xy):
			if i == 0:
				x,y = val
				xm = x
				ym = y
				continue
			x, y = val

			p = x - xm
			q = y - ym
			if (p,q) in gess9:
				gess9[(p, q)] += 1
			else:
				gess9[(p, q)] = 1
			xm = x
			ym = y

		p, q = max(gess9, key=gess9.get)
		nai9 = gess9[(p,q)]

		if nai9 > ans:
			ans = nai9

	tmp = max(nai, nai2, nai3,nai4, nai5,nai6,nai1,nai7,nai8,ans)

	print(N-tmp)



if __name__ == "__main__":
	main()

Submission status: Wrong Answer

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

vectors = []
ans_inv = 0
for i in range(N):
    for j in range(i+1,N):
        vector = [x_y[i][0]-x_y[j][0],x_y[i][1]-x_y[j][1]]
#        print(vector)
        if vector[0]<0:
            vector = [x_y[j][0]-x_y[i][0],x_y[j][1]-x_y[i][1]]
        vectors.append(vector)
cnt = 0
for i in range(len(vectors)):
    cnt = max(cnt,vectors.count(vectors[i]))
#if N == 2:
#    print('1')
#else:
print(N-cnt)

Submission status: Wrong Answer

Solution code:
#標準入力
N = int(input())
S = []
S = [list(map(int, input().split())) for i in range(N)]

ans = 1
i = 0
j = 0
for _ in range(N):
  if i==N:
    break
  try:
    a =(S[i+1][1]-S[i][1])/(S[i+1][0]-S[i][0])
    b = S[i][1]-a*S[i][0]
    print(i)
    for _ in range(N):
      if j == N:
        i = N
        break
      if S[j][1]!=a*S[j][0]+b:
        ans+=1
        i = j
        break
      j +=1  
  except:
    print('111')
    print(i)
    for _ in range(N):
      if j == N:
        i = N
        break
      if S[j][0]!=S[i][0]:
        ans+=1
        i = j
        break
      j+=1
    
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
n = int(input())
xy = []
for i in range(n):
    a = list(input().split())
    xy.append(a)

#print(xy)
s = n
for i in range(n-1):
    if xy[i][0] !="a":
        for j in range(i+1,n):
            if xy[j][0] !="a":
                p = int(xy[i][0])-int(xy[j][0])
                q = int(xy[i][1])-int(xy[j][1])
                m = n
                #print(p)
                #print(q)
                for c in range(n-1):
                    if xy[c][0] !="a":
                        for b in range(c+1,n):
                            #print(int(xy[c][0])-int(xy[b][0]))
                            if xy[b][0] != "a":
                                if abs(p) == abs(int(xy[c][0])-int(xy[b][0])) and abs(q) == abs(int(xy[c][1])-int(xy[b][1])):
                                    m -= 1
                                    xy[b][0] = "a"
                #print(m)
                if s>m:
                    s = m
                    #print("s"+ str(s))

print(s)

Submission status: Wrong Answer

Solution code:

N = int(input())
XY = []

for i in range(N):
    x, y = map(int, input().split(" "))
    XY.append((x, y))

val_max = 10 ** 9

Div_list = []

for i in range(N):
    x_i, y_i = XY[i]
    for j in range(i+1, N):
        x_j, y_j = XY[j]
        Div_list.append((x_i - x_j, y_i - y_j))
        Div_list.append((x_j - x_i, y_j - y_i))

Div_list_sorted = sorted(Div_list)

Div_list_len = len(Div_list_sorted)

count_max = 0
if Div_list_len == 1:
    count_max = 1
else:

    skip = 0

    for i in range(Div_list_len):
        count = 1
        if skip > 0:
            skip -= 1
            continue

        s_i = Div_list_sorted[i]
        if s_i[0] == 0 or s_i[1] == 0:
            continue

        for j in range(i+1, Div_list_len):
            s_j = Div_list_sorted[j]

            if s_i == s_j:
                count += 1

        skip = (count - 1)
        if count > count_max:
            count_max = count


print(N - count_max)

Submission status: Wrong Answer

Solution code:

from collections import defaultdict


def read_input():
    n = int(input())

    points = []
    for i in range(n):
        points.append(tuple(map(int, input().split())))

    return n, points


# calc p3 is on line made by p1 and d
def check_on_line(p1, d, p3):
    a = ((p3[0] - p1[0]), (p3[1] - p1[1]))

    if d[0] != 0 and d[1] != 0:
        if a[0] % d[0] != 0 or a[1] % d[1] != 0:
            return False
        return a[0] // d[0] == a[1] // d[1]

    if d[0] != 0: # d[1] sould be 0
        return a[1] == 0 and a[0] % d[0] == 0

    # d[0] sould be 0 and (0, 0) is not valid
    return a[0] == 0 and a[1] % d[1] == 0



def dist_point_to_point(p1, p2):
    return p2[0] - p1[0], p2[1] - p1[1]


def submit():
    n, points = read_input()

    if n == 1:
        print(1)
        return

    p2p_dist = {}
    pd_list = defaultdict(list)
    for p1 in points:
        for p2 in points:
            if p1 == p2:
                continue
            p2p_dist[(p1, p2)] = dist_point_to_point(p1, p2)

            for p3 in points:
                if check_on_line(p1, p2p_dist[(p1, p2)], p3):
                    pd_list[(p1, p2p_dist[(p1, p2)])].append(p3)

    pq_list = list(set(p2p_dist.values()))

    min_line_c = 51
    for p, q in pq_list:
        line_c = 0
        point_c = 0
        used = {}
        for s in points:
            used[s] = False

        # count lines covering all points by direction of (p, q)
        for s in points:
            if used[s]:
                continue

            # statpoint
            used[s] = True
            point_c += 1

            # points on line made by s and (p, q)
            for pl in pd_list[(s, (p, q))]:
                if not used[pl]:
                    used[pl] = True
                    point_c += 1

            line_c += 1
            # print(used, line_c)

            if point_c >= n:
                break

        if min_line_c > line_c:
            min_line_c = line_c

    print(min_line_c)

if __name__ == '__main__':
    submit()

Submission status: Wrong Answer

Solution code:
n=int(input())
r=[]
a=[]
for i in range(n):
  b,c=(int(j) for j in input().split())
  for k in range(i):
    d=a[k][0]-b
    e=a[k][1]-c
    if d<0:
      d=-d
      e=-e
    r.append([d,e])
  a.append([b,c])
r.sort()
if n>1:
  p=r[0]
x=1
z=1
t=0
q=[]
for i in range(len(r)-1):
  if r[i]==r[i+1]:
    x=x+1
  else:
    if x>z:
      p=r[i]
    x=1
if n==1:
  print(1)
else:
  for i in range(n):
    if a[i] not in q:
      t=t+1
    q.append([a[i][0]+p[0],a[i][1]+p[1]])
    q.append([a[i][0]-p[0],a[i][1]-p[1]])
  print(t)

Submission status: Wrong Answer

Solution code:
import numpy as np
N=int(input())
x = [0] * N
y = [0] * N
ans = N

for i in range(N):
  x[i], y[i] = map(int, input().split())
  
for i in range(N-1):
  cost = N
  for j in range(i+1,N):
    p = x[i] - x[j]
    q = y[i] - y[j]
    if p == 0 and q==0:
      cost = N*2
    diffx = np.diff(x)
    diffy = np.diff(y)
    for k in range(N-1):
      if diffx[k] == p and diffy[k] == q:
        cost = cost - 1
      if diffx[k] == -p and diffy[k] == -q:
        cost = cost - 1
  ans = min(ans,cost)

print(ans)

Submission status: Wrong Answer

Solution code:
import math

N = int(input())

ball = [0] * N

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

ans = N

# p,q の組
for i in range(N) :
    for j in range(N) :
        p = ball[j][0] - ball[i][0]
        q = ball[j][1] - ball[i][1]

        if p == 0 and q == 0 :
            continue

        group = []

        if p == 0 :
            if q < 0 :
                q = -q
            for k in range(N) : # xがゼロ以下になるまで引き，切片を求める
                if ball[k][1] >= 0 :
                    mul = math.ceil(ball[k][1] / q)
                    b = ball[k][1] - q * mul
                else :
                    mul = math.ceil(-ball[k][1] / q) - 1
                    b = ball[k][1] + q * mul
                x = ball[k][0]
                group.append((x,b))
        else :
            if p < 0 :
                p = -p
                q = -q
            for k in range(N) :
                if ball[k][0] >= 0 :
                    mul = math.ceil(ball[k][0] / p)
                    b = ball[k][1] - q * mul
                    x = ball[k][0] - p * mul
                else :
                    mul = math.ceil(-ball[k][0] / p) - 1
                    b = ball[k][1] + q * mul
                    x = ball[k][0] + p * mul
                group.append((x,b))
        count = set(group)
        if len(count) <= 0 :
            continue
        ans = min(ans,len(count))

print(ans)