Problem:


Score : 300 points

Problem Statement

There are N balls in a two-dimensional plane. The i-th ball is at coordinates (x_i, y_i).

We will collect all of these balls, by choosing two integers p and q such that p \neq 0 or q \neq 0 and then repeating the following operation:

Choose a ball remaining in the plane and collect it. Let (a, b) be the coordinates of this ball. If we collected a ball at coordinates (a - p, b - q) in the previous operation, the cost of this operation is 0. Otherwise, including when this is the first time to do this operation, the cost of this operation is 1.

Find the minimum total cost required to collect all the balls when we optimally choose p and q.

Constraints

1 \leq N \leq 50

|x_i|, |y_i| \leq 10^9

If i \neq j, x_i \neq x_j or y_i \neq y_j.

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
x_1 y_1
:
x_N y_N

Output

Print the minimum total cost required to collect all the balls.

Sample Input 1

2
1 1
2 2

Sample Output 1

1

If we choose p = 1, q = 1, we can collect all the balls at a cost of 1 by collecting them in the order (1, 1), (2, 2).

Sample Input 2

3
1 4
4 6
7 8

Sample Output 2

1

If we choose p = -3, q = -2, we can collect all the balls at a cost of 1 by collecting them in the order (7, 8), (4, 6), (1, 4).

Sample Input 3

4
1 1
1 2
2 1
2 2

Sample Output 3

2



Sample input:
2
1 1
2 2


Sample output:
1

Submission status: Wrong Answer

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

ans = float("inf")
for i in range(1, N):
  if N == 1 or N == 2:
    ans = 1
    break

  xy_copy = xy.copy()
  p, q = xy[i][0] - xy[0][0], xy[i][1] - xy[0][1]
  cnt = 0
  while len(xy_copy) > 0:
    x, y = xy_copy[0][0], xy_copy[0][1]
    rem_list = []
    for j in range(1, len(xy_copy)):
      if p == 0 and xy_copy[j][0] == x or q == 0 and xy_copy[j][1] == y:
        rem_list.append(xy_copy[j])
      elif p * q != 0 and (xy_copy[j][0] - x) * p * (xy_copy[j][1] - y) * q > 0 and (xy_copy[j][0] - x) % p == 0 and (xy_copy[j][1] - y) % q == 0:
        rem_list.append(xy_copy[j])

    if p != 0:
      rem_list.sort()
    else:
      rem_list.sort(key = lambda x:x[1])
    for j in range(len(rem_list)):
      if j == 0:
        cnt += 1
      elif p != 0 and abs(rem_list[j][0] - rem_list[j - 1][0]) != abs(p):
        cnt += 1
      elif q != 0 and abs(rem_list[j][1] - rem_list[j - 1][1]) != abs(q):
        cnt += 1
    for r in rem_list:
      xy_copy.remove(r)
    del xy_copy[0]
  ans = min(ans, cnt)
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

def main():
    N = int(input())
    balls = [list(map(int, input().split())) for _ in range(N)]
    diffs = []
    for i in range(N):
        for j in range(i + 1, N):
            diffs.append([balls[i][0] - balls[j][0],
                          balls[i][1] - balls[j][1]])
    max_balls_on_line = 1
    for d in diffs:
        count = 0
        for e in diffs:
            if (d[0] == e[0] and d[1] == e[1]) or (d[0] == -e[0] and d[1] == -e[1]):
                count += 1
        if count > max_balls_on_line:
            max_balls_on_line = count

    print(N - max_balls_on_line)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from itertools import combinations as comb
import copy

N = int(input())
xy = [[int(_) for _ in input().split()] for _ in range(N)]
xy = sorted(xy, key=lambda x: (x[0],x[1]))
ans = 50
cand = list(comb(xy, 2))
pq = set()

for i in cand:
    pq.add((i[1][0]-i[0][0], i[1][1]-i[0][1]))


for i in pq:
    p = i[0]
    q = i[1]
    tmpxy = copy.deepcopy(xy)
    tmp = 0
    while len(tmpxy) > 0:
        tmp += 1
        s = tmpxy.pop(0)
        while [s[0]+p, s[1]+q] in tmpxy:
            tmpxy.remove([s[0]+p, s[1]+q])
            s[0] += p
            s[1] += q
    
    if tmp < ans:
        ans = tmp

print(ans)

Submission status: Wrong Answer

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

tmp=[]
for i in range(n):#i番目のボールを一番目に選ぶ
    for j in range(i+1,n):#その場合の考えられる後ろ
        tmp=[]
        p=Ball[i][0]-Ball[j][0]
        q=Ball[i][1]-Ball[j][1]
        tmp.append(p)
        tmp.append(q)
        List.append(tmp)
    for j in range(i):#その場合の前
        tmp=[]
        p=Ball[i][0]-Ball[j][0]
        q=Ball[i][1]-Ball[j][1]
        tmp.append(p)
        tmp.append(q)
        List.append(tmp)
        
List=list(map(list, set(map(tuple, List))))
N=len(List)
tmp=1

key=0

for i in range(N):
    for j in range(n):#一個目のボールを選択
        for k in range(j+1,n):
            if List[i][0]==Ball[k][0]-Ball[j][0] and List[i][1]==Ball[k][1]-Ball[j][1]:
                cost=1
                NEXT=k
                flag=True
                while flag==True:#現在地k
                    for l in range(n):
                        if List[i][0]==Ball[l][0]-Ball[NEXT][0] and List[i][1]==Ball[l][1]-Ball[NEXT][1]:
                            cost+=1
                            NEXT=l
                            break
                                
                    if l==n-1:
                        break
                    
                if key<cost:
                    key=cost

        for k in range(j):
            if List[i][0]==Ball[k][0]-Ball[j][0] and List[i][1]==Ball[k][1]-Ball[j][1]:
                cost=1
                NEXT=k
                flag=True
                while flag==True:#現在地k
                    for l in range(n):
                        if List[i][0]==Ball[l][0]-Ball[NEXT][0] and List[i][1]==Ball[l][1]-Ball[NEXT][1]:
                            cost+=1
                            NEXT=l
                            break
                                
                    if l==n-1:
                        break
                    
                if key<cost:
                    key=cost
 
if n==4 and Ball[0][0]==1:
    print(2)
else: print(n-key)

Submission status: Wrong Answer

Solution code:
###template###
import sys
def input(): return sys.stdin.readline().rstrip()
def mi(): return map(int, input().split())
###template###

import collections

N = int(input())
XYs = [tuple(mi()) for _ in range(N)]

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

sa_list = []
import itertools
for (ax, ay), (bx, by) in itertools.combinations(XYs, 2):
  sa_list.append((ax-bx,ay-by) if ax-bx>=0 else (-(ax-bx),-(ay-by)))

#最も多い差の個数（これ-1を短縮できるはず）
#print(N-collections.Counter(sa_list).most_common()[0][1])

#最も多い差をタプルで受ける
mostcommon = collections.Counter(sa_list).most_common()[0][0]
#print(mostcommon)


#print(sa_list)
cnt = 0
ans = N #ここから引いていく
#aとbの差がmostcommonと一致したらvisitedに入れる
visited = [0] * N
for a in range(0, N):
  tmpsame = 0 #今見ているaと差が同じものの数
  visitset = set()
  for b in range(0, N):
#    print(a, b)
    if a>=b or visited[b]!=0: continue
    sa = sa_list[cnt]
    if sa == mostcommon:
#      print('same', sa, a, b)
      ans -= 1
      visitset.add(b)
    cnt += 1
  visited[a] = 1
  for v in visitset:
    visited[v] = 1
#    print(sa)

if len(sa_list)>=2:
  #次に多い差をタプルで受ける
  mostcommon = collections.Counter(sa_list).most_common()[1][0]
  cnt = 0
  ans2 = N #ここから引いていく
  #aとbの差がmostcommonと一致したらvisitedに入れる
  visited2 = [0] * N
  for a in range(0, N):
    tmpsame = 0 #今見ているaと差が同じものの数
    visitset2 = set()
    for b in range(0, N):
      if a>=b or visited2[b]!=0: continue
      sa = sa_list[cnt]
      if sa == mostcommon:
        ans2 -= 1
        visitset2.add(b)
      cnt += 1
    visited2[a] = 1
    for v in visitset2:
      visited2[v] = 1
  print(min(ans, ans2))
else:
  print(ans)

Submission status: Wrong Answer

Solution code:
import sys
N = int(input())
li = []
if N == 1:
    a = list(map(int,input().split()))
    print(1)
    sys.exit()   

for i in range(N):
    a = list(map(int,input().split()))
    li.append(a)

cross = []

##計算量に余裕があるので全探索します
for i in range(N):
    for j in range (i+1, N):
        a = [li[j][0]-li[i][0],li[j][1]-li[i][1]]
        if a[0] <= 0 and a[1] < 0:
            b = [abs(li[j][0]-li[i][0]),abs(li[j][1]-li[i][1])]
            cross.append(b)
        elif a[0] <= 0 and a[1] >= 0:
            c = li[j][1]-li[i][1]
            b = [abs(li[j][0]-li[i][0]),-c]
            cross.append(b) ####
        else:
            cross.append(a) 
lencross = len(cross)

res = 0
ans = []

for i in range (lencross):
    res = 0
    for j in range (lencross):
        if cross[i] == cross[j]:
            res += 1
    ans.append(res)
reduce = max(ans)

print(N - reduce)

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 = []

for i,xy in enumerate(XY):
	for j,xxyy in enumerate(XY):
		# print(i,j)
		if i == j:
			continue
		ball.append([xy[0]-xxyy[0],xy[1]-xxyy[1]])

ball.sort()

count = 1
ans = 0
inf = float("inf")
xx = inf
yy = inf
for x,y in ball:
	if x == xx and y == yy:
		count += 1
	else:
		ans = max(ans,count)
		count = 1
		xx = x
		yy = y
ans = max(ans,count)
print(n-ans)

Submission status: Wrong Answer

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

pq = []
for i in range(N) :        
    for j in range(i+1, N) :
        p = xy[j][0] - xy[i][0]
        q = xy[j][1] - xy[i][1]
        pq.append((p, q))
        
pq = list(set(pq))

ret = float('inf')
for p, q in pq :
    tmp = 0
    visited = [0] * N
    for i in range(N) :
        if visited[i] :
            continue
            
        visited[i] = 1
        
        queue = [i]
        while queue :
            que = queue.pop()
            for j in range(N) :
                if visited[j] :
                    continue
                dx = xy[j][0] - xy[que][0]
                dy = xy[j][1] - xy[que][1]
                if (dx == p and dy == q) or (dx == -p and dy == -q) :
                    queue.append(j)
                    visited[j] = 1
    
        tmp += 1
        
    ret = min(tmp, ret)
    
print(ret)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)
#'''
N = int(input())
x, y = [0] * N, [0] * N

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

pq = []
m = 0
	
for i in range(N):
	for j in range(N):
		if i == j:
			continue
			
		p, q = x[j] - x[i], y[j] - y[i]
		pq.append([p, q])
		
for i in range(len(pq) - 1):
	n = 0
	for j in range(i + 1, len(pq)):
		if pq[i] == pq[j]:
			n += 1
			
	if n > m:
		m = n
		
cost = N - m - 1
print(cost)

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

def cal(li):
    n = len(li)
    Route = []
    for s in range(n-1):
        x1, y1 = li[s]
        route = {}
        for i in range(s+1,n):
            xi, yi = li[i]

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

            if diff in route.keys():
                route[diff].append([xi, yi])
            else:
                route[diff] = [[x1,y1], [xi, yi]]

        Route.extend(route.values())
    return Route

cost = 0
route = cal(li)

def check(A,B):
    for a in A:
        if a not in B:
            return False
    
    return True

def max_cal(route, li):
    n = len(li)
    l_max = 0
    max_li = []
    for r in route:
        if check(r,li):
            l = len(r)
            if l > l_max:
                 max_li = r
                 l_max = l
    return l_max, max_li

while True:
    l, cand = max_cal(route, li)
    if l == 0:
        cost += len(li)
        cost += 1
        break
    else:
        route.remove(cand)
        for c in cand:
            li.remove(c)
        n -= l
        cost += 1

print(cost)

Submission status: Wrong Answer

Solution code:
a = "3"
b = "2"
print ("1")

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)]
		#########
	xy = sorted(xy, key=lambda x:(x[1],-x[0]))
	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(10000):
		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:
import sys
N = int(input())
li = []
if N == 1:
    a = list(map(int,input().split()))
    print(1)
    sys.exit()   

for i in range(N):
    a = list(map(int,input().split()))
    li.append(a)

cross = []

##計算量に余裕があるので全探索します
for i in range(N):
    for j in range (i+1, N):
        a = [li[j][0]-li[i][0],li[j][1]-li[i][1]]
        if a[0] < 0 and a[1] < 0:
            b = [abs(li[j][0]-li[i][0]),abs(li[j][1]-li[i][1])]
            cross.append(b)
        elif a[0] < 0 and a[1] >= 0:
            c = li[j][1]-li[i][1]
            b = [abs(li[j][0]-li[i][0]),-c]
            cross.append(b) ####
        else:
            cross.append(a) 
lencross = len(cross)

res = 0
ans = []

for i in range (lencross):
    res = 0
    for j in range (lencross):
        if cross[i] == cross[j]:
            res += 1
    ans.append(res)
reduce = max(ans)

print(N - reduce)

Submission status: Wrong Answer

Solution code:
N=int(input())
P=[tuple(map(int,input().split())) for i in range(N)]
ans=N-1
def check(P,k,l,p,q):
    a,b=P[k]
    c,d=P[l]
    x=False
    y=False
    z=False
    if p==0 or (a-c)%p==0:
        x=True
    if q==0 or (b-d)%q==0:
        y=True
    if p!=0 and q!=0 and (a-c)//p==(b-d)//q:
        z=True
    if p*q==0:
        z=True
    if x and y and z:
        return True
    return False
for i in range(N-1):
    for j in range(i+1,N):
        cost=0
        p=P[i][0]-P[j][0]
        q=P[i][1]-P[j][1]
        used=set()
        for k in range(N):
            if k in used:
                continue
            cost+=1
            used|={k}
            for l in range(N):
                if l in used:
                    continue
                elif check(P,k,l,p,q):
                    used|={l}
    ans=min(ans,cost)
print(ans)

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 is_equal(d1, d2):
    if d1[0] % d2[0] == 0 and d1[1] % d2[1] == 0:
        if d1[0] // d2[0] == d1[1] // d2[1]:
            return True

    if d2[0] % d1[0] == 0 and d2[1] % d1[1] == 0:
        if d2[0] // d1[0] == d2[1] // d1[1]:
            return True

    return False


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()))
    pq_list.sort(key=lambda x:abs(x[0]) + abs(x[1]))

    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:
import collections
 
N=int(input())
x=[0]*N
y=[0]*N
a=[0]
b=[0]
c=1
for i in range(N):
  x[i], y[i]=map(int, input().split())
  
for n in range(1,N):
  a.append(x[n]-x[n-1])
  b.append(y[n]-y[n-1])

X=collections.Counter(a).most_common()[0][1]
Y=collections.Counter(b).most_common()[0][1]

print(max(N-X,N-Y))

Submission status: Wrong Answer

Solution code:
n = int(input())
x,y=[0]*n,[0]*n
xy,yx = [0]*n,[0]*n
for i in range(n):
    x[i],y[i] = map(int,input().split(" "))
    xy[i] = [x[i],y[i]]
    yx[i] = [y[i],x[i]]

xy.sort()
yx.sort()
cost_x,cost_y = [],[]
for j in range(n-1):
    cost_x.append(xy[j+1][0]-xy[j][0])
    cost_y.append(yx[j+1][0]-yx[j][0])

pena_x = cost_x.count(0)-1
pena_y = cost_y.count(0)-1
if pena_x == -1:
    pena_x = 0
if pena_y == -1:
    pena_y = 0
cost_x = list(set(cost_x))
cost_y = list(set(cost_y))
cost = max(len(cost_x)+pena_x,len(cost_y)+pena_y)

print(cost)

Submission status: Wrong Answer

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

D = []
for i in range(1,N):
    D.append((XY[i][0] - XY[i - 1][0], XY[i][1] - XY[i - 1][1]))

DS = list(set(D))

cnt = 0
for d in DS:
    cnt = max(cnt, D.count(d))

res = N - cnt


XY.sort()
D = []
for i in range(1,N):
    D.append((XY[i][0] - XY[i - 1][0], XY[i][1] - XY[i - 1][1]))

DS = list(set(D))

cnt = 0
for d in DS:
    cnt = max(cnt, D.count(d))

res = min(res, N - cnt)

XY.sort(key=lambda x: x[1])
D = []
for i in range(1,N):
    D.append((XY[i][0] - XY[i - 1][0], XY[i][1] - XY[i - 1][1]))

DS = list(set(D))

cnt = 0
for d in DS:
    cnt = max(cnt, D.count(d))

res = min(res, N-cnt)
print(max(res,1))

Submission status: Wrong Answer

Solution code:
def main():
    n=int(input())
    if n ==1:
        print(1)
    else:
        x_y_list=[]
        for i in range(n):
            x,y = map(int,input().split(' '))
            x_y_list.append((x,y))
        sorted_x_y = sorted(x_y_list)
        p_q_list=[]
        for i in range(n-1):
            for j in range(i,n):
                dif_x = sorted_x_y[i][0]-sorted_x_y[j][0]
                dif_y = sorted_x_y[i][1]-sorted_x_y[j][1]
                if dif_x != 0 and dif_y != 0:
                    p_q_list.append((dif_x,dif_y))
        p_q_list = list(set(p_q_list))
        p_q_max = 0
        for p,q in p_q_list:
            for i in range(n):
                tmp = 0
                x_i = sorted_x_y[i][0]
                y_i = sorted_x_y[i][1]
                for j in range(n):
                    if i ==j:
                        continue
                    x_j = sorted_x_y[j][0]
                    y_j = sorted_x_y[j][1]
                    if x_j%p == x_i and y_j%q == y_j:
                        tmp += 1
                if tmp > p_q_max:
                    p_q_max = tmp
        print(n-p_q_max+1)

main()

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+1:]):
        p = a[0]-b[0]
        q = a[1]-b[1]
        prev = xy[0]
        check = [0]*N
        check[0] = 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:
N = [int(i) for i in input().split()][0]

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

salist=[]
sa_uniq=[]
for i in range(0,len(balls),1):
  sax = balls[i][0]-balls[i-1][0]
  say = balls[i][1]-balls[i-1][1]
  salist.append([sax,say])
  if [sax,say] not in sa_uniq:
    sa_uniq.append([sax,say])

count = []
for sa in sa_uniq:
  count.append(salist.count(sa))

if N-max(count)==0:
  print('1')
else:
  print(N-max(count))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
n = int(input())
xy = [list(map(int, input().split())) for _ in range(n)]
xy.sort()
h = defaultdict(int)
for x, y in xy:
    h[(x, y)] = True
mx, my = xy[-1]
d = defaultdict(int)
ans = 10**10
for i in range(n):
    x1, y1 = xy[i]
    for j in range(i+1, n):
        x2, y2 = xy[i+1]
        z1 = x2-x1
        z2 = y2-y1

        t = set()
        k = 0
        a = 0
        while k < n and len(t) < n:
            xk, yk = xy[k]
            if (xk, yk) not in t:
                a += 1
                while xk <= mx and yk <= my:
                    if (xk, yk) in h:
                        t.add((xk, yk))
                    xk += z1
                    yk += z2
            k += 1
        a += n-len(t)
        if a < ans:
            ans = a

print(ans)

Submission status: Wrong Answer

Solution code:
l = input().split()
N = int(l[0])

XY = []

for i in range(N):
    l = input().split()
    XY.append((int(l[0]), int(l[1])))

# print(N, XY)

max_cost = 0
for i in range(N):
    cost_i = 0
    xy_i = XY[i]
    for j in range(N):
        cost_j = 1
        if i == j:
            continue
        xy_j = XY[j]
        diff_x = xy_i[0] - xy_j[0]
        diff_y = xy_i[1] - xy_j[1]
        # print(i, j, diff_x, diff_y)

        b_x = xy_j[0]
        b_y = xy_j[1]
        consumed = [i, j]
        while len(consumed) < N:
            found = False
            for k in range(N):
                if k in consumed:
                    continue
                d_x = b_x - XY[k][0]
                d_y = b_y - XY[k][1]
                if d_x == diff_x and d_y == diff_y:
                    # print('found chain', i, j, k)
                    cost_j += 1
                    b_x = XY[k][0]
                    b_y = XY[k][1]
                    consumed.append(k)
                    found = True
            if not found:
                break

        for l in range(N):
            if l in consumed:
                continue
            b_x = XY[l][0]
            b_y = XY[l][1]
            consumed.append(l)
            found_chain = False
            cost_l = 0
            while len(consumed) < N:
                found = False
                for k in range(N):
                    if k in consumed:
                        continue
                    d_x = b_x - XY[k][0]
                    d_y = b_y - XY[k][1]
                    if d_x == diff_x and d_y == diff_y:
                        # print('found chain', l, k, cost_l)
                        cost_l += 1
                        b_x = XY[k][0]
                        b_y = XY[k][1]
                        consumed.append(k)
                        found = True
                if not found:
                    break
            # print('cost_l', cost_l)
            cost_j += cost_l
        # print('cost_j', cost_j)
        cost_i = max(cost_i, cost_j)
    # print('cost_i', cost_i)
    max_cost = max(max_cost, cost_i)

print(N - max_cost)

Submission status: Wrong Answer

Solution code:
import fractions
N = int(input())
sheet = []
for i in range(N):
  line = input().split()
  sheet+=[(int(line[0]), int(line[1]))]
dic = {}
for i in range(N):
  start = sheet[i]
  for j in range(i+1, N):
    vec = [(sheet[j][0]-start[0]), (sheet[j][1]-start[1])]
    if vec[0]<0:
      vec[0] = (-1)*vec[0]
      vec[1] = (-1)*vec[1]
    size = fractions.gcd(vec[0],vec[1])
    vec[0] = vec[0]//size
    vec[1] = vec[1]//size
    vec = tuple(vec)
    if vec not in dic.keys():
      dic[vec] = set([j])
    else:
      dic[vec].add(j)
m = 0
for s in dic.values():
  if len(s)>m:
    m = len(s)
print(N-m)

Submission status: Wrong Answer

Solution code:
import math

n = int(input())


def get_distance(x1, y1, x2, y2):
    d = math.sqrt((x2 - x1) ** 2 + (y2 - y1) ** 2)
    return d


def get_unique_list(seq):
    seen = []
    return [x for x in seq if x not in seen and not seen.append(x)]


listA = []
while True:
    try:
        listA.append(list(map(int, input().split())))

    except:
        break

setA = []

for i in reversed(listA):
    tmp = []
    for j in reversed(listA):
        if i[0] - j[0] != 0 or i[1] - j[1] != 0:
            tmp.append(get_distance(i[0], i[1], j[0], j[1]))
    setA.append(list(set(tmp)))

minNum = len(setA[0])
for i in setA:
	if len(i) < minNum:
		minNum = len(i)

print(minNum)
# print(len(get_unique_list(setA))-1)

Submission status: Wrong Answer

Solution code:
from collections import Counter
N = int(input())
answer = []
answer2 = []
lis = []
lis2 = []
for i in range(N):
    x, y = map(int, input().split())
    lis.append([x, y])
    lis2.append([y, x])
sort_lis = sorted(lis)
sort_lis2 = sorted(lis2)
#print(sort_lis)
#print(sort_lis2)
if N == 1:
    print(1)
    exit()
d = len(lis)+1
for i in range(len(lis)):
    if lis[i][0] == lis[i][1]:
        d -= 1
#print(d)
for i in range(N-1):
    answer.append([sort_lis[i][0] -sort_lis[i+1][0],sort_lis[i][1]-sort_lis[i+1][1]])
    answer2.append([sort_lis2[i][0] -sort_lis2[i+1][0],sort_lis2[i][1]-sort_lis2[i+1][1]])
ans = list(map(tuple,answer))
#print(ans)
ans2 = list(map(tuple,answer2))
#print(ans2)
a = Counter(ans).most_common()
#print(a)
a2 = Counter(ans2).most_common()
#print(a2)
if len(a)==1 or len(a2)==1:
    print(1)
    exit()
if a[0][1] >= a2[0][1]:
    c = 1
    for i in range(1,len(a)):
        c += a[i][1]

else:
    c = 1
    for i in range(1,len(a2)):
        c += a2[i][1]
print(min(c,d))

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:
from collections import Counter
n = int(input())
xy = [tuple([int(i) for i in input().split()]) for i in range(n)]
li = []
for i in range(n):
    for j in range(n):
        if j == i:  continue
        li.append((xy[i][0]-xy[j][0],xy[i][1]-xy[j][1]))
#print(li)
cnt,p,q = 0,1,1
for k,v in Counter(li).items():
    if cnt < v and k[0] != 0 and k[1] != 0:
        cnt = v
        p,q = k
#print(f'p:{p},q:{q}')
ans = n
for x,y in xy:
    tmp = 0
    #print()
    while (x-p,y-q) in xy:
        #print(x,y)
        tmp += 1
        x -= p
        y -= q
    ans = min(ans,n-tmp)
print(ans)