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:
import sys
sys.setrecursionlimit(1000000)
def input():
    return sys.stdin.readline()[:-1]

'''
n=int(input())
for i in range(n):
    a[i]=int(input())
    a[i],b[i]=map(int,input().split())
a=[int(x) for x in input().split()]
n,m=map(int,input.split())
from operator import itemgetter
a = [(1, "c", 1), (1, "b", 3), (2, "a", 0), (1, "a", 2)]
print(sorted(a))  # 0 番目の要素でソート、先頭の要素が同じなら 1 番目以降の要素も見る
print(sorted(a, key=itemgetter(0)))  # 0 番目の要素だけでソート
print(sorted(a, key=itemgetter(0, 2)))  # 0 番目と 2 番目の要素でソート
print(sorted(a, key=lambda x: x[0] * x[2]))  # 0 番目の要素 * 2 番目の要素でソート
print(sorted(a, reverse=True))  # 降順にソート
a.sort()  # 破壊的にソート、sorted() よりも高速
try: # エラーキャッチ list index out of range
    for i in range():
        k=b[i]
except IndexError as e:
    print(i)
'''

test_data1 = '''\
4 4
1 4
3 3
6 2
8 1
'''

test_data2 = '''\
4 2
0 0
1 1
2 2
3 3
'''

test_data3 = '''\
4 3
-1000000000 -1000000000
1000000000 1000000000
-999999999 999999999
999999999 -999999999
'''
td_num=3

def GetTestData(index):
    if index==1:
        return test_data1
    if index==2:
        return test_data2
    if index==3:
        return test_data3

if False:
    with open("../test.txt", mode='w') as f:
        f.write(GetTestData(td_num))
    with open("../test.txt") as f:
        # Start Input code ---------------------------------------
        
        n,k=map(int,f.readline().split())
        x=[0]*n
        y=[0]*n
        for i in range(n):
            x[i],y[i]=map(int,f.readline().split())
            
        # End Input code ---------------------------------------
else:
    for i in range(1):
        # Start Input 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())
        # End Input code ---------------------------------------
#print('n,k,x,y=',n,k,x,y)
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):                
                cnt=0
                for i in range(n):
                    if min(x[x1],x[x2])<=x[i] and x[i]<=max(x[x1],x[x2]) and min(y[y1],y[y2])<=y[i] and y[i]<=max(y[y1],y[y2]):
                        cnt+=1
                        
                if cnt>=k:
                    ans=min(ans,abs(x[x2]-x[x1])*abs(y[y2]-y[y1]))
                    #print(x1,x2,y1,y2,ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)
def input():
    return sys.stdin.readline()[:-1]

'''
n=int(input())
for i in range(n):
    a[i]=int(input())
    a[i],b[i]=map(int,input().split())
a=[int(x) for x in input().split()]
n,m=map(int,input.split())
from operator import itemgetter
a = [(1, "c", 1), (1, "b", 3), (2, "a", 0), (1, "a", 2)]
print(sorted(a))  # 0 番目の要素でソート、先頭の要素が同じなら 1 番目以降の要素も見る
print(sorted(a, key=itemgetter(0)))  # 0 番目の要素だけでソート
print(sorted(a, key=itemgetter(0, 2)))  # 0 番目と 2 番目の要素でソート
print(sorted(a, key=lambda x: x[0] * x[2]))  # 0 番目の要素 * 2 番目の要素でソート
print(sorted(a, reverse=True))  # 降順にソート
a.sort()  # 破壊的にソート、sorted() よりも高速
try: # エラーキャッチ list index out of range
    for i in range():
        k=b[i]
except IndexError as e:
    print(i)
'''

test_data1 = '''\
4 4
1 4
3 3
6 2
8 1
'''

test_data2 = '''\
4 2
0 0
1 1
2 2
3 3
'''

test_data3 = '''\
4 3
-1000000000 -1000000000
1000000000 1000000000
-999999999 999999999
999999999 -999999999
'''
td_num=3

def GetTestData(index):
    if index==1:
        return test_data1
    if index==2:
        return test_data2
    if index==3:
        return test_data3

if False:
    with open("../test.txt", mode='w') as f:
        f.write(GetTestData(td_num))
    with open("../test.txt") as f:
        # Start Input code ---------------------------------------
        
        n,k=map(int,f.readline().split())
        x=[0]*n
        y=[0]*n
        for i in range(n):
            x[i],y[i]=map(int,f.readline().split())
            
        # End Input code ---------------------------------------
else:
    for i in range(1):
        # Start Input 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())
        # End Input code ---------------------------------------
#print('n,k,x,y=',n,k,x,y)
ans=10**20
for x1 in range(n):
    for x2 in range(n):
        for y1 in range(n):
            for y2 in range(n):                
                cnt=0
                for i in range(n):
                    if min(x[x1],x[x2])<=x[i] and x[i]<=max(x[x1],x[x2]) and min(y[y1],y[y2])<=y[i] and y[i]<=max(y[y1],y[y2]):
                        cnt+=1
                        
                if cnt>=k:
                    ans=min(ans,abs(x[x2]-x[x1])*abs(y[y2]-y[y1]))
                    #print(x1,x2,y1,y2,ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)
#def input():
#    return sys.stdin.readline()[:-1]

'''
n=int(input())
for i in range(n):
    a[i]=int(input())
    a[i],b[i]=map(int,input().split())
a=[int(x) for x in input().split()]
n,m=map(int,input.split())
from operator import itemgetter
a = [(1, "c", 1), (1, "b", 3), (2, "a", 0), (1, "a", 2)]
print(sorted(a))  # 0 番目の要素でソート、先頭の要素が同じなら 1 番目以降の要素も見る
print(sorted(a, key=itemgetter(0)))  # 0 番目の要素だけでソート
print(sorted(a, key=itemgetter(0, 2)))  # 0 番目と 2 番目の要素でソート
print(sorted(a, key=lambda x: x[0] * x[2]))  # 0 番目の要素 * 2 番目の要素でソート
print(sorted(a, reverse=True))  # 降順にソート
a.sort()  # 破壊的にソート、sorted() よりも高速
try: # エラーキャッチ list index out of range
    for i in range():
        k=b[i]
except IndexError as e:
    print(i)
'''

test_data1 = '''\
4 4
1 4
3 3
6 2
8 1
'''

test_data2 = '''\
4 2
0 0
1 1
2 2
3 3
'''

test_data3 = '''\
4 3
-1000000000 -1000000000
1000000000 1000000000
-999999999 999999999
999999999 -999999999
'''
td_num=3

def GetTestData(index):
    if index==1:
        return test_data1
    if index==2:
        return test_data2
    if index==3:
        return test_data3

if False:
    with open("../test.txt", mode='w') as f:
        f.write(GetTestData(td_num))
    with open("../test.txt") as f:
        # Start Input code ---------------------------------------
        
        n,k=map(int,f.readline().split())
        x=[0]*n
        y=[0]*n
        for i in range(n):
            x[i],y[i]=map(int,f.readline().split())
            
        # End Input code ---------------------------------------
else:
    for i in range(1):
        # Start Input 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())
        # End Input code ---------------------------------------
#print('n,k,x,y=',n,k,x,y)
ans=10**20
for x1 in range(n):
    for x2 in range(n):
        for y1 in range(n):
            for y2 in range(n):                
                cnt=0
                for i in range(n):
                    if min(x[x1],x[x2])<=x[i] and x[i]<=max(x[x1],x[x2]) and min(y[y1],y[y2])<=y[i] and y[i]<=max(y[y1],y[y2]):
                        cnt+=1
                        
                if cnt>=k:
                    ans=min(ans,abs(x[x2]-x[x1])*abs(y[y2]-y[y1]))
                    #print(x1,x2,y1,y2,ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def solve(N, K, XYs):
    ans = 10 ** 19 + 1
    Ys = [y for x, y in XYs]
    Xs = [x for x, y in XYs]
    for y1 in Ys:
        for y2 in Ys:
            if y1 >= y2:
                continue
            for x1 in Xs:
                for x2 in Xs:
                    if x1 >= x2:
                        continue
                    y1, y2 = min(y1, y2), max(y1, y2)
                    x1, x2 = min(x1, x2), max(x1, x2)
                    if len([(x, y) for x, y in XYs if x1 <= x <= x2 and y1 <= y <= y2]) >= K:
                        ans = min(ans, abs(y2 - y1) * abs(x2 - x1))
    return ans

if __name__ == "__main__":
    N, K = tuple(map(int, input().split(" ")))
    XYs = [tuple(map(int, input().split(" "))) for _ in range(N)]
    print(solve(N, K, XYs))

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations

def solve(N, K, XYs):
    ans = 10 ** 19 + 1
    Ys = [y for x, y in XYs]
    Xs = [x for x, y in XYs]
    for y1, y2 in combinations(Ys, r=2):
        for x1, x2 in combinations(Xs, r=2):
            y1, y2 = min(y1, y2), max(y1, y2)
            x1, x2 = min(x1, x2), max(x1, x2)
            if len([(x, y) for x, y in XYs if x1 <= x <= x2 and y1 <= y <= y2]) >= K:
                ans = min(ans, abs(y2 - y1) * abs(x2 - x1))
    return ans


if __name__ == "__main__":
    N, K = tuple(map(int, input().split(" ")))
    XYs = [tuple(map(int, input().split(" "))) for _ in range(N)]
    print(solve(N, K, XYs))

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations


def solve(N, K, XYs):
    ans = 10 ** 19 + 1
    for candidate in combinations(XYs, r=K):
        candidate = list(candidate)
        xs = sorted([x for x, y in candidate])
        max_x = xs[-1]
        min_x = xs[0]
        ys = sorted([y for x, y in candidate])
        max_y = ys[-1]
        min_y = ys[0]

        ans = min(ans, abs(max_x - min_x) * abs(max_y - min_y))
    return ans


if __name__ == "__main__":
    N, K = tuple(map(int, input().split(" ")))
    XYs = [tuple(map(int, input().split(" "))) for _ in range(N)]
    print(solve(N, K, XYs))

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
xy = []
for _ in range(n):
  xy.append(tuple(map(int, input().split())))

mins = None
for i, _xl in enumerate(xy):
  for _xr in xy[i:]:
    for j, _yu in enumerate(xy):
      for _yd in xy[j:]:
        c = 0
        for _xy in xy:
          if min(_xl[0], _xr[0]) <= _xy[0] <= max(_xl[0], _xr[0]) and min(_yd[1], _yu[1]) <= _xy[1] <= max(_yd[1], _yu[1]):
            c += 1
        if c >= k:
          if mins is None:
            mins = abs(_xl[0] - _xr[0]) * abs(_yu[1] - _yd[1])
          elif mins > abs(_xl[0] - _xr[0]) * abs(_yu[1] - _yd[1]):
            mins = abs(_xl[0] - _xr[0]) * abs(_yu[1] - _yd[1])
print(mins)

Submission status: Time Limit Exceeded

Solution code:
import itertools
N,K = map(int,input().split())
zahyou = []
for i in range(N):
  zahyou.append(list(map(int,input().split())))
ans = float('inf')
X = []
Y = []
for i in range(N):
  X.append(zahyou[i][0])
  Y.append(zahyou[i][1])
P = list(itertools.combinations(X,2))
Q = list(itertools.combinations(Y,2))
for i in range(len(P)):
  for j in range(len(Q)):
    x1 = min(P[i][0],P[i][1])
    x2 = max(P[i][0],P[i][1])
    y1 = min(Q[j][0],Q[j][1])
    y2 = max(Q[j][0],Q[j][1])
    cnt = 0
    for k in range(N):
      if x1 <= zahyou[k][0] <= x2 and y1 <= zahyou[k][1] <= y2:
        cnt += 1
    if cnt >= K:
      if ans >= (x2-x1)*(y2-y1):
        ans = (x2-x1)*(y2-y1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
xy = []
for _ in range(n):
  xy.append(tuple(map(int, input().split())))

mins = None
for i, _xl in enumerate(xy):
  for _xr in xy[i:]:
    for j, _yu in enumerate(xy):
      for _yd in xy[j:]:
        c = 0
        for _xy in xy:
          if min(_xl[0], _xr[0]) <= _xy[0] <= max(_xl[0], _xr[0]) and min(_yd[1], _yu[1]) <= _xy[1] <= max(_yd[1], _yu[1]):
            c += 1
        if c >= k:
          if mins is None:
            mins = abs(_xl[0] - _xr[0]) * abs(_yu[1] - _yd[1])
          elif mins > abs(_xl[0] - _xr[0]) * abs(_yu[1] - _yd[1]):
            mins = abs(_xl[0] - _xr[0]) * abs(_yu[1] - _yd[1])
print(mins)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
lst = [list(map(int, input().split())) for i in range(n)]

min_area = 10**100
for a in lst:
    for b in lst:
        for c in lst:
            for d in lst:
                count = 0
                for e in lst:
                    if a[0] <= e[0] <= b[0] or a[0] >= e[0] >= b[0]:
                        if c[1] <= e[1] <= d[1] or c[1] >= e[1] >= d[1]:
                            count += 1
                if count >= k:
                    area = abs(a[0] - b[0]) * abs(c[1] - d[1])
                    if area < min_area:
                        min_area = area
print(min_area)

Submission status: Time Limit Exceeded

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

xlst = []
ylst = []

for x,y in XY:
    x += 10**9 + 1
    y += 10**9 + 1
    xlst.append(x)
    ylst.append(y)

xset = sorted(list(set(xlst)))
yset = sorted(list(set(ylst)))

# print(xset, yset)

S = [ [0]*(N+1) for _ in range(N+1)]

for x,y in zip(xlst,ylst):
    x=xset.index(x)+1
    y=yset.index(y)+1
    S[y][x] = 1

for y in range(N+1):
    for x in range(1, N+1):
        S[y][x] += S[y][x-1]
for x in range(N+1):
    for y in range(1,N+1):
        S[y][x] += S[y-1][x]


ans = float("inf")
for i in range(N):
    for j in range(N):
        for k in range(N):
            for ll in range(N):

                left     = xlst[i]
                right    = xlst[j]
                top      = ylst[k]
                bottom   = ylst[ll]

                if right <= left: continue
                if bottom <= top: continue

                left = xset.index(left)+1
                right = xset.index(right)+1
                top = yset.index(top)+1
                bottom=yset.index(bottom)+1


                cnt = 0
                cnt += S[bottom][right]
                # print(cnt)
                cnt += S[top-1][left-1]
                # print(cnt)
                cnt -= S[top-1][right]
                # print(cnt)
                cnt -= S[bottom][left-1]
                # print(cnt)
                if cnt >= K:
                    left = xset[left    -1 ]
                    right = xset[right  -1 ]
                    top = yset[top      -1 ]
                    bottom = yset[bottom-1 ]
                    rect_area = (right-left)*(bottom-top)
                    ans = min(ans, rect_area)
                
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())

point=[]
answer=10**19
for i in range(N):
  point.append(list(map(int,input().split())))
sorted(point)
for left in range(N):
  for right in range(N):
    dx=point[right][0]-point[left][0]
    for ceil in range(N):
      for bottom in range(N):
        if point[bottom][1] > point[ceil][1]:
          continue
        count=0
        for i in range(N):
          x=point[i][0]
          y=point[i][1]
          if point[left][0]<=x and x<=point[right][0] and point[bottom][1]<=y and y<=point[ceil][1]:
            count+=1
        if count>=K:
          answer=min(answer,dx*(point[ceil][1]-point[bottom][1]))
     
          
print(answer)

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())

point=[]
answer=10**19
for i in range(N):
  point.append(list(map(int,input().split())))
  
for left in range(N):
  for right in range(N):
    if point[right][0]<point[left][0]:
      continue
    for ceil in range(N):
      for bottom in range(N):
        if point[bottom][1] > point[ceil][1]:
          continue
        count=0
        for i in range(N):
          x=point[i][0]
          y=point[i][1]
          if point[left][0]<=x and x<=point[right][0] and point[bottom][1]<=y and y<=point[ceil][1]:
            count+=1
        if count>=K:
          answer=min(answer,(point[right][0]-point[left][0])*(point[ceil][1]-point[bottom][1]))
     
          
print(answer)

Submission status: Time Limit Exceeded

Solution code:
# d
N,K = map(int, input().split())
xy = []
for _ in range(N):
    xy.append( tuple(map(int, input().split())) )
xs,ys = map(list, zip(*xy))
xs.sort()
ys.sort()
ans = float('inf')
for l in range(N):
    for r in range(l+1,N):
        for b in range(N):
            for t in range(b+1,N):
                xl,xr = xs[l],xs[r]
                yb,yt = ys[b],ys[t]
                cnt = 0
                for xi,yi in xy:
                    if xl<=xi<=xr and yb<=yi<=yt: 
                        cnt += 1
                if cnt>=K:
                    ans = min(ans, (xr-xl)*(yt-yb))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import product
N, K = map(int, input().split())
XY = []
X, Y = [], []
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 = 10 ** 19
for l, r, t, b in product(X, X, Y, Y):
    if l > r or t > b:
        continue
    area = (r - l) * (b - t)
    if area >= ans:
        continue
    cnt = -K
    for x, y in XY:
        if l <= x <= r and t <= y <= b:
            cnt +=1
            if cnt >= 0:
                break
    if cnt >= 0:
        ans = area

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int, input().split())
X = []; Y = []
oriX  = []; oriY = []


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

X = sorted(list(set(X)))
Y = sorted(list(set(Y)))

for i in range(len( oriX)) :
    oriX[i] = X.index(oriX[i] )
    oriY[i] = Y.index( oriY[i] )  

MAP = [ [0] * len(oriX) for _ in (oriY)]
for i in range(len(oriX)):
    MAP[ oriY[i] ][ oriX[i] ] = 1


ans = float("inf")

for i in range(len(oriX)):
    for j in range(len(oriX)):
        if i == j : continue

        for p in range(len(oriY)):
            for q in range(len(oriY)):
                if p == q: continue


                npoints = 0
                for c in range(N):
                    if  oriX[i] <= oriX[c] <= oriX[j]:
                        if oriY[p] <= oriY[c] <= oriY[q]:
                            npoints += 1
                        
                # for h in range(oriY[p], oriY[q]+1):
                #     for w in range(oriX[i], oriX[j]+1):
                #         if MAP[h][w] == 1: 
                #             npoints += 1

                if npoints >= K:
                    tmp = (X[oriX[j]] - X[oriX[i]]) * (Y[oriY[q]] - Y[oriY[p]])
                    ans = min(tmp, ans)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int, input().split())
X = []; Y = []
oriX  = []; oriY = []


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

X = sorted(list(set(X)))
Y = sorted(list(set(Y)))

for i in range(len( oriX)) :
    oriX[i] = X.index(oriX[i] )
    oriY[i] = Y.index( oriY[i] )  

MAP = [ [0] * len(oriX) for _ in (oriY)]
for i in range(len(oriX)):
    MAP[ oriY[i] ][ oriX[i] ] = 1


ans = float("inf")

for i in range(len(oriX)):
    for j in range(len(oriX)):
        if i == j : continue

        for p in range(len(oriY)):
            for q in range(len(oriY)):
                if p == q: continue


                npoints = 0
                for h in range(oriY[p], oriY[q]+1):
                    for w in range(oriX[i], oriX[j]+1):
                        if MAP[h][w] == 1: 
                            npoints += 1

                if npoints >= K:
                    tmp = (X[oriX[j]] - X[oriX[i]]) * (Y[oriY[q]] - Y[oriY[p]])
                    ans = min(tmp, ans)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations

N,K=map(int,input().split())
o=[tuple(map(int,input().split())) for _ in range(N)]
ans=float("inf")

for i,j in combinations(o,2):
    x1,y1=i
    x2,y2=j
    xmax,xmin=max(x1,x2),min(x1,x2)

    for k,l in combinations(o,2):
        x3,y3=k
        x4,y4=l
        ymax,ymin=max(y3,y4),min(y3,y4)

        v=0
        for m in o:
            x5,y5=m
            if xmin<=x5<=xmax and ymin<=y5<=ymax:
                v+=1
        
        if v>=K:
            ans=min(ans,(ymax-ymin)*(xmax-xmin))


print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
z=[list(map(int,input().split()))for _ in range(n)]
x=[i for i,_ in z]
y=[j for _,j in z]
x.sort()
y.sort()
a=10**20
for i,l in enumerate(x):
    for r in x[i+1:]:
        for v,d in enumerate(y):
            for u in y[v+1:]:
                if sum([1for i,j in z if l<=i<=r and d<=j<=u])>=k:
                    a=min(a,(r-l)*(u-d))
print(a)

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
z=[tuple(map(int,input().split()))for _ in range(N)]
x=[i for i,_ in z]
y=[j for _,j in z]
x.sort()
y.sort()
a=10**20
for i in range(N):
    for j in range(i+1,N):
        for k in range(N):
            for l in range(k+1,N):
                l,r,d,u=x[i],x[j],y[k],y[l]
                if sum([l<=v<=r and d<=w<=u for v,w in z])>=K:
                    a=min(a,(r-l)*(u-d))
print(a)

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
z=[list(map(int,input().split()))for _ in range(N)]
x=[]
y=[]
for i,j in z:
    x.append(i)
    y.append(j)
x.sort()
y.sort()
a=10**20
for i in range(N):
    for j in range(i+1,N):
        for k in range(N):
            for l in range(k+1,N):
                l,r,d,u=x[i],x[j],y[k],y[l]
                if sum([l<=v<=r and d<=w<=u for v,w in z])>=K:
                    a=min(a,(r-l)*(u-d))
print(a)

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
z=[list(map(int,input().split()))for _ in range(N)]
x=[]
y=[]
for i,j in z:
    x.append(i)
    y.append(j)
x.sort()
y.sort()
a=10**20
for i in range(N):
    for j in range(i+1,N):
        for k in range(N):
            for l in range(k+1,N):
                l,r,d,u=x[i],x[j],y[k],y[l]
                if sum(l<=v<=r and d<=w<=u for v,w in z)>=K:
                    a=min(a,(r-l)*(u-d))
print(a)

Submission status: Time Limit Exceeded

Solution code:
from itertools import*
n,k=map(int,input().split())
a=10**20
for z in combinations(sorted(list(map(int,input().split()))for _ in range(n)),k):
    y=[j for _,j in z]
    a=min(a,(z[-1][0]-z[0][0])*(max(y)-min(y)))
print(a)

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
z=[list(map(int,input().split()))for _ in range(n)]
x=[]
y=[]
for i,j in z:
    x.append(i)
    y.append(j)
x.sort()
y.sort()
a=10**20
for i,l in enumerate(x):
    for r in x[i+1:]:
        for v,d in enumerate(y):
            for u in y[v+1:]:
                if sum(l<=i<=r and d<=j<=u for i,j in z)>=k:
                    a=min(a,(r-l)*(u-d))
print(a)

Submission status: Time Limit Exceeded

Solution code:
from itertools import*
n,k=map(int,input().split())
z=[list(map(int,input().split()))for _ in range(n)]
x=[]
y=[]
for i,j in z:
    x.append(i)
    y.append(j)
x.sort()
y.sort()
a=10**20
for s,t in combinations(x,2):
    for u,v in combinations(y,2):
        c=sum(s<=i<=t and u<=j<=v for i,j in z)
        if c>=k:
            a=min(a,(t-s)*(v-u))
print(a)

Submission status: Time Limit Exceeded

Solution code:
from itertools import*
n,k=map(int,input().split())
a=10**20
for z in combinations([list(map(int,input().split()))for _ in range(n)],k):
    x=[]
    y=[]
    for i,j in z:
        x.append(i)
        y.append(j)
    a=min(a,(max(x)-min(x))*(max(y)-min(y)))
print(a)

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
D=[]
X=[]
Y=[]

for i in range(N):
    x,y=map(int,input().split())
    D.append([x,y])
    X.append(x)
    Y.append(y)
    
X.sort()
Y.sort()
D.sort()
ans=10**20
for a in range(len(X)):
    for b in range(len(X)-a):
        if len(X)-b-a<K:
            break
        for c in range(len(Y)):
            for d in range(len(Y)-c):
                cnt=0
                for e in range(a,len(X)-b):
                    if X[a]<=D[e][0]<=X[len(X)-1-b] and Y[c]<=D[e][1]<=Y[len(Y)-1-d]:
                        cnt+=1
                if cnt>=K and ans>abs(X[a]-X[len(X)-1-b])*abs(Y[c]-Y[len(Y)-1-d]):
                    ans=abs(X[a]-X[len(X)-1-b])*abs(Y[c]-Y[len(Y)-1-d])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
D=[]
X=[]
Y=[]

for i in range(N):
    x,y=map(int,input().split())
    D.append([x,y])
    X.append(x)
    Y.append(y)
    
X.sort()
Y.sort()
ans=10**20
for a in range(len(X)):
    for b in range(len(X)-a):
        if len(X)-b-a<K:
            break
        for c in range(len(Y)):
            for d in range(len(Y)-c):
                cnt=0
                for e in range(N):
                    if X[a]<=D[e][0]<=X[len(X)-1-b] and Y[c]<=D[e][1]<=Y[len(Y)-1-d]:
                        cnt+=1
                if cnt>=K and ans>abs(X[a]-X[len(X)-1-b])*abs(Y[c]-Y[len(Y)-1-d]):
                    ans=abs(X[a]-X[len(X)-1-b])*abs(Y[c]-Y[len(Y)-1-d])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
D=[]
X=[]
Y=[]

for i in range(N):
    x,y=map(int,input().split())
    D.append([x,y])
    X.append(x)
    Y.append(y)
    
X.sort()
Y.sort()
ans=10**20
for a in range(len(X)):
    for b in range(len(X)-a):
        for c in range(len(Y)):
            for d in range(len(Y)-c):
                cnt=0
                for e in range(N):
                    if X[a]<=D[e][0]<=X[len(X)-1-b] and Y[c]<=D[e][1]<=Y[len(Y)-1-d]:
                        cnt+=1
                if cnt>=K and ans>abs(X[a]-X[len(X)-1-b])*abs(Y[c]-Y[len(Y)-1-d]):
                    ans=abs(X[a]-X[len(X)-1-b])*abs(Y[c]-Y[len(Y)-1-d])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
X = []
Y = []
for _ in range(N):
    x, y = map(int, input().split())
    X.append(x)
    Y.append(y)
Xs = sorted(X)
Ys = sorted(Y)
ans = float('inf')
for left in range(N - 1):
    for right in range(left + 1, N):
        for down in range(N - 1):
            for up in range(down + 1, N):
                count = 0
                for i in range(N):
                    if Xs[left] <= X[i] <= Xs[right] and Ys[down] <= Y[i] <= Ys[up]:
                            count += 1
                if count >= K:
                    ans = min(ans, (Xs[right] - Xs[left]) * (Ys[up] - Ys[down]))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,k_num = map(int,input().split())
info =[list(map(int,input().split())) for i in range(n)]
li_x = []
li_y = []

for i in range(n):
  if info[i][0] not in li_x:
    li_x.append(info[i][0])
  if info[i][1] not in li_y:
    li_y.append(info[i][1])

li_x = sorted(li_x)
li_y = sorted(li_y)

ans = float("inf")

for i in range(len(li_x)):
  for j in range(i,len(li_x)):
    for k in range(len(li_y)):
      for l in range(k,len(li_y)):
        count = 0
        for m in range(n):
          if li_x[i]<=info[m][0]<=li_x[j] and li_y[k]<=info[m][1]<=li_y[l]:
            count += 1
        if count ==k_num:
          ans = min(ans,(li_x[j]-li_x[i])*(li_y[l]-li_y[k]))
print(ans)

Submission status: Time Limit Exceeded

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

tup = ()
for i in range(N):
    tup += (i,)

data = list(itertools.combinations(tup,2))
ans = []

for x in range(len(data)):
    for y in range(len(data)):
        cnt = 0
        x_side = data[x]
        y_side = data[y]
        x_left = min(s[x_side[0]][0],s[x_side[1]][0])
        x_right = max(s[x_side[0]][0],s[x_side[1]][0])
        y_bottom = min(s[y_side[0]][1],s[y_side[1]][1])
        y_top = max(s[y_side[0]][1],s[y_side[1]][1])
        for i in s:
            if (x_left <= i[0] and i[0] <= x_right)and(y_bottom <= i[1] and i[1] <= y_top):
                cnt += 1
        if cnt >= K:
            ans.append((x_right-x_left)*(y_top-y_bottom))
    
        
print(min(ans))

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
N, K = (list)(map(int, input().split()))
pos_x = []
pos_y = []

for _ in range(N):
    a, b = map(int, input().split())
    pos_x.append(a)
    pos_y.append(b)


def count_point(x, y):
    ret = 0
    x_min = min(x)
    x_max = max(x)
    y_min = min(y)
    y_max = max(y)
    for i in range(N):
        if x_min <= pos_x[i] <= x_max and y_min <= pos_y[i] <= y_max:
            ret += 1
    return ret


def calc_area(x, y):
    ret = (x[1]-x[0])*(y[1]-y[0])
    return (abs)(ret)


set_x = set(pos_x)
set_y = set(pos_y)


area = float('inf')
for cand_x in combinations(set_x, 2):
    for cand_y in combinations(set_y, 2):
        if count_point(cand_x, cand_y) >= K:
            area = min(area, calc_area(cand_x, cand_y))
print(area)

Submission status: Time Limit Exceeded

Solution code:
import bisect


def countInside(x1, y1, x2, y2, XY, X):
    minX = min(x1, x2)
    maxX = max(x1, x2)
    minY = min(y1, y2)
    maxY = max(y1, y2)
    ret = 0
    minXidx = bisect.bisect_left(X, minX)
    maxXidx = bisect.bisect_left(X, maxX)

    # for x, y in XY:
    for x, y in XY[minXidx:maxXidx + 1]:
        if minX <= x and x <= maxX and minY <= y and y <= maxY:
            ret += 1
    return ret


N, K = [int(x) for x in input().split()]

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

X = list(X)
Y = list(Y)
X.sort()
Y.sort()

import itertools

XY2 = list(itertools.product(X, Y))

ans = float("inf")

for i in range(len(XY2)):
    for j in range(len(XY2)):
        if i > j:
            x1, y1 = XY2[i][0], XY2[i][1]
            x2, y2 = XY2[j][0], XY2[j][1]
            if K <= countInside(x1, y1, x2, y2, XY, XYonlyX):
                area = abs(x1 - x2) * abs(y1 - y2)
                ans = min(area, ans)

print(ans)