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.

Solution (Python):






import sys
input = sys.stdin.readline

import math
from collections import deque
from fractions import gcd
from functools import lru_cache






MOD = 10**9+7
INF = float('inf')






def inputI(): return int(input().strip())
def inputS(): return input().strip()
def inputIL(): return list(map(int,input().split()))
def inputSL(): return list(map(str,input().split()))
def inputILs(n): return list(int(input()) for _ in range(n))
def inputSLs(n): return list(input().strip() for _ in range(n))
def inputILL(n): return [list(map(int, input().split())) for _ in range(n)]
def inputSLL(n): return [list(map(str, input().split())) for _ in range(n)]


def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])
    return arr


def lcm(a, b):
    return a * b // gcd (a, b)






N,K = inputIL()
P = inputILL(N)



xtic = list(set([xy[0] for xy in P]))
ytic = list(set([xy[1] for xy in P]))
xtic.sort()
ytic.sort()


o_list = []
for x in xtic:
  for y in ytic:
    o_list.append([x,y])
ans = INF

for p in o_list:
  x0,y0 = p
  for xmax in xtic:
    if xmax < x0:
      continue
    else:
      tempP = []
      for q in P:
        if x0 <= q[0] <= xmax and y0 <= q[1]:
          tempP.append(q)
      if len(tempP) < K:
        continue
      tempP = sorted(tempP, key=lambda x:x[1])
      ans = min(ans,(xmax-x0)*(tempP[K-1][1]-y0))
      
      
      
      

      
print(ans)

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

x = sorted(v for v, _ in X)
y = sorted(v for _, v in X)
ans = 10 ** 20
for i in range(N - 1):
    for j in range(i + 1, N):
        for k in range(N - 1):
            for l in range(k + 1, N):
                x1 = x[i]
                x2 = x[j]
                y1 = y[k]
                y2 = y[l]
                num = 0
                for n in range(N):
                    if x1 <= X[n][0] <= x2 and y1 <= X[n][1] <= y2:
                        num += 1
                if num >= K:
                    ans = min(ans, (x2 - x1) * (y2 - y1))

print(ans)

Solution (Python):
from copy import deepcopy
N, K = map(int, input().split())
X, Y = [], []
for _ in range(N):
    x, y = map(int, input().split())
    X.append(x)
    Y.append(y)
PX, PY = deepcopy(X), deepcopy(Y)
X.sort()
Y.sort()

ans = (X[-1] - X[0]) * (Y[-1] - Y[0])

for xi in range(N - 1):
    for xj in range(xi + 1, N):
        for yi in range(N - 1):
            for yj in range(yi + 1, N):
                num = 0
                lx, rx = X[xi], X[xj]
                by, uy = Y[yi], Y[yj]

                for i in range(N):
                    if lx <= PX[i] and PX[i] <= rx and by <= PY[i] and PY[i] <= uy:
                        num += 1

                if num >= K:
                    ans = min(ans, (rx - lx) * (uy - by))
print(ans)

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

xlist,ylist,xylist=[],[],[]
xyset=set()
xydic={}
yxdic={}
for i in range(N):
  x,y=map(int,input().split())
  xlist.append(x)
  ylist.append(y)
  xylist.append((x,y))
  xyset.add((x,y))
  xydic[x]=y
  yxdic[y]=x

xy_prod_list=[]
for x in xlist:
  for y in ylist:
    xy_prod_list.append((x,y))
xy_prod_list.sort()


num_ld_dic={}
for xx,yy in xy_prod_list:
  num_ld=0
  for x,y in xylist:
    if x<=xx and y<=yy:
      num_ld+=1
  num_ld_dic[(xx,yy)]=num_ld


answer=float("inf")
for i in range(len(xy_prod_list)):
  x1,y1=xy_prod_list[i]
  for j in range(len(xy_prod_list)):
    x2,y2=xy_prod_list[j]
    if x1>=x2 or y1>=y2:
      continue
    
    area=(x2-x1)*(y2-y1)
    if area>answer:
      continue
      
    num_point=num_ld_dic[(x2,y2)]-num_ld_dic[(x1,y2)]-num_ld_dic[(x2,y1)]+num_ld_dic[(x1,y1)]
    if (x1,y1) in xyset:  
      num_point+=1
    else:
      xx=yxdic[y1]
      if x1<=xx<=x2:
        num_point+=1
      yy=xydic[x1]
      if y1<=yy<=y2:
        num_point+=1
      
    if num_point>=K:
      
      answer=min(answer,area)
    
print(answer)

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

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

ans = float('INF')

for left in range(N):
    for right in range(N):
        for top in range(N):
            for bottom in range(N):
                if X[right]-X[left] <= 0:
                    continue
                if Y[top]-Y[bottom] <= 0:
                    continue
                cnt = 0
                for i in range(N):
                    if X[left] <= X[i] <= X[right] and Y[bottom] <= Y[i] <= Y[top]:
                        cnt += 1
                if cnt >= K:
                    ans = min(ans, (X[right]-X[left])*(Y[top]-Y[bottom]))

print(ans)

Solution (Python):
import sys
input = sys.stdin.readline

n, k = [int(x) for x in input().split()]
xy = []
for _ in range(n):
    xy.append([int(x) for x in input().split()])
ans = float('inf')
xy.sort()
for i in range(n):
    left = xy[i][0]
    y = [xy[i][1]]
    for j in range(i + 1, n):
        right = xy[j][0]
        y.append(xy[j][1])
        y.sort()
        if j - i + 1 < k:
            continue
        for p in range(len(y)):
            bottom = y[p]
            for q in range(len(y)):
                if q - p + 1 < k:
                    continue
                top = y[q]
                ans = min(ans, (right - left)*(top - bottom))
print(ans)

Solution (Python):
n,k=map(int,input().split())
li=sorted([list(map(int,input().split())) for i in range(n)],key=lambda x:(x[1],x[0]))
ans=float("INF")

for i in range(n):
    for j in range(i+1,n):
        ux,lx=max(li[i][0],li[j][0]),min(li[i][0],li[j][0])
        l,r=0,0
        cnt=int(lx<=li[r][0]<=ux)

        while True:

            while r<n-1 and cnt<k:
                r+=1
                cnt+=int(lx<=li[r][0]<=ux)
            if cnt<k or not(0<=r<=n-1) or not(0<=l<=n-1) or r<=l :break
            if ans>(ux-lx)*(li[r][1]-li[l][1]):
                ans=(ux-lx)*(li[r][1]-li[l][1])

            cnt-=int(lx<=li[l][0]<=ux)
            l+=1
print(ans)

Solution (Python):
from itertools import combinations

n,k = map(int,input().split())
xy = [list(map(int,input().split())) + [i] for i in range(n)]
x_order = sorted(xy)
y_order = sorted(xy,key = lambda x:x[1])

pos = [[None]*2 for _ in range(n)]

for i,(x,y,j) in enumerate(x_order):
    pos[j][0] = i
for i,(x,y,j) in enumerate(y_order):
    pos[j][1] = i

count = [[0] * (n+1) for _ in range(n+1)]

for x,y in pos:
    count[y+1][x+1] += 1

for i in range(n+1):
    for j in range(1,n+1):
        count[i][j] += count[i][j-1]

for i in range(n+1):
    for j in range(1,n+1):
        count[j][i] += count[j-1][i]

ans = float('inf')
for x1,x2 in combinations(range(1,n+1),2):
    for y1,y2 in combinations(range(1,n+1),2):
        if count[y2][x2] - count[y2][x1-1] - count[y1-1][x2] + count[y1-1][x1-1] >=k:
            S = (x_order[x2-1][0] - x_order[x1-1][0]) * (y_order[y2-1][1] - y_order[y1-1][1])
            ans = min(ans, S)
print(ans)

Solution (Python):
import itertools

def main():
  n,k = map(int, input().split())
  xy = [tuple(map(int, input().split())) for i in range(n)]
  INF = 10 ** 20
  ans = INF
  for i in itertools.combinations(xy,2):
    max_x,min_x = -INF,INF
    for x,Y in i:
      max_x = max(max_x,x)
      min_x = min(min_x,x)
    for j in itertools.combinations(xy,2):
      max_y,min_y = -INF,INF
      for X,y in j:
        max_y = max(max_y,y)
        min_y = min(min_y,y)
      inrec = 0
      for xi,yi in xy:
        if  (min_x <= xi <= max_x) and (min_y <= yi <= max_y):
          inrec += 1
      if (inrec >= k):
        ans = min(ans,(max_x-min_x)*(max_y-min_y))
  print(ans)
  
if __name__ == '__main__':
  main()

Solution (Python):
import sys
stdin = sys.stdin
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()
sys.setrecursionlimit(10**6)

n,k = na()
xy = []

for i in range(n):
    x,y = na()
    xy.append((x,y))

xy.sort()
ans = 10000000000000000000000000000

for i in range(n):
    for j in range(i+1, n):
        x = xy[j][0] - xy[i][0]
        yy = sorted(xy[i:j+1], key=lambda x:x[1])
        for u in range(len(yy)-k+1):
            y = yy[u+k-1][1] - yy[u][1]
            ans = min(ans, y*x)
            
print(ans)

Solution (Python):
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())

Xs = sorted(X)
Ys = sorted(Y)
XY = sorted(list(zip(X,Y)))
ans = 1e100
for i in range(n-k+1):
    for j in range(i+k-1,n):
        w = Xs[j] - Xs[i]
        XYs = sorted(XY[i:j+1],key = lambda x:x[1])
        h = 1e100
        for l in range(len(XYs) - k + 1):
            h = min(h, XYs[l + k - 1][1] - XYs[l][1])
        ans = min(ans , h*w)
print(ans)

Solution (Python):


import io
import math
import scipy.sparse
import numpy

nim, mike = map(int, input().split())
array = [list(map(int, input().split())) for i in range(nim)]

answer = 10**100
sortx = sorted(array, key = lambda x: x[0])
for a, pt1 in enumerate(sortx[:nim-mike+1]):
    for b, pt2 in enumerate(sortx[a+mike-1:]):
        
        sorty = sorted(sortx[a:a+mike+b], key = lambda x: x[1])
        sorty_len = len(sorty)
        for c, pt3 in enumerate(sorty[:sorty_len-mike+1]):
            
            pt4 = sorty[c+mike-1]
            
            if pt3[1] <= pt1[1] and pt3[1] <= pt2[1] and pt4[1] >= pt1[1] and pt4[1] >= pt2[1]:
                answer = min(answer, (pt2[0] - pt1[0]) * (pt4[1] - pt3[1]))
print(answer)

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

MAX = 10**9
MIN = -1 * MAX
def check(x_r, x_l, y_t, y_b):
    tl = [MIN, MAX]
    br = [MAX, MIN]
    if x_r == x_l or y_t == y_b:
        return False, -1

    tl[0] = max(tl[0], xy[x_l][0])
    tl[1] = min(tl[1], xy[y_t][1])
    br[0] = min(br[0], xy[x_r][0])
    br[1] = max(br[1], xy[y_b][1])

    
    cnt = 0
    for i in range(n):
        if tl[0] <= xy[i][0] <= br[0] and br[1] <= xy[i][1] <= tl[1]:
            cnt += 1
    if cnt < k:
        return False, -1
    area = (br[0] - tl[0]) * (tl[1] - br[1])
    return True, area

INF = 10**20
ans = INF
for a in range(n):
    for b in range(n):
        if a == b:
            continue
        if xy[a][0] < xy[b][0]:
            continue
        for c in range(n):
            for d in range(n):
                if c == d:
                    continue
                if xy[c][1] < xy[d][1]:
                    continue
                f, area = check(a, b, c, d)
                if f:
                    ans = min(ans, area)
print(ans)

Solution (Python):
n,K=map(int,input().split())
S=[[0 for i in range(n+1)] for j in range(n+1)]
p=[list(map(int,input().split())) for i in range(n)]
p.sort(key=lambda x:x[1])
for i in range(n):
    p[i].append(i)
p.sort()
y=[0]*n
for i in range(n):
    y[i]=p[i][2]
for i in range(n):
    S[i+1][y[i]+1]=1
X=[p[i][0] for i in range(n)]
Y=[p[i][1] for i in range(n)]
X.sort();Y.sort()
for i in range(1,n+1):
    for j in range(1,n+1):
        S[i][j]=S[i][j]+S[i][j-1]+S[i-1][j]-S[i-1][j-1]
ans=10**20
for i in range(n):
    for j in range(n):
        for k in range(i+1,n+1):
            for l in range(j+1,n+1):
                if S[k][l]-S[k][j]-S[i][l]+S[i][j]>=K:
                    
                    if ans > (X[k-1]-X[i])*(Y[l-1]-Y[j]):
                        ans = (X[k-1]-X[i])*(Y[l-1]-Y[j])
                
print(ans)

Solution (Python):
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 = float('inf')
sx = sorted(x)
sy = sorted(y)
for xi in range(N):
    for xj in range(xi+1,N):
        for yi in range(N):
            for yj in range(yi+1,N):
                lx = sx[xi]
                rx = sx[xj]
                by = sy[yi]
                uy = sy[yj]
                cnt = 0
                for i in range(N):
                    if lx <= x[i] <= rx and by <= y[i] <= uy:
                        cnt += 1
                if cnt >= K:
                    area = (rx-lx)*(uy-by)
                    ans = min(ans,area)
print(ans)

Solution (Python):
import sys
from collections import *
import heapq
import math
import bisect
import copy
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

n,k=map(int,input().split())
xy=[list(map(int,input().split())) for i in range(n)]
ru=[[0]*(n+1) for i in range(n+1)]
lst=sorted(xy)
lst2=sorted(xy,key=lambda x: x[1])

for i in range(n):
    for j in range(n):
        flag=0
        for l in range(n):
            if xy[l]==[lst[i][0],lst2[j][1]]:
                flag=1
        if flag:
            ru[i+1][j+1]=1
        ru[i+1][j+1]+=ru[i+1][j]+ru[i][j+1]-ru[i][j]

xdic=defaultdict(int)
ydic=defaultdict(int)
for i in range(n):
    xdic[lst[i][0]]=i+1
    ydic[lst2[i][1]]=i+1


lst=[0]*n
lst2=[0]*n
for i in range(n):
    x,y=xy[i]
    lst[i],lst2[i]=x,y
lst,lst2=list(permutations(lst,2)),list(permutations(lst2,2))
ans=float('inf')
for i in range(len(lst)):
    xl,xr=min(lst[i]),max(lst[i])
    for j in range(len(lst2)):
        yl,yr=min(lst2[j]),max(lst2[j])
        
        if ru[xdic[xr]][ydic[yr]]-ru[xdic[xr]][ydic[yl]-1]-ru[xdic[xl]-1][ydic[yr]]+ru[xdic[xl]-1][ydic[yl]-1] >=k:
            ans=min(ans,(xr-xl)*(yr-yl))
print(ans)

Solution (Python):
from itertools import combinations
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

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

xc = list(combinations(x,2))
yc = list(combinations(y,2))
ans = 4*10**18

for yy in yc:
    u = max(yy)
    d = min(yy)
    for xx in xc:
        r = max(xx)
        l = min(xx)
        count = 0
        for i in range(n):
            if l <= x[i] <=r and d <= y[i] <=u: count += 1
        if count >= k:
            ans = min(ans, (u-d)*(r-l))

print(ans)

Solution (Python):

import itertools as it

from functools import *
import sys
sys.setrecursionlimit(100000)
input = sys.stdin.readline


def acinput():
    return list(map(int, input().split(" ")))


def II():
    return int(input())



N, K = acinput()


ary = [acinput() for i in range(N)]
x = list(map(lambda x: x[0], sorted(ary, key=lambda s: s[0])))
y = list(map(lambda x: x[1], sorted(ary, key=lambda x: x[1])))





res = 10**20
for sy in it.combinations(y, 2):
    
    for sx in it.combinations(x, 2):
        
        
        count = 0
        for sa in ary:
            
            if sy[0] <= sa[1] and sa[1] <= sy[1]:
                if sx[0] <= sa[0] and sa[0] <= sx[1]:
                    count += 1

        
        if count >= K:
            
            
            dx=sx[1]-sx[0]
            dy=sy[1]-sy[0]
            
            res = min(res, dx*dy)
            

print(res)

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    
    from itertools import combinations, permutations, accumulate, groupby
    
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    

    
    

    n,k = map(int, input().split())
    xy = [list(map(int, input().split())) for _ in range(n)]
    x = sorted(xy, key=lambda a: a[0])
    y = sorted(xy, key=lambda a: a[1])

    res = 10**20
    for l in range(n):
        for r in range(l+1, n):
            for b in range(n):
                for t in range(b+1, n):
                    cnt = 0
                    for vx, vy in x[l:r+1]:
                        if y[b][1] <= vy <= y[t][1]:
                            cnt += 1
                        if cnt >= k:
                            res = min(res, (x[r][0]-x[l][0])*(y[t][1]-y[b][1]))
                            break
    print(res)

if __name__ == '__main__':
    main()

Solution (Python):
import itertools

N, K = map(int, input().split())
P = [tuple(map(int, input().split())) for _ in range(N)]

X = sorted([x for x, _ in P])
Y = sorted([y for _, y in P])
dict_x = {v: k + 1 for k, v in enumerate(X)}
dict_y = {v: k + 1 for k, v in enumerate(Y)}

table = [[0] * (N + 1) for _ in range(N + 1)]
for x, y in P:
    table[dict_y[y]][dict_x[x]] = 1

for x in range(N + 1):
    for y in range(N):
        table[y + 1][x] += table[y][x]
for y in range(N + 1):
    for x in range(N):
        table[y][x + 1] += table[y][x]

ans = float('inf')
for x1, x2 in itertools.combinations(range(N), 2):
    for y1, y2 in itertools.combinations(range(N), 2):
        if table[y2 + 1][x2 + 1] - table[y2 + 1][x1] - table[y1][x2 + 1] + table[y1][x1] >= K:
            ans = min(ans, (X[x2] - X[x1]) * (Y[y2] - Y[y1]))
print(ans)

Solution (Python):
n,k= map(int,input().split())
grid=[]
gridx=set()
gridy=set()
for i in range(n):
    x,y= map(int,input().split())
    grid.append((x,y))
    gridx.add(x)
    gridy.add(y)
gridxl = sorted(gridx)
xlen = len(gridxl)
gridyl = sorted(gridy)
ylen = len(gridyl)
atable = [[0 for _ in range(ylen+1)] for _ in range(xlen+1)]
for i in range(n):
    (px,py) = grid[i]
    xid = gridxl.index(px)
    yid = gridyl.index(py)
    atable[yid+1][xid+1]=1
for i in range(1,ylen+1):
    for j in range(1,xlen+1):atable[i][j]+=atable[i][j-1]
for j in range(1,xlen+1):
    for i in range(1,ylen+1):atable[i][j]+=atable[i-1][j]
gmin = 99999999999999999999
for x1 in range(1,xlen):
    for x2 in range(x1,xlen+1):
        for y1 in range(1,ylen):
            for y2 in range(y1,ylen+1):
                a = atable[y2][x2]
                b = atable[y1-1][x2]
                c = atable[y2][x1-1]
                d = atable[y1-1][x1-1]
                rui = a - b - c + d
                if rui>=k:
                    r = (gridxl[x2-1]-gridxl[x1-1])*(gridyl[y2-1]-gridyl[y1-1])
                    if gmin>r:
                        gmin = min(gmin,r)                  
print(gmin)

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

xy=sorted(xy, key=lambda x:x[0])


lst=[]
for left in range(0, N-K+1):
    for right in range(left+K-1,N):
        
        W = xy[right][0] - xy[left][0]
        
        temp=sorted(xy[left:right+1], key=lambda x:x[1])
        
        
        for bottom in range(0, right-left+1 - K+1):
            
            H = temp[bottom+K-1][1] - temp[bottom][1]
            
            lst.append(H * W)

print(min(lst))

Solution (Python):
n,k=map(int,input().split())
x=[0]*n
y=[0]*n
a=[]
for i in range(n):
  x[i],y[i]=map(int,input().split())
  a.append((x[i],y[i]))
ans=4*(10**18)
x.sort()
y.sort()
for i in range(n-1):
  for j in range(i+1,n):
    for l in range(n-1):
      for m in range(l+1,n):
        L=x[i]
        R=x[j]
        D=y[l]
        U=y[m]
        if L==R or U==D:
          continue
        cnt=0
        for s in a:
          if L<=s[0]<=R and D<=s[1]<=U:
            cnt+=1
        if cnt>=k:
          ans=min(ans,(R-L)*(U-D))
print(ans)

Solution (Python):

n, k = map(int, input().split())
xy = [tuple(map(int, input().split())) for _ in range(n)]
ans = 10 ** 50
xy.sort()
for l in range(0, n):
    for r in range(l+k-1, n):
        y = [xy[i][1] for i in range(l, r+1)]
        y.sort()
        h = 10 ** 50
        for i in range(len(y)-k+1):
            h = min(h, y[i+k-1] - y[i])
        ans = min(ans, h * (xy[r][0] - xy[l][0]))
print(ans)

Solution (Python):

n,k=map(int,input().split())
x=[0]*n
y=[0]*n
a=[]
for i in range(n):
  x[i],y[i]=map(int,input().split())
  a.append((x[i],y[i]))
ans=4*(10**18)
x.sort()
y.sort()
for i in range(n-1):
  for j in range(i+1,n):
    for l in range(n-1):
      for m in range(l+1,n):
        L=x[i]
        R=x[j]
        D=y[l]
        U=y[m]
        if L==R or U==D:
          continue
        cnt=0
        for s in a:
          if L<=s[0]<=R and D<=s[1]<=U:
            cnt+=1
        if cnt>=k:
          ans=min(ans,(R-L)*(U-D))
print(ans)

Solution (Python):
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n,k = inpl()
xary = []; yary = []
a = []
for i in range(n):
    x,y = inpl()
    xary.append(x)
    yary.append(y)
    a.append((x,y))
xary.sort(); yary.sort()
res = INF
for xi in range(n-1):
    for xj in range(xi+1,n):
        for yi in range(n-1):
            for yj in range(yi+1,n):
                cnt = 0
                l = xary[xi]; r = xary[xj]
                d = yary[yi]; u = yary[yj]
                
                for i in range(n):
                    x,y = a[i]
                    if l<=x<=r and d<=y<=u:
                        cnt += 1
                if cnt >= k:
                    res = min(res, (r-l)*(u-d))
print(res)

Solution (Python):
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

def main():
    n,k = inpl()
    xary = []; yary = []
    a = []
    x_append = xary.append
    y_append = yary.append
    a_append = a.append
    for i in range(n):
        x,y = inpl()
        xary.append(x)
        yary.append(y)
        a.append((x,y))
    xary.sort(); yary.sort()
    res = INF
    for xi in range(n-1):
        for xj in range(xi+1,n):
            for yi in range(n-1):
                for yj in range(yi+1,n):
                    cnt = 0
                    l = xary[xi]; r = xary[xj]
                    d = yary[yi]; u = yary[yj]
                    
                    for i in range(n):
                        x,y = a[i]
                        if l<=x<=r and d<=y<=u:
                            cnt += 1
                    if cnt >= k:
                        res = min(res, (r-l)*(u-d))
    print(res)
if __name__ == "__main__":
    main()

Solution (Python):
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

def main():
    n,k = inpl()
    xary = []; yary = []
    a = []
    x_append = xary.append
    y_append = yary.append
    a_append = a.append
    for i in range(n):
        x,y = inpl()
        xary += [x]
        yary += [y]
        a += [[x,y]]
    xary.sort(); yary.sort()
    res = INF
    for xi in range(n-1):
        for xj in range(xi+1,n):
            for yi in range(n-1):
                for yj in range(yi+1,n):
                    cnt = 0
                    l = xary[xi]; r = xary[xj]
                    d = yary[yi]; u = yary[yj]
                    
                    for i in range(n):
                        x,y = a[i]
                        if l<=x<=r and d<=y<=u:
                            cnt += 1
                    if cnt >= k:
                        res = min(res, (r-l)*(u-d))
    print(res)
if __name__ == "__main__":
    main()

Solution (Python):
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

def main():
    n,k = inpl()
    xary = []; yary = []
    a = []
    x_append = xary.append
    y_append = yary.append
    a_append = a.append
    for i in range(n):
        x,y = inpl()
        x_append(x)
        y_append(y)
        a_append((x,y))
    xary.sort(); yary.sort()
    res = INF
    for xi in range(n-1):
        for xj in range(xi+1,n):
            for yi in range(n-1):
                for yj in range(yi+1,n):
                    cnt = 0
                    l = xary[xi]; r = xary[xj]
                    d = yary[yi]; u = yary[yj]
                    
                    for i in range(n):
                        x,y = a[i]
                        if l<=x<=r and d<=y<=u:
                            cnt += 1
                    if cnt >= k:
                        res = min(res, (r-l)*(u-d))
    print(res)
if __name__ == "__main__":
    main()

Solution (Python):
from itertools import combinations
N, K = map(int, input().split())
dots = sorted([tuple(map(int, input().split())) for _ in range(N)], key=lambda x: x[0])

ans = 10 ** 37
for i in range(N):
    for j in range(i+K-1, N):
        width = dots[j][0] - dots[i][0]
        y = sorted([l for _, l in dots[i:j+1]])
        for a, b in zip(y, y[K-1:]):
            height = b - a
            ans = min(ans, width*height)

print(ans)

Solution (Python):
import sys
input = sys.stdin.readline


def main():
    n, k = map(int, input().split())
    X, Y = [], []
    for _ in range(n):
        x, y = map(int, input().split())
        X.append(x)
        Y.append(y)
    X_s = sorted(X)
    Y_s = sorted(Y)
    f_inf = float("inf")
    res = f_inf

    for x1 in range(n):
        for x2 in range(x1 + 1, n):
            for y1 in range(n):
                for y2 in range(y1 + 1, n):
                    lx, rx = X_s[x1], X_s[x2]
                    by, uy = Y_s[y1], Y_s[y2]
                    cnt = 0
                    for i in range(n):
                        if lx <= X[i] <= rx and by <= Y[i] <= uy:
                            cnt += 1
                    if cnt >= k:
                        res = min(res, (rx - lx) * (uy - by))
    print(res)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.readline


def main():
    n, k = map(int, input().split())
    X, Y = [], []
    for _ in range(n):
        x, y = map(int, input().split())
        X.append(x)
        Y.append(y)
    X_s = sorted(X)
    Y_s = sorted(Y)
    f_inf = float("inf")
    res = f_inf

    for x1 in range(n):
        for x2 in range(x1 + 1, n):
            for y1 in range(n):
                for y2 in range(y1 + 1, n):
                    lx, rx = X_s[x1], X_s[x2]
                    by, uy = Y_s[y1], Y_s[y2]
                    cnt = 0
                    for i in range(n):
                        if lx <= X[i] <= rx and by <= Y[i] <= uy:
                            cnt += 1
                    if cnt >= k:
                        res = min(res, abs(rx - lx) * abs(uy - by))
    print(res)


if __name__ == '__main__':
    main()

Solution (Python):
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions
from decimal import Decimal
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n,K = inpl()
a = [inpl() for _ in range(n)]
res = INF
a.sort(key=lambda x:x[0])
for j in range(n-1):
    for k in range(j+1,n):
        l = a[j][0]
        r = a[k][0]
        b = [a[j],a[k]]
        cnt = 2
        for _ in range(n):
            if _ == j or _ == k:
                continue
            if l < a[_][0] < r:
                cnt += 1
                b += [a[_]]
        if cnt < K: continue
        b.sort(key=lambda x:x[1])
        for _ in range(cnt-K+1):
            u = max(x[1] for x in b[_:_+K])
            d = min(x[1] for x in b[_:_+K])
            res = min(res, (r-l)*(u-d))
            
print(res)

Solution (Python):
from itertools import accumulate
def compress(arr):
    *XS, = set(arr)
    XS.sort()
    return {e: i for i, e in enumerate(XS)}
n, k = map(int, input().split())
XY = [list(map(int, input().split())) for _ in range(n)]
X, Y = zip(*XY)
comp_X = compress(X)
comp_Y = compress(Y)
len_X = len(comp_X)
len_Y = len(comp_Y)
rev_X = {j:i for i, j in comp_X.items()}
rev_Y = {j:i for i, j in comp_Y.items()}
C = [[0]*(len_Y+1) for _ in range(len_X+1)]
for x, y in XY:
  C[comp_X[x]+1][comp_Y[y]+1] = 1
for i in range(1, len_X+1):
  C[i] = list(accumulate(C[i]))
C = list(zip(*C))
for j in range(1, len_Y+1):
  C[j] = list(accumulate(C[j]))
C = list(zip(*C))
def test(x1, x2, y1, y2):
  cnt = C[x2][y2] - C[x1][y2] - C[x2][y1] + C[x1][y1]
  if cnt >= k:
    temp = (rev_X[x2-1] - rev_X[x1]) * (rev_Y[y2-1] - rev_Y[y1])
    return temp
  return float("inf")
ans = float("inf")
for x1 in range(len_X):
  for x2 in range(x1+1, len_X+1):
    for y1 in range(len_Y):
      for y2 in range(y1+1, len_Y+1):
        ans = min(ans, test(x1, x2, y1, y2))
print(ans)