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: Time Limit Exceeded

Solution code:
# Picking Up
# グラフ,有向グラフ,ベクトル, ２次元、コスト,

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

for k, ke in enumerate(S):
    for i, ie in enumerate(S):
        if k == i:
            continue
        t_vec_x1 = ie[0] - ke[0]
        t_vec_y1 = ie[1] - ke[1]
        edge = 0
        for l,le in enumerate(S):
            for m, me in enumerate(S):
                if l == m:
                    continue
                vec_x = me[0] - le[0]
                vec_y = me[1] - le[1]
                if t_vec_x1 == vec_x and t_vec_y1 == vec_y:
                    edge += 1
        cost = min(cost, N - edge)
        # t_vec_x2 = S[k][0] - S[i][0]
        # t_vec_y2 = S[k][1] - S[i][1]
        # edge = 0
        # for l in range(sl):
        #     for m in range(sl):
        #         if l == m:
        #             continue
        #         vec_x = S[l][0] - S[m][0]
        #         vec_y = S[l][1] - S[m][1]
        #         if t_vec_x2 == vec_x and t_vec_y2 == vec_y:
        #             edge += 1
        # print(edge)
        cost = min(cost, N - edge)

print(cost)

Submission status: Time Limit Exceeded

Solution code:
# Picking Up
# グラフ,有向グラフ,ベクトル, ２次元、コスト,

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

for k in range(len(S)):
    for i in range(len(S)):
        if k == i:
            continue
        t_vec_x1 = S[i][0] - S[k][0]
        t_vec_y1 = S[i][1] - S[k][1]
        edge = 0
        for l in range(len(S)):
            for m in range(len(S)):
                if l == m:
                    continue
                vec_x = S[m][0] - S[l][0]
                vec_y = S[m][1] - S[l][1]
                if t_vec_x1 == vec_x and t_vec_y1 == vec_y:
                    edge += 1
        cost = min(cost, N - edge)
        # t_vec_x2 = S[k][0] - S[i][0]
        # t_vec_y2 = S[k][1] - S[i][1]
        # edge = 0
        # for l in range(len(S)):
        #     for m in range(len(S)):
        #         if l == m:
        #             continue
        #         vec_x = S[l][0] - S[m][0]
        #         vec_y = S[l][1] - S[m][1]
        #         if t_vec_x2 == vec_x and t_vec_y2 == vec_y:
        #             edge += 1
        # print(edge)
        cost = min(cost, N - edge)

print(cost)

Submission status: Time Limit Exceeded

Solution code:
# Picking Up
# グラフ,有向グラフ,ベクトル, ２次元、コスト,

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

for k in range(len(S)):
    for i in range(len(S)):
        if k == i:
            continue
        t_vec_x1 = S[i][0] - S[k][0]
        t_vec_y1 = S[i][1] - S[k][1]
        edge = 0
        for l in range(len(S)):
            for m in range(len(S)):
                if l == m:
                    continue
                vec_x = S[m][0] - S[l][0]
                vec_y = S[m][1] - S[l][1]
                if t_vec_x1 == vec_x and t_vec_y1 == vec_y:
                    edge += 1
        cost = min(cost, N - edge)
        t_vec_x2 = S[k][0] - S[i][0]
        t_vec_y2 = S[k][1] - S[i][1]
        edge = 0
        for l in range(len(S)):
            for m in range(len(S)):
                if l == m:
                    continue
                vec_x = S[l][0] - S[m][0]
                vec_y = S[l][1] - S[m][1]
                if t_vec_x2 == vec_x and t_vec_y2 == vec_y:
                    edge += 1
        # print(edge)
        cost = min(cost, N - edge)

print(cost)

Submission status: Time Limit Exceeded

Solution code:
import itertools
import collections
n=int(input())
s=[list(map(int, input().split())) for i in range(n)]
ans=[]
x=list(itertools.permutations(s))

if n==1:
    print(n)
else:
    v=[]
    r=[]
    for i in range(len(x)):
        e=[]
        v=[]
        for j in range(n-1):
            a=x[i][j][0]
            b=x[i][j+1][0]
            c=x[i][j][1]
            d=x[i][j+1][1]
            v.append(b-a)
            v.append(d-c) 
        q=[v[i:i+2] for i in range(0,len(v),2)]
        for i in range(len(q)):
            e.append(q.count(q[i]))
        r.append(max(e))
    print(n-max(r))

Submission status: Time Limit Exceeded

Solution code:
# 未完成
import numpy as np
import sys
N = int(input())
x = np.zeros(N)
y = np.zeros(N)
kouholist = []
ans = N
if N == 1:
    print(1)
    sys.exit()

for i in range(N):
    x[i], y[i] = map(int, input().split())
for m in range(N):
    for p in range(N):
        if m == p:
            continue
        diff_x = x[m] - x[p]
        diff_y = y[m] - y[p]
        ans_kari = N
        for r in range(N):
            for q in range(N):
                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: Time Limit Exceeded

Solution code:
# 未完成
import numpy as np
import sys
N = int(input())
x = np.zeros(N)
y = np.zeros(N)
kouholist = []
ans = []
if N == 1:
    print(1)
    sys.exit()

for i in range(N):
    x[i], y[i] = map(int, input().split())
for m in range(N):
    for p in range(N):
        if m == p:
            continue
        diff_x = x[m] - x[p]
        diff_y = y[m] - y[p]

        ans_kari = 0
        for r in range(N):
            for q in range(N):
                if x[q] - x[r] == diff_x and y[q] - y[r] == diff_y:
                    ans_kari += 1
        ans.append(ans_kari)

print("{}".format(N-max(ans)))

Submission status: Time Limit Exceeded

Solution code:
# 未完成
import numpy as np
import sys
N = int(input())
x = np.zeros(N)
y = np.zeros(N)
kouholist = []
ans = []
if N == 1:
    print(1)
    sys.exit()

for i in range(N):
    x[i], y[i] = map(int, input().split())
for m in range(N):
    for p in range(N):
        if m == p:
            continue
        diff_x = x[m] - x[p]
        diff_y = y[m] - y[p]
        if (diff_x, diff_y) not in kouholist:
            kouholist.append((diff_x, diff_y))

for list_i in kouholist:
    ans_kari = 0
    for r in range(N):
        for q in range(N):
            if x[q] - x[r] == list_i[0] and y[q] - y[r] == list_i[1]:
                ans_kari += 1
    ans.append(ans_kari)

print("{}".format(N-max(ans)))

Submission status: Time Limit Exceeded

Solution code:
import itertools
import collections
n=int(input())
s=[list(map(int, input().split())) for i in range(n)]
ans=[]
x=list(itertools.permutations(s))

if n==1:
    print(n)
else:
    v=[]
    r=[]
    for i in range(len(x)):
        e=[]
        v=[]
        for j in range(n-1):
            a=x[i][j][0]
            b=x[i][j+1][0]
            c=x[i][j][1]
            d=x[i][j+1][1]
            v.append(b-a)
            v.append(d-c) 
        q=[v[i:i+2] for i in range(0,len(v),2)]
        for i in range(len(q)):
            e.append(q.count(q[i]))
            r.append(max(e))
    print(n-max(r))

Submission status: Time Limit Exceeded

Solution code:
# 未完成
import numpy as np
N = int(input())
x = np.zeros(N)
y = np.zeros(N)
kouholist = []
ans = []
if N == 1:
    print(1)
else:
    for i in range(N):
        x[i], y[i] = map(int, input().split())
    for m in range(N):
        for p in range(N):
            if m == p:
                continue
            diff_x = x[m] - x[p]
            diff_y = y[m] - y[p]
            if (diff_x, diff_y) not in kouholist:
                kouholist.append((diff_x, diff_y))

    for list_i in kouholist:
        ans_kari = 0
        for r in range(N):
            for q in range(N):
                if x[q] - x[r] == list_i[0] and y[q] - y[r] == list_i[1]:
                    ans_kari += 1
        ans.append(ans_kari)

    print("{}".format(N-max(ans)))

Submission status: Time Limit Exceeded

Solution code:
# 未完成
import numpy as np
N = int(input())
x = np.zeros(N)
y = np.zeros(N)
kouholist = []
ans = []
if N == 1:
    print(1)
else:
    for i in range(N):
        x[i], y[i] = map(int, input().split())
    for m in range(N):
        for p in range(N):
            if m == p:
                continue
            diff_x = x[m] - x[p]
            diff_y = y[m] - y[p]
            if (diff_x, diff_y) not in kouholist:
                kouholist.append((diff_x, diff_y))

    for list_i in kouholist:
        ans_kari = 0
        for r in range(N):
            for q in range(N):
                if r == q:
                    continue
                if x[q] - x[r] == list_i[0] and y[q] - y[r] == list_i[1]:
                    ans_kari += 1
        ans.append(ans_kari)

    print("{}".format(N-max(ans)))

Submission status: Time Limit Exceeded

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())
ans = 0
for m in range(N):
    for p in range(N):
        if m == p:
            continue
        diff_x = x[m] - x[p]
        diff_y = y[m] - y[p]
        ans_kari = 0
        for r in range(N):
            for q in range(N):
                if r == q:
                    continue
                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(int(N-ans)))

Submission status: Time Limit Exceeded

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


ans = 0
for m in range(N):
    for p in range(N):
        if m == p:
            continue
        diff_x = x[m] - x[p]
        diff_y = y[m] - y[p]
        ans_kari = 0
        for r in range(N):
            for q in range(N):
                if r == q:
                    continue
                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(int(N-ans)))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
li_ = []
 
for i in range(N):
  a, b = map(int, input().split())
  li_.append([a, b])
li_.sort()    
 
li_1 = [x[0] for x in li_]
li_2 = [x[1] for x in li_]
a_ = max(li_1) - min(li_1)
b_ = max(li_2) - min(li_2)
 
def picking_up(p, q):
  li = [x for x in li_]
  cost = 0
  for i in range(N):
    if len(li) == 0:
      break
    cost += 1
    if len(li) == 0:
      break
    a, b = li[0][0], li[0][1]
    li.remove([a,b])
    while [a+p, b+q] in li:
        li.remove([a+p, b+q])
        a, b = a+p, b + q
  return cost
 
 
new_cost = 100
for p in range(a_+1):
    for q in range(b_+1):
        cost = picking_up(p, q)
        if cost < new_cost:
            new_cost = cost
           
print(new_cost)

Submission status: Time Limit Exceeded

Solution code:

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

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

  diff = []
  for i in range(N):
    for j in range(i, N):
      p = XY[i][0]-XY[j][0]
      q = XY[i][1]-XY[j][1]
      if (p, q) == (0, 0) or (p, q) in diff:
        continue
      diff.append((p, q))    

  from itertools import permutations

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

if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
import math
N = int(input())
x,y = map(int, input().split())
dis_list = [[x,y]]
for i in range(N-1):
	x , y = map(int,input().split())
	for j in range(len(dis_list)):
		x = abs(x- dis_list[j][0])
		y = abs(y-dis_list[j][1])
		dis_list.append([x,y])
dis_list = dis_list[1:1+N*(N-1)//2]
counter = Counter(map(tuple, dis_list))
if N == 1:
    print(1)
else:
    print(N-counter.most_common()[0][1])

Submission status: Time Limit Exceeded

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

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

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

from itertools import combinations, permutations

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

Submission status: Time Limit Exceeded

Solution code:
n = int(input());
point = [[0]*2 for i in range(n) ];
for i in range(n) :
	s = input().split(" ");
	point[i][0] = int(s[0]);
	point[i][1] = int(s[1]);
vec = [[0]*3 for i in range(1)];
leng = 1;
for i in range(n) :
	for j in range(n) :
		if i != j  :
			x = point[i][0] - point[j][0];
			y = point[i][1] - point[j][1];
			for k in range(leng) :
				if vec[k][0] == x and vec[k][1] == y :
					vec[k][2] = vec[k][2] + 1;
				else :
					vec.append([x,y,1]);
					leng = leng + 1;
vec.sort(key=lambda x:x[2]);
print(n-vec[leng-1][2]);

Submission status: Time Limit Exceeded

Solution code:
n = int(input());
point = [[0]*2 for i in range(n) ];
for i in range(n) :
	s = input().split(" ");
	point[i][0] = int(s[0]);
	point[i][1] = int(s[1]);
point.sort(key=lambda x:x[0]);
vec = [[0]*3 for i in range(1)];
leng = 1;
for i in range(n) :
	for j in range(n) :
		if i != j  :
			x = point[i][0] - point[j][0];
			y = point[i][1] - point[j][1];
			for k in range(leng) :
				if vec[k][0] == x and vec[k][1] == y :
					vec[k][2] = vec[k][2] + 1;
				else :
					vec.append([x,y,1]);
					leng = leng + 1;
vec.sort(key=lambda x:x[2]);
print(n-vec[leng-1][2]);

Submission status: Time Limit Exceeded

Solution code:
# 残っているボールを1つ選んで回収、(a, b)
# (a-p, b-q) コスト0

import itertools

score = 1
p = 0
q = 0

n = int(input())
e = [[int(i) for i in input().split()] for i in range(n)]

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

arr = list(itertools.permutations(e))
for i, parent in enumerate(arr):
    if i == 0:
        for j, child in enumerate(parent):
            if j == 0:
                p = parent[j + 1][0] - child[0]
                q = parent[j + 1][1] - child[1]
                score = 1
                continue
            if not child[0] == parent[j-1][0] + p and not child[1] == parent[j - 1][1] + q:
                score += 1
    else:
        tmp_p = p
        tmp_q = q
        sc = score
        for j, child in enumerate(parent):
            if j == 0:
                p = parent[j + 1][0] - child[0]
                q = parent[j + 1][1] - child[1]
                score = 1
                continue
            if not child[0] == parent[j-1][0] + p and not child[1] == parent[j - 1][1] + q:
                score += 1
            if score > sc:
                p = tmp_p
                q = tmp_q
                score = sc
                break

print(score)

Submission status: Time Limit Exceeded

Solution code:
# 残っているボールを1つ選んで回収、(a, b)
# (a-p, b-q) コスト0

import itertools

score = 1
p = 0
q = 0

n = int(input())
e = [[int(i) for i in input().split()] for i in range(n)]

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

arr = list(itertools.permutations(e))
for i, parent in enumerate(arr):
    if i == 0:
        for j, child in enumerate(parent):
            if j == 0:
                p = parent[j + 1][0] - child[0]
                q = parent[j + 1][1] - child[1]
                score = 1
                continue
            if not child[0] == parent[j-1][0] + p and not child[1] == parent[j - 1][1] + q:
                score += 1
    else:
        tmp_p = p
        tmp_q = q
        sc = score
        for j, child in enumerate(parent):
            if j == 0:
                p = parent[j + 1][0] - child[0]
                q = parent[j + 1][1] - child[1]
                score = 1
                continue
            if not child[0] == parent[j-1][0] + p and not child[1] == parent[j - 1][1] + q:
                score += 1
            if score > sc:
                p = tmp_p
                q = tmp_q
                score = sc
                continue

print(score)

Submission status: Time Limit Exceeded

Solution code:
class UF():
  def __init__(self, N):
    self._parent=[n for n in range(0, N)]
    self._size=[1] * N

  def find_root(self, x):
    if self._parent[x]==x:return x
    self._parent[x]=self.find_root(self._parent[x])
    return self._parent[x]

  def unite(self, x, y):
    gx=self.find_root(x)
    gy=self.find_root(y)
    if gx==gy:return

    if self._size[gx]<self._size[gy]:
      self._parent[gx]=gy
      self._size[gy]+=self._size[gx]
    else:
      self._parent[gy]=gx
      self._size[gx]+=self._size[gy]

  def size(self, x):
    return self._size[self.find_root(x)]

  def samegroup(self, x, y):
    return self.find_root(x)==self.find_root(y)

  def groupnum(self):
    N=len(self._parent)
    ans=0
    for i in range(N):
      if self.find_root(i)==i:
        ans+=1
    return ans

  def reset(self):
    self._parent=[n for n in range(0, n)]

n=int(input())
UF=UF(n)
l=[list(map(int,input().split())) for i in range(n)]
if n==1:
  print(1)
else:
  ans=[]
  for i in range(n):
    x1=l[i][0]
    y1=l[i][1]
    for j in range(n):
      if i!=j:
        x2=l[j][0]
        y2=l[j][1]
        p=x1-x2
        q=y1-y2
        for k1 in range(n):
          for k2 in range(n):
            if k1!=k2:
              if (l[k1][0]-p==l[k2][0] and l[k1][1]-q==l[k2][1]) or (l[k1][0]+p==l[k2][0] and l[k1][1]+q==l[k2][1]):
                UF.unite(k1,k2)
        ans.append(UF.groupnum())
        UF.reset()
  print(min(ans))

Submission status: Time Limit Exceeded

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

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

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

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

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

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

def main():

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

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

	gess = {}
	xm = 0
	ym = 0

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

	for _ in range(50000):
		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: Time Limit Exceeded

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

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

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

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

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

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

def main():

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

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

	gess = {}
	xm = 0
	ym = 0

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

	for _ in range(100000):
		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: Time Limit Exceeded

Solution code:
def gcd(a, b):
    if b < 0:
        return gcd(a, -b)
    if b == 0:
        return a
    else:
        return gcd(b, a%b)

def solve():
    N = int(raw_input())
    xy = [None] * N
    for i in range(N):
        xi, yi = [int(_) for _ in raw_input().split()]
        xy[i] = (xi, yi)
    xy.sort(key = lambda x: x[0])
    pq_set = []
    def AddToPQSet(ele):
        pq, i, j = ele
        # if len(pq_set) == 0 or pq_set[0][0] > pq:
        #     pq_set.insert(0, (pq, set()))
        #     pq_set[0][1].add(i)
        #     pq_set[0][1].add(j)
        added_flag = False
        for ind in range(0, len(pq_set)):
            if pq_set[ind][0] == pq:
                subset_added = False
                for subset in pq_set[ind][1]:
                    if i in subset:
                        subset.add(j)
                        subset_added = True
                    elif j in subset:
                        subset.add(i)
                        subset_added = True
                if not subset_added:
                    tmp_set = set()
                    tmp_set.add(i)
                    tmp_set.add(j)
                    pq_set[ind][1].append(tmp_set)
                added_flag = True
            elif pq_set[ind][0] > pq:
                tmp_set = set()
                tmp_set.add(i)
                tmp_set.add(j)
                pq_set.insert(ind, (pq, [tmp_set]))
                added_flag = True
        if not added_flag:
            tmp_set = set()
            tmp_set.add(i)
            tmp_set.add(j)
            pq_set.append((pq, [tmp_set]))
        # print pq
        # print "i = " + str(i) + ", j = " + str(j)
        # print pq_set

    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]
            _gcd = gcd(p,q)
            # print "i = " + str(i) + ", j = " + str(j)
            # print p, q, _gcd
            p = p / _gcd
            q = q / _gcd
            AddToPQSet(((p,q),i,j))

    maxcntpq = 0
    # print pq_set
    for i in range(len(pq_set)):
        if len(pq_set[i][1]) > maxcntpq:
            num_subset = len(pq_set[i][1])
            cnt = 0
            for subset in pq_set[i][1]:
                cnt += len(subset)
            cnt -= num_subset
            if cnt > maxcntpq:
                maxcntpq = cnt
    print N - maxcntpq

if __name__ == '__main__':
    solve()