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):
def main():

    N, K = map(int, input().split())
    p = []
    for _ in range(N):
        x, y = map(int, input().split())
        p.append([x, y])
    p.sort(key = lambda x: x[0])

    min_area = float('inf')
    for i in range(N-1):
        for j in range(i+1, N):
            if j-i+1 >= K:
                x1 = p[i][0]
                x2 = p[j][0]
                ys = []
                for k in range(i, j+1):
                    ys.append(p[k][1])
                ys.sort()
                for k in range(len(ys)):
                    for l in range(k+K-1, len(ys)):
                        y1 = ys[k]
                        y2 = ys[l]
                        area = (x2-x1)*(y2-y1)
                        if area > 0:
                            min_area = min(min_area, area)
    return min_area

if __name__ == '__main__':
    print(main())

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')
move = [(0, 1), (1, 1), (-1, 1), (0, -1), (1, -1), (-1, -1), (1, 0), (-1, 0)]

def A():
    a, b, c = LI()
    if a == b:
        print(c)
    if b == c:
        print(a)
    if a == c:
        print(b)
    return


def B():
    h, w = LI()
    s = SR(h)
    for y in range(h):
        for x in range(w):
            if s[y][x] == ".":
                b = 0
                for my, mx in move:
                    ym = my + y
                    xm = mx + x
                    if 0 <= ym < h and 0 <= xm < w:
                        if s[ym][xm] == "
                            b += 1
                s[y][x] = b
    for i in range(h):
        print("".join(map(str, s[i])))
    return


def C():
    n, m = LI()
    edg = [[] for i in range(n)]
    ab = LIR_(m)
    for a,b in ab:
        edg[a].append(b)
        edg[b].append(a)
    ans = 0
    for a, b in ab:
        c = [True] * n
        ed = defaultdict(int)
        q = deque()
        q.append(0)
        c[0] = False
        ed[(a,b)] = True
        while q:
            now = q.pop()
            for e in edg[now]:
                if ed[(now,e)] or ed[(e,now)]:
                    continue
                ed[(now, e)] = True
                c[e] = False
                q.appendleft(e)
        if True in c:
            ans += 1
    print(ans)
    return


def D():
    n, k = LI()
    xy = LIR(n)
    fullserch = list(itertools.combinations(range(n), 2))
    ans = inf
    for a, b in fullserch:
        minx = min(xy[a][0], xy[b][0])
        maxx = max(xy[a][0], xy[b][0])
        for c, d in fullserch:
            miny = min(xy[c][1], xy[d][1])
            maxy = max(xy[c][1], xy[d][1])
            x = 0
            
            for i in range(n):
                if minx <= xy[i][0] <= maxx and miny <= xy[i][1] <= maxy:
                    x += 1

            if x >= k:
                ans = min(ans, (maxx - minx) * (maxy - miny))
    print(ans) 
    return


if __name__ == '__main__':
    D()

Solution (Python):
n, k =  [ int(v) for v in input().split() ] 
node_list = [] 
x_list = []
y_list = []

for i in range(n):
    x, y = [ int(v) for v in input().split() ]
    node_list.append((x,y))
    x_list.append(x)
    y_list.append(y)
x_list.sort()
y_list.sort()


x_list = [ (x_list[i],x_list[j]) for i in range(n-k+1) for j in range(i+k-1,n) ]
y_list = [ (y_list[i],y_list[j]) for i in range(n-k+1) for j in range(i+k-1,n) ]

def check(in_x,in_y):
    xl, xr, yu, yd = in_x[0], in_x[1], in_y[0], in_y[1]
    ok = 0
    for i in node_list:
        if xl <= i[0] <= xr and yu <= i[1] <= yd:
            ok += 1

    if ok >= k:
        return (xr-xl) * (yd-yu)
    else:
        return 10**19

ans = 10**19
for i in x_list:
    for j in y_list:
        ans = min(ans, check(i,j))
print(ans)

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

ret = float('inf')
for i in range(N) :
    for j in range(i, N) :
        for k in range(j, N) :
            for l in range(k, N) :
                x, y = zip(xy[i], xy[j], xy[k], xy[l])
                mx, Mx = min(x), max(x)
                my, My = min(y), max(y)
                
                counter = 0
                for m in range(N) :
                    if mx <= xy[m][0] <= Mx and my <= xy[m][1] <= My :
                        counter += 1
                if counter >= K :
                    ret = min(ret, (Mx-mx)*(My-my))
print(ret)

Solution (Python):
N,K=map(int,input().split())
point=[tuple(map(int,input().split())) for i in range(N)]
point.sort(key=lambda x:x[0])
ans=float('inf')
for i in range(1+N-K):
    for j in range(i+K,N+1):
        x=point[j-1][0]-point[i][0]
        now=point[i:j]
        now.sort(key=lambda x:x[1])
        for k in range(j-i-K+1):
            ans=min(x*(now[k+K-1][1]-now[k][1]),ans)
print(ans)

Solution (Python):



import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline



n,k = [int(i) for i in readline().split()]
xy = [[int(i) for i in readline().split()] for i in range(n)]

xy.sort()

ans = 4*10**18+10
for i in range(n):
    for j in range(i+k-1,n):
        dx = xy[j][0] - xy[i][0]
        y = sorted(xy[k][1] for k in range(i,j+1))

        L = len(y)-k+1
        for i in range(L):
            dy = y[i+k-1]-y[i]
            ans = min(ans,dy*dx)
        


print(ans)

Solution (Python):
N, K = map(int, input().split())
XY = []
X = []
Y = []
for _ in range(N):
    x, y = map(int, input().split())
    XY.append((x, y))
    X.append(x)
    Y.append(y)
X.sort()
Y.sort()
ix = {v: i for i, v in enumerate(X)}
iy = {v: i for i, v in enumerate(Y)}
m = [[0] * (len(X) + 1) for _ in range(len(Y) + 1)]
for x, y in XY:
    m[iy[y] + 1][ix[x] + 1] += 1
for y in range(len(Y) + 1):
    for x in range(len(X)):
        m[y][x + 1] += m[y][x]
for x in range(len(X) + 1):
    for y in range(len(Y)):
        m[y + 1][x] += m[y][x]
ans = float("inf")
for x0 in range(len(X) - 1):
    for x1 in range(x0 + 1, len(X)):
        for y0 in range(len(Y) - 1):
            for y1 in range(y0 + 1, len(Y)):
                n = m[y1 + 1][x1 + 1] - m[y0][x1 + 1] - \
                    m[y1 + 1][x0] + m[y0][x0]
                if n >= K:
                    s = (X[x1] - X[x0]) * (Y[y1] - Y[y0])
                    ans = min(ans, s)
print(ans)

Solution (Python):
N, K = map(int, input().split())
XY = []
X = []
Y = []
for _ in range(N):
    x, y = map(int, input().split())
    XY.append((x, y))
    X.append(x)
    Y.append(y)
X.sort()
Y.sort()
ix = {v: i for i, v in enumerate(X)}
iy = {v: i for i, v in enumerate(Y)}
m = [[0] * (len(X) + 1) for _ in range(len(Y) + 1)]
for x, y in XY:
    m[iy[y] + 1][ix[x] + 1] += 1
for y in range(len(Y) + 1):
    for x in range(len(X)):
        m[y][x + 1] += m[y][x]
for x in range(len(X) + 1):
    for y in range(len(Y)):
        m[y + 1][x] += m[y][x]
ans = float("inf")
for x0 in range(len(X) - 1):
    for x1 in range(x0 + 1, len(X)):
        for y0 in range(len(Y) - 1):
            for y1 in range(y0 + 1, len(Y)):
                n = m[y1 + 1][x1 + 1] - m[y0][x1 + 1] - \
                    m[y1 + 1][x0] + m[y0][x0]
                if n >= K:
                    s = (X[x1] - X[x0]) * (Y[y1] - Y[y0])
                    ans = min(ans, s)
print(ans)

Solution (Python):



import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))


n,K = LI()
xy = []
for _ in range(n):
    x,y = LI()
    xy.append((x,y))
ans = inf
for _ , uy in xy:
    for _ , dy in xy:
        if uy < dy:
            continue
        for rx , _ in xy:
            for lx , _ in xy:
                if rx < lx:
                    continue
                cnt = 0
                for x,y in xy:
                    if lx <= x <= rx and dy <= y <= uy:
                        cnt += 1
                if cnt >= K:
                    ans = min(ans,(rx - lx)*(uy - dy))
print(ans)

Solution (Python):



import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))


n,K = LI()
xy = []
X = []
Y = []
for _ in range(n):
    x,y = LI()
    xy.append([x,y])
    X.append(x)
    Y.append(y)
X.sort(reverse = True)
Y.sort(reverse = True)
ans = inf
for i in range(n):
    uy = Y[i]
    for j in range(i+1,n):
        dy = Y[j]
        for k in range(n):
            rx = X[k]
            for l in range(k+1,n):
                lx = X[l]
                cnt = 0
                for x,y in xy:
                    if lx <= x <= rx and dy <= y <= uy:
                        cnt += 1
                if cnt >= K:
                    S = (uy - dy)*(rx - lx)
                    ans = min(ans,S)
print(ans)

Solution (Python):
N,K = map(int,input().split())
p = sorted([list(map(int,input().split())) for _ in range(N)])
x, y = zip(*p)
inf = float('inf')
ans = inf

for i in range(N-K+1):
    for j in range(K+i-1, N):
        Ys = sorted(y[i:j+1])
        for k in range(len(Ys)-K+1):
            ans = min(ans, (x[j]-x[i])*(Ys[k+K-1]-Ys[k]))
print(ans)

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


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

    Xs = []
    Ys = []
    for x, y in XY:
        Xs.append(x)
        Ys.append(y)
    Xs.sort()
    Ys.sort()
    points = [[0 for _ in range(N)] for _ in range(N)]

    for x, y in XY:
        ix = bisect_left(Xs, x)
        iy = bisect_left(Ys, y)
        points[ix][iy] += 1

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

    for ix in range(1, N+1):
        s = 0
        for iy in range(1, N+1):
            if ix == 1:
                sumpoints[ix][iy] = points[ix-1][iy-1]
            if points[ix-1][iy-1] == 1:
                s = 1
            sumpoints[ix][iy] = sumpoints[ix-1][iy] + s

    ans = int(8E18)
    for lx in range(N-1):
        for rx in range(lx+1, N):
            for ly in range(N-1):
                for ry in range(ly+1, N):
                    if sumpoints[rx+1][ry+1] - sumpoints[rx+1][ly] - sumpoints[lx][ry+1] + sumpoints[lx][ly] >= K:
                        s = (Xs[rx]-Xs[lx])*(Ys[ry]-Ys[ly])
                        ans = min(ans, s)
    print(ans)

if __name__ == "__main__":
    main()

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

    def count(x_min, x_max, y_min, y_max, i, j):
        OK = 0
        
        for m, n in XY[i:j + 1]:
            if y_min <= n <= y_max:
                OK += 1
        if OK >= K:
            return True
        return False

    ans = 10 ** 20
    for i, val_i in enumerate(XY[:N - 1]):
        a = val_i[0]
        for j in range(i + K - 1, N):
            b = XY[j][0]
            e = b - a
            
            for k, c in XY:
                
                for l, d in XY:
                    
                    if c < d:
                        if  e * (d - c) < ans and count(a, b, c, d, i, j):
                            
                            ans = e * (d - c)
                            
    print (ans)
    return

if __name__ == '__main__':
    main()

Solution (Python):

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

def count(x_min, x_max, y_min, y_max):
    cnt = 0
    for i in range(N):
        if x_min <= X[i] <= x_max and y_min <= Y[i] <= y_max:
            cnt += 1
    return cnt

ans = 10 ** 20
for i in range(N):
    for j in range(N):
        for k in range(N):
            for l in range(N):
                
                if X[i] < X[j] and Y[k] < Y[l]:
                    if count(X[i], X[j], Y[k], Y[l]) >= K:
                        
                        ans = min(ans, (X[j] - X[i]) * (Y[l] - Y[k]))
print (ans)

Solution (Python):
N, K = map(int, input().split())
XY = [list(map(int, input().split())) for _ in range(N)]
XY.sort()
X, Y = zip(*XY)
r = 10**20
for x0 in range(N - K + 1):
  for x1 in range(K + x0 - 1, N):
    Ys = sorted(Y[x0:x1 + 1])
    for y0 in range(len(Ys) - K + 1):
      r = min(r, (X[x1] - X[x0]) * (Ys[y0 + K - 1] - Ys[y0]))
print(r)

Solution (Python):
N, K = map(int, input().split())
XY = [list(map(int, input().split())) for _ in range(N)]
XY.sort()
X, Y = zip(*XY)
r = float('inf')
for x0 in range(N - K + 1):
  for x1 in range(K + x0 - 1, N):
    x = X[x1] - X[x0]
    Y_s = sorted(Y[x0:x1 + 1])
    for y0 in range(len(Y_s) - K + 1):
      y = Y_s[y0 + K - 1] - Y_s[y0]
      r = min(r, x * y)
print(r)

Solution (Python):
N, K = map(int, input().split())
XY = [list(map(int, input().split())) for _ in range(N)]
XY.sort()
X, Y = zip(*XY)
r = 10**20
for x0 in range(N - K + 1):
  for x1 in range(K + x0 - 1, N):
    x = X[x1] - X[x0]
    Y_s = sorted(Y[x0:x1 + 1])
    for y0 in range(len(Y_s) - K + 1):
      y = Y_s[y0 + K - 1] - Y_s[y0]
      r = min(r, x * y)
print(r)

Solution (Python):
N, K = map(int, input().split())
XY = [list(map(int, input().split())) for _ in range(N)]
XY.sort()
r = 10**20
for xi0 in range(N - K + 1):
  for xi1 in range(K + xi0 - 1, N):
    x = XY[xi1][0] - XY[xi0][0]
    XY_ys = sorted(XY[xi0:xi1 + 1], key=lambda a: a[1])
    for yi0 in range(len(XY_ys) - K + 1):
      y = XY_ys[yi0 + K - 1][1] - XY_ys[yi0][1]
      r = min(r, x * y)
print(r)

Solution (Python):
N, K = map(int, input().split())
XY = [list(map(int, input().split())) for _ in range(N)]
X, Y = zip(*XY)
X_s = sorted(X)
Y_s = sorted(Y)

r = 10**20
for xi0 in range(N):
  for xi1 in range(xi0, N):
    for yi0 in range(N):
      for yi1 in range(yi0, N):
        x0 = X_s[xi0]
        x1 = X_s[xi1]
        y0 = Y_s[yi0]
        y1 = Y_s[yi1]
        c = 0
        for x, y in XY:
          if x0 <= x <=x1 and y0 <= y <= y1:
            c += 1
        if c >= K:
          r = min(r, (x1 - x0) * (y1 - y0))
print(r)

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

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


ans = float('inf')

for lx, _ in XY:
    for rx, _ in XY:
        if lx > rx:
            continue
        for _, dy in XY:
            for _, uy in XY:
                if dy > uy:
                    continue
                count = 0
                for x,y in XY:
                    if lx <= x <= rx and dy <= y <= uy:
                        count += 1
                if count >= K:
                    ans = min(ans,(rx-lx)*(uy-dy))
print(ans)

Solution (Python):
n,k=map(int,input().split())
xy=[]
for i in range(n):
    tmp=[int(j) for j in input().split()]
    xy.append((tmp[0],tmp[1]))
from operator import itemgetter
xy.sort(key=itemgetter(1))
xy.sort(key=itemgetter(0))
xy=tuple(xy)
l=tuple(enumerate(xy))
ans=10**100
for i,(a,b) in l[:n-k+1]:
    for j,(c,d) in l[i+k-1:]:
        l1=sorted(y for x,y in xy[i:j+1])
        l2=l1[k-1:]
        for p,q in zip(l1,l2):
            if p<=b and q>=d:
                ans=min(ans,(c-a)*(q-p))
print(ans)

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

ans = float('inf')
for lx, _ in point :
    for rx, _ in point :
        if lx > rx :
            continue
        for _, ly in point :
            for _, ry in point :
                if ly > ry :
                    continue
                count = 0
                for x, y in point :
                    if lx <= x <= rx and ly <= y <= ry :
                        count += 1
                if count >= K :
                    ans = min(ans, (rx - lx) * (ry - ly))

print(ans)

Solution (Python):
import math
import copy
from operator import mul
from functools import reduce
from collections import defaultdict
from collections import Counter
from collections import deque

from itertools import product

from itertools import permutations

from itertools import combinations

from itertools import accumulate
from bisect import bisect_left, bisect_right

import re







def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
 
def i_inpl(): return int(input())
def l_inpl(): return list(map(int, input().split()))
def line_inpl(x): return [i_inpl() for _ in range(x)]

INF = int(1e50)
MOD = int(1e9)+7 


def create_grid(H, W, value = 0):
    return [[ value for _ in range(W)] for _ in range(H)]



def main():
    N, K = l_inpl()
    xy = []
    for _ in range(N):
        xi, yi = l_inpl()
        xy.append([xi, yi])

    ans = INF * INF
    xy.sort()

    for l, (xl, yl) in list(enumerate(xy))[:N-K+1]:
        for r, (xr, yr) in list(enumerate(xy))[l+K-1:]:
            ys = sorted([ y for _, y in xy[l:r+1]]) 
            for yd, yu in zip(ys, ys[K-1:]):
                if yd <= yl and yd <= yr and yl <= yu and yr <= yu:
                
                    ans = min(ans, (xr-xl) * (yu - yd))
    
    print(ans)
if __name__ == "__main__":
    main()

Solution (Python):
import math
import copy
from operator import mul
from functools import reduce
from collections import defaultdict
from collections import Counter
from collections import deque

from itertools import product

from itertools import permutations

from itertools import combinations

from itertools import accumulate
from bisect import bisect_left, bisect_right

import re







def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
 
def i_inpl(): return int(input())
def l_inpl(): return list(map(int, input().split()))
def line_inpl(x): return [i_inpl() for _ in range(x)]

INF = int(1e18)
MOD = int(1e9)+7 


def create_grid(H, W, value = 0):
    return [[ value for _ in range(W)] for _ in range(H)]



def main():
    N, K = l_inpl()
    xy = []
    for _ in range(N):
        xi, yi = l_inpl()
        xy.append([xi, yi])

    ans = INF * INF
    xy.sort()

    for l, (xl, yl) in list(enumerate(xy))[:N-K+1]:
        for r, (xr, yr) in list(enumerate(xy))[l+K-1:]:
            ys = sorted([ y for _, y in xy[l:r+1]]) 
            for yd, yu in zip(ys, ys[K-1:]):
                
                if yd <= yl and yr <= yu:
                    ans = min(ans, (xr-xl) * (yu - yd))
    
    print(ans)
if __name__ == "__main__":
    main()

Solution (Python):

import sys
from itertools import product
INF = float("inf")


def solve(N: int, K: int, x: "List[int]", y: "List[int]"):
    sx = sorted(x)
    sy = sorted(y)
    m = INF

    for (i, x1), (j, y1) in product(enumerate(sx[:-K+1]), enumerate(sy[:-K+1])):
        
        for x2 in sx[i+1:]:
            for y2 in sy[j+1:]:
                
                counter = sum([1 for xx, yy in zip(x, y)
                               if (x1 <= xx <= x2) and (y1 <= yy <= y2)])
                if counter >= K:
                    area = abs((y2-y1)*(x2-x1))
                    m = min(m, area)
                    break   
    print(m)
    return


def main():

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


if __name__ == '__main__':
    main()

Solution (Python):

import sys
INF = float("inf")


def solve(N: int, K: int, x: "List[int]", y: "List[int]"):
    sx = sorted(x)
    sy = sorted(y)
    acc = [[0]*N for _ in range(N)]

    for i, x1 in enumerate(sx):
        for j, y1 in enumerate(sy):
            acc[i][j] = sum([True for xx, yy in zip(x, y)
                             if xx <= x1 and yy <= y1])

    m = INF

    for i, x1 in enumerate(sx[:-K+1]):
        for j, y1 in enumerate(sy[:-K+1]):
            
            for x2 in sx[i+1:]:
                for y2 in sy[j+1:]:
                    
                    counter = 0
                    for xx, yy in zip(x, y):
                        if (x1 <= xx <= x2) and (y1 <= yy <= y2):
                            counter += 1
                    if counter >= K:
                        flag = True
                        area = abs((y2-y1)*(x2-x1))
                        if area < m:
                            m = area
                        break   
    print(m)
    return


def main():

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


if __name__ == '__main__':
    main()

Solution (Python):
import sys

if __name__ == '__main__':
    N, K = map(int, input().split())
    xy_list = [list(map(int, input().split())) for i in range(N)]

    all_x = sorted(list(set([xy[0] for xy in xy_list])))
    all_y = sorted(list(set([xy[1] for xy in xy_list])))

    answer = sys.maxsize
    for i in range(len(all_x)):
        x1 = all_x[i]
        for j in range(i+1, len(all_x)):
            x2 = all_x[j]
            for k in range(len(all_y)):
                y1 = all_y[k]
                for l in range(k+1, len(all_y)):
                    y2 = all_y[l]
                    if K <= len([xy for xy in xy_list if (x1 <= xy[0] <= x2) and (y1 <= xy[1] <= y2)]) and answer > (x2-x1) * (y2-y1):
                        answer = (x2-x1) * (y2-y1)

    print(answer)

Solution (Python):
import sys

if __name__ == '__main__':
    N, K = map(int, input().split())
    xy_list = [list(map(int, input().split())) for i in range(N)]

    all_x = sorted(list(set([xy[0] for xy in xy_list])))
    all_y = sorted(list(set([xy[1] for xy in xy_list])))

    answer = sys.maxsize
    for i in range(len(all_x)):
        x1 = all_x[i]
        for j in range(i+1, len(all_x)):
            x2 = all_x[j]
            for k in range(len(all_y)):
                y1 = all_y[k]
                for l in range(k+1, len(all_y)):
                    y2 = all_y[l]
                    if K <= len([xy for xy in xy_list if (x1 <= xy[0] <= x2) and (y1 <= xy[1] <= y2)]) and answer > (x2-x1) * (y2-y1):
                        answer = (x2-x1) * (y2-y1)

    print(answer)

Solution (Python):
import sys

if __name__ == '__main__':
    N, K = map(int, input().split())
    xy_list = [list(map(int, input().split())) for i in range(N)]

    all_x = sorted(list(set([xy[0] for xy in xy_list])))
    all_y = sorted(list(set([xy[1] for xy in xy_list])))

    answer = sys.maxsize
    for i in range(len(all_x)):
        x1 = all_x[i]
        for j in range(i+1, len(all_x)):
            x2 = all_x[j]
            for k in range(len(all_y)):
                y1 = all_y[k]
                for l in range(k+1, len(all_y)):
                    y2 = all_y[l]
                    if answer > (x2-x1) * (y2-y1) and K <= sum(map(lambda xy: (x1 <= xy[0] <= x2) and (y1 <= xy[1] <= y2), xy_list)):
                        answer = (x2-x1) * (y2-y1)

    print(answer)

Solution (Python):
n,k=map(int,input().split())
xy=[list(map(int,input().split())) for _ in [0]*n]
xy=sorted(xy,key=lambda x:x[0])
temp=[]
for i in range(n):
    for j in range(i+k-1,n):
        temp.append([xy[j][0]-xy[i][0]]+sorted([y for x,y in xy[i:j+1]]))
m=10**19      
for t in temp:
    l=len(t)-1
    for i in range(1,l-k+2):
        m=min(m,t[0]*(t[i+k-1]-t[i]))
print(m)

Solution (Python):
def main():
    N,K = map(int,input().split())
    XY = [list(map(int,input().split())) for _ in [0]*N]
    iX = [0]*N
    iY = [0]*N
    for i,xy in enumerate(XY):
        x,y = xy
        iX[i] = x
        iY[i] = y
    iX.sort()
    iY.sort()
    X = {x:i for i,x in enumerate(iX)}
    Y = {y:i for i,y in enumerate(iY)}

    c = [[0]*(N+1) for i in [0]*(N+1)]
    for x,y in XY:
        c[Y[y]+1][X[x]+1] = 1

    for i in range(N):
        ci1 = c[i+1]
        for j in range(N):
            ci1[j+1] += ci1[j]
    for i in range(N):
        c[i+1] = [ci1j+cij for ci1j,cij in zip(c[i+1],c[i])]

    ans = 10**20
    for u in range(N):
        for d in range(u+K-1,N):
            l = 0
            r = K-1
            dY = iY[d]-iY[u]
            cd = c[d+1]
            cu = c[u]
            while r<N:
                if cd[r+1]+cu[l]-cu[r+1]-cd[l] >=K:
                    ans = min(ans, (iX[r] - iX[l])*dY)
                    l+=1
                else:r+=1

    print(ans)
main()

Solution (Python):
def main():
    N,K = map(int,input().split())
    XY = [list(map(int,input().split())) for _ in [0]*N]
    iX = [0]*N
    iY = [0]*N
    for i,xy in enumerate(XY):
        x,y = xy
        iX[i] = x
        iY[i] = y
    iX.sort()
    iY.sort()
    X = {x:i for i,x in enumerate(iX)}
    Y = {y:i for i,y in enumerate(iY)}

    c = [[0]*(N+1) for i in [0]*(N+1)]
    for x,y in XY:
        c[Y[y]+1][X[x]+1] = 1

    for i in range(N):
        ci1 = c[i+1]
        for j in range(N):
            ci1[j+1] += ci1[j]
    for i in range(N):
        ci1 = c[i+1]
        ci = c[i]
        for j,cij in enumerate(ci[1:],1):
            ci1[j] += cij

    ans = 10**20
    for u in range(N):
        for d in range(u+K-1,N):
            l = 0
            r = K-1
            dY = iY[d]-iY[u]
            cd = c[d+1]
            cu = c[u]
            while r<N:
                if cd[r+1]+cu[l]-cu[r+1]-cd[l] >=K:
                    ans = min(ans, (iX[r] - iX[l])*dY)
                    l+=1
                else:r+=1

    print(ans)
main()

Solution (Python):
def main():
    N,K = map(int,input().split())
    XY = [list(map(int,input().split())) for _ in [0]*N]
    iX = [0]*N
    iY = [0]*N
    for i,xy in enumerate(XY):
        x,y = xy
        iX[i] = x
        iY[i] = y
    iX.sort()
    iY.sort()
    X = {x:i for i,x in enumerate(iX)}
    Y = {y:i for i,y in enumerate(iY)}

    c = [[0]*(N+1) for i in [0]*(N+1)]
    for x,y in XY:
        c[Y[y]+1][X[x]+1] = 1

    for i in range(N):
        ci1 = c[i+1]
        for j in range(N):
            ci1[j+1] += ci1[j]
    for i in range(N):
        ci1 = c[i+1]
        ci = c[i]
        for j in range(N):
            ci1[j+1] += ci[j+1]

    ans = 10**20
    for u in range(N):
        for d in range(u+K-1,N):
            l = 0
            r = K-1
            dY = iY[d]-iY[u]
            cd = c[d+1]
            cu = c[u]
            while r<N:
                if cd[r+1]+cu[l]-cu[r+1]-cd[l] >=K:
                    ans = min(ans, (iX[r] - iX[l])*dY)
                    l+=1
                else:r+=1

    print(ans)
main()

Solution (Python):
def main():
    N,K = map(int,input().split())
    XY = [list(map(int,input().split())) for _ in [0]*N]
    XY.sort()
    iX = [0]*N
    iY = [0]*N
    for i,xy in enumerate(XY):
        x,y = xy
        iX[i] = x
        iY[i] = y
    iY.sort()
    X = {x:i for i,x in enumerate(iX)}
    Y = {y:i for i,y in enumerate(iY)}

    c = [[0]*(N+1) for i in [0]*(N+1)]
    for x,y in XY:
        c[Y[y]+1][X[x]+1] = 1

    for i in range(N):
        ci1 = c[i+1]
        for j in range(N):
            ci1[j+1] += ci1[j]
    for i in range(N):
        ci1 = c[i+1]
        ci = c[i]
        for j in range(N):
            ci1[j+1] += ci[j+1]

    ans = 10**20
    for u in range(N):
        for d in range(u+K-1,N):
            l = 0
            r = K-1
            dY = iY[d]-iY[u]
            cd = c[d+1]
            cu = c[u]
            while r<N:
                if cd[r+1]+cu[l]-cu[r+1]-cd[l] >=K:
                    ans = min(ans, (iX[r] - iX[l])*dY)
                    l+=1
                else:r+=1

    print(ans)
main()

Solution (Python):
def main():
    N,K = map(int,input().split())
    XY = [list(map(int,input().split())) for _ in [0]*N]
    XY.sort()
    
    iX = [x for x,y in XY]
    iY = [y for x,y in XY]
    iY.sort()
    X = {x:i for i,x in enumerate(iX)}
    Y = {y:i for i,y in enumerate(iY)}

    c = [[0]*(N+1) for i in [0]*(N+1)]
    for x,y in XY:
        c[Y[y]+1][X[x]+1] = 1

    for i in range(N):
        ci1 = c[i+1]
        for j in range(N):
            ci1[j+1] += ci1[j]
    for i in range(N):
        ci1 = c[i+1]
        ci = c[i]
        for j in range(N):
            ci1[j+1] += ci[j+1]

    ans = 10**20
    for u in range(N):
        for d in range(u+K-1,N):
            l = 0
            r = K-1
            dY = iY[d]-iY[u]
            cd = c[d+1]
            cu = c[u]
            while r<N:
                if cd[r+1]+cu[l]-cu[r+1]-cd[l] >=K:
                    ans = min(ans, (iX[r] - iX[l])*dY)
                    l+=1
                else:r+=1

    print(ans)
main()