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:
N, K = map(int, input().split())

XY = [tuple(map(int,input().split())) for i in range(N)]


dots = XY[:]

import sys
INT_MAX = sys.maxsize


def sub_f(x, ans_list):
    right_x, left_x = x[0], x[1]
    ans = INT_MAX
    for ((_, under_y), (_, top_y)) in itertools.combinations(dots, 2):
        if under_y > top_y:
            under_y, top_y = top_y, under_y
        counter = 0
        for d_x, d_y in dots:
            if  (left_x <= d_x) and (d_x <= right_x) and (under_y <= d_y) and (d_y <= top_y):
                counter += 1

        if counter >= K:
            area = (top_y-under_y) * (right_x-left_x)
            ans = min(ans, area)
    #return ans
    ans_list.append(ans)

import itertools
multiprocessing_inputs = []
for ((left_x, _), (right_x, _)) in itertools.combinations(dots, 2):
    if left_x > right_x:
        left_x, right_x = right_x, left_x
    
    multiprocessing_inputs.append((right_x, left_x))
    #ans_list.append(sub_f(right_x, left_x))


import threading
ans_list = []
threadlist = []
for x in multiprocessing_inputs:
    #ans_list = p.map(sub_f, multiprocessing_inputs)
    th = threading.Thread(target=sub_f, args=(x, ans_list))
    threadlist.append(th)
for th in threadlist:
    th.start()
for th in threadlist:
    th.join()

ans = min(ans_list)
print(ans)

Submission status: Time Limit Exceeded

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

XY = [tuple(map(int,input().split())) for i in range(N)]


dots = XY[:]

import sys
INT_MAX = sys.maxsize


def sub_f(right_x, left_x):
    ans = INT_MAX
    for ((_, under_y), (_, top_y)) in itertools.combinations(dots, 2):
        if under_y > top_y:
            under_y, top_y = top_y, under_y
        counter = 0
        for d_x, d_y in dots:
            if  (left_x <= d_x) and (d_x <= right_x) and (under_y <= d_y) and (d_y <= top_y):
                counter += 1

        if counter >= K:
            area = (top_y-under_y) * (right_x-left_x)
            ans = min(ans, area)
    return ans

import itertools
ans_list = []
for ((left_x, _), (right_x, _)) in itertools.combinations(dots, 2):
    if left_x > right_x:
        left_x, right_x = right_x, left_x
    
    ans_list.append(sub_f(right_x, left_x))
      
ans = min(ans_list)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N, K = map(int, input().split())

XY = [tuple(map(int,input().split())) for i in range(N)]

dots = XY[:]

import sys
INT_MAX = sys.maxsize

ans = INT_MAX

import itertools
for ((left_x, _), (right_x, _)) in itertools.combinations(dots, 2):
    if left_x > right_x:
        left_x, right_x = right_x, left_x
    for ((_, under_y), (_, top_y)) in itertools.combinations(dots, 2):
        if under_y > top_y:
            under_y, top_y = top_y, under_y
        counter = 0
        for d_x, d_y in dots:
            if  (left_x <= d_x) and (d_x <= right_x) and (under_y <= d_y) and (d_y <= top_y):
                counter += 1
                
        if counter >= K:
            area = (top_y-under_y) * (right_x-left_x)
            if ans > area:
                ans = area
            
print(ans)

Submission status: Time Limit Exceeded

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

XY = [tuple(map(int,input().split())) for i in range(N)]

dots = XY[:]

import sys
INT_MAX = sys.maxsize

ans = INT_MAX

import itertools
for ((left_x, _), (right_x, _)) in itertools.combinations(dots, 2):
    if left_x > right_x:
        left_x, right_x = right_x, left_x
    for ((_, under_y), (_, top_y)) in itertools.combinations(dots, 2):
        if under_y > top_y:
            under_y, top_y = top_y, under_y
        counter = 0
        for d_x, d_y in dots:
            if  (left_x <= d_x) and (d_x <= right_x) and (under_y <= d_y) and (d_y <= top_y):
                counter += 1
                
        if counter >= K:
            area = (top_y-under_y) * (right_x-left_x)
            if ans > area:
                ans = area
            
print(ans)

Submission status: Time Limit Exceeded

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

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

import sys
INT_MAX = sys.maxsize

ans = INT_MAX

import itertools
for ((left_x, _), (right_x, _)) in itertools.combinations(dots, 2):
    if left_x > right_x:
        left_x, right_x = right_x, left_x
    for ((_, under_y), (_, top_y)) in itertools.combinations(dots, 2):
        if under_y > top_y:
            under_y, top_y = top_y, under_y
        counter = 0
        for d_x, d_y in dots:
            if  (left_x <= d_x) and (d_x <= right_x) and (under_y <= d_y) and (d_y <= top_y):
                counter += 1
                
        if counter >= K:
            area = (top_y-under_y) * (right_x-left_x)
            if ans > area:
                ans = area
            
print(ans)

Submission status: Time Limit Exceeded

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

XY = []
for _ in range(N):
    x, y = map(int, input().split())
    XY.append((x, y))
    
import numpy as np
dots = np.asarray(XY[:])

import sys
INT_MAX = sys.maxsize

ans = INT_MAX

import itertools
for ((left_x, _), (right_x, _)) in itertools.combinations(dots, 2):
    if left_x > right_x:
        left_x, right_x = right_x, left_x
    for ((_, under_y), (_, top_y)) in itertools.combinations(dots, 2):
        if under_y > top_y:
            under_y, top_y = top_y, under_y
        counter = 0
        for d_x, d_y in dots:
            if  (left_x <= d_x) and (d_x <= right_x) and (under_y <= d_y) and (d_y <= top_y):
                counter += 1
                
        if counter >= K:
            area = (top_y-under_y) * (right_x-left_x)
            if ans > area:
                ans = area
            
print(ans)

Submission status: Time Limit Exceeded

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

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

import sys
INT_MAX = sys.maxsize

ans = INT_MAX

import itertools
for ((left_x, _), (right_x, _)) in itertools.combinations(dots, 2):
    if left_x > right_x:
        left_x, right_x = right_x, left_x
    for ((_, under_y), (_, top_y)) in itertools.combinations(dots, 2):
        if under_y > top_y:
            under_y, top_y = top_y, under_y
            
        counter = 0
        for d_x, d_y in dots:
            if  (left_x <= d_x) and (d_x <= right_x) and (under_y <= d_y) and (d_y <= top_y):
                counter += 1
                
        if counter >= K:
            area = (top_y-under_y) * (right_x-left_x)
            if ans > area:
                ans = area
            
print(ans)

Submission status: Time Limit Exceeded

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

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

import sys
INT_MAX = sys.maxsize

ans = INT_MAX

import itertools
for ((left_x, _), (right_x, _)) in itertools.permutations(dots, 2):
    if left_x > right_x:
        left_x, right_x = right_x, left_x
    
    for ((_, under_y), (_, top_y)) in itertools.permutations(dots, 2):
        if under_y > top_y:
            under_y, top_y = top_y, under_y
            
        counter = 0
        for d_x, d_y in dots:
            if  (left_x <= d_x) and (d_x <= right_x) and (under_y <= d_y) and (d_y <= top_y):
                counter += 1
                
        if counter >= K:
            area = (top_y-under_y) * (right_x-left_x)
            if ans > area:
                ans = area
            
print(ans)

Submission status: Time Limit Exceeded

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

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

import sys
INT_MAX = sys.maxsize

ans = INT_MAX

import itertools
for ((left_x, _), (right_x, _)) in itertools.permutations(dots, 2):
    if left_x > right_x:
        left_x, right_x = right_x, left_x
    
    for ((_, under_y), (_, top_y)) in itertools.permutations(dots, 2):
        if under_y > top_y:
            under_y, top_y = top_y, under_y
            
        counter = 0
        for d_x, d_y in dots:
            if  (left_x <= d_x) and (d_x <= right_x) and (under_y <= d_y) and (d_y <= top_y):
                counter += 1
                
        if counter >= K:
            area = (top_y-under_y) * (right_x-left_x)
            ans = min(ans, area)
            
print(ans)

Submission status: Time Limit Exceeded

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

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

import sys
INT_MAX = sys.maxsize

ans = INT_MAX

import itertools
for left_d, right_d in itertools.permutations(dots, 2):
    if left_d[0] < right_d[0]:
        left_x = left_d[0]
        right_x = right_d[0]
    else:
        left_x = right_d[0]
        right_x =  left_d[0]
    
    for under_d, top_d in itertools.permutations(dots, 2):
        if under_d[1] < top_d[1]:
            under_y = under_d[1]
            top_y = top_d[1]
        else:
            under_y = top_d[1]
            top_y = under_d[1]
            
        counter = 0
        for d in dots:
            if  (left_x <= d[0]) and (d[0] <= right_x) and (under_y <= d[1]) and (d[1] <= top_y):
                counter += 1
            if counter >= K:
                break
                
        if counter >= K:
            area = (top_y-under_y) * (right_x-left_x)
            ans = min(ans, area)
            
print(ans)

Submission status: Time Limit Exceeded

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

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

dots = XY[:]

import sys
INT_MAX = sys.maxsize

ans = INT_MAX

import itertools
for left_d, right_d in itertools.permutations(dots, 2):
    if left_d[0] < right_d[0]:
        left_x = left_d[0]
        right_x = right_d[0]
    else:
        left_x = right_d[0]
        right_x =  left_d[0]
    
    for under_d, top_d in itertools.permutations(dots, 2):
        if under_d[1] < top_d[1]:
            under_y = under_d[1]
            top_y = top_d[1]
        else:
            under_y = top_d[1]
            top_y = under_d[1]
            
        counter = 0
        for d in dots:
            if  (left_x <= d[0]) and (d[0] <= right_x) and (under_y <= d[1]) and (d[1] <= top_y):
                counter += 1
                
        if counter >= K:
            area = (top_y-under_y) * (right_x-left_x)
            ans = min(ans, area)    
print(ans)

Submission status: Time Limit Exceeded

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

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

dots = XY[:]

import sys
INT_MAX = sys.maxsize

ans = INT_MAX

import itertools
for left_d, right_d in itertools.permutations(dots, 2):
    if left_d[0] < right_d[0]:
        left_x = left_d[0]
        right_x = right_d[0]
    else:
        left_x = right_d[0]
        right_x =  left_d[0]
    
    for under_d, top_d in itertools.permutations(dots, 2):
        if under_d[1] < top_d[1]:
            under_y = under_d[1]
            top_y = top_d[1]
        else:
            under_y = top_d[1]
            top_y = under_d[1]
            
        counter = 0
        for d in dots:
            if  (left_x <= d[0]) and (d[0] <= right_x) and (under_y <= d[1]) and (d[1] <= top_y):
                counter += 1
                
        if counter >= K:
            area = (top_y-under_y) * (right_x-left_x)
            ans = min(ans, area)
            
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
import itertools
n,k=map(int,input().split())
X,Y,XY=[0]*n,[0]*n,[0]*n
for i in range(n):
  x,y=map(int,input().split())
  X[i],Y[i],XY[i]=x,y,[x,y]
X.sort()
Y.sort()
def count(x1,x2,y1,y2):
  ct=0
  for x,y in XY:
    if x1<=x<=x2 and y1<=y<=y2:
      ct+=1
  return ct
ans=float("inf")
for x1,x2 in itertools.combinations(X,2):
  for y1,y2 in itertools.combinations(Y,2):
    if count(x1,x2,y1,y2)==k:
      ans=min(ans,abs((x1-x2)*(y1-y2)))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
n,k=map(int,input().split())
X,Y,XY=[],[],[]
for i in range(n):
  x,y=map(int,input().split())
  X.append(x)
  Y.append(y)
  XY.append([x,y])
def count(x1,x2,y1,y2):
  ct=0
  if x1>x2:
    x1,x2=x2,x1
  if y1>y2:
    y1,y2=y2,y1
  for x,y in XY:
    if x1<=x<=x2 and y1<=y<=y2:
      ct+=1
  return ct
ans=float("inf")
for x1,x2 in itertools.combinations(X,2):
  for y1,y2 in itertools.combinations(Y,2):
    if count(x1,x2,y1,y2)==k:
      ans=min(ans,abs((x1-x2)*(y1-y2)))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
n,k=map(int,input().split())
X,Y,XY=[],[],[]
for i in range(n):
  x,y=map(int,input().split())
  X.append(x)
  Y.append(y)
  XY.append([x,y])
def count(x1,x2,y1,y2):
  ct=0
  if x1>x2:
    x1,x2=x2,x1
  if y1>y2:
    y1,y2=y2,y1
  for x,y in XY:
    if x1<=x<=x2 and y1<=y<=y2:
      ct+=1
  return ct
ans=float("inf")
for x1,x2 in itertools.combinations(X,2):
  for y1,y2 in itertools.combinations(Y,2):
    if count(x1,x2,y1,y2)==k:
      ans=min(ans,abs((x1-x2)*(y1-y2)))
print(ans)

Submission status: Time Limit Exceeded

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

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

dots = XY[:]

import sys
INT_MAX = sys.maxsize

x_dots = [(x, y) for x, y in dots]
x_dots = sorted(x_dots)
y_dots = [(x, y) for x, y in dots]
y_dots = sorted(y_dots, key=lambda x: x[1])

ans = INT_MAX

for left_i, (left_p_x, _) in enumerate(x_dots):
    for right_i, (right_p_x, _) in enumerate(x_dots[left_i:]):
        for under_i, (_, under_p_y) in enumerate(y_dots):
            for top_i, (_, top_p_y) in enumerate(y_dots[under_i:]):
                counter = 0
                for x, y in dots:
                    if left_p_x <= x and x <= right_p_x and under_p_y <= y and y <= top_p_y:
                        counter += 1
                
                if counter >= K:
                    area = (top_p_y-under_p_y) * (right_p_x-left_p_x)
                    ans = min(ans, area)


print(ans)

Submission status: Time Limit Exceeded

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

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

dots = XY[:]

import sys
INT_MAX = sys.maxsize

x_dots = [(x, y) for x, y in dots]
x_dots = sorted(x_dots)
y_dots = [(x, y) for x, y in dots]
y_dots = sorted(y_dots, key=lambda x: x[1])

ans = INT_MAX

for left_i, left_p in enumerate(x_dots):
    for right_i, right_p in enumerate(x_dots[left_i:]):
        for under_i, under_p in enumerate(y_dots):
            for top_i, top_p in enumerate(y_dots[under_i:]):
                counter = 0
                for x, y in dots:
                    if left_p[0] <= x and x <= right_p[0] and under_p[1] <= y and y <= top_p[1]:
                        counter += 1
                
                if counter >= K:
                    area = (top_p[1]-under_p[1]) * (right_p[0]-left_p[0])
                    ans = min(ans, area)


print(ans)

Submission status: Time Limit Exceeded

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

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

dots = XY[:]

import sys
INT_MAX = sys.maxsize

x_dots = [(x, y) for x, y in dots]
x_dots = sorted(x_dots)
y_dots = [(x, y) for x, y in dots]
y_dots = sorted(y_dots, key=lambda x: x[1])

ans = INT_MAX
for l in range(N):
    l_val = x_dots[l][0]
    for r in range(l+1, N+1):
        r_val = x_dots[l:r][-1][0]
        x_dots_set = set(x_dots[l:r])
        for u in range(N):
            u_val = y_dots[u][1]
            for t in range(u+1, N+1):
                #xy_dots =  set(x_dots[l:r]) & set(y_dots[u:t])
                xy_dots =  x_dots_set & set(y_dots[u:t])
                if len(xy_dots) >= K:
                    #print("---")
                    #print(l, r, x_dots[l:r])
                    #print(u, t, y_dots[u:t])
                    #print(x_dots[l:r])
                    #l_val = x_dots[l:r][0][0]
                    #r_val = x_dots[l:r][-1][0]
                    
                    #u_val = y_dots[u:t][0][1]
                    t_val = y_dots[u:t][-1][1]
                    #print((r-l)*(t-u))
                    if ans > (r_val-l_val)*(t_val-u_val):
                        ans = (r_val-l_val)*(t_val-u_val)
                    else:
                        break
print(ans)


#y_dots = sorted(y_dots, key=lambda x: x[1])
#ans = INT_MAX

Submission status: Time Limit Exceeded

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

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

dots = XY[:]

import sys
INT_MAX = sys.maxsize

x_dots = [(x, y) for x, y in dots]
x_dots = sorted(x_dots)
y_dots = [(x, y) for x, y in dots]
y_dots = sorted(y_dots, key=lambda x: x[1])

ans = INT_MAX
for l in range(N):
    l_val = x_dots[l][0]
    for r in range(l+1, N+1):
        r_val = x_dots[l:r][-1][0]
        for u in range(N):
            u_val = y_dots[u][1]
            for t in range(u+1, N+1):
                xy_dots =  set(x_dots[l:r]) & set(y_dots[u:t])
                if len(xy_dots) >= K:
                    #print("---")
                    #print(l, r, x_dots[l:r])
                    #print(u, t, y_dots[u:t])
                    #print(x_dots[l:r])
                    #l_val = x_dots[l:r][0][0]
                    #r_val = x_dots[l:r][-1][0]
                    
                    #u_val = y_dots[u:t][0][1]
                    t_val = y_dots[u:t][-1][1]
                    #print((r-l)*(t-u))
                    if ans > (r_val-l_val)*(t_val-u_val):
                        ans = (r_val-l_val)*(t_val-u_val)
                    else:
                        break
print(ans)


#y_dots = sorted(y_dots, key=lambda x: x[1])
#ans = INT_MAX

Submission status: Time Limit Exceeded

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

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

dots = XY[:]

import sys
INT_MAX = sys.maxsize

x_dots = [(x, y) for x, y in dots]
x_dots = sorted(x_dots)
y_dots = [(x, y) for x, y in dots]
y_dots = sorted(y_dots, key=lambda x: x[1])

ans = INT_MAX
for l in range(N):
    l_val = x_dots[l][0]
    for r in range(l+1, N+1):
        for u in range(N):
            u_val = y_dots[u][1]
            for t in range(u+1, N+1):
                xy_dots =  set(x_dots[l:r]) & set(y_dots[u:t])
                if len(xy_dots) >= K:
                    #print("---")
                    #print(l, r, x_dots[l:r])
                    #print(u, t, y_dots[u:t])
                    #print(x_dots[l:r])
                    #l_val = x_dots[l:r][0][0]
                    r_val = x_dots[l:r][-1][0]
                    
                    #u_val = y_dots[u:t][0][1]
                    t_val = y_dots[u:t][-1][1]
                    #print((r-l)*(t-u))
                    if ans > (r_val-l_val)*(t_val-u_val):
                        ans = (r_val-l_val)*(t_val-u_val)
                    else:
                        break
print(ans)


#y_dots = sorted(y_dots, key=lambda x: x[1])
#ans = INT_MAX

Submission status: Time Limit Exceeded

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

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

dots = XY[:]

import sys
INT_MAX = sys.maxsize

x_dots = [(x, y) for x, y in dots]
x_dots = sorted(x_dots)
y_dots = [(x, y) for x, y in dots]
y_dots = sorted(y_dots, key=lambda x: x[1])

ans = INT_MAX
for l in range(N):
    for r in range(l+1, N+1):
        for u in range(N):
            for t in range(u+1, N+1):
                xy_dots =  set(x_dots[l:r]) & set(y_dots[u:t])
                if len(xy_dots) >= K:
                    #print("---")
                    #print(l, r, x_dots[l:r])
                    #print(u, t, y_dots[u:t])
                    #print(x_dots[l:r])
                    l_val = x_dots[l:r][0][0]
                    r_val = x_dots[l:r][-1][0]
                    
                    u_val = y_dots[u:t][0][1]
                    t_val = y_dots[u:t][-1][1]
                    #print((r-l)*(t-u))
                    if ans > (r_val-l_val)*(t_val-u_val):
                        ans = (r_val-l_val)*(t_val-u_val)
                    else:
                        break
print(ans)


#y_dots = sorted(y_dots, key=lambda x: x[1])
#ans = INT_MAX

Submission status: Time Limit Exceeded

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

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

dots = XY[:]

import sys
INT_MAX = sys.maxsize

x_dots = [(x, y) for x, y in dots]
x_dots = sorted(x_dots)
y_dots = [(x, y) for x, y in dots]
y_dots = sorted(y_dots, key=lambda x: x[1])

ans = INT_MAX
for l in range(N):
    for r in range(l+1, N+1):
        for u in range(N):
            for t in range(u+1, N+1):
                xy_dots =  set(x_dots[l:r]) & set(y_dots[u:t])
                if len(xy_dots) >= K:
                    #print("---")
                    #print(l, r, x_dots[l:r])
                    #print(u, t, y_dots[u:t])
                    #print(x_dots[l:r])
                    l_val = x_dots[l:r][0][0]
                    r_val = x_dots[l:r][-1][0]
                    
                    u_val = y_dots[u:t][0][1]
                    t_val = y_dots[u:t][-1][1]
                    #print((r-l)*(t-u))
                    if ans > (r_val-l_val)*(t_val-u_val):
                        ans = (r_val-l_val)*(t_val-u_val)
print(ans)


#y_dots = sorted(y_dots, key=lambda x: x[1])
#ans = INT_MAX

Submission status: Time Limit Exceeded

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

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

dots = XY[:]

import sys
INT_MAX = sys.maxsize

x_dots = [(x, y) for x, y in dots]
x_dots = sorted(x_dots)
y_dots = [(x, y) for x, y in dots]
y_dots = sorted(y_dots, key=lambda x: x[1])

ans = INT_MAX
for l in range(N):
    for r in range(l+1, N+1):
        for u in range(N):
            for t in range(u+1, N+1):
                xy_dots =  set(x_dots[l:r]) & set(y_dots[u:t])
                if len(xy_dots) >= K:
                    #print("---")
                    #print(l, r, x_dots[l:r])
                    #print(u, t, y_dots[u:t])
                    #print(x_dots[l:r])
                    l_val = x_dots[l:r][0][0]
                    r_val = x_dots[l:r][-1][0]
                    
                    u_val = y_dots[u:t][0][1]
                    t_val = y_dots[u:t][-1][1]
                    #print((r-l)*(t-u))
                    ans = min(ans, (r_val-l_val)*(t_val-u_val))
print(ans)


#y_dots = sorted(y_dots, key=lambda x: x[1])
#ans = INT_MAX

Submission status: Time Limit Exceeded

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

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

if __name__ == '__main__':
    dots = XY[:]

    import sys
    INT_MAX = sys.maxsize

    x_dots = [(x, y) for x, y in dots]
    x_dots = sorted(x_dots)
    y_dots = [(x, y) for x, y in dots]
    y_dots = sorted(y_dots, key=lambda x: x[1])

    ans = INT_MAX
    for i in range(N):
        for j in range(i+1, N):
            sub_x_dots = set(x_dots[i:j+1])
            xl = x_dots[i:j+1][0][0]
            xr = x_dots[i:j+1][-1][0]
            for k in range(N):
                for l in range(k+1, N):
                    sub_y_dots = set(y_dots[k:l+1])
                    #print("----")
                    #print(x_dots[i:j+1])
                    #print(y_dots[k:l+1])
                    intersection = sub_x_dots & sub_y_dots
                    if len(intersection) >= K:
                        yl = y_dots[k:l+1][0][1]
                        yr = y_dots[k:l+1][-1][1]
                        area = (xl-xr) * (yl-yr)

                        ans = min(ans, area)
    print(ans)

Submission status: Time Limit Exceeded

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

XY = []
for _ in range(N):
    x, y = map(int, input().split())
    XY.append((x, y))
    
if __name__ == '__main__':
    dots = XY[:]

    import sys
    INT_MAX = sys.maxsize

    x_dots = [(x, y) for x, y in dots]
    x_dots = sorted(x_dots)
    y_dots = [(x, y) for x, y in dots]
    y_dots = sorted(y_dots, key=lambda x: x[1])

    ans = INT_MAX
    for i in range(N):
        for j in range(i+1, N):
            sub_x_dots = set(x_dots[i:j+1])
            xl = x_dots[i:j+1][0][0]
            xr = x_dots[i:j+1][-1][0]
            for k in range(N):
                for l in range(k+1, N):
                    sub_y_dots = set(y_dots[k:l+1])
                    #print("----")
                    #print(x_dots[i:j+1])
                    #print(y_dots[k:l+1])
                    intersection = sub_x_dots & sub_y_dots
                    if len(intersection) >= K:
                        yl = y_dots[k:l+1][0][1]
                        yr = y_dots[k:l+1][-1][1]
                        area = (xl-xr) * (yl-yr)

                        ans = min(ans, area)
    print(ans)

Submission status: Time Limit Exceeded

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

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

import sys
INT_MAX = sys.maxsize

x_dots = [(x, y) for x, y in dots]
x_dots = sorted(x_dots)
y_dots = [(x, y) for x, y in dots]
y_dots = sorted(y_dots, key=lambda x: x[1])

ans = INT_MAX
for i in range(N):
    for j in range(i+1, N):
        sub_x_dots = set(x_dots[i:j+1])
        xl = x_dots[i:j+1][0][0]
        xr = x_dots[i:j+1][-1][0]
        for k in range(N):
            for l in range(k+1, N):
                sub_y_dots = set(y_dots[k:l+1])
                #print("----")
                #print(x_dots[i:j+1])
                #print(y_dots[k:l+1])
                intersection = (sub_x_dots) & sub_y_dots
                if len(intersection) >= K:
                    yl = y_dots[k:l+1][0][1]
                    yr = y_dots[k:l+1][-1][1]
                    area = (xl-xr) * (yl-yr)
                    
                    ans = min(ans, area)
print(ans)

Submission status: Time Limit Exceeded

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

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

import sys
INT_MAX = sys.maxsize

x_dots = [(x, y) for x, y in dots]
x_dots = sorted(x_dots)
y_dots = [(y, x) for x, y in dots]
y_dots = sorted(y_dots)
y_dots = [(x, y) for y, x in y_dots]

ans = INT_MAX
for i in range(N):
    for j in range(i+1, N):
        sub_x_dots = set(x_dots[i:j+1])
        xl = x_dots[i:j+1][0][0]
        xr = x_dots[i:j+1][-1][0]
        for k in range(N):
            for l in range(k+1, N):
                sub_y_dots = set(y_dots[k:l+1])
                #print("----")
                #print(x_dots[i:j+1])
                #print(y_dots[k:l+1])
                intersection = (sub_x_dots) & sub_y_dots
                if len(intersection) >= K:
                    yl = y_dots[k:l+1][0][1]
                    yr = y_dots[k:l+1][-1][1]
                    area = (xl-xr) * (yl-yr)
                    
                    ans = min(ans, area)
print(ans)

Submission status: Time Limit Exceeded

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

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

import sys
INT_MAX = sys.maxsize

x_dots = [(x, y) for x, y in dots]
x_dots = sorted(x_dots)
y_dots = [(y, x) for x, y in dots]
y_dots = sorted(y_dots)
y_dots = [(x, y) for y, x in y_dots]

ans = INT_MAX
for i in range(N):
    for j in range(i+1, N):
        for k in range(N):
            for l in range(k+1, N):
                #print("----")
                #print(x_dots[i:j+1])
                #print(y_dots[k:l+1])
                intersection = (set(x_dots[i:j+1]) & set(y_dots[k:l+1]))
                if len(intersection) >= K:
                    xl = x_dots[i:j+1][0][0]
                    xr = x_dots[i:j+1][-1][0]
                    yl = y_dots[k:l+1][0][1]
                    yr = y_dots[k:l+1][-1][1]
                    area = (xl-xr) * (yl-yr)
                    
                    ans = min(ans, area)
print(ans)

Submission status: Time Limit Exceeded

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

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

dots = XY[:]

import sys
INT_MAX = sys.maxsize

x_dots = [(x, y) for x, y in dots]
x_dots = sorted(x_dots)
y_dots = [(y, x) for x, y in dots]
y_dots = sorted(y_dots)
y_dots = [(x, y) for y, x in y_dots]

ans = INT_MAX
for i in range(N):
    for j in range(i+1, N):
        for k in range(N):
            for l in range(k+1, N):
                #print("----")
                #print(x_dots[i:j+1])
                #print(y_dots[k:l+1])
                intersection = (set(x_dots[i:j+1]) & set(y_dots[k:l+1]))
                if len(intersection) >= K:
                    xl = x_dots[i:j+1][0][0]
                    xr = x_dots[i:j+1][-1][0]
                    yl = y_dots[k:l+1][0][1]
                    yr = y_dots[k:l+1][-1][1]
                    area = (xl-xr) * (yl-yr)
                    ans = min(ans, area)
print(ans)

Submission status: Time Limit Exceeded

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

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

list_x=list()
list_y=list()
list_z=list()

ans=float('inf')

for i in range(N):
  x,y=(int(val) for val in input().split())
  list_x.append(x)
  list_y.append(y)
  list_z.append((x,y))

list_x.sort()
list_y.sort()

for i in list_y:
  for j in list_y:
    for k in list_x:
      for l in list_x:
        cnt=0
        for m in range(len(list_z)):
          if l<=list_z[m][0]<=k and j<=list_z[m][1]<=i:
            cnt+=1
          if K <= cnt:
            tmp=(i-j)*(k-l)
            if tmp < ans:
              ans=tmp

print(ans)