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:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
 
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

import collections

n = ni()

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

balls = []
dis = []

for i in range(n):
    x,y = na()
    for b in balls:
        dis.append(str(abs(b[0]-x))+'_'+str(abs(b[1]-y)))
    balls.append([x,y])

c = collections.Counter(dis)
m = c.most_common()

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

u = m[0][1]
if u == 1:
    u = 0

print(n-u)

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

	xy.sort()
	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],-x[1]))
	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)]

	tmp = max(nai, nai2)

	print(N-tmp)



if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
N = int(input())
xy = sorted([list(map(int, input().split())) for _ in range(N)])
diffx = set()
diffy = set()
for i in range(N-1):
    diffx.add(xy[i+1][0] - xy[i][0])
    diffy.add(xy[i+1][1] - xy[i][1])
ans = 51
for p in diffx:
    for q in diffy:
        cost = 1
        for i in range(1, N):
            if xy[i-1][0] + p == xy[i][0] and xy[i-1][1] + q == xy[i][1]:
                continue
            cost += 1
        ans = min(cost, ans)
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter
N = int(input())
XY = [[int(i) for i in input().split()]+[j] for j in range(N)]
XY.sort()

sa = ["" for i in range(N)]
prex = XY[0][0]
prey = XY[0][1]

for i,j,k in XY:
    sa[k] += str(i-prex)
    sa[k] += str(j-prey)
    prex = i
    prey = j
    
sa1 = Counter(sa)
ans,ans1 = sa1.most_common()[0]
print(N-ans1)

Submission status: Wrong Answer

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

n = int(input())
arr = sorted([list(map(int, input().rstrip().split())) for _ in range(n)])
dif = []
for i in range(1, n):
    x = arr[i][0] - arr[i - 1][0]
    y = arr[i][1] - arr[i - 1][1]
    dif += [(x, y)]

ans = float("inf")
for p, q in set(dif):
    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:
import math


def main():
    N = int(input())
    XY = [
        [int(a) for a in input().split()]
        for a in range(N)
    ]

    r = N
    for i in range(N):
        xy1 = XY[i]
        for j in range(i + 1, N):
            xy2 = XY[j]
            dx = xy1[0] - xy2[0]
            dy = xy1[1] - xy2[1]
            if dx == 0 and dy == 0:
                continue

            bs = set()
            if dx != 0:

                for x, y in XY:
                    k = math.ceil(-x / dx)
                    t = x + k * dx, y + k * dy
                    bs.add(t)
                r = min(len(bs), r)
            else:
                for x, y in XY:
                    bs.add(y)
                r = min(len(bs), r)

    print(r)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import collections

n = input()
N = int(n)

XY = []
for i in range(N):
    x, y = input().split()
    X = int(x)
    Y = int(y)
    XY.append((X, Y))

diff = []
for xy in XY:
    for xy2 in XY:
        dx = xy[0] - xy2[0]
        dy = xy[1] - xy2[1]
        # d = dx * 10 + dy
        d = (dx, dy)
        if d[0] == 0 and d[1] == 0:
            continue
        diff.append(d)

clist = collections.Counter(diff)
result = N # - clist.most_common()[0][1]
print(result)

Submission status: Wrong Answer

Solution code:
n = int(input())

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

lst = []

for i in range(n):
    for j in range(i+1,n):
        if a[j][0]-a[i][0] <= 0 and a[j][1]-a[i][1] <= 0:
            lst.append([a[i][0]-a[j][0], a[i][1]-a[j][1]])
        else:
            lst.append([a[j][0]-a[i][0], a[j][1]-a[i][1]])

if n ==1:
    print(1)
else:
    x = 0
    for i in range(len(lst)):
        c = 1
        for j in range(i+1,len(lst)):
            if lst[i] == lst[j]:
                c += 1
        x = max(x,c)
    print(n-x)

Submission status: Wrong Answer

Solution code:
def most_frequent(List):
    counter = 0
    num = List[0]

    for i in List:
        curr_frequency = List.count(i)
        if(curr_frequency> counter):
            counter = curr_frequency
            num = i

    return num

n = int(input())
c = []
for i in range(n):
    x,y = map(int,input().split())
    c.append([x,y])
l = []
for i in range(len(c)-1):
    for j in range(i+1,len(c)):
        l.append([c[j][0]-c[i][0],c[j][1]-c[i][1]])
if(n==1):
    z = most_frequent(c)
else:
    z = most_frequent(l)
l = 1
for i in range(1,len(c)):
    if([c[i][0]-z[0],c[i][1]-z[1]] not in c):
        l+=1
print(l)

Submission status: Wrong Answer

Solution code:
words = lambda t : list(map(t, input().split()))
n = int(input())
xys = []
for i in range(n):
    (x,y) = words(int)
    xys.append((x,y))

min_score = -1
for i in range(n):
    xy1 = xys[i]
    for j in range(i,n):
        a = set(xys)
        xy2 = xys[j]
        p = xy1[0] - xy2[0]
        q = xy1[1] - xy2[1]
        score = 0
        while len(a) > 0:
            score += 1
            (x,y) = a.pop()
            xup = x + p
            yup = y + q
            while (xup,yup) in a:
                a.remove((xup,yup))
                xup = xup + p
                yup = yup + q
            xdn = x - p
            ydn = y - p
            while (xdn,ydn) in a:
                a.remove((xdn,ydn))
        if min_score == -1:
            min_score = score
        else:
            min_score = min(min_score,score)
print(min_score)

Submission status: Wrong Answer

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

def most_common(lst):
    return max(set(lst), key=lst.count)

def f(pts, p, q):
    c = []
    for pt in pts:
        c.append(q*pt[0]-p*pt[1])

    mc = most_common(c)
    return list(filter(lambda pt: q*pt[0]-p*pt[1] != mc, pts))

################################################################################

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

res = 0
while len(pts) > 0:
    res += 1
    mn = pts
    for i in range(len(pts)):
        for j in range(i+1, len(pts)):
            l = f(pts, pts[i][0]-pts[j][0], pts[i][1]-pts[j][1])
            if len(l) < len(mn):
                mn = l

    pts = mn

print(res)

Submission status: Wrong Answer

Solution code:
N = int(input())
xy = list(list(map(int,input().split()))+[0]for i in range(N))
xy.sort()
ans = 50
hoge = 0
p,q = 0,0

def func(n):
    xy[n][2] = 1
    if [xy[n][0]+p,xy[n][1]+q,0] in xy:
        func(xy.index([xy[n][0]+p,xy[n][1]+q,0]))


for i in range(N):
    for j in range(i+1,N):
        p,q = xy[j][0]-xy[i][0],xy[j][1]-xy[i][1]
        for k in range(N):
            if xy[k][2] == 0:
                func(k)
                p,q = -p,-q
                func(k)
                p,q = -p,-q
                hoge += 1
        ans = min(hoge,ans)
        hoge = 0
        for k in range(N):
            xy[k][2] = 0
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
xlist = []
ylist=[]
for i in range(n):
    x,y = map(int,input().split())
    xlist.append(x)
    ylist.append(y)
    
import collections
xlist_sa=[]
ylist_sa=[]
for j in range(len(xlist)-1):
    xlist_sa.append(abs(xlist[j]-xlist[j+1]))
    ylist_sa.append(abs(ylist[j]-ylist[j+1]))

a = [x - y for (x, y) in zip(xlist_sa,ylist_sa)]

c = collections.Counter(a)
print(len(c.most_common()))

Submission status: Wrong Answer

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import numpy as np

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

N = int(input())
xy = [[] for i in range(N)]
for i in range(N):
    xy[i] = [int(i) for i in input().split()]

xy = np.array(xy)

count_dic = {}
xy.sort()
for i in range(N):
    for j in range(i+1,N):
        diff = xy[i] - xy[j]
        p,q = diff
        pq = str(p)+str(q)
        pq2 = str(-p)+str(-q)
        if pq in count_dic:
            count_dic[pq] += 1
        else:
            count_dic[pq] = 1
        if pq2 in count_dic:
            count_dic[pq2] += 1
        else:
            count_dic[pq2] = 1
# print(count_dic)
ans = 1
for k,v in sorted(count_dic.items(), key = lambda x:-x[1]):
    ans = N - v
    break
print(max(1,ans))

Submission status: Wrong Answer

Solution code:
n=int(input())
sm=[]
count=1
for _ in range(n):
    xi,yi=map(int,input().split())
    smi=xi+yi
    sm.append(smi)
sm.sort()
for i in range(n-2):
    if sm[i]!=sm[i+1]:
        if (sm[i]+sm[i+2])//2==sm[i+1]:
            count+=0
        else:
            count+=1
    else:
        count+=0
print(count)

Submission status: Wrong Answer

Solution code:
from itertools import permutations, product

N = int(input())
balls = []
for i in range(N):
  balls.append(tuple(map(int, input().split())))
  
def cost(ball_before, ball_after, p, q):
  if ball_before == (ball_after[0] - p, ball_after[1] - q):
    return 0, ball_after
  else:
    return 1, ball_after
    
total_costs = []

p_q_set = set()
all_comb = product(balls, balls)
for i in all_comb:
  p_q_set.add((i[0][0] - i[1][0], i[0][1] - i[1][1]))

for p_q in list(p_q_set):
  for scenario in permutations(balls):
    total_cost = 0
    ball_before = scenario[0]
    for next_ball in scenario:
      c, ball_before = cost(ball_before, next_ball, p_q[0], p_q[1])
      total_cost += c
    total_costs.append(total_cost)
print(min(total_costs))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

def readInts():
  return [int(s) for s in input().split(" ")]

def cost(N, points, pointToIndex, p, q):
  s = 0
  visited = [False for _ in range(N)]
  for i in range(N):
    if visited[i]: continue

    s += 1
    visited[i] = True

    k = 1
    while (points[i][0] + p * k <= points[-1][0]) and (points[i][1] + q * k <= points[-1][1]):
      np = (points[i][0] + p * k, points[i][1] + q * k)
      if np in pointToIndex and not visited[pointToIndex[np]]:
        visited[pointToIndex[np]] = True
        k += 1
      else:
        break

  return s

def main():
  N = readInts()[0]
  points = [tuple(readInts()) for _ in range(N)]
  points.sort()

  ans = N

  pointToIndex = {}
  for i, point in enumerate(points):
    pointToIndex[point] = i

  for i in range(N-1):
    for j in range(i+1, N):
      p = points[j][0] - points[i][0]
      q = points[j][1] - points[i][1]
      ans = min(ans, cost(N, points, pointToIndex, p, q))
  print(ans)

if __name__ == "__main__":
  main()

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-1):
    for k in range(N-1):
        if x[k] > x[k + 1]:
            x[k], y[k] = x[k + 1], y[k + 1]
        if x[k] == x[k + 1] and y[k] > y[k + 1]:
            x[k], y[k] = x[k + 1], y[k + 1]

ans = N
for m in range(N):
    for p in range(m):
        diff_x = x[m] - x[p]
        diff_y = y[m] - y[p]
        ans_kari = N
        for q in range(N):
            for r in range(q):
                if x[q] - x[r] == diff_x and y[q] - y[r] == diff_y:
                    ans_kari -= 1
        if ans_kari < ans:
            ans = ans_kari
print("{}".format(ans))

Submission status: Wrong Answer

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

cost_min = 10 ** 4
if N == 1 or N == 2:
  print(1)
else:
  xy.sort()
  for i in range(N-1):
    cost = 1
    p = xy[i][0] - xy[i+1][0]
    q = xy[i][1] - xy[i+1][1]
    for j in range(N-1):
      if xy[j+1][0] + p == xy[j][0] and xy[j+1][1] + q == xy[j][1]:
        pass
      else:
        cost += 1
    if cost < cost_min:
      cost_min = cost
  xy = sorted(xy, key=lambda x: x[1])
  for i in range(N-1):
    cost = 1
    p = xy[i][0] - xy[i+1][0]
    q = xy[i][1] - xy[i+1][1]
    for j in range(N-1):
      if xy[j+1][0] + p == xy[j][0] and xy[j+1][1] + q == xy[j][1]:
        pass
      else:
        cost += 1
    if cost < cost_min:
      cost_min = cost
      
  print(cost_min)

Submission status: Wrong Answer

Solution code:
import sys
from itertools import combinations

def main():
    input = sys.stdin.readline
    N = int(input())
    cord = []
    for _ in range(N):
        x, y = map(int, input().split())
        cord.append((x, y))

    ans = 50
    for a in combinations(cord, 2):
        x1, y1 = a[0]
        x2, y2 = a[1]

        if x1 == x2:
            slope = 0
        else:
            slope = (y2 - y1) / (x2 - x1)

        intercepts = set()
        for x, y  in cord:
            intercept = y - slope * x
            intercept = round(intercept, 12)
            intercepts.add(intercept)

        ans = min(ans, len(intercepts))

    return ans


if __name__ == '__main__':
    print(main())

Submission status: Wrong Answer

Solution code:
n = int(input())
x = [list(map(int, input().split())) for _ in range(n)]
ans = float('inf')
for d1 in x:
    for d2 in x:
        tmp = n
        if d1 == d2:
            continue
        p = d1[0] - d2[0]
        q = d1[1] - d2[1]
        s = set()
        for idx, d3 in enumerate(x):
            for d4 in x:
                if tuple(d4) not in s and d3 != d4 and (d4[0] - d3[0] == p and d4[1] - d3[1] == q or d4[0] - d3[0] == -p and d4[1] - d3[1] == -q):
                    tmp -= 1
                    break
            s.add(tuple(d3))
        ans = min(ans, tmp)
if n == 1:
    print(1)
else:
    print(max(1, ans))

Submission status: Wrong Answer

Solution code:
from collections import Counter
N = int(input())
xy = [list(map(int, input().split())) for _ in range(N)]
xlist = []
for i, (x, y) in enumerate(xy):
    if i == 0:
        tmpx = x
        tmpy = y
        continue
    xlist.append((abs(tmpx-x), abs(tmpy-y)))
    tmpx = x
    tmpy = y

c = Counter(xlist)
ret = 0
m = 0
for (x, y) in c:
    if x != 0 and y != 0:
        m = max(m, c[(x, y)])
    ret += c[(x, y)]
print(ret-m+1)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python

n = int( input() )
xy = []
for _ in range(n): xy.append( [ int(x) for x in input().strip().split() ] )
#
if n==1:
    print( 1 )
    exit()
#
distmap = dict()
for i in range(n):
    xi,yi = xy[i]
    for j in range(i+1,n):
        xj, yj = xy[j]
        xd = xi - xj
        yd = yi - yj
        if xd<0:
            xd*= -1
            yd*= -1
        k = "{} {}".format(xd,yd)
        distmap[k]= distmap.get(k,0) + 1
#
d = max( distmap.values() )
print( n-d )

Submission status: Wrong Answer

Solution code:
n = int(input())

li = []

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

li.sort()

diff_dic = {}

dup = []

x1, y1 = li[0]
for s in range(1,n-1):
    for i in range(s,n):
        xi, yi = li[i]

        if xi != x1:
            diff = (yi - y1)/(xi - x1)
        else:
            diff = 10e10

        if diff in diff_dic.keys():
            diff_dic[diff] += 1
        else:
            diff_dic[diff] = 1

        dup.append(max(diff_dic.values()))

try:
	print(n-max(dup))
except:
  	print(1)

Submission status: Wrong Answer

Solution code:
import sys

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

XY.sort(key=lambda x: x[0])
XY.sort(key=lambda x: x[1])

if N == 1:
    print(1)
    sys.exit()
    
PQ = {}
for i in range(1, len(XY)):
    pq = XY[i][0] - XY[i-1][0], XY[i][1] - XY[i-1][1]
    if pq in PQ.keys():
        PQ[pq] += 1
    else:
        PQ[pq] = 1
pq = max(PQ, key=lambda x: PQ[x])
print(N - PQ[pq])

Submission status: Wrong Answer

Solution code:

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

tilt_map = {}

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

    for i in range(N):
        for j in range(i+1, N):
            a = xy[i]
            b = xy[j]
            tilt_x = a[0] - b[0]
            tilt_y = a[1] - b[1]
            key = str(tilt_x) + ":" + str(tilt_y)
            if key in tilt_map:
                tilt_map[key] += 1
            else:
                tilt_map[key] = 1


    most_key = sorted(tilt_map.items(), key=lambda x: x[1], reverse=True)[0][0]

    idx = most_key.index(":")
    m_dx = int(most_key[:idx])
    m_dy = int(most_key[idx+1:])

    if m_dx == 0:
        if m_dy < 0:
            m_dy *= -1
        xy.sort(key=lambda x: x[1])
    else:
        if m_dx < 0:
            m_dx *= -1
            m_dy *= -1
        xy.sort(key=lambda x:x[0])

    pos = xy.pop(0)
    cost = 1

    while len(xy) > 0:
        next_x = pos[0] + m_dx
        next_y = pos[1] + m_dy
        for _xy in xy[::]:
            if _xy[0] == next_x and _xy[1] == next_y:
                xy.remove([next_x, next_y])
                pos = [next_x, next_y]
                break
        else:
            pos = xy.pop(0)
            cost += 1
    print(cost)

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])
xy.sort()

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]

print(ans+1)

Submission status: Wrong Answer

Solution code:
n = int(input())
arr = [list(map(int, input().split())) for _ in range(n)]
ans = set()
ans_rev = set()
for i in range(n-1):
  a, b = arr[i]
  c, d = arr[i+1]
  x, y = (a-c), (b-d)
  ans.add((x,y))

arr.sort(reverse=True)
for i in range(n-1):
  a, b = arr[i]
  c, d = arr[i+1]
  x, y = (a-c), (b-d)
  ans_rev.add((x,y))
print(min(len(ans_rev), len(ans)))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
n = int(input())

x_list = list()
y_list = list()
for _ in range(n):
    x, y = map(int, input().split())
    x_list.append(x)
    y_list.append(y)

max_x = max(x_list)
max_y = max(y_list)

ans = float('inf')
for p in range(x):
    for q in range(y):
        cost = 0
        if p + q == 0:
            continue
        for i in range(1, n):
            if x_list[i] - x_list[i - 1] != p or y_list[i] - y_list[i - 1] != q:
                cost += 1
        ans = min(ans, cost)

print(ans + 1)

Submission status: Wrong Answer

Solution code:
n = int(input())
xs = []
ys = []
tilt_set = set()

# def is_available(cost):
#     tilt_set = set()
#     for i in range(n):
#         for j in range(i + 1, n):
#             tilt_set.add(ys[j]/ys[i] - xs[j]/xs[i])
#     if len(tilt_set) == cost:
#         return True
#     else:
#         return False

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


for i in range(n):
    for j in range(i + 1, n):
#        tilt_set.add(ys[j]/ys[i] - xs[j]/xs[i])
        if xs[j] == xs[i] or ys[j] == ys[i]:
            continue
        else:
            tilt_set.add((ys[j] - ys[i]) / (xs[j] - xs[i]))

#print(tilt_set)
print(len(tilt_set))

Submission status: Wrong Answer

Solution code:
N=int(input())
A=[]
for i in range(N):
  x,y=map(int,input().split())
  A.append((x,y))
ans=10000000
for k in range(N):
  for j in range(k):
    p=A[k][0]-A[j][0]
    q=A[k][1]-A[j][1]
    c=0
    for s in range(N):
      flag=False
      for t in range(N):
        if A[s][0]-p==A[t][0] and A[s][1]-q==A[t][1]:
          flag=True 
          break
      if not flag:
        c+=1
    ans=min(c,ans)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from itertools import combinations

def main():
    input = sys.stdin.readline
    N = int(input())
    cord = []
    for _ in range(N):
        x, y = map(int, input().split())
        cord.append((x, y))

    ans = 50
    for a in combinations(cord, 2):
        x1, y1 = a[0]
        x2, y2 = a[1]

        if x1 == x2:
            slope = 0
        else:
            slope = (y2 - y1) / (x2 - x1)

        intercepts = set()
        for x, y  in cord:
            intercept = y - slope * x
            intercept = round(intercept, 5)
            intercepts.add(intercept)

        ans = min(ans, len(intercepts))

    return ans


if __name__ == '__main__':
    print(main())

Submission status: Wrong Answer

Solution code:
N = int(input())
xy = sorted([list(map(int, input().split())) for _ in range(N)])
diffx = set()
diffy = set()
for i in range(N-1):
    diffx.add(xy[i+1][0] - xy[i][0])
    diffy.add(xy[i+1][1] - xy[i][1])
ans = 51
for p in diffx:
    for q in diffy:
        cost = 1
        for i in range(1, N):
            if xy[i-1][0] - p == xy[i][0] and xy[i-1][1] - q == xy[i][1]:
                continue
            cost += 1
        ans = min(cost, ans)
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter

n = int(input())
xy = [list(map(int,input().split())) for i in range(n)]
ball = []
x,y = xy[0][0],xy[0][1]

for xx,yy in xy[1:]:
	ball.append([xx-x,yy-y])
	x = xx
	y = yy

ball.sort()

res = 1
ans = 1
cur = [10**9,10**9]
for x,y in ball:
	# print(x,y,cur)
	if x == cur[0] and y == cur[1]:
		res+=1
	else:
		ans = max(ans,res)
		res = 1
		cur = [x,y]
ans = max(ans,res)
print(n-ans)

Submission status: Wrong Answer

Solution code:
N = int(input())

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

vec = []
for i in range(N):
    for j in range(i+1,N,1):
        vec.append([point[i][0]-point[j][0],point[i][1]-point[j][1]])

N2 = len(vec)
check = [[0 for i in range(N2)] for j in range(N2)]

for i in range(N2):
    for j in range(i+1,N2,1):
        minus = [-vec[j][0],-vec[j][1]]
        if vec[i] == vec[j] or vec[i] == minus:
            check[i][j] += 1
#print(vec,check)

ans = 0
for i in range(N2):
    for j in range(N2):
        cnt = check[i][j]+check[j][i]
        if ans < cnt:
            ans = cnt

if N == 2:
    print(1)
else:
    print(N-ans-1)

Submission status: Wrong Answer

Solution code:
def sol(inp=input):
    n=int(inp())
    pts=[tuple(map(int,inp().split())) for _ in range(n)]
    min_cost=n
    pt1=pts[0]
    for pt2 in pts[1:]:
        p,q=(pt1[0]-pt2[0],pt1[1]-pt2[1])
        searched=[False for _ in range(n)]
        searched[0]=True
        cost=1
        for i,pt in enumerate(pts):
            if searched[i]:
                continue
            searched[i]=True
            if (pt[0]+p,pt[1]+q) not in pts:
                cost+=1
        min_cost=min(cost,min_cost)
    return '{}'.format(min_cost)
print(sol())

Submission status: Wrong Answer

Solution code:
N = int(input())

l = []
for _ in range(N) :
    ll = list(map(int, input().split()))
    l.append(ll)

#print(l)

dic = {}

for i in range(1, N) :
    #subl.append([l[i][0] - l[i-1][0], l[i][1] - l[i-1][1]])
    #k = 1000000001*(l[i][0] - l[i-1][0]) + l[i][1] - l[i-1][1]
    k = str(l[i][0] - l[i-1][0]) + '+' + str(l[i][1] - l[i-1][1])

    if l[i][0] - l[i-1][0] == 0 and l[i][1] - l[i-1][1] == 0:
        continue

    if k not in dic :
        dic[k] = 1
    else :
        dic[k] += 1

#print(dic)

if len(dic) == 0 :
    print(N)
else :
    print(N - max(dic.values()))

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque  # 双方向キュー
from collections import defaultdict  # 初期化済み辞書
from heapq import heapify, heappush, heappop, heappushpop  # プライオリティキュー
from bisect import bisect_left, bisect_right  # 二分探索
#import numpy as np  # 1.8.2
#import scipy  # 0.13.3

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in ss]
ss2nnn = lambda ss: [s2nn(s) for s in ss]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline().rstrip() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

def main():
    N = i2n()
    xy = ii2nnn(N)
    dicx = defaultdict(lambda: 0)
    xy.sort(key=lambda v: v[1])
    xy.sort(key=lambda v: v[0])
    for i in range(1, len(xy)):
        dx = xy[i][0] - xy[i-1][0]
        dy = xy[i][1] - xy[i-1][1]
        if dx == 0 and dy == 0:
            continue
        key = '%d %d' % (dx, dy)
        dicx[key] += 1
    dicy = defaultdict(lambda: 0)
    xy.sort(key=lambda v: v[1])
    for i in range(1, len(xy)):
        dx = xy[i][0] - xy[i-1][0]
        dy = xy[i][1] - xy[i-1][1]
        if dx == 0 and dy == 0:
            continue
        key = '%d %d' % (dx, dy)
        dicy[key] += 1
    nm = 0
    for v in dicx.values():
        if nm < v:
            nm = v
    for v in dicy.values():
        if nm < v:
            nm = v
    print(N - nm)

main()

Submission status: Wrong Answer

Solution code:
N = int(input())

prev_a, prev_b = map(int, input().split())
diffs = {}
for _ in range(N - 1):
  a, b = map(int, input().split())
  key = "{} {}".format(prev_a - a, prev_b - b)
  if key not in diffs:
    diffs[key] = 1
  else:
    diffs[key] += 1

if (len(diffs.values()) <= 1):
  print(1)
else:
  print(N - 1 - max(diffs.values()))

Submission status: Wrong Answer

Solution code:
import sys
from itertools import combinations

def main():
    input = sys.stdin.readline
    N = int(input())
    cord = []
    for _ in range(N):
        x, y = map(int, input().split())
        cord.append((x, y))

    ans = 50
    for a in combinations(cord, 2):
        x1, y1 = a[0]
        x2, y2 = a[1]

        if x1 == x2:
            slope = 0
        else:
            slope = (y2 - y1) / (x2 - x1)

        intercepts = set()
        for x, y  in cord:
            intercept = y - slope * x
            intercept = round(intercept, 5)
            intercepts.add(intercept)

        print(intercepts)
        ans = min(ans, len(intercepts))

    return ans


if __name__ == '__main__':
    print(main())

Submission status: Wrong Answer

Solution code:
n = int(input())
x = [0]*n
dis = {}

for i in range(n) :
	x[i] = input()
x.sort()

for i in range(n-1) :
	nowX, nowY = x[i].split()
	pastX, pastY = x[i+1].split()
	s = str(int(pastX)-int(nowX)) + "," + str(int(pastY)-int(nowY))
	if s in dis : dis[s] += 1
	else : dis[s] = 1

print(len(dis))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = [tuple(map(int, input().split())) for i in range(n)]
t = set(a)
minans = 1000000000000
for i in range(n):
    for j in range(i + 1, n):
        r = t.copy()
        p = a[i][0] - a[j][0]
        q = a[i][1] - a[j][1]
        curans = 0
        while r:
            curans += 1
            m = r.pop()
            z = m
            while (m[0] + p, m[1] + q) in r:
                m = (m[0] + p, m[1] + q)
                r.remove(m)
            m = z
            while (m[0] - p, m[1] - q) in r:
                m = (m[0] - p, m[1] - q)
                r.remove(m)
        minans = min(minans, curans)
print(minans)

Submission status: Wrong Answer

Solution code:
import numpy as np
N = int(input())
x_y = []
for i in range(N):
	x_y.append(list(map(int,input().split())))
ans_1 = []	
ans_2 = []
if N == 1:
	print(1)
else:
	for i in range(N):
		first_ = x_y[i]
		for j in range(N - 1 - i):
			second_ = x_y[i+j+1]
			dif = [abs(first_[0] - second_[0]),abs(first_[1] - second_[1])]
			if dif not in ans_1:
				ans_1.append(dif)
				ans_2.append(1)
			else:
				ans_2[ans_1.index(dif)] += 1
				
	print(N - max(ans_2))

Submission status: Wrong Answer

Solution code:
n = int(input())
xy = []
diff = []
for _ in range(n):
  tmp = list(map(int,input().split()))
  xy.append(tmp)
for i in range(n):
  for j in range(n):
    if j != i:
      tmpd = [ xy[j][0] - xy[i][0] , xy[j][1] - xy[i][1] ]
      flag = 0
      for mxy in diff:
        if mxy[1:] == tmpd:
            flag = 1
            mxy[0] += 1
            break
      if flag == 0:
        diff.append([0]+tmpd)
diff.sort()
diff.reverse()
if n == 1:
  print(0)
else:
  print(n-diff[0][0]-1)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
import sys
N = int(input())
B = [[int(i) for i in input().split()] for i in range(N)]
B.sort()

d = []
for i, b in enumerate(B[1:]):
    d.append([b[0] - B[i][0], b[1] - B[i][1]])
dt = list(map(tuple, d))
ans = len(set(dt))
print(ans)