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 _ in range(N):
    temp_x, temp_y = map(int, input().split())
    xy.append((temp_x, temp_y))

sort_xy = sorted(xy)
diff = []
prev_x = 0
prev_y = 0
for (x,y) in sort_xy:
    diff.append((x-prev_x, y-prev_y))
    prev_x = x
    prev_y = y

diff.pop(0)
    
print(len(set(diff)))

Submission status: Wrong Answer

Solution code:
from collections import Counter
n = int(input())
a = [list(map(int,input().split())) for _ in range(n)]
if n == 1:
    print(1)
    exit()

b = sorted(a)
c = sorted(a, key=lambda x:x[1])
bd = []
cd = []
for i in range(n-1):
    b0 = b[i+1][0] - b[i][0]
    b1 = b[i+1][1] - b[i][1]
    bd.append((b0, b1))
    
    c0 = c[i+1][0] - c[i][0]
    c1 = c[i+1][1] - c[i][1]
    cd.append((c0, c1))
    
cbd = Counter(bd)
ccd = Counter(cd)
print(n-max(cbd.most_common()[0][1], ccd.most_common()[0][1]))

Submission status: Wrong Answer

Solution code:
import atexit
import io
import sys

buff = io.BytesIO()
sys.stdout = buff


@atexit.register
def write():
    sys.__stdout__.write(buff.getvalue())

n = input()
d = {}
l = []
for i in xrange(n):
	x,y = map(int, raw_input().split())
	d[(x,y)] = i
	l.append((x,y))
l.sort()
ans = n
for i in xrange(n):
	for j in xrange(n):
		if i == j:
			continue
		curr = 0
		flag = [0 for k in xrange(n)]
		p = l[j][0] - l[i][0]
		q = l[j][1] - l[i][1]
		for k in xrange(n):
			if flag[k]:
				continue
			curr += 1
			index = k
			flag[k] = 1
			while True:
				next_x = l[index][0] + p
				next_y = l[index][1] + q
				if (next_x, next_y) in d:
					if flag[d[(next_x, next_y)]] == 1:
						break
					flag[d[(next_x, next_y)]] = 1
				else:
					break
				index = d[(next_x, next_y)]
		ans = min(ans, curr)
print ans

Submission status: Wrong Answer

Solution code:
def make_key(x, y):
    return str(x) + "k" + str(y)


inp = input()
n = int(inp)
balls = []
for i in range(n):
    inp = input()
    split_input = inp.split()
    x = int(split_input[0])
    y = int(split_input[1])
    balls.append([x, y])
possible_pq = {}
max_key = None
max_number = 0
for base_ball in balls:
    for target_ball in balls:
        diff_x = target_ball[0] - base_ball[0]
        diff_y = target_ball[1] - base_ball[1]
        if diff_x < 0:
            diff_x = diff_x * -1
            diff_y = diff_y * -1
        if diff_y == 0 and diff_x == 0:
            continue
        diff = make_key(diff_x, diff_y)
        if diff in possible_pq:
            possible_pq[diff] = possible_pq[diff] + 1
        else:
            possible_pq[diff] = 1
        if max_number < possible_pq[diff]:
            max_number = possible_pq[diff]
            max_key = diff
print(n - max_number // 2)

Submission status: Wrong Answer

Solution code:
x = []
y = []

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

if N == 1:
    print(1)
    exit()
    
count = 1
p = x[1] - x[0]
q = y[1] - y[0]

# print("p, q = ", p, q)

for i in range(1, N):
    if ((x[i-1] + p) != x[i]) or ((y[i-1] + q) != y[i]):
        count += 1
        

count2 = 1
p2 = x[N-2] - x[N-1]
q2 = y[N-2] - y[N-1]

# print("p2, q2 = ", p2, q2)

for i in range(1, N):
    if ((x[i-1] - p) != x[i]) or ((y[i-1] - q) != y[i]):
        count2 += 1

if count < count2:
    print(count)
else:
    print(count2)

Submission status: Wrong Answer

Solution code:
def count(xy, pq):

    cnt = 0
    for k in range(n):
        
        for l in range(k+1, n):
            if (xy[l][0] - xy[k][0] == pq[0]) and (xy[l][1] - xy[k][1] == pq[1]):
                cnt += 1



    return cnt


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

m = 0
xy.sort(key = lambda xy:xy[0])
for i in range(n):
    for j in range(i+1, n):
        pq = [xy[j][0] - xy[i][0], xy[j][1] - xy[i][1]]
        if m < count(xy,pq):
            m = count(xy,pq)
print(n-m)

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)
u = c.most_common()[0][1]
if u == 1:
    u = 0

print(n-u)

Submission status: Wrong Answer

Solution code:
import collections

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

ans_li = []
rest = len(li)-1

for i in range(len(li)):
  for j in range(rest):
    x = li[i][0] - li[-j][0]
    y = li[i][1] - li[-j][1]
    ans_li.append([x,y])

  rest -= 1
  
# c = collections.Counter(ans_li)
max_a = 0
for i in ans_li:
  a = ans_li.count(i)
  if a > max_a:
    max_a = a
print(max_a)
# print(c.most_common()[0,1])

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]
    if k == 0 :
        continue

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

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

Submission status: Wrong Answer

Solution code:
N = int(input())
XY = []
for i in range(N):
  XY.append(list([int(i) for i in input().split()]))

diff_XY = []
ans = N

for i in range(N):
  for j in range(i+1,N):
    diff_XY.append([XY[i][0]-XY[j][0],XY[i][1]-XY[j][1]])

ans_diff = 1

for xy in diff_XY:
  ans_diff = max(ans_diff,diff_XY.count(xy))

print(ans-ans_diff)

Submission status: Wrong Answer

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left, bisect_right
from copy import copy
inf=float('inf')
mod = 10**9+7
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N = I()
    XY = LLIN(N)
    ans = inf
    for i in range(N):
        for j in range(N):
            if i == j:
                continue
            p = XY[i][0] - XY[j][0]
            q = XY[i][1] - XY[j][1]
            pre_exist = set()
            pre_exist.add((XY[i][0], XY[i][1]))
            mini_ans = 1
            for (x, y) in XY:
                found = False
                for (px, py) in pre_exist.copy():
                    dx = px - x
                    dy = py - y
                    if p == 0 and q == 0:
                        found = True
                        break
                    else:
                        if p == 0:
                            if dy / q == dy // q and dx==0:
                                found = True
                                break
                            continue
                        elif q == 0:
                            if dx / p == dx // p and dy==0:
                                found = True
                                break
                            continue
                    if dx / p == dy / q:
                        if dx/p == dx//p:
                            found = True
                            break
                    else:
                        continue
                if not found:
                    pre_exist.add((x,y))
                    mini_ans += 1
                        
            ans = min(ans, mini_ans)
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
n = int(input())
xy = [list(map(int, input().split())) for i in range(n)]

xy.sort()
s = defaultdict(int)
for i in range(n-1):
  s[(xy[i+1][0]-xy[i][0], xy[i+1][1]-xy[i][1])] += 1
s[(0, 0)] = 0
m = max(s.values())
ans = 1 + (n-m-1)

xy.sort(key=lambda x: x[1])
s = defaultdict(int)
for i in range(n-1):
  s[(xy[i+1][0]-xy[i][0], xy[i+1][1]-xy[i][1])] += 1
s[(0, 0)] = 0
m = max(s.values())
ans = min(ans, 1 + (n-m-1))

print(ans)

Submission status: Wrong Answer

Solution code:
def cul(p,q):
    tmp=0
    for i in range(1,N):
        for j in range(i):
            tmpp,tmpq=a[i][0]-a[j][0],a[i][1]-a[j][1]
            if tmpp==p and tmpq==q: tmp+=1
            elif tmpp==-p and tmpq==-q: tmp+=1
    return N-tmp

N=int(input())
dic={}
ans=100
a=[list(map(int,input().split())) for i in range(N)]
for i in range(1,N):
    for j in range(i):
        p,q=a[i][0]-a[j][0],a[i][1]-a[j][1]
        ans=min(ans,cul(p,q))
    
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

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

X2 = np.array(X)
Y2 = np.array(Y)

I = list(range(N))


for i in range(N):
  z = np.polyfit(X2, Y2, 1)
  YY = np.polyval(z, X2)
  D = (YY - Y2)
  j = np.argmax(np.abs(D))
  if (np.abs(D[j]) < 0.00001):
    break
  np.delete(X2, j)
  np.delete(Y2, j)

YY = np.polyval(z, np.array(X))
D = (YY - np.array(Y))
J = np.where(np.abs(D) >= 0.00001)
print(len(J) + 1)

Submission status: Wrong Answer

Solution code:
###############################################################################

from sys import stdout
from bisect import bisect_left as binl
from copy import copy, deepcopy
from collections import defaultdict
import math


mod = 1


def intin():
    input_tuple = input().split()
    if len(input_tuple) <= 1:
        return int(input_tuple[0])
    return tuple(map(int, input_tuple))


def intina():
    return [int(i) for i in input().split()]


def intinl(count):
    return [intin() for _ in range(count)]


def modadd(x, y):
    global mod
    return (x + y) % mod


def modmlt(x, y):
    global mod
    return (x * y) % mod


def mod_inv(x):
    # available only when mod is prime
    global mod
    return pow(x, mod - 2, mod)


def gcm(x, y):
    while y != 0:
        z = x % y
        x = y
        y = z
    return x


def combination(x, y):
    assert(x >= y)

    ret = math.factorial(x)
    ret = ret // (math.factorial(x - y) * math.factorial(y))

    return ret


def get_divisors(x):
    retlist = []
    for i in range(1, int(x**0.5) + 3):
        if x % i == 0:
            retlist.append(i)
            retlist.append(x // i)
    return retlist


def get_factors(x):
    retlist = []
    for i in range(2, int(x**0.5) + 3):
        while x % i == 0:
            retlist.append(i)
            x = x // i
    retlist.append(x)
    return retlist


def make_linklist(xylist):
    linklist = {}
    for a, b in xylist:
        linklist.setdefault(a, [])
        linklist.setdefault(b, [])
        linklist[a].append(b)
        linklist[b].append(a)
    return linklist


def calc_longest_distance(linklist, v=1):
    distance_list = {}
    distance_count = 0
    distance = 0
    vlist_previous = []
    vlist = [v]
    nodecount = len(linklist)

    while distance_count < nodecount:
        vlist_next = []
        for v in vlist:
            distance_list[v] = distance
            distance_count += 1
            vlist_next.extend(linklist[v])
        distance += 1
        vlist_to_del = vlist_previous
        vlist_previous = vlist
        vlist = list(set(vlist_next) - set(vlist_to_del))

    max_distance = -1
    max_v = None
    for v, distance in distance_list.items():
        if distance > max_distance:
            max_distance = distance
            max_v = v

    return (max_distance, max_v)


def calc_tree_diameter(linklist, v=1):
    _, u = calc_longest_distance(linklist, v)
    distance, _ = calc_longest_distance(linklist, u)
    return distance


class UnionFind:

    def __init__(self, n):
        self.parent = [i for i in range(n)]

    def root(self, i):
        if self.parent[i] == i:
            return i
        self.parent[i] = self.root(self.parent[i])
        return self.parent[i]

    def unite(self, i, j):
        rooti = self.root(i)
        rootj = self.root(j)
        if rooti == rootj:
            return
        if rooti < rootj:
            self.parent[rootj] = rooti
        else:
            self.parent[rooti] = rootj

    def same(self, i, j):
        return self.root(i) == self.root(j)


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


def main():
    n = intin()
    xylist = intinl(n)

    pqmap = defaultdict(list)

    for i in range(n):
        for j in range(n):
            if i == j:
                continue
            ansl = 1
            x1, y1 = xylist[i]
            x2, y2 = xylist[j]

            p = abs(x1 - x2)
            q = abs(y1 - y2)
            g = gcm(p, q)
            p = p // g
            q = q // g

            pqmap[(p, q)].append((i, j))

    pqcount = defaultdict(int)
    checkedlist = []
    for (p, q), ijlist in pqmap.items():
        for i, j in ijlist:
            if i in checkedlist and j in checkedlist:
                continue
            checkedlist.append(i)
            checkedlist.append(j)
            pqcount[(p, q)] += 1

    maxpqcount = 0
    for count in pqcount.values():
        maxpqcount = max(maxpqcount, count)

    print(n - maxpqcount)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys,collections,math,random;sys.setrecursionlimit(10**7)
def Is(): return [int(x) for x in sys.stdin.readline().split()]
def Ss(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

n = I()
d = collections.defaultdict(int)
x,y = Is()
for i in range(n-1):
    nx,ny = Is()
    diff = nx - x, ny - y
    d[tuple(diff)] += 1
    x,y = nx,ny
d = d.items()
#print(d)
maxi = 0
for e in d:
    maxi = max(maxi,e[1])
print(n-maxi)

Submission status: Wrong Answer

Solution code:
import itertools


def main():
  n = int(input())
  p = [tuple(map(int, input().split())) for _ in range(n)]
  c = {}

  if n == 1:
    print(1)
    return

  for i, j in itertools.combinations(range(len(p)), 2):
    d = (abs(p[j][0] - p[i][0]), abs(p[j][1] - p[i][1]))

    if d not in c:
      c[d] = 1
    else:
      c[d] += 1

  print(len(p) - max(c.values()))


if __name__ == '__main__':
  main()

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
        if xd>0: yd= yj - yi
        else: yd= yi - yj
        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())
A = [[int(s) for s in input().split()] for _ in range(N)]
x0, y0 = A[0]
cost = N
for xi, yi in A[1:]:
    p = x0 - xi
    q = y0 - yi
    cost = min([cost, len(set([q * a[0] - p * a[1] for a in A]))])

print(cost)

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]
        for idx, d3 in enumerate(x):
            for d4 in x[(idx + 1):]:
                if 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
        ans = min(ans, tmp)
print(max(1, ans))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7


import collections
import itertools
import operator


class UnionFind:
    def __init__(self, elems=None):
        class KeyDict(dict):
            def __missing__(self, key):
                self[key] = key
                return key

        self.parent = KeyDict()
        self.rank = collections.defaultdict(int)

        if elems is not None:
            for elem in elems:
                _, _ = self.parent[elem], self.rank[elem]

    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1

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

    def grouper(self):
        roots = [(x, self.find(x_par)) for x, x_par in self.parent.items()]
        root = operator.itemgetter(1)
        for _, group in itertools.groupby(sorted(roots, key=root), root):
            yield [x for x, _ in group]


def main(): 
    N = II()
    position = []
    for _ in range(N):
        position.append(LI())

    min_ = INF
    import itertools
    for A, B in itertools.combinations(range(N), 2):
        uf = UnionFind(range(N))
        p = position[A][0] - position[B][0]
        q = position[A][1] - position[B][1]
        # print(p,q)
        uf.unite(A, B)
        for X, Y in itertools.combinations(range(N), 2):
            if A == X and B == Y:
                continue
            if (p == position[X][0] - position[Y][0] and q == position[X][1] - position[Y][1]) or (p == position[Y][0] - position[X][0] and q == position[Y][1] - position[X][1]):
                uf.unite(X, Y)
        
        min_ = min(min_, len(list(uf.grouper())))
    print(min_)


main()

Submission status: Wrong Answer

Solution code:
N=int(input())
 
X=[]
for i in range(N):
  X.append(list(map(int,input().split())))
  
X.sort()
PQ=[]
 
for i in range(1,N):
  [p,q]=[X[i][0]-X[i-1][0],X[i][1]-X[i-1][1]]
  if [p,q] not in PQ:
    PQ.append([p,q])
print(len(PQ))

Submission status: Wrong Answer

Solution code:
def solve():
  n = int(input())
  queue = []
  queue2 = []
  for i in range(n):
   x,y = (int(i) for i in input().split())
   queue.append((x,y))
  for i in range(n):
    for j in range(n):
      if i!=j:
        x1,y1 = queue[i]
        x2,y2 = queue[j]
        p = x2-x1
        q = y2-y1
        queue2.append((p,q))
  queue2 = list(set(queue2))
  ans = n
  while queue2:
    p,q = queue2.pop(0)

    for j in range(n):
     nx,ny = queue[j]
     cost = 0
     for i in range(n):
      x,y = queue[i]
      if nx == x and ny == y:
        cost += 1
      else:
        #print(nx,ny,x,y,p,q)
        if (x-p == nx)and(y-q == ny):
         cost += 0
        else:
         cost += 1
        nx = x
        ny = y
     #print(cost)
     ans = min(ans,cost)
  print(ans)
solve()

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 = []
for i in range(len(sub)):
    if sub[i] not in tmpli:
        tmpli.append(sub[i])

ans = len(tmpli)
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
xy_array = [[int(x) for x in input().split()] for y in range(n)]
xy_array = sorted(xy_array, key=lambda x: (x[0], x[1]))

a_array = []
tmp_x, tmp_y = xy_array[0]
for x, y in xy_array[1:]:
    a_array.append([tmp_x-x, tmp_y-y])
    tmp_x, tmp_y = x, y

res = float("inf")
for ax, ay in a_array:
    tmp_res = 1
    now_x, now_y = xy_array[-1]
    for x, y in reversed(xy_array[:-1]):
        if now_x+ax == x and now_y+ay == y:
            pass
        else:
            tmp_res += 1
        now_x, now_y = x, y
    res = min(res, tmp_res)
print(res)

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

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:
# -*- coding: utf-8 -*-

import sys
from itertools import combinations
from collections import Counter

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N=INT()

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

xy=[]
for i in range(N):
    x,y=MAP()
    xy.append((x, y))

C=Counter()
for comb in combinations(xy, 2):
    a,b=comb
    C[(a[0]-b[0], a[1]-b[1])]+=1

mx=max(C.values())
print(N-mx)

Submission status: Wrong Answer

Solution code:

n=int(input())

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

diffs={}
for i in range(n-1):
    for j in range(i+1,n):
        dx=pts[i][0]-pts[j][0]
        dy=pts[i][1]-pts[j][1]
        if dx<0 :
            dx=-dx
            dy=-dy
        key="{},{}".format(dx,dy)
        if key in diffs:
            diffs[key]+=1
        else:
            diffs[key]=1

max=0
maxkey=""
for k,v in diffs.items():
    if v>max:
        max=v
        maxkey=k
        
print(n-max)

Submission status: Wrong Answer

Solution code:
N=int(input())
ball=[tuple(map(int,input().split())) for i in range(N)]
ans=N-1
for i in range(N-1):
    for j in range(i+1,N):
        cost=1
        p=ball[j][0]-ball[i][0]
        q=ball[j][1]-ball[i][1]
        used={i,j}
        for l in range(N):
            if l not in used:
                    x=ball[l][0]-ball[i][0]
                    y=ball[l][1]-ball[i][1]
                    a,b,c=False,False,False
                    if p==0:
                        if x==0:
                            a=True
                            c=True
                        if y%q==0:
                            b=True
                    elif q==0:
                        if y==0:
                            b=True
                            c=True
                        if x%p==0:
                            a=True
                    elif p!=0 and q!=0:
                        if x%p==0 and y%q==0 and x//p==y//q:
                            a,b,c=True,True,True
                    if a and b and c:
                        used|={l}
        for k in range(N):
            if k in used:
                continue
            else:
                cost+=1
                used|={k}
                for l in range(N):
                    if l not in used:
                        x=ball[l][0]-ball[k][0]
                        y=ball[l][1]-ball[k][1]
                        a,b,c=False,False,False
                        if p==0:
                            if x==0:
                                a=True
                                c=True
                            if y%q==0:
                                b=True
                        elif q==0:
                            if y==0:
                                b=True
                                c=True
                            if x%p==0:
                                a=True
                        elif p!=0 and q!=0:
                            if x%p==0 and y%q==0 and x//p==y//q:
                                a,b,c=True,True,True
                        if a and b and c:
                            used|={l}
        if len(used)==N:
            ans=min(ans,cost)
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
n = int(input())
if n==1:
  print(1)
  exit()
xy = [list(map(int, input().split())) for i in range(n)]

xy.sort()
s = defaultdict(int)
for i in range(n-1):
  s[(xy[i+1][0]-xy[i][0], xy[i+1][1]-xy[i][1])] += 1
s[(0, 0)] = 0
m = max(s.values())
ans = 1 + (n-m-1)

xy.sort(key=lambda x: x[1])
s = defaultdict(int)
for i in range(n-1):
  s[(xy[i+1][0]-xy[i][0], xy[i+1][1]-xy[i][1])] += 1
s[(0, 0)] = 0
m = max(s.values())
ans = min(ans, 1 + (n-m-1))

print(ans)

Submission status: Wrong Answer

Solution code:
def make_key(x, y):
    return str(x) + "k" + str(y)


inp = input()
n = int(inp)
balls = []
for i in range(n):
    inp = input()
    split_input = inp.split()
    x = int(split_input[0])
    y = int(split_input[1])
    balls.append([x, y])
possible_pq = {}
max_key = None
max_number = 0
for base_ball in balls:
    # print("base")
    # print(base_ball)
    for target_ball in balls:
        diff_x = target_ball[0] - base_ball[0]
        diff_y = target_ball[1] - base_ball[1]
        if diff_x < 0:
            diff_x = diff_x * -1
            diff_y = diff_y * -1
        # print("target ")
        # print(target_ball)
        #
        # print(diff_x)
        # print(diff_y)
        diff = make_key(diff_x, diff_y)
        if diff in possible_pq:
            possible_pq[diff] = possible_pq[diff] + 1
        else:
            possible_pq[diff] = 1
        if max_number < possible_pq[diff]:
            max_number = possible_pq[diff]
            max_key = diff
# print(max_number)
# print(max_key)
print(n - max_number // 2)

Submission status: Wrong Answer

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


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

diff=[None]*(N-1)
for i in range(N-1):
  diff[i] = [x_y[i+1][1]-x_y[i][1],x_y[i+1][0]-x_y[i][0]]

diff = sorted(diff)
c=1
for i in range(N-2):
  if (diff[i+1][0]-diff[i][0]==0)and(diff[i+1][1]-diff[i][1]==0):
    pass
  else:
    c+=1

print(c)

Submission status: Wrong Answer

Solution code:
n = int(input())
xy = [list(map(int, input().split())) for _ in range(n)]
#
# xy.sort()
# xy = xy[::-1]
# sa = []
# for i in range(1, n):
#     sa.append([xy[i - 1][0] - xy[i][0], xy[i - 1][1] - xy[i][1]])
#
# xy.sort(key=lambda x:x[1])
# xy2 = xy
# print(xy2)
# xy2 = xy2[::-1]
# sa2 = []
# for i in range(1, n):
#     sa2.append([xy[i - 1][0] - xy[i][0], xy[i - 1][1] - xy[i][1]])
# print(sa, sa2)

sa = []
for i, j in xy:
    for k, l in xy:
        sa.append([i - k, j - l])

#sa1

xy.sort()
xy = xy[::-1]
ans = 10000000000000000000
i = 0
while True:
    if i >= len(sa):
        break
    if sa[i] == [0, 0]:
        del sa[i]
        i -= 1
    i += 1


for p, q in sa:
    tmp = 1
    for i in range(1, n):
        x = xy[i][0]
        y = xy[i][1]
        if xy[i - 1][0] == x - p and xy[i - 1][1] == y - q:
            1
        else:
            tmp += 1
    ans = min(ans, tmp)
xy.sort(key=lambda x:x[1])

for p, q in sa:
    tmp = 1
    for i in range(1, n):
        x = xy[i][0]
        y = xy[i][1]
        if xy[i - 1][0] == x - p and xy[i - 1][1] == y - q:
            1
        else:
            tmp += 1
    ans = min(ans, tmp)
if len(xy) == 1:
    ans = 1
print(ans)

Submission status: Wrong Answer

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

ans = N - 1
for i in range(N):
    for j in range(i + 1, N):
        xi, yi = P[i]
        xj, yj = P[j]

        tmp = 1
        if xj == xi:
            for x, y in P:
                if x != xi:
                    tmp += 1
        else:
            K = (yj - yi) / (xj - xi)
            for x, y in P:
                if x == xi:
                    tmp += 1
                    continue
                if (y - yi) / (x - xi) == K:
                    tmp += 0
                else:
                    tmp += 1

        ans = min(ans, tmp)

print(ans)

Submission status: Wrong Answer

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

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

memo = False
ans = 1e9+7
for x, y in diff:
  cost = 1
  for X, Y in XY:
    if not memo:
      memo = (X, Y)
      continue
    if (X - x, Y - y) == memo:
      pass
    else:
      cost += 1
    memo = (X, Y)
  ans = min(cost, ans)
print(ans)

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 = abs(xi - xj)
        yd = abs(yi - yj)
        k = "{} {}".format(xd,yd)
        distmap[k]= distmap.get(k,0) + 1
#
d = max( distmap.values() )
print( n-d )