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):
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
for i in range(1):
    a.sort(key=lambda x:x[i])
    for j in range(n-1):
        for k in range(j+1,n):
            l = a[j][i]
            r = a[k][i]
            b = [a[j],a[k]]
            cnt = 2
            for _ in range(n):
                if _ == j or _ == k:
                    continue
                if l < a[_][i] < r:
                    cnt += 1
                    b += [a[_]]
            if cnt < K: continue
            b.sort(key=lambda x:x[i^1])
            
            for _ in range(cnt-K+1):
                u = max(x[i^1] for x in b[_:_+K])
                d = min(x[i^1] for x in b[_:_+K])
                res = min(res, (r-l)*(u-d))
                
print(res)

Solution (Python):
from collections import deque
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    n,k=MI()
    xx=set()
    yy=set()
    xy=[]
    for _ in range(n):
        x,y=MI()
        xy.append((x,y))
        xx.add(x)
        yy.add(y)
    xy.sort()
    xx=list(sorted(xx))
    yy = list(sorted(yy))
    xn=len(xx)
    yn=len(yy)
    ans=10**20
    for t in range(yn):
        y2=yy[t]
        for b in range(t):
            y1=yy[b]
            r=-1
            s=0
            i=j=0
            for l,x1 in enumerate(xx):
                while i<n and xy[i][0]<x1:
                    if y1 <= xy[i][1] <= y2: s -= 1
                    i += 1
                while s<k and r+1<xn:
                    r+=1
                    x2=xx[r]
                    while j<n and xy[j][0]<=x2:
                        if y1<=xy[j][1]<=y2:s+=1
                        j+=1
                if s>=k:
                    cur=(x2-x1)*(y2-y1)
                    if cur<ans:ans=cur
    print(ans)

main()

Solution (Python):
def main():
    from itertools import combinations
    import bisect
    N, K = map(int, input().split())
    xy = [tuple(map(int, input().split())) for i in range(N)]
    xy.sort(key=lambda x: x[0])
    X = [x[0] for x in xy]

    ans = 40**18
    for a, b in combinations(range(N), 2):
        A, B = max(xy[a][0], xy[b][0]), min(xy[a][0], xy[b][0])
        r = bisect.bisect_right(X, A)
        l = bisect.bisect_left(X, B)
        for c, d in combinations(range(N), 2):
            tmp = 0
            C, D = max(xy[c][1], xy[d][1]), min(xy[c][1], xy[d][1])

            for i in range(l, r):
                if xy[i][1] <= C and xy[i][1] >= D:
                    tmp += 1
            

            if tmp >= K and ans > (A-B) * (C - D):
                ans = (A-B) * (C - D)

    print(ans)
main()

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

n,k=map(int,input().split())
xy=[tuple(map(int,input().split())) for _ in range(n)]
X=sorted(set(xy[i][0] for i in range(n)))
Y=sorted(set(xy[i][1] for i in range(n)))


from itertools import combinations

ans=10**20
for x1,x2 in combinations(X,2):
    for y1,y2 in combinations(Y,2):
        c=0
        for x,y in xy:
            if x1<=x<=x2 and y1<=y<=y2:
                c+=1
        if c>=k:
            ans=min(ans,(x2-x1)*(y2-y1))
print(ans)

Solution (Python):
from itertools import accumulate, combinations

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())
cx_to_x = sorted(list(set(X)))
x_to_cx = {k : i for i, k in enumerate(cx_to_x)}
cy_to_y = sorted(list(set(Y)))
y_to_cy = {k : i for i, k in enumerate(cy_to_y)}
nx = len(cx_to_x)
ny = len(cy_to_y)
points = [[0] * nx for _ in range(ny)]
for x, y in zip(X, Y):
    points[y_to_cy[y]][x_to_cx[x]] += 1
cum = [[0] * (nx+1)] + [list(accumulate([0] + row)) for row in points]
for i in range(1, ny+1):
    for j in range(nx+1):
        cum[i][j] += cum[i-1][j]
ans = float('inf')
for x1, x2 in combinations(range(nx), 2):
    for y1, y2 in combinations(range(ny), 2):
        cnt = cum[y2+1][x2+1] - cum[y2+1][x1] - cum[y1][x2+1] + cum[y1][x1]
        if cnt >= K:
            area = (cx_to_x[x2] - cx_to_x[x1]) * (cy_to_y[y2] - cy_to_y[y1])
            ans = min(ans, area)
print(ans)

Solution (Python):
N,K = map(int,input().split())
XY = [tuple(map(int,input().split())) for i in range(N)]
xs = []
ys = []
for x,y in XY:
    xs.append(x)
    ys.append(y)
xs.sort()
ys.sort()

def is_ok(l,r,d,u):
    k = 0
    for x,y in XY:
        if l <= x <= r and d <= y <= u:
            k += 1
            if k >= K:
                return True
    return False

ans = float('inf')
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):
                l,r,d,u = xs[i],xs[j],ys[k],ys[l]
                if (r-l)*(u-d) >= ans: continue
                if is_ok(l,r,d,u):
                    ans = (r-l)*(u-d)
print(ans)

Solution (Python):
from itertools import combinations

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

ans = 10**20
for rect in combinations(XY, r=min(K, 4)):
    X = [x for x, _ in rect]
    Y = [y for _, y in rect]

    miX, mxX = min(X), max(X)
    miY, mxY = min(Y), max(Y)

    cnt = len([x for x, y in XY if miY <= y <= mxY and miX <= x <= mxX])
    if cnt >= K:
        ans = min(ans, (mxX - miX) * (mxY - miY))
print(ans)

Solution (Python):
n,k=map(int,input().split())
XY=[[0]*2 for i in range(n)]
X=[0]*n
Y=[0]*n
Z=[i for i in range(1,n+1)]
for i in range(n):
  X[i],Y[i]=map(int,input().split())
  XY[i]=[X[i],Y[i]]
X.sort()
Y.sort()
XX=dict(zip(X,Z))
YY=dict(zip(Y,Z))
XXX=dict(zip(Z,X))
YYY=dict(zip(Z,Y))
A=[[0]*n for i in range(n)]
for i in range(n):
  A[XX[XY[i][0]]-1][YY[XY[i][1]]-1]+=1
C=[[0]*(n+1) for i in range(n+1)]
for i in range(1,n+1):
  for j in range(1,n+1):
    C[i][j]=C[i-1][j]+C[i][j-1]-C[i-1][j-1]+A[i-1][j-1]
ans=10**20
for i in range(1,n):
  for j in range(i+1,n+1):
    for s in range(1,n):
      for t in range(s+1,n+1):
        if C[j][t]-C[j][s-1]-C[i-1][t]+C[i-1][s-1]<k:
          continue
        a=(XXX[j]-XXX[i])*(YYY[t]-YYY[s])
        if a<ans:
          ans=a
print(ans)

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

v.sort()

ans=10**20
for i in range(0,N-1):
    for j in range(i+1,N):
        data=[]
        for k in range(i,j+1):
            x,y=v[k]
            data.append(y)
        data.sort()
        if K>len(data):
            continue
        else:
            for k in range(0,len(data)-K+1):
                w=v[j][0]-v[i][0]
                h=data[k+K-1]-data[k]
                test=w*h
                if ans>test:
                    ans=test

print(ans)

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

ans = float('inf')
for i in range(N - K + 1):
    for j in range(i + K - 1, N):
        x = P[j][0] - P[i][0]
        if x == 0:
            continue

        Q = P[i: j + 1]
        Q.sort(key=lambda q: q[1])
        y = Q[-1][1] - Q[0][1]
        for k in range(0, len(Q) - K + 1):
            for l in range(k + K - 1, len(Q)):
                ny = Q[l][1] - Q[k][1]
                if ny == 0:
                    continue
                y = min(y, ny)
        ans = min(ans, x * y)

print(ans)

Solution (Python):





import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols
    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])
    return ret


class cumsum2d:  
    def __init__(self, ls: list):
        '''
        2次元のリストを受け取る
        '''
        from itertools import product
        H = len(ls)
        W = len(ls[0])
        self.ls_accum = [[0] * (W + 1)]
        for l in ls:
            self.ls_accum.append([0] + l)

        
        for i, j in product(range(1, H + 1), range(1, W + 1)):
            self.ls_accum[i][j] += self.ls_accum[i - 1][j]
        
        for i, j in product(range(1, H + 1), range(1, W + 1)):
            self.ls_accum[i][j] += self.ls_accum[i][j - 1]

    def total(self, i1, j1, i2, j2):
        '''
        点(i1,j1),(i1,j2),(i2,j1),(i2,j2)の4点が成す四角の中の合計を取り出す
        ただし i1<=i2, j1<=j2
        ただし、i軸に関しては[i1,i2),j軸に関しては[j1,j2)の半開区間である
        '''
        return self.ls_accum[i2][j2] - self.ls_accum[i1][j2] \
            - self.ls_accum[i2][j1] + self.ls_accum[i1][j1]


class ZaAtu:
    def __init__(self, ls):
        
        self.i_to_orig = sorted(set(ls))
        self.orig_to_i = {}
        for i, zahyou in enumerate(self.i_to_orig):
            self.orig_to_i[zahyou] = i
        self.len = len(self.i_to_orig)

    def __len__(self):
        return len(self.i_to_orig)


from itertools import product

N, K = read_ints()
X_ori, Y_ori = read_col(N, 2)
X = ZaAtu(X_ori)
Y = ZaAtu(Y_ori)
table = [[0] * Y.len for _ in range(X.len)]  
for x, y in zip(X_ori, Y_ori):
    i = X.orig_to_i[x]
    j = Y.orig_to_i[y]
    table[i][j] += 1

table = cumsum2d(table)

ans = (2 * 10**9)**2 + 114514
for i, j in product(range(X.len), range(Y.len)):  
    for ii, jj in product(range(i, X.len + 1), range(j, Y.len + 1)):  
        if table.total(i, j, ii, jj) >= K:
            S = (X.i_to_orig[ii - 1] - X.i_to_orig[i]) * \
                (Y.i_to_orig[jj - 1] - Y.i_to_orig[j])
            ans = min(ans, S)
print(ans)

Solution (Python):







def main():
    N, K = map(int, input().split())
    x, y = [None] * N, [None] * N
    for i in range(N):
        x[i], y[i] = map(int, input().split())
    
    points = [[i, x[i], y[i]] for i in range(N)]
    points_ysort = sorted(points, key=lambda p: p[2], reverse=True)
    points_ysort_rev = list(reversed(points_ysort))
    points_xsort = sorted(points, key=lambda p: p[1], reverse=False)
    points_xsort_rev = list(reversed(points_xsort))
    
    min_area = 4 * (10**18)
    outsides_top = []
    
    t = 0
    while t <= N-K:
        

        top_i, top_x, top_y = points_ysort[t]

        outsides_bottom = []
        b = 0
        while b < N:
            

            bottom_i, bottom_x, bottom_y = points_ysort_rev[b]

            if bottom_i == top_i:
                break

            
            n_outsides_left = 0
            l = 0
            while l < N:
                left_i, left_x, left_y = points_xsort[l]

                if left_x > top_x:
                    break

                if left_i in outsides_top or left_i in outsides_bottom:
                    l += 1
                    continue
                
                
                n_outsides_right = 0
                r = 0
                while r < N:
                    if N - t - b - n_outsides_left - n_outsides_right < K:
                        break

                    right_i, right_x, right_y = points_xsort_rev[r]

                    if right_i == left_i:
                        break
                    
                    if right_x < top_x:
                        break
                    
                    if right_i in outsides_top or right_i in outsides_bottom:
                        r += 1
                        continue

                    area = (top_y - bottom_y) * (right_x - left_x)
                    if area < min_area:
                        min_area = area
                    
                    
                    n_outsides_right += 1
                    r += 1
                
                
                n_outsides_left += 1
                l += 1
            
            outsides_bottom.append(bottom_i)
            b += 1
        
        outsides_top.append(top_i)
        t += 1

    return min_area


print(main())

Solution (Python):
n,K = map(int,input().split())
X, Y = [], []
dots = []
for _ in range(n):
    x,y = map(int,input().split())
    dots.append((x,y))
    X.append(x)
    Y.append(y)
X.sort()
Y.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):
                x1,x2 = X[i], X[j]
                y1,y2 = Y[k], Y[l]
                cnt = 0
                for dot in dots:
                    if x1<=dot[0]<=x2 and y1<=dot[1]<=y2:
                        cnt += 1
                if cnt >= K:
                    ans = min(ans, (x2-x1)*(y2-y1))
print(ans)

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

xy.sort()
ans = 10**20

for i in range(n):
    for j in range(i,n):
        xy_tmp = xy[i:j+1]
        if len(xy_tmp) >= k:
            l1 = xy_tmp[0][0]
            r1 = xy_tmp[-1][0]
            xy_tmp.sort(key = lambda x: x[1])
            for jj in range(len(xy_tmp) - k + 1):
                ans = min(ans, (r1-l1) * (xy_tmp[k+jj-1][1] - xy_tmp[jj][1]))

print(ans)

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

    ans = 10 ** 20

    for i in range(n):
        for j in range(i+1, n):
            for ii in range(n):
                for jj in range(ii+1, n):
                    l = min(xy[i][0], xy[j][0])
                    r = max(xy[i][0], xy[j][0])
                    d = min(xy[ii][1], xy[jj][1])
                    u = max(xy[ii][1], xy[jj][1])
                    cnt = 0
                    for x,y in xy:
                        if l <= x <= r and d <= y <= u:
                            cnt += 1
                    if cnt >= k:
                        ans = min(ans, (r-l) * (u - d))

    print(ans)

if __name__ == '__main__':
    main()

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

xy.sort()
ans = 10**20

for i in range(n):
    for j in range(i,n):
        xy_tmp = xy[i:j+1]
        if len(xy_tmp) >= k:
            l1 = xy_tmp[0][0]
            r1 = xy_tmp[-1][0]
            xy_tmp.sort(key = lambda x: x[1])
            for jj in range(len(xy_tmp) - k + 1):
                ans = min(ans, (r1-l1) * (xy_tmp[k+jj-1][1] - xy_tmp[jj][1]))

print(ans)

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

for i in l:
    for j in l:
        if i[0] >= j[0]:
            continue
        for s in l1:
            count = 0
            for w,h in l1:
                if i[0] <= w <= j[0] and s[1] <= h:
                    count += 1
                if count==k:
                    ans = (min(ans,(j[0]-i[0])*(h-s[1])))
                    break
                
print(ans)

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

for i in l:
    for j in l:
        if i[0] >= j[0]:
            continue
        for s in l1:
            count = 0
            for w,h in l1:
                if i[0] <= w <= j[0] and s[1] <= h:
                    count += 1
                if count==k:
                    ans = (min(ans,(j[0]-i[0])*(h-s[1])))
                    break
                
print(ans)

Solution (Python):

from itertools import combinations
import sys
try:
    from typing import List
except ImportError:
    pass


def solve(N: int, K: int, x: "List[int]", y: "List[int]"):
    pts = sorted(zip(x, y))
    ys = sorted(y)
    ans = float("inf")
    for y1, y2 in combinations(ys, 2):
        xs = [x for x, y in pts if y1 <= y <= y2]
        if len(xs) >= K:
            ans = min(
                ans,
                (y2 - y1) * min(x2 - x1 for x1, x2 in zip(xs, xs[K - 1:]))
            )
    print(ans)


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

P = []

for i in range(N):
    P.append(list(map(int,input().split())))

x = []
y = []
for i in range(N):
    x.append(P[i][0])
    y.append(P[i][1])

x.sort()
y.sort()

num = [[0]*len(y) for i in range(len(x))]
data = [[0]*len(y) for i in range(len(x))]

for i in range(N):
    for j in range(len(x)):
        if P[i][0] == x[j]:
            x0 = j
            break
    for j in range(len(y)):
        if P[i][1] == y[j]:
            y0 = j
            break
    data[x0][y0] += 1

num[0][0] = data[0][0]

for i in range(1,len(x)):
    num[i][0] = num[i-1][0] + data[i][0]

for i in range(1,len(y)):
    num[0][i] = num[0][i-1] + data[0][i]

for i in range(1,len(x)):
    for j in range(1,len(y)):
        num[i][j] = num[i-1][j] + num[i][j-1] - num[i-1][j-1] + data[i][j]

can = []
for i in range(1,len(x)-1):
    for j in range(i+1,len(x)):
        for k in range(1,len(y)-1):
            for l in range(k+1,len(y)):
                if num[j][l] - num[j][k-1] - num[i-1][l] + num[i-1][k-1] >= K:
                    can.append((x[j]-x[i])*(y[l]-y[k]))
for i in range(len(x)):
    for j in range(1,len(y)-1):
        for k in range(j+1,len(y)):
            if num[i][k] - num[i][j-1] >= K:
                can.append((x[i]-x[0])*(y[k]-y[j]))

for i in range(1,len(x)-1):
    for j in range(i+1,len(x)):
        for k in range(len(y)):
            if num[j][k] - num[i-1][k] >= K:
                can.append((x[j]-x[i])*(y[k]-y[0]))

for i in range(len(x)):
    for j in range(len(y)):
        if num[i][j] >= K:
            can.append((x[i]-x[0])*(y[j]-y[0]))







print(min(can))

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

xy.sort()

ans = float("inf")
for i in range(n):
    for j in range(i + k - 1, n):
        width = xy[j][0] - xy[i][0]
        y = [e for _, e in xy[i:j+1]]
        y.sort()
        for e1, e2 in zip(y, y[k-1:]):
            height = e2 - e1
            area = width * height
            ans = min(ans, area)

print(ans)

Solution (Python):
N, K= map(int, input().split())
li = [list(map(int, input().split())) for i in range(N)]
xx = [p[0] for p in li]
yy = [p[1] for p in li]
xx.sort()
yy.sort()
Min = (xx[N-1]-xx[0])*(yy[N-1]-yy[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):
                cnt = 0
                for p in li:
                    [x, y] = p
                    if xx[xi] <= x <= xx[xj] and yy[yi] <= y <= yy[yj]:
                        cnt += 1
                if cnt >= K:
                    Min = min(Min, (xx[xj]-xx[xi])*(yy[yj]-yy[yi]))
print(Min)

Solution (Python):
import sys
input = sys.stdin.readline
INF = 10**20
MOD = 10**9 + 7
from bisect import insort_left

def main():
    n,k = map(int,input().split())
    XY = [tuple(map(int,input().split())) for _ in range(n)]  
    XY.sort(key = lambda x:x[0])
    
    ans = INF
    for l in range(n - k + 1):
        Y = [XY[i][1] for i in range(l,l + k - 1)]
        Y.sort()
        dif = -1
        for r in range(l + k - 1, n):
            dif += 1
            insort_left(Y,XY[r][1])
            w = INF
            for i in range(dif + 1):
                w = min(w, Y[i + k - 1] - Y[i])
            ans = min(ans, w * (XY[r][0] - XY[l][0]))
    
    print(ans)   

if __name__=='__main__':
    main()

Solution (Python):
import sys
def input():
    return sys.stdin.readline()[:-1]
N,K=map(int,input().split())
s=[tuple(map(int,input().split())) for i in range(N)]
lx,ly=[],[]
for i in s:
    lx.append(i[0])
    ly.append(i[1])
lx.sort()
ly.sort()
a=10**20
t=N-K
for i in range(N-1):
    for j in range(i+1,N):
        for k in range(N-1):
            for m in range(k+1,N):
                S=(lx[j]-lx[i])*(ly[m]-ly[k])
                if S>=a:
                    continue
                c=0
                for n in s:
                    if lx[i]<=n[0]<=lx[j] and ly[k]<=n[1]<=ly[m]:
                        continue
                    c+=1
                    if c>t:
                        break
                else:
                    a=S
print(a)

Solution (Python):
n,k=map(int,input().split())
points=[]
for _ in range(n):
    x,y=map(int,input().split())
    points.append((x,y))
points.sort()
ans=float('inf')
for i in range(n-k+1):
    for j in range(i+k-1,n):
        y_sorted=sorted(points[i:j+1],key=lambda x:x[1])
        height_min=float('inf')
        for l in range(j-i-k+2):
            height_min=min(height_min,y_sorted[l+k-1][1]-y_sorted[l][1])
            ans=min(ans,(points[j][0]-points[i][0])*height_min)
print(ans)

Solution (Python):


N,K=map(int,input().split())

point=[]
for _ in range(N):
    point.append(list(map(int,input().split())))

point.sort(key=lambda x: x[0])

shin=10**200
able=N-K
for i in range(able+1):
    temp_high=point[:N-i]
    for j in range(able+1-i):
        temp_low=temp_high[j:]
        for k in range(able+1-i-j):
            temp_left=temp_low[:]
            temp_left.sort(key=lambda x: x[1])
            temp_left=temp_left[k:len(temp_left)-(able+1-i-j)+k+1]
            
            
            if temp_left:
                ans=temp_left[:]
            elif temp_low:
                ans=temp_low[:]
            else:
                ans=temp_high[:]
            x=[]
            y=[]
            for item in ans:
                x.append(item[0])
                y.append(item[1])
            
            
            num=((max(x)-min(x))*(max(y)-min(y)))
            shin=min(shin,num)

print(shin)

Solution (Python):
def main():
    N,K = map(int,input().split())
    XY = [list(map(int,input().split())) for _ in [0]*N]
    
    iX = sorted(x for x,y in XY)
    iY = sorted(y for x,y in XY)
    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 = 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):
from itertools import combinations

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

ans = 10**18*5

for x in combinations(range(N), 2):
    u = max(P[x[0]][0], P[x[1]][0])
    d = min(P[x[0]][0], P[x[1]][0])
    for y in combinations(range(N), 2):
        r = max(P[y[0]][1], P[y[1]][1])
        l = min(P[y[0]][1], P[y[1]][1])
        count = 0
        for i in range(N):
            if d <= P[i][0] <= u and l <= P[i][1] <= r:
                count += 1
        if count >= K:
            ans = min(ans, (u - d) * (r - l))

print(ans)

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

points.sort()
ans = float('inf')

for i in range(n-k+1):
  for j in range(i+k-1,n):
    y_sorted = sorted(points[i:j+1], key = lambda x:x[1])
    height_min = float('inf')
    for l in range(j-i-k+2):
      height_min = min(height_min,y_sorted[l+k-1][1] - y_sorted[l][1])
    ans = min(ans, (points[j][0]-points[i][0])*height_min)
print(ans)

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, atan, degrees
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect

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()))
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=map(int,input().split())
x,y,xy=[],[],[]
for _ in range(n):
  a,b=map(int,input().split())
  x.append(a)
  y.append(b)
  xy.append((a,b))
x.sort()
y.sort()
ans=float('inf')
for i in range(n-1):
  x1=x[i]
  for j in range(i+1,n):
    x2=x[j]
    for l in range(n-1):
      y1=y[l]
      for m in range(l+1,n):
        y2=y[m]
        cnt=0
        for o in range(n):
          x3,y3=xy[o]
          if x1<=x3<=x2 and y1<=y3<=y2:
            cnt+=1
        if cnt>=k:
          ans=min(ans,(x2-x1)*(y2-y1))
print(ans)

Solution (Python):

import math
import heapq
import bisect
import numpy as np
from collections import Counter


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

ans = 10**20

for lx in range(N):
    for rx in range(lx+1,N+1):
        L2 = L[lx:rx]
        L2 = sorted(L2, key=lambda x:x[1])
        for ly in range(len(L2)):
            L3 = L2[ly:ly+K]
            if len(L3) >= K:
                ans = min(ans, (L[rx-1][0]-L[lx][0])*(L3[-1][1]-L3[0][1]))

print(ans)

Solution (Python):
from itertools import combinations
N, K, *L = map(int, open(0).read().split())
L = [(x,y) for x,y in zip(*[iter(L)]*2)]
ans = float('inf')
for m in combinations(L,2):
  for n in combinations(L,2):
    mx = min(m,key=lambda x:x[0])[0]
    Mx = max(m,key=lambda x:x[0])[0]
    my = min(n,key=lambda x:x[1])[1]
    My = max(n,key=lambda x:x[1])[1]
    cnt = 0
    for x,y in L:
      if mx<=x<=Mx and my<=y<=My:
        cnt += 1
    if cnt>=K:
      ans = min(ans, (Mx-mx)*(My-my))
print(ans)

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

xy.sort()

ans = INF
for i in range(n):
	for j in range(i + k - 1, n):
		width = xy[j][0] - xy[i][0]

		y = [xy[idx][1] for idx in range(i, j + 1)]
		y.sort()

		for e1, e2 in zip(y, y[k-1:]):
			height = e2 - e1
			area = width * height
			ans = min(ans, area)

print(ans)

Solution (Python):
from collections import defaultdict

N, K = map(int, input().split())
xy = [list(map(int, input().split())) for _ in range(N)]
INF = 10 ** 19

acc = defaultdict(int)

x = [-INF]
y = [-INF]

for ex, ey in xy:
	acc[(ex, ey)] = 1
	x.append(ex)
	y.append(ey)

x.sort()
y.sort()

for i in range(N):
	for j in range(N + 1):
		acc[(x[i+1], y[j])] += acc[(x[i], y[j])]

for j in range(N):
	for i in range(N + 1):
		acc[(x[i], y[j+1])] += acc[(x[i], y[j])]

ans = INF
for i in range(1, N + 1):
	for j in range(i + 1, N + 1):
		for k in range(1, N + 1):
			for l in range(k + 1, N + 1):
				cnt = acc[(x[j], y[l])] - acc[(x[j], y[k-1])] - acc[(x[i-1], y[l])] + acc[(x[i-1], y[k-1])]
				if cnt >= K:
					sq = (x[j] - x[i]) * (y[l] - y[k])
					ans = min(ans, sq)

print(ans)

Solution (Python):
from itertools import combinations
N, K = map(int, input().split())
xy = [tuple(map(int, input().split())) for i in range(N)]

ans = float("inf")
for p1, p2 in combinations(xy, 2):
    x1 = p1[0]
    x2 = p2[0]
    if x2 < x1:
        x1, x2 = x2, x1
        
    for p3, p4 in combinations(xy, 2):
        y1 = p3[1]
        y2 = p4[1]
        if y2 < y1:
            y1, y2 = y2, y1
        
        count = 0
        for x, y in xy:
            if x >= x1 and x <= x2 and y >= y1 and y <= y2:
                count += 1

        if count >= K:
            ans = min(ans, (x2-x1)*(y2-y1))


print(ans)

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()

def count_inside(x1, x2, y1, y2, points):
    cnt = 0
    if x2 < x1:
        x1, x2 = x2, x1
    if y2 < y1:
        y1, y2 = y2, y1

    for p in points:
        if x1 <= p[0] <= x2 and y1 <= p[1] <= y2:
            cnt += 1
    return cnt

def main():
    N, K = LI()
    points = []
    for _ in range(N):
        x, y = LI()
        points.append((x, y))
    points = sorted(points, key=lambda x: (x[0], x[1]))
    X = [p[0] for p in points]
    Y = [p[1] for p in points]
    area = inf
    for i in range(N):
        x1 = X[i]
        for j in range(i+1, N):
            x2 = X[j]
            for k in range(N):
                y1 = Y[k]
                for l in range(k+1, N):
                    y2 = Y[l]
                    if K == count_inside(x1, x2, y1, y2, points):
                        _area = abs(x1-x2) * abs(y1-y2)
                        area = min(_area, area)
    print(area)

main()