Problem:


Score : 400 points

Problem Statement

We have N points in a two-dimensional plane.

The coordinates of the i-th point (1 \leq i \leq N) are (x_i,y_i).

Let us consider a rectangle whose sides are parallel to the coordinate axes that contains K or more of the N points in its interior.

Here, points on the sides of the rectangle are considered to be in the interior.

Find the minimum possible area of such a rectangle.  

Constraints

2 \leq K \leq N \leq 50 

-10^9 \leq x_i,y_i \leq 10^9 (1 \leq i \leq N) 

x_i≠x_j (1 \leq i<j \leq N) 

y_i≠y_j (1 \leq i<j \leq N) 

All input values are integers. (Added at 21:50 JST)  

Input

Input is given from Standard Input in the following format:  

N K  
x_1 y_1
:  
x_{N} y_{N}

Output

Print the minimum possible area of a rectangle that satisfies the condition.  

Sample Input 1

4 4
1 4
3 3
6 2
8 1

Sample Output 1

21

One rectangle that satisfies the condition with the minimum possible area has the following vertices: (1,1), (8,1), (1,4) and (8,4).

Its area is (8-1) × (4-1) = 21.  

Sample Input 2

4 2
0 0
1 1
2 2
3 3

Sample Output 2

1

Sample Input 3

4 3
-1000000000 -1000000000
1000000000 1000000000
-999999999 999999999
999999999 -999999999

Sample Output 3

3999999996000000001

Watch out for integer overflows.  



Sample input:
4 4
1 4
3 3
6 2
8 1


Sample output:
21

Submission status: Time Limit Exceeded

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

import sys

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 list4d(a, b, c, d, e): return [[[[e] * d for j in range(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(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
# 20億^2で10^18を超えるので19乗で
INF = 10 ** 19
MOD = 10 ** 9 + 7

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

ans = INF
# 4点組み合わせ全部試す
for i in range(N):
    x1, y1 = XY[i]
    for j in range(N):
        x2, y2 = XY[j]
        for k in range(N):
            x3, y3 = XY[k]
            for l in range(N):
                x4, y4 = XY[l]
                xl, xr = min(x1, x2, x3, x4), max(x1, x2, x3, x4)
                yl, yr = min(y1, y2, y3, y4), max(y1, y2, y3, y4)
                # 4点の内側にいくつ点があるか数える
                k = 0
                for x5, y5 in XY:
                    if xl <= x5 <= xr and yl <= y5 <= yr:
                        k += 1
                if k >= K:
                    ans = min(ans, (xr-xl) * (yr-yl))
print(ans)

Submission status: Time Limit Exceeded

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

import sys

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 list4d(a, b, c, d, e): return [[[[e] * d for j in range(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(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
# 20億^2で10^18を超えるので19乗で
INF = 10 ** 19
MOD = 10 ** 9 + 7

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

ans = INF
# 4点組み合わせ全部試す
for i in range(N):
    x1, y1 = XY[i]
    for j in range(N):
        x2, y2 = XY[j]
        for i in range(N):
            x3, y3 = XY[i]
            for j in range(N):
                x4, y4 = XY[j]
                xl, xr = min(x1, x2, x3, x4), max(x1, x2, x3, x4)
                yl, yr = min(y1, y2, y3, y4), max(y1, y2, y3, y4)
                # 4点の内側にいくつ点があるか数える
                k = 0
                for x5, y5 in XY:
                    if xl <= x5 <= xr and yl <= y5 <= yr:
                        k += 1
                if k >= K:
                    ans = min(ans, (xr-xl) * (yr-yl))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import*
n,k,*L=map(int,open(0).read().split())
p=[(x,y) for x,y in zip(*[iter(L)]*2)]
X=sorted(x for x,y in p)+[0]
Y=sorted(y for x,y in p)
ans=float("inf")
for i,mx in enumerate(X[:-k]):
	for Mx in X[i+k-1:-1]:
		for my,My in combinations(Y,2):
			if sum(mx<=x<=Mx and my<=y<=My for x,y in p)>=k:
				ans=min(ans,(Mx-mx)*(My-my))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import*
n,k,*L=map(int,open(0).read().split())
p=[(x,y) for x,y in zip(*[iter(L)]*2)]
X=sorted(x for x,y in p)
Y=sorted(y for x,y in p)
ans=float("inf")
for mx,Mx in combinations(X,2):
	for my,My in combinations(Y,2):
		if sum(mx<=x<=Mx and my<=y<=My for x,y in p)>=k:
			ans=min(ans,(Mx-mx)*(My-my))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import*
n,k,*L=map(int,open(0).read().split())
p=[(x,y) for x,y in zip(*[iter(L)]*2)]
X=sorted(x for x,y in p)
Y=sorted(y for x,y in p)
ans=float("inf")
for mx,Mx in combinations(X,2):
	for my,My in combinations(Y,2):
		if sum(mx<=x<=Mx and my<=y<=My for x,y in p)>=k:
			ans=min(ans,(Mx-mx)*(My-my))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
N,K=map(int,input().split())
XY=[list(map(int,input().split())) for i in range(N)]
l=[i for i in range(N)]
ans=float("inf")
for v in itertools.combinations(l,2):
  xmax=max(XY[v[0]][0],XY[v[1]][0])
  xmin=min(XY[v[0]][0],XY[v[1]][0])
  ymax=max(XY[v[0]][1],XY[v[1]][1])
  ymin=min(XY[v[0]][1],XY[v[1]][1])
  k=0
  for xy in XY:
    x,y=xy[0],xy[1]
    if xmin<=x and x<=xmax:
      if ymin<=y and y<=ymax:
        k+=1    
  if k>=K:
    ans=min(ans,(xmax-xmin)*(ymax-ymin))
    
for v in itertools.combinations(l,3):
  xmax=max(XY[v[0]][0],XY[v[1]][0],XY[v[2]][0])
  xmin=min(XY[v[0]][0],XY[v[1]][0],XY[v[2]][0])
  ymax=max(XY[v[0]][1],XY[v[1]][1],XY[v[2]][1])
  ymin=min(XY[v[0]][1],XY[v[1]][1],XY[v[2]][1])
  k=0
  for xy in XY:
    x,y=xy[0],xy[1]
    if xmin<=x and x<=xmax:
      if ymin<=y and y<=ymax:
        k+=1    
  if k>=K:
    ans=min(ans,(xmax-xmin)*(ymax-ymin))
    
for v in itertools.combinations(l,4):
  xmax=max(XY[v[0]][0],XY[v[1]][0],XY[v[2]][0],XY[v[3]][0])
  xmin=min(XY[v[0]][0],XY[v[1]][0],XY[v[2]][0],XY[v[3]][0])
  ymax=max(XY[v[0]][1],XY[v[1]][1],XY[v[2]][1],XY[v[3]][1])
  ymin=min(XY[v[0]][1],XY[v[1]][1],XY[v[2]][1],XY[v[3]][1])
  k=0
  for xy in XY:
    x,y=xy[0],xy[1]
    if xmin<=x and x<=xmax:
      if ymin<=y and y<=ymax:
        k+=1    
  if k>=K:
    ans=min(ans,(xmax-xmin)*(ymax-ymin))
print(ans)

Submission status: Time Limit Exceeded

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

ans = 10 ** 20

for x1 in range(N):
    for x2 in range(x1 + 1, N):
        for y1 in range(N):
            for y2 in range(y1 + 1, N):
                u = max(XY[x1][0], XY[x2][0])
                d = min(XY[x1][0], XY[x2][0])
                r = max(XY[y1][1], XY[y2][1])
                l = min(XY[y1][1], XY[y2][1])
                c = sum([d <= x <= u and l <= y <= r for x, y in XY])
                ans = min(ans, (u - d) * (r - l)) if c >= K else ans

print(ans)

Submission status: Time Limit Exceeded

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

ans = 10 ** 20

for x1 in range(N):
    for x2 in range(x1, N):
        for y1 in range(N):
            for y2 in range(y1, N):
                u = max(XY[x1][0], XY[x2][0])
                d = min(XY[x1][0], XY[x2][0])
                r = max(XY[y1][1], XY[y2][1])
                l = min(XY[y1][1], XY[y2][1])
                c = sum([d <= x <= u and l <= y <= r for x, y in XY])
                ans = min(ans, (u - d) * (r - l)) if c >= K else ans

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from itertools import combinations
read = sys.stdin.read

N, K, *xy = map(int, read().split())
xy = list(zip(*[iter(xy)] * 2))
X = [x for x, y in xy]
Y = [y for x, y in xy]
answer = 10 ** 20

for i in combinations(X, 2):
    for j in combinations(Y, 2):
        top = max(j)
        bottom = min(j)
        left = min(i)
        right = max(i)
        cnt = 0
        for x, y in xy:
            if left <= x <= right and bottom <= y <= top:
                cnt += 1
        if cnt < K:
            continue

        S = (top - bottom) * (right - left)
        if S < answer:
            answer = S

print(answer)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
import itertools

def solve(N: int, K: int, x: "List[int]", y: "List[int]"):
    answer = 10**19

    x_set = sorted(list(set(x)))
    y_set = sorted(list(set(y)))
    x_combination = list(itertools.combinations(x_set,2))
    y_combination = list(itertools.combinations(y_set,2))

    
    for x_l, x_u in x_combination:
        for y_l, y_u in y_combination:
            count = 0
            for i in range(N):
                if y_l <= y[i] <= y_u and x_l <= x[i] <= x_u:
                    count +=1
            if count >= K:
                answer = min(answer,(y_u-y_l)*(x_u-x_l))

    print(answer)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    x = [int()] * (N)  # type: "List[int]"
    y = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        x[i] = int(next(tokens))
        y[i] = int(next(tokens))
    solve(N, K, x, y)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n,bod = map(int,input().split())
points = []
x = []
y = []
for i in range(n):
    a,b = map(int,input().split())
    x.append(a)
    y.append(b)
    points.append([a,b])

x.sort()
y.sort()


ans = 1e20

for i in range(n):
    for j in range(1,n-i):
        for k in range(n):
            for l in range(1,n-k):
                lef = x[i]
                rig = x[-j]
                bot = y[k]
                top = y[-l]

                cnt = 0
                for m in range(n):
                    if lef <= points[m][0] <= rig and bot <= points[m][1] <= top:
                        cnt += 1
                if cnt >= bod:
                    area = (rig-lef)*(top-bot)
                    if area < ans:
                        ans = area


print(ans)

Submission status: Time Limit Exceeded

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

X = sorted(X)
Y = sorted(Y)
mi = 1<<200
for i in range(N):
    for j in range(i+1, N):
        for k in range(N):
            for l in range(k+1, N):
                s = 0
                for x, y in XY:
                    if X[i] <= x <= X[j] and Y[k] <= y <= Y[l]:
                        s += 1
                if s >= K:
                    mi = min(mi, (X[j] - X[i]) * (Y[l] - Y[k]))

print(mi)

Submission status: Time Limit Exceeded

Solution code:
def main():
    N, K = map(int, input().split())
    dots = []
    for _ in range(N):
        x, y = map(int, input().split())
        dots.append((x,y))

    ans = float('inf')

    for i in range(N):
        for j in range(N):
            for k in range(N):
                for l in range(N):
                    if i == j == k == l:
                        continue
                    right = max(dots[i][0],dots[j][0],dots[k][0],dots[l][0])
                    left = min(dots[i][0],dots[j][0],dots[k][0],dots[l][0])
                    bottom = min(dots[i][1],dots[j][1],dots[k][1],dots[l][1])
                    top = max(dots[i][1],dots[j][1],dots[k][1],dots[l][1])

                    cnt = 0
                    for x, y in dots:
                        if left <= x <= right and bottom <= y <= top:
                            cnt += 1

                    if cnt >= K:
                        ans = min(ans, (top - bottom) * (right - left))
    print(ans)



if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import itertools
n,k=map(int,input().split())
l=[]
for i in range(n):
    l.append(list(map(int,input().split())))
c=itertools.combinations(range(n),2)
d=itertools.combinations(range(n),2)
ans=10**25
for i0 in range(n):
    for i1 in range(n):
        for j0 in range(n):
            for j1 in range(n):
                i=[i0,i1]
                j=[j0,j1]
                #print(i,j)
                lx=min(l[i[0]][0],l[i[1]][0])
                rx=max(l[i[0]][0],l[i[1]][0])
                dy=min(l[j[0]][1],l[j[1]][1])
                uy=max(l[j[0]][1],l[j[1]][1])
                tk=0
                for p in l:
                    if lx<=p[0]<=rx and dy<=p[1]<=uy:
                        tk+=1
                if tk>=k:
                    ans=min(ans,(uy-dy)*(rx-lx))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
list_x = []
list_y = []
for _ in range(n):
  x, y = map(int, input().split())
  list_x.append(x)
  list_y.append(y)
sort_list_x = sorted(list_x)
sort_list_y = sorted(list_y)

result = (sort_list_x[-1] - sort_list_x[0]) * (sort_list_y[-1] - sort_list_y[0])
for i, xl in enumerate(sort_list_x[:-1]):
  for xr in sort_list_x[i+1:]:
    for j, yd in enumerate(sort_list_y[:-1]):
      for yu in sort_list_y[j+1:]:
        inner = 0
        for i in range(n):
          if xl <= list_x[i] <= xr and yd <= list_y[i] <= yu:
            inner += 1
        if inner >= k:
          result = min(result, (xr-xl)*(yu-yd))
print(result)

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
xy=[list(map(int,input().split())) for _ in range(n)]
x=[xy[i][0] for i in range(n)]
y=[xy[i][1] for i in range(n)]
res = 10**20
for i in range(n):
    xl = xy[i][0]
    for j in range(n):
        xr = xy[j][0]
        if xr<xl:continue
        for p in range(n):
            yl = xy[p][1]
            for q in range(n):
                yr = xy[q][1]
                if yr<yl:continue
                tres = 0
                for sxy in xy:
                    if sxy[0] >= xl and sxy[0] <= xr and sxy[1] >= yl and sxy[1] <= yr:
                        tres += 1
                if tres >= k:
                    res = min(res,(xr-xl)*(yr-yl))
print(res)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations

def count_inclued_points(cmbxi, cmbyi):
  return len(set([xi for x, xi in X[cmbxi[0]:cmbxi[1]+1]]).intersection([yi for y, yi in Y[cmbyi[0]:cmbyi[1]+1]]))

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

ans = float('inf')
for cmbxi in combinations([i for i in range(N)],2):
  for cmbyi in combinations([i for i in range(N)],2):
    rngx = [min(X[cmbxi[0]][0], X[cmbxi[1]][0]), max(X[cmbxi[1]][0], X[cmbxi[1]][0])]
    rngy = [min(Y[cmbyi[0]][0], Y[cmbyi[1]][0]), max(Y[cmbyi[1]][0], Y[cmbyi[1]][0])]
    #print(cmbxi, cmbyi, count_inclued_points(cmbxi, cmbyi))
    if count_inclued_points(cmbxi, cmbyi) >= K:
      ans = min(ans, (rngx[1]-rngx[0])*(rngy[1]-rngy[0]))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations

def count_inclued_points(rngx, rngy):
  cnt_p = 0
  
  for x,y in XY:
    if rngx[0] <= x and x<= rngx[1] and rngy[0] <= y and y<= rngy[1]:
      cnt_p += 1
      
  return cnt_p

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

ans = float('inf')
for cmbx in combinations(X,2):
  for cmby in combinations(Y,2):
    rngx = [min(cmbx[0], cmbx[1]), max(cmbx[1], cmbx[1])]
    rngy = [min(cmby[0], cmby[1]), max(cmby[1], cmby[1])]
    if count_inclued_points(rngx, rngy) >= K:
      ans = min(ans, (rngx[1]-rngx[0])*(rngy[1]-rngy[0]))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import copy
import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
mod = 10**9 + 7
inf = float('inf')
ans = int(0)

N, K = LI()
x = [0]*N; y = [0]*N
for i in range(N):
    x[i], y[i] = LI()

X = copy.deepcopy(x); Y = copy.deepcopy(y)
X.sort(); Y.sort()

Xcandi = [0]*2; Ycandi = [0]*2
ylower = 0; yupper = N-1; ycur = (ylower+yupper)//2
ansC = []
for i in range(N-1):
    Xcandi[0] = X[i]
    for j in range(i+1,N):
        Xcandi[1] = X[j]
        for k in range(N-1):
            ylower = k+1; yupper = N - 1; ycur = (ylower + yupper) // 2
            Ycandi[0] = Y[k]
            while(True):
                cur = int(0)
                Ycandi[1] = Y[ycur]
                for l in range(N):
                    if Xcandi[0] <= x[l] <= Xcandi[1] and Ycandi[0] <= y[l] <= Ycandi[1]:
                        cur += 1
                if yupper - ylower >= 2:
                    if cur < K:
                        ylower = ycur
                        ycur = (ycur + yupper) // 2
                    else:
                        yupper = ycur
                        ycur = (ycur + ylower) // 2
                else:
                    if cur < K:
                        cur = int(0)
                        Ycandi[1] = Y[yupper]
                        for l in range(N):
                            if Xcandi[0] <= x[l] <= Xcandi[1] and Ycandi[0] <= y[l] <= Ycandi[1]:
                                cur += 1
                        if cur < K:
                            break
                    else:
                        Ycandi[1] = Y[ycur]
                        """
                        cur = int(0)
                        Ycandi[1] = Y[ylower]
                        for l in range(N):
                            if Xcandi[0] <= x[l] <= Xcandi[1] and Ycandi[0] <= y[l] <= Ycandi[1]:
                                cur += 1
                        if cur < K:
                            Ycandi[1] = Y[ylower+1]
                            """
                    cur = (Xcandi[1] - Xcandi[0])*(Ycandi[1] - Ycandi[0])
                    ansC.append(cur)
#                    print(Xcandi,Ycandi)
                    break

#print(ansC)
print(min(ansC))

Submission status: Time Limit Exceeded

Solution code:
import copy
import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
mod = 10**9 + 7
inf = float('inf')
ans = int(0)

N, K = LI()
x = [0]*N; y = [0]*N
for i in range(N):
    x[i], y[i] = LI()

X = copy.deepcopy(x); Y = copy.deepcopy(y)
X.sort(); Y.sort()

Xcandi = [0]*2; Ycandi = [0]*2
ylower = 0; yupper = N-1; ycur = (ylower+yupper)//2
ansC = []
for i in range(N-1):
    Xcandi[0] = X[i]
    for j in range(i+1,N):
        Xcandi[1] = X[j]
        for k in range(N-1):
            ylower = k+1; yupper = N - 1; ycur = (ylower + yupper) // 2
            Ycandi[0] = Y[k]
            while(True):
                cur = int(0)
                Ycandi[1] = Y[ycur]
                for l in range(N):
                    if Xcandi[0] <= x[l] <= Xcandi[1] and Ycandi[0] <= y[l] <= Ycandi[1]:
                        cur += 1
                if yupper - ylower >= 2:
                    if cur < K:
                        ylower = ycur
                        ycur = (ycur + yupper) // 2
                    else:
                        yupper = ycur
                        ycur = (ycur + ylower) // 2
                else:
                    if cur < K:
                        cur = int(0)
                        Ycandi[1] = Y[yupper]
                        for l in range(N):
                            if Xcandi[0] <= x[l] <= Xcandi[1] and Ycandi[0] <= y[l] <= Ycandi[1]:
                                cur += 1
                        if cur < K:
                            break
                    else:
                        cur = int(0)
                        Ycandi[1] = Y[ylower]
                        for l in range(N):
                            if Xcandi[0] <= x[l] <= Xcandi[1] and Ycandi[0] <= y[l] <= Ycandi[1]:
                                cur += 1
                        if cur < K:
                            Ycandi[1] = Y[ylower+1]
                    cur = (Xcandi[1] - Xcandi[0])*(Ycandi[1] - Ycandi[0])
                    ansC.append(cur)
#                    print(Xcandi,Ycandi)
                    break

#print(ansC)
print(min(ansC))

Submission status: Time Limit Exceeded

Solution code:
import copy
import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
mod = 10**9 + 7
inf = float('inf')
ans = int(0)

N, K = LI()
x = [0]*N; y = [0]*N
for i in range(N):
    x[i], y[i] = LI()

X = copy.deepcopy(x); Y = copy.deepcopy(y)
X.sort(); Y.sort()

Xcandi = [0]*2; Ycandi = [0]*2
ylower = 0; yupper = N-1; ycur = (ylower+yupper)//2
ansC = []
for i in range(N-1):
    Xcandi[0] = X[i]
    for j in range(i+1,N):
        Xcandi[1] = X[j]
        for k in range(N-1):
            ylower = k+1; yupper = N - 1; ycur = (ylower + yupper) // 2
            Ycandi[0] = Y[k]
            while(True):
                cur = int(0)
                Ycandi[1] = Y[ycur]
                for l in range(N):
                    if Xcandi[0] <= x[l] <= Xcandi[1] and Ycandi[0] <= y[l] <= Ycandi[1]:
                        cur += 1
                if yupper - ylower >= 2:
                    if cur < K:
                        ylower = ycur
                        ycur = (ycur + yupper) // 2
                    else:
                        yupper = ycur
                        ycur = (ycur + ylower) // 2
                else:
                    cur = int(0)
                    Ycandi[1] = Y[yupper]
                    for l in range(N):
                        if Xcandi[0] <= x[l] <= Xcandi[1] and Ycandi[0] <= y[l] <= Ycandi[1]:
                            cur += 1
                    if cur < K:
                        break
                    else:
                        cur = int(0)
                        Ycandi[1] = Y[ylower]
                        for l in range(N):
                            if Xcandi[0] <= x[l] <= Xcandi[1] and Ycandi[0] <= y[l] <= Ycandi[1]:
                                cur += 1
                        if cur < K:
                            Ycandi[1] = Y[ylower+1]
                    cur = (Xcandi[1] - Xcandi[0])*(Ycandi[1] - Ycandi[0])
                    ansC.append(cur)
#                    print(Xcandi,Ycandi)
                    break

#print(ansC)
print(min(ansC))

Submission status: Time Limit Exceeded

Solution code:
import itertools
n,k=map(int,input().split())
l=[]
for i in range(n):
    l.append(list(map(int,input().split())))
c=itertools.combinations(range(n),k)
ans=1e25
for i in c:
    ax=-1e11
    ix=1e11
    ay=-1e11
    iy=1e11
    for j in i:
        ax=max(ax,l[j][0])
        ix=min(ix,l[j][0])
        ay=max(ay,l[j][1])
        iy=min(iy,l[j][1])
    ans=min(ans,(ax-ix)*(ay-iy))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
n,k=map(int,input().split())
l=[]
for i in range(n):
    l.append(list(map(int,input().split())))
c=itertools.combinations(range(n),k)
ans=1e25
for i in c:
    x=[]
    y=[]
    for j in i:
        x.append(l[j][0])
        y.append(l[j][1])
    ans=min(ans,(max(x)-min(x))*(max(y)-min(y)))
print(ans)

Submission status: Time Limit Exceeded

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

ans=1e20
for i in range(n):
    for j in range(i+1, n):
        for a in range(n):
            for b in range(a+1, n):
                cnt=0
                x1=min(x[i],x[j])
                x2=max(x[i],x[j])
                y1=min(y[a],y[b])
                y2=max(y[a],y[b])
                for c in range(n):
                    if x1<=x[c]<=x2 and y1<=y[c]<=y2: cnt+=1
                if cnt>=k:
                    ans=min(ans,(x2-x1)*(y2-y1))
print(ans)

Submission status: Time Limit Exceeded

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

XY.sort()
x_list, y_list = [list(l) for l in zip(*XY)]

min_area = 10**24
for x1 in x_list:
    for y1 in y_list:
        for x2 in x_list:
            for y2 in y_list:
                if x1 > x2 or y1 > y2:
                    continue
                c = 0
                for x3, y3 in XY:
                    if x1 <= x3 <= x2 and y1 <= y3 <= y2:
                        c += 1
                if c >= K:
                    min_area = min(
                        min_area,
                        (x2-x1)*(y2-y1)
                    )

print(min_area)

Submission status: Time Limit Exceeded

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

XY.sort()
x_list, y_list = [list(l) for l in zip(*XY)]

min_area = 10**24
for x1 in x_list:
    for y1 in y_list:
        for x2 in x_list:
            for y2 in y_list:
                if x1 > x2 or y1 > y2:
                    continue
                c = 0
                for x3, y3 in XY:
                    if x1 <= x3 <= x2 and y1 <= y3 <= y2:
                        c += 1
                if c >= K:
                    min_area = min(
                        min_area,
                        (x2-x1)*(y2-y1)
                    )

print(min_area)

Submission status: Time Limit Exceeded

Solution code:
import sys
def LI(): return([int(x) for x in sys.stdin.readline().split()])

N,K = LI()
XY = [LI() for _ in range(N)]

X = []
Y = []
for x,y in XY:
    if not(x in X):
        X.append(x)
    if not(y in Y):
        Y.append(y)
X.sort()
Y.sort()

ans = []
for xl in range(len(X)-1):
    for xr in range(xl,len(X)):
        for yd in range(len(Y)-1):
            for yu in range(yd,len(Y)):
                ans_tmp = 0
                for x,y in XY:
                    if X[xl]<=x<=X[xr] and Y[yd]<=y<=Y[yu]:
                        ans_tmp += 1
                if ans_tmp >= K:
                    ans.append((X[xr]-X[xl])*(Y[yu]-Y[yd]))
print(min(ans))

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
x_list = [0]*N
y_list = [0]*N
for i in range(N):
    x_list[i], y_list[i] = map(int, input().split())

x_sort_list = sorted(x_list)
y_sort_list = sorted(y_list)
ans = float("inf")

for i in range(len(x_sort_list)):
    for j in range(len(y_sort_list)):
        for k in range(i+1, len(x_sort_list)):
            for l in range(j+1, len(y_sort_list)):
                num = 0
                for m in range(N):
                    if x_sort_list[i] <= x_list[m] <= x_sort_list[k] and y_sort_list[j] <= y_list[m] <= y_sort_list[l]:
                        num += 1
                if num >= K:
                    ans = min((x_sort_list[k] - x_sort_list[i]) * (y_sort_list[l] - y_sort_list[j]), ans)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations

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

area = float('inf')

for x1,x2 in combinations(range(n),2):
  for y1,y2 in combinations(range(n),2):
    
    point = 0
    for i in range(n):
      if (min(P[x1][0],P[x2][0])<= P[i][0] <=max(P[x1][0],P[x2][0]) 
      and min(P[y1][1],P[y2][1])<= P[i][1] <=max(P[y1][1],P[y2][1])):
        point += 1
    if point==k:
      area = min(area,abs(P[x1][0]-P[x2][0])*abs(P[y1][1]-P[y2][1]))
      
print(area)

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split())
ary = [list(map(int,input().split())) for _ in range(n)]
ary_x = sorted(ary)
ary_y = sorted(ary,key=lambda x:(x[1],x[0]))
ans = float("Inf")

for xi in range(n):
    for xj in range(1,n):
        for yi in range(n):
            for yj in range(1,n):
                count = 0
                lx,rx = ary_x[xi][0],ary_x[xj][0]
                by,uy = ary_y[yi][1],ary_y[yj][1]

                for i in range(n):
                    if lx <= ary[i][0] <= rx and by <= ary[i][1] <= uy:
                        count += 1
                if count >= k:
                    if ans > (rx - lx) * (uy - by):
                        ans = (rx - lx) * (uy - by)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split())
ary = [list(map(int,input().split())) for _ in range(n)]
ary_x = sorted(ary)
ary_y = sorted(ary,key=lambda x:(x[1],x[0]))
ans = float("Inf")

for xi in range(n):
    for xj in range(1,n):
        for yi in range(n):
            for yj in range(1,n):
                count = 0
                lx,rx = ary_x[xi][0],ary_x[xj][0]
                by,uy = ary_y[yi][1],ary_y[yj][1]

                for i in range(n):
                    if lx <= ary[i][0] <= rx and by <= ary[i][1] <= uy:
                        count += 1
                if count >= k:
                    ans = min(ans,(rx - lx) * (uy - by))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n,k = map(int,input().split())
ary = [list(map(int,input().split())) for _ in range(n)]
ary_x = sorted(ary)
ary_y = sorted(ary,key=lambda x:(x[1],x[0]))
num = np.array(ary,dtype=float)
ans = float("Inf")

for xi in range(n):
    for xj in range(1,n):
        for yi in range(n):
            for yj in range(1,n):
                count = 0
                lx,rx = ary_x[xi][0],ary_x[xj][0]
                by,uy = ary_y[yi][1],ary_y[yj][1]

                for i in range(n):
                    if lx <= ary[i][0] <= rx and by <= ary[i][1] <= uy:
                        count += 1
                if count >= k:
                    ans = min(ans,(rx - lx) * (uy - by))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
n,k = map(int,input().split())
ary = [list(map(int,input().split())) for _ in range(n)]
ary = list(itertools.combinations(ary,k))
ans = float("Inf")
for i in range(len(ary)):
    a = []
    for j in enumerate(zip(*ary[i])):
        a.append([min(j[1]),max(j[1])])
    if ans > (a[0][1] - a[0][0]) * (a[1][1] - a[1][0]):
        ans = (a[0][1] - a[0][0]) * (a[1][1] - a[1][0])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import itertools
n,k = map(int,input().split())
ary = np.array([list(map(int,input().split())) for _ in range(n)],dtype=float)
a = list(itertools.combinations(ary,k))
ans = float("Inf")
for i in a:
    min_a = np.min(i,axis=0)
    max_a = np.max(i,axis=0)
    a = max_a[0] - min_a[0]
    b = max_a[1] - min_a[1]
    ans = min(ans,int(a)*int(b))
print(ans)