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):
N, K = map(int, input().split())
S = []
T = []
A = []
for i in range(N):
    x, y = map(int, input().split())
    S.append(x)
    T.append(y)
    A.append([x, y])

S.sort()
T.sort()
ans = float("inf")
for i in range(N):
    for j in range(i+1, N):
        for k in range(N):
            for l in range(k+1, N):
                c = 0
                for x, y in A:
                    if S[i] <= x <= S[j]:
                        if T[k] <= y <= T[l]:
                            c += 1
                if c >= K:
                    ans = min(ans, (S[j] - S[i])*(T[l] - T[k]))
print(ans)

Solution (Python):
N, K = list(map(int, input().split()))
X = [0]*N
Y = [0]*N
for i in range(N):
    X[i], Y[i] = list(map(int, input().split()))
YS = [[Y[i], i] for i in range(N)]
YS.sort()


ans = 10**20
for i in range(N):
    for j in range(i+1, N):
        l, r = X[i], X[j]
        if l > r:
            l, r = r, l
        u = 0
        d = 0
        A = [(l <= X[k] <= r) for k in range(N)]
        
        ct = A[YS[0][1]]
        for d in range(N):
            while ct < K:
                u += 1
                if u >= N:
                    break
                ct += A[YS[u][1]]
                
            else:
                S = (r-l)*(YS[u][0]-YS[d][0])
                ans = min(ans, S)
                ct -= A[YS[d][1]]
print(ans)

Solution (Python):
n, k = map(int, input().split())
xv, yv = [], []
xy = []
for _ in range(n):
    x, y = map(int, input().split())
    xv.append(x)
    yv.append(y)
    xy.append((x, y))

xv = sorted(xv)
yv = sorted(yv)
ans = (xv[n-1] - xv[0]) * (yv[n-1] - yv[0])
for l in range(n):
    lx = xv[l]
    for r in range(l+1, n):
        rx = xv[r]
        for b in range(n):
            by = yv[b]
            for t in range(b+1, n):
                ty = yv[t]
                cnt = 0
                for x, y in xy:
                    if lx <= x <= rx and by <= y <= ty:
                        cnt += 1
                if cnt >= k:
                    ans = min(ans, (rx - lx)*(ty - by))
print(ans)

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce, lru_cache
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def TUPLE(): return tuple(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 





N, K = MAP()
xy = [LIST() for _ in range(N)]
ans = INF

xy.sort()
for l in range(N-K+1):  
	for r in range(l+K, N+1):  
		y = sorted(xy[l:r], key = lambda x: x[1]) 
		for i in range(r-l-K+1):
			sq = (xy[r-1][0] - xy[l][0])*(y[i+K-1][1] - y[i][1])
			ans = min(ans, sq)
print(ans)

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

P = [[int(_) for _ in input().split()] for n in range(N)]

X = []
Y = []
for n in range(N):
    x, y = P[n]
    X.append(x)
    Y.append(y)
X.sort()
Y.sort()

ans = 10 ** 20
for xi in range(N):
    for xj in range(xi+1, N):
        for yi in range(N):
            for yj in range(yi+1, N):
                x1, y1 = X[xi], Y[yi]
                x2, y2 = X[xj], Y[yj]
                c = 0
                for v in range(N):
                    x, y = P[v]
                    if x1 <= x <= x2 and y1 <= y <= y2:
                        c += 1
                if c >= K:
                    ans = min(ans, (x2-x1) * (y2-y1))
print(ans)

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def TUPLE(): return tuple(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 

from decimal import *



N, K = MAP()
xy = [LIST() for _ in range(N)]
x, y = zip(*xy)

x = sorted(x)
y = sorted(y)

ans = INF
for ax, bx in combinations(x, 2):
	for ay, by in combinations(y, 2):
		cnt = 0
		for cx, cy in xy:
			if ax <= cx <= bx and ay <= cy <= by:
				cnt += 1
		if K <= cnt:
			ans = min(ans, (bx-ax)*(by-ay))

print(ans)

Solution (Python):
from itertools import combinations, product
import bisect as bs

def tuple_int(iterable):
    return tuple(map(int, iterable.split()))

def S_with_K_plots(plots, K):
    result = []
    X, Y = sorted([x for x,y in plots]), sorted([y for x,y in plots])
    for xinf, xsup in combinations(X,2):
        for yinf in Y:
            ysup = [y for x,y in plots if xinf<=x<=xsup and y >= yinf]
            if len(ysup) < K: continue
            ysup.sort()
            result.append((xsup-xinf)*(ysup[K-1]-yinf))
    return result

if __name__ == '__main__':
    with open(0) as f:
        N, K = map(int, f.readline().split())
        plots = list(map(tuple_int, f.readlines()))
    print(min(S_with_K_plots(plots, K)))

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def TUPLE(): return tuple(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 

from decimal import *



N, K = MAP()
xy = [LIST() for _ in range(N)]

ans = INF
for (ax, ay), (bx, by) in combinations(xy, 2):
	edge_left = min(ax, bx)
	edge_right = max(ax, bx)
	edge_top = max(ay, by)
	edge_bottom = min(ay, by)
	cnt = 0
	for cx, cy in xy:
		if cx == ax or cx == bx:
			continue
		elif edge_left <= cx <= edge_right and edge_bottom <= cy <= edge_top:
			cnt += 1
	if K <= cnt+2:
		ans = min((edge_right-edge_left)*(edge_top-edge_bottom), ans)

for (ax, ay), (bx, by), (cx, cy) in combinations(xy, 3):
	edge_left = min(ax, bx, cx)
	edge_right = max(ax, bx, cx)
	edge_top = max(ay, by, cy)
	edge_bottom = min(ay, by, cy)
	cnt = 0
	for dx, dy in xy:
		if dx == ax or dx == bx or dx == cx:
			continue
		elif edge_left <= dx <= edge_right and edge_bottom <= dy <= edge_top:
			cnt += 1
	if K <= cnt+3:
		ans = min((edge_right-edge_left)*(edge_top-edge_bottom), ans)

for (ax, ay), (bx, by), (cx, cy), (dx, dy) in combinations(xy, 4):
	edge_left = min(ax, bx, cx, dx)
	edge_right = max(ax, bx, cx, dx)
	edge_top = max(ay, by, cy, dy)
	edge_bottom = min(ay, by, cy, dy)
	cnt = 0
	for ex, ey in xy:
		if ex == ax or ex == bx or ex == cx or ex == dx:
			continue
		elif edge_left <= ex <= edge_right and edge_bottom <= ey <= edge_top:
			cnt += 1
	if K <= cnt+4:
		ans = min((edge_right-edge_left)*(edge_top-edge_bottom), ans)

print(ans)

Solution (Python):
import sys
from collections import deque
from functools import lru_cache
import bisect
import copy
import heapq
import itertools
import math
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


def main():
    N, K = read_values()
    P = [tuple(read_values()) for _ in range(N)]

    X = sorted([x for x, _ in P])
    Y = sorted([y for _, y in P])

    res = 10 ** 20
    for xl in range(N):
        for xr in range(xl + 1, N):
            for yl in range(N):
                for yr in range(yl + 1, N):
                    k = sum(X[xl] <= x <= X[xr] and Y[yl] <= y <= Y[yr] for x, y in P)
                    
                    if K <= k:
                        res = min(res, (X[xr] - X[xl]) * (Y[yr] - Y[yl]))
    print(res)



if __name__ == "__main__":
    main()

Solution (Python):


def main():
    N,K = map(int,input().split())
    que = []
    que_x =  []
    que_y = []
    for i in range(N):
        x,y = map(int,input().split())
        que_x.append(x)
        que_y.append(y)
        que.append((x,y))
    que_x.sort()
    que_y.sort()
    ans = 10**100
    for i in range(N):
        for j in range(i,N):
            for _i in range(N):
                for _j in range(_i,N):
                    h,w = que_x[j]-que_x[i],que_y[_j] -que_y[_i]
                    cnt = 0
                    for x,y in que:
                        if que_x[i]<=x<=que_x[j] and que_y[_i]<=y<=que_y[_j]:
                            cnt += 1
                    if cnt >=K:
                        ans = min(ans,h*w)
    print(ans)
    return




if __name__ == "__main__":
    main()

Solution (Python):
def solve():
  n, k = map(int, input().split())
  p = [tuple(map(int, input().split())) for i in range(n)]
  p.sort()
  ans = 4000000000000000000
  for i in range(k, n + 1):
      for j in range(n - i + 1):
          x = p[i + j - 1][0] - p[j][0]
          s = [p[a][1] for a in range(j, i + j)]
          s.sort()
          y = 4000000000
          for a in range(i - k + 1):
            y = min(y, s[a + k - 1] - s[a])
          ans = min(ans, x * y)
  print(ans)
solve()

Solution (Python):
def solve():
  n, k = map(int, input().split())
  p = [tuple(map(int, input().split())) for i in range(n)]
  p.sort()
  ans = 4000000000000000000
  for i in range(k, n + 1):
      for j in range(n - i + 1):
          x = p[i + j - 1][0] - p[j][0]
          s = [p[a][1] for a in range(j, i + j)]
          s.sort()
          y = 4000000000
          for a in range(i - k + 1):
            y = min(y, s[a + k - 1] - s[a])
          ans = min(ans, x * y)
  print(ans)
solve()

Solution (Python):
n, k = map(int, input().split())
p = [tuple(map(int, input().split())) for i in range(n)]
p.sort()
ans = 4000000000000000000
for i in range(k, n + 1):
    for j in range(n - i + 1):
        x = p[i + j - 1][0] - p[j][0]
        s = [p[a][1] for a in range(j, i + j)]
        s.sort()
        y = 4000000000
        for a in range(i - k + 1):
          y = min(y, s[a + k - 1] - s[a])
        ans = min(ans, x * y)
print(ans)

Solution (Python):
n,k=map(int,input().split())

dot=[]
xxx=[]
yyy=[]

ans=float('inf')

for i in range(n):
  x,y=map(int,input().split())
  dot.append([x,y])
  xxx.append(x)
  yyy.append(y)

xxx.sort()
yyy.sort()

for sx in range(n):
  for sy in range(n):
    for gx in range(sx+1,n):
      for gy in range(sy+1,n):
        cnt=0
        for lst in dot:
          if xxx[sx]<=lst[0]<=xxx[gx]:
            if yyy[sy]<=lst[1]<=yyy[gy]:
              cnt+=1
      
        if cnt>=k:
          if xxx[sx]==xxx[gx] or yyy[sy]==yyy[gy]:
            continue
          ans=min(ans,(xxx[gx]-xxx[sx])*(yyy[gy]-yyy[sy]))


print(ans)

Solution (Python):
N,K=map(int,input().split())
nodes=[]
for i in range(N):
  x,y=map(int,input().split())
  nodes.append((x,y))
nodes.sort()
import math
ans=math.inf
count=0
for i in range(N):
  for j in range(i+1,N):
    for k in range(N):
      for l in range(i+1,N):
        count=0
        for m in range(N):
          small=min(nodes[k][1],nodes[l][1])
          big=max(nodes[k][1],nodes[l][1])
          if nodes[i][0]<=nodes[m][0]<=nodes[j][0] and small<=nodes[m][1]<=big:
            count+=1
        if count>=K:
          ans=min(ans,(nodes[j][0]-nodes[i][0])*(big-small))
print(ans)

Solution (Python):
n, k = map(int, input().split())
p = sorted([tuple(map(int, input().split())) for i in range(n)])
ans = 4 * 10**18
for i in range(k, n + 1):
    for j in range(n - i + 1):  
        x = p[i + j - 1][0] - p[j][0]
        s = sorted([p[a][1] for a in range(j, i + j)])
        y = min(s[a + k - 1] - s[a] for a in range(i - k + 1))
        ans = min(ans, x * y)
print(ans)

Solution (Python):
N,K=map(int,input().split())
point=[list(map(int,input().split())) for _ in range(N)]
ans=10**30



for i in range(N):
    for j in range(i,N):
        x1,_=point[i]
        x2,_=point[j]
        minx=min(x1,x2)
        maxx=max(x1,x2)
        for k in range(N):
            for l in range(k,N):
                _,y1= point[k]
                _,y2= point[l]
                miny = min(y1,y2)
                maxy = max(y1,y2)
                cnt=0
                menseki=(maxx-minx)*(maxy-miny)
                for m in range(N):
                    x,y=point[m]
                    if (minx<=x<=maxx)and(miny<=y<=maxy):
                        cnt=cnt+1
                if cnt>=K:
                    ans=min(ans,menseki)
print(ans)

"""
for i in range(N):
    for j in range(i+1,N):
        
        menseki=Decimal(1)
        x1,y1=point[i]
        x2,y2=point[j]
        if x1<x2:
            abx=Decimal(x2)-Decimal(x1)
        else:
            abx=Decimal(x1)-Decimal(x2)
        if y1<y2:
            aby=Decimal(y2)-Decimal(y1)
        else:
            aby=Decimal(y1)-Decimal(y2)
        print("")
        print(abx,aby)
        menseki=abx*aby
        print(menseki)
        minx=min(x1,x2)
        maxx=max(x1,x2)
        miny=min(y1,y2)
        maxy=max(y1,y2)
        pnum=0
        print(minx,maxx,miny,maxy)
        for x,y in point:
            
            if (minx<=x<=maxx)and(miny<=y<=maxy):
                pnum=pnum+1
        print(pnum)
        if pnum>=K:
            ans=ans.min(menseki)
            print(ans)
print(ans)
"""

Solution (Python):
def abc075_d():
    n, k = map(int, input().split())
    P = []
    xarr = []
    yarr = []
    for _ in range(n):
        x, y = (int(x) for x in input().split())
        P.append((x, y))
        xarr.append(x)
        yarr.append(y)
    xarr.sort()
    yarr.sort()

    ans = 5*10**18
    for s, xi in enumerate(xarr):
        for xj in xarr[s+1:]:
            cand = [(x, y) for x, y in P if xi <= x and x <= xj]
            for t, yi in enumerate(yarr):
                for yj in yarr[t+1:]:
                    cnt = len([y for x, y in cand if yi <= y and y <= yj])
                    if cnt >= k:
                        area = (xj - xi) * (yj - yi)
                        ans = min(ans, area)
    print(ans)

if __name__ == '__main__':
    abc075_d()

Solution (Python):
def abc075_d():
    n, k = map(int, input().split())
    P = []
    xarr = []
    yarr = []
    for _ in range(n):
        x, y = (int(x) for x in input().split())
        P.append((x, y))
        xarr.append(x)
        yarr.append(y)
    xarr.sort()
    yarr.sort()

    def count_inside(xi, xj, yi, yj)->int:
        res = 0
        for x, y in P:
            if xi <= x and x <= xj and yi <= y and y <= yj:
                res += 1
        return res

    ans = 5*10**18
    for s, xi in enumerate(xarr):
        for xj in xarr[s+1:]:
            for t, yi in enumerate(yarr):
                for yj in yarr[t+1:]:
                    if count_inside(xi, xj, yi, yj) >= k:
                        area = (xj - xi) * (yj - yi)
                        ans = min(ans, area)
    print(ans)

if __name__ == '__main__':
    abc075_d()

Solution (Python):
def abc075_d():
    n, k = map(int, input().split())
    P = []
    xarr = []
    yarr = []
    for _ in range(n):
        x, y = (int(x) for x in input().split())
        P.append((x, y))
        xarr.append(x)
        yarr.append(y)
    xarr.sort()
    yarr.sort()

    def count_inside(xi, xj, yi, yj)->int:
        res = 0
        for x, y in P:
            if xarr[xi] <= x and x <= xarr[xj] and yarr[yi] <= y and y <= yarr[yj]:
                res += 1
        return res

    ans = 5*10**18
    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):
                    if count_inside(xi, xj, yi, yj) >= k:
                        area = (xarr[xj] - xarr[xi]) * (yarr[yj] - yarr[yi])
                        ans = min(ans, area)
    print(ans)

if __name__ == '__main__':
    abc075_d()

Solution (Python):

import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub, itemgetter, attrgetter


import sys


buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()

def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def ref(N, M, XY):
    ans = INF
    for i in combinations(range(N), r=M):
        minx = INF
        miny = INF
        maxx = -INF
        maxy = -INF
        for j in i:
            x, y = XY[j]
            minx = min(minx, x)
            maxx = max(maxx, x)
            miny = min(miny, y)
            maxy = max(maxy, y)
        ans = min(ans, (maxx-minx)*(maxy-miny))
    return ans

@mt
def slv(N, M, XY):
    XY.sort(key=itemgetter(1))
    XY.sort()
    

    ans = INF
    for i, (x, y) in enumerate(XY):
        yl = [y]
        for j in range(i+1, N):
            x2, y2 = XY[j]
            lx = x2-x
            yl.append(y2)

            if len(yl) >= M:
                yl.sort()
                for k in range(len(yl)-M+1):
                    ly = yl[k+M-1] -  yl[k]
                    ans = min(ans, lx*ly)
    return ans

def main():
    N, M = read_int_n()
    XY = [read_int_n() for _ in range(N)]
    print(slv(N, M, XY))



if __name__ == '__main__':
    main()

Solution (Python):
from sys import stdin
def input():
    return stdin.readline().strip()

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

xy.sort()


ans = 10 ** 19
for left in range(n-k+1):
    for right in range(left+k-1, n):
        horiz = xy[right][0] - xy[left][0]

        choose = sorted(xy[left:right+1], key=lambda x: x[1])
        for down in range(len(choose)-k+1):
            
            
            area = horiz * (choose[down+k-1][1] - choose[down][1])
            if area < ans:
                ans = area

print(ans)

Solution (Python):
from sys import stdin
def input():
    return stdin.readline().strip()

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

xy.sort()


ans = float('inf')
for left in range(n-k+1):
    for right in range(left+k-1, n):
        choose = sorted(xy[left:right+1], key=lambda x: x[1])
        for down in range(len(choose)-k+1):
            area = (xy[right][0] - xy[left][0]) * (choose[down+k-1][1] - choose[down][1])
            if area < ans:
                ans = area

print(ans)

Solution (Python):
n,k = map(int, input().split())
xs = []
ys = []
ps = []
for i in range(n):
    x,y = map(int, input().split())
    xs.append(x)
    ys.append(y)
    ps.append((x,y))

xs = sorted(list(set(xs)))
ys = sorted(list(set(ys)))
xdic = {x:i for i, x in enumerate(xs)}
ydic = {y:i for i, y in enumerate(ys)}
xrdic = {i:x for i, x in enumerate(xs)}
yrdic = {i:y for i, y in enumerate(ys)}
nx = len(xs)
ny = len(ys)


fs = [[0] * (1+ny) for i in range(nx+1)]
for x,y in ps:
    ix = xdic[x]
    iy = ydic[y]
    fs[ix][iy] += 1

acc = [[0] * (1+ny) for i in range(nx+1)]
for i in range(nx):
    for j in range(ny):
        acc[i+1][j+1] = acc[i+1][j] + acc[i][j+1] - acc[i][j] + fs[i][j]

def calc(sx,sy,tx,ty):
    ix1 = xrdic[sx]
    ix2 = xrdic[tx]
    iy1 = yrdic[sy]
    iy2 = yrdic[ty]
    return (ix2-ix1) * (iy2-iy1)


ans = 10**20
for sx in range(nx+1):
    for sy in range(ny+1):
        for tx in range(sx+1, nx+1):
            for ty in range(sy+1, ny+1):
                cnt = acc[tx][ty] - acc[sx][ty] - acc[tx][sy] + acc[sx][sy]
                if cnt >= k:
                    S = calc(sx,sy,tx-1,ty-1)
                    ans = min(ans, S)
print(ans)

Solution (Python):
import sys
from itertools import combinations 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N, K = map(int, readline().split())
X = []
Y = []
XY = []
for _ in range(N):
    x,y = map(int,readline().split())
    X.append(x)
    Y.append(y)
    XY.append((x,y))
INF = 10**31
ans = INF
for x1,x2 in combinations(X,2):
    for y1,y2 in combinations(Y,2):
        if x1 > x2:
            x1,x2 = x2,x1
        if y1 > y2:
            y1,y2 = y2,y1
        cnt = 0 
        for x,y in XY:
            if x1 <= x <= x2 and y1 <= y <= y2:
                cnt += 1 
        if cnt >= K:
            tmp = (x2-x1)*(y2-y1)
            ans = min(ans,tmp)

print(ans)

Solution (Python):
n,m=map(int,input().split())
x=[0]*n
y=[0]*n
for i in range(n):
  x[i],y[i]=map(int,input().split())
ans=10**19
for i in range(n):
  for j in range(i,n):
    for k in range(j,n):
      for l in range(k,n):
        xl=min(x[i],x[j],x[k],x[l])
        xr=max(x[i],x[j],x[k],x[l])
        yl=min(y[i],y[j],y[k],y[l])
        yh=max(y[i],y[j],y[k],y[l])
        cnt=0
        for c in range(n):
          cnt+=xl<=x[c]<=xr and yl<=y[c]<=yh
        if cnt>=m:ans=min(ans,(xr-xl)*(yh-yl))
print(ans)

Solution (Python):
import collections, itertools, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def S(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()

def resolve():
    N, K = LI()
    xy = [LI() for _ in range(N)]

    
    x_coord = [i[0] for i in xy]
    x_coord.sort()
    x_val_num = {x_coord[i]: i for i in range(N)}
    y_coord = [i[1] for i in xy]
    y_coord.sort()
    y_val_num = {y_coord[i]: i for i in range(N)}

    
    xy_cnt = [[0] * N for _ in range(N)]
    for x, y in xy:
        xy_cnt[y_val_num[y]][x_val_num[x]] = 1
    
    
    xy_acm = [[0] * (N + 1) for _ in range(N + 1)]
    for i in range(N):
        for j in range(N):
            xy_acm[i+1][j+1] = xy_cnt[i][j] + xy_acm[i+1][j] + xy_acm[i][j+1] - xy_acm[i][j]
    
    

    ans = INF
    for yl, yu in itertools.combinations(range(N + 1), 2):
        for xl, xu in itertools.combinations(range(N + 1), 2):
            cnt = xy_acm[yu][xu] - xy_acm[yu][xl] - xy_acm[yl][xu] + xy_acm[yl][xl]
            
            if cnt >= K:
                ans = min((x_coord[xu-1] - x_coord[xl]) * (y_coord[yu-1] - y_coord[yl]), ans)

    print(ans)

if __name__ == '__main__':
    resolve()

Solution (Python):
import collections, itertools, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def S(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()

def resolve():
    N, K = LI()
    xy = [LI() for _ in range(N)]

    

    x_coord = [i[0] for i in xy]
    x_coord.sort()
    x_val_num = {x_coord[i]: i for i in range(N)}
    y_coord = [i[1] for i in xy]
    y_coord.sort()
    y_val_num = {y_coord[i]: i for i in range(N)}

    
    xy_cnt = [[0] * N for _ in range(N)]
    for x, y in xy:
        xy_cnt[y_val_num[y]][x_val_num[x]] = 1
    
    
    xy_acm = [[0] * (N + 1) for _ in range(N + 1)]
    for i in range(N):
        for j in range(N):
            xy_acm[i+1][j+1] = xy_cnt[i][j] + xy_acm[i+1][j] + xy_acm[i][j+1] - xy_acm[i][j]
    
    

    ans = INF
    for yl, yu in itertools.combinations(range(N + 1), 2):
        for xl, xu in itertools.combinations(range(N + 1), 2):
            cnt = xy_acm[yu][xu] - xy_acm[yu][xl] - xy_acm[yl][xu] + xy_acm[yl][xl]
            
            if cnt >= K:
                ans = min((x_coord[xu-1] - x_coord[xl]) * (y_coord[yu-1] - y_coord[yl]), ans)

    print(ans)

if __name__ == '__main__':
    resolve()

Solution (Python):
import collections, itertools, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def S(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()

def resolve():
    N, K = LI()
    xy = [LI() for _ in range(N)]

    

    x_cnt = collections.Counter([i[0] for i in xy])
    x_coordinate = list(x_cnt.keys())
    x_coordinate.sort()
    
    y_cnt = collections.Counter([i[1] for i in xy])
    y_coordinate = list(y_cnt.keys())
    y_coordinate.sort()
    len_y_c = len(y_coordinate)

    ans = INF
    for xl, xh in itertools.combinations(x_coordinate, 2):
        
        for i in range(len_y_c - 1):
            yl = y_coordinate[i]
            for j in range(i + 1, len_y_c):
                yh = y_coordinate[j]
                cnt = len([(i, j) for i, j in xy if xl <= i <= xh and yl <= j <= yh])
                if cnt >= K:
                    ans = min((xh - xl) * (yh - yl), ans)
                    break

    print(ans)

if __name__ == '__main__':
    resolve()

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




xs_decode = sorted(map(lambda t: t[0], xys))
ys_decode = sorted(map(lambda t: t[1], xys))
xs_encode = {e:i for i, e in enumerate(xs_decode)}
ys_encode = {e:i for i, e in enumerate(ys_decode)}

H = len(xs_encode)
W = len(ys_encode)

field_csum = [[0] * (W+1) for _ in range(H+1)]
for x, y in xys:
    i = xs_encode[x]
    j = ys_encode[y]
    field_csum[i+1][j+1] += 1
for i in range(H+1):
    for j in range(W):
        field_csum[i][j+1] += field_csum[i][j]
for i in range(H):
    for j in range(W+1):
        field_csum[i+1][j] += field_csum[i][j]


ans = 1 << 63 

for bi in range(H):
    for ei in range(bi + 1, H + 1):
        for bj in range(W):
            for ej in range(bj + 1, W + 1):
                if field_csum[ei][ej] - field_csum[bi][ej] - field_csum[ei][bj] + field_csum[bi][bj] >= K:
                    area = (xs_decode[ei-1] - xs_decode[bi]) * (ys_decode[ej-1] - ys_decode[bj])
                    ans = min(ans, area)
                    break 

print(ans)

Solution (Python):
from itertools import combinations
def main():
    N, K = map(int, input().split())
    P = [list(map(int, input().split())) for _ in range(N)]
    ans = 1<<62
    for t in combinations(P, min(4, K)):
        xs, ys = zip(*t)
        xmin = min(xs)
        xmax = max(xs)
        ymin = min(ys)
        ymax = max(ys)
        area = (xmax-xmin) * (ymax-ymin)
        if ans < area:
            continue
        k = 0
        for x, y in P:
            if xmin <= x <= xmax and ymin <= y <= ymax:
                k += 1
        if k >= K:
            ans = area
    print(ans)

main()

Solution (Python):
n, k = map(int, input().split())
xy = []
X = []
Y = []
for i in range(n):
    x, y = map(int, input().split())
    X.append(x)
    Y.append(y)
    xy.append([x, y])
X.sort()
Y.sort()
ans = float("inf")
for i in range(n):
    for j in range(i + 1, n):
        for l in range(n):
            for m in range(l + 1, n):
                count = 0
                for o in range(n):
                    if X[i] <= xy[o][0] <= X[j] and Y[l] <= xy[o][1] <= Y[m]:
                        count += 1
                if count >= k:
                    ans = min(ans, (X[j] - X[i]) * (Y[m] - Y[l]))
print(ans)

Solution (Python):
N,K = map(int,input().split())
A = sorted([list(map(int,input().split()))for n in range(N)])
ans = float("inf")

for i in range(N-K+1):
  for j in range(i+K-1,N):
    P = A[j][0]-A[i][0]
    C = sorted([a[1] for a in A[i:j+1]])
    for k in range(j-i-K+2):
      Q = C[k+K-1]-C[k]
      ans = min(ans,P*Q)

print(ans)

Solution (Python):
N, K = (int(x) for x in input().split())
Plot = [tuple(int(x) for x in input().split()) for _ in range(N)]
X = [p[0] for p in Plot]
Y = [p[1] for p in Plot]
X.sort()
Y.sort()

ans = 10e20
from itertools import combinations
for x1, x2 in combinations(X, 2):
    for y1 in Y:
        y2 = [y for x,y in Plot if x1 <= x <= x2 and y1 <= y]
        if len(y2) < K:
            break
        y2.sort()
        S = (x2-x1)*(y2[K-1]-y1)
        ans = min(ans, S)
print(ans)