Problem:
 Score : 400 points    Problem Statement We have N points in a two-dimensional plane. The coordinates of the i -th point (1 \leq i \leq N) are (x_i,y_i) . Let us consider a rectangle whose sides are parallel to the coordinate axes that contains K or more of the N points in its interior. Here, points on the sides of the rectangle are considered to be in the interior. Find the minimum possible area of such a rectangle.      Constraints  2 \leq K \leq N \leq 50   -10^9 \leq x_i,y_i \leq 10^9 (1 \leq i \leq N)   x_i≠x_j (1 \leq i<j \leq N)   y_i≠y_j (1 \leq i<j \leq N)   All input values are integers. (Added at 21:50 JST)         Input Input is given from Standard Input in the following format:  N  K  x_1  y_1  :  x_{N}  y_{N}       Output Print the minimum possible area of a rectangle that satisfies the condition.        Sample Input 1 4 4
1 4
3 3
6 2
8 1      Sample Output 1 21  One rectangle that satisfies the condition with the minimum possible area has the following vertices: (1,1) , (8,1) , (1,4) and (8,4) . Its area is (8-1) × (4-1) = 21 .       Sample Input 2 4 2
0 0
1 1
2 2
3 3      Sample Output 2 1       Sample Input 3 4 3
-1000000000 -1000000000
1000000000 1000000000
-999999999 999999999
999999999 -999999999      Sample Output 3 3999999996000000001  Watch out for integer overflows.

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,K = list(map(int, input().split()))
xy = [tuple(map(int, input().split())) for _ in range(n)]
xs = list(set([item[0] for item in xy]))
ys = list(set([item[1] for item in xy]))
xs.sort()
ys.sort()
dx = {x:i for i,x in enumerate(xs)}
dy = {y:i for i,y in enumerate(ys)}
lx = len(xs)
ly = len(ys)
c = [[0]*ly for _ in range(lx)]
for x,y in xy:
    c[dx[x]][dy[y]] += 1
from itertools import combinations, combinations_with_replacement
def cumsum2(v):
    
    h,w = len(v), len(v[0])
    v.insert(0, [0]*w)
    for l in v:
        l.insert(0, 0)
    for i in range(1,h+1):
        for j in range(1,w+1):
            v[i][j] = v[i-1][j] + v[i][j-1] - v[i-1][j-1] + v[i][j]
    return v
cumsum2(c)
ans = float("inf")
for i,j,k,l in combinations_with_replacement(range(n),4):

    mx = min(xy[i][0], xy[j][0], xy[k][0], xy[l][0])
    my = min(xy[i][1], xy[j][1], xy[k][1], xy[l][1])
    Mx = max(xy[i][0], xy[j][0], xy[k][0], xy[l][0])
    My = max(xy[i][1], xy[j][1], xy[k][1], xy[l][1])
    ix,iy = dx[mx], dy[my]
    Ix,Iy = dx[Mx], dy[My]
    count = c[Ix+1][Iy+1] - c[Ix+1][iy] - c[ix][Iy+1] + c[ix][iy]
    if count>=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 i in range(N)]
xy.sort()
ans = 10**20
for l in range(N):
    for r in range(l,N,1):
        tmp=[]
        for i in range(l,r+1,1):
            tmp.append(xy[i][1])
        tmp.sort()
        for d in range(0,len(tmp)-K+1,1):
            ans = min(ans,(tmp[d+K-1]-tmp[d])*(xy[r][0]-xy[l][0]))

print(ans)

Solution (Python):
def cnt(xl, xr, yb, yt):
    c = 0
    for i in range(n):
        if xl <= xy[i][0] <= xr and yb <= xy[i][1] <= yt:
            c += 1
    return c


n, k = map(int, input().split())

x = []
y = []
xy = []
for i in range(n):
    u, v = map(int, input().split())
    x.append(u)
    y.append(v)
    xy.append([u,v])
    
x.sort()
y.sort()

ans = (x[-1]-x[0])*(y[-1]-y[0])
for l in range(n-1):
    for r in range(l+1, n):
        xl, xr = x[l], x[r]
        for b in range(n-1):
            for t in range(b+1, n):
                yb, yt = y[b], y[t]
                s = (xr-xl)*(yt-yb)
                if s < ans:
                    ck = cnt(xl, xr, yb, yt)
                    
                    if ck >= k:
                        ans = s
print(ans)

Solution (Python):
def da_generate(h,w,a):
    da = [[0]*w for j in range(h)]
    da[0][0] = a[0][0]
    for i in range(1,w):
        da[0][i] = da[0][i-1]+a[0][i]
    for i in range(1,h):
        cnt_w = 0
        for j in range(w):
            cnt_w += a[i][j]
            da[i][j] = da[i-1][j]+cnt_w
    return da

def da_calc(da,p,q,x,y):
    if p > x or q > y:
        return 0
    if p == 0 and q == 0:
        return da[x][y]
    if p == 0:
        return da[x][y]-da[x][q-1]
    if q == 0:
        return da[x][y]-da[p-1][y]
    return da[x][y]-da[p-1][y]-da[x][q-1]+da[p-1][q-1]

n , k = map(int,input().split())
mototen = []
atuten = []
zax = []
zay = []
for i in range(n):
    x , y = map(int,input().split())
    mototen.append((x,y))
    zax.append(x)
    zay.append(y)
zax.sort()
zay.sort()

a = [[0 for i in range(len(zay))] for j in range(len(zax))]

for x , y in mototen:
    atx = zax.index(x)
    aty = zay.index(y)
    a[atx][aty] += 1
b = da_generate(len(zax),len(zay),a)
ans = float("inf")
for p in range(len(zax)-1):
    for q in range(len(zay)-1):
        for x in range(p+1,len(zax)):
            for y in range(q+1,len(zax)):
                kar = da_calc(b,p,q,x,y)
                if kar >= k:
                    men = (zax[x]-zax[p])*(zay[y]-zay[q])
                    ans = min(ans,men)
print(ans)

Solution (Python):
from copy import deepcopy
import sys
def main():
    input = sys.stdin.readline
    n, k = map(int, input().split())
    x, y = [], []
    for i in range(n):
        x_, y_ = map(int, input().split())
        x.append(x_)
        y.append(y_)
    X, Y = deepcopy(x), deepcopy(y)
    x.sort()
    y.sort()
    ans = (x[-1] - x[0]) * (y[-1] - y[0])
    for i in range(n):
        for j in range(i + 1, n):
            for K in range(n):
                for l in range(K + 1, n):
                    cnt = 0
                    x1, x2, y1, y2 = x[i], x[j], y[K], y[l]
                    for m in range(n):
                        if x1 <= X[m] <= x2 and y1 <= Y[m] <= y2:
                            cnt += 1
                    if cnt >= k:
                        ans = min(ans, (x2 - x1) * (y2 - y1))
    print(ans)
if __name__ == "__main__":
    main()

Solution (Python):
import sys
import math
import collections
import bisect
import itertools



sys.setrecursionlimit(10 ** 7)
INF = 10 ** 20
MOD = 10 ** 9 + 7


ni = lambda: int(sys.stdin.readline().rstrip())
ns = lambda: map(int, sys.stdin.readline().rstrip().split())
na = lambda: list(map(int, sys.stdin.readline().rstrip().split()))
na1 = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().rstrip().split()))




def main():
    n, k = ns()
    pos = []
    for _ in range(n):
        x, y = ns()
        pos.append((x, y))

    ans = INF
    for tmp in itertools.combinations_with_replacement(pos, 4):
        xl = max(tmp, key=lambda t: t[0])[0]
        xs = min(tmp, key=lambda t: t[0])[0]
        yl = max(tmp, key=lambda t: t[1])[1]
        ys = min(tmp, key=lambda t: t[1])[1]

        cnt = 0
        for xi, yi in pos:
            if xs <= xi <= xl and ys <= yi <= yl:
                cnt += 1
        if cnt >= k:
            ans = min(ans, (xl - xs) * (yl - ys))

    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
import sys
import math
import collections
import bisect
import itertools



sys.setrecursionlimit(10 ** 7)
INF = 10 ** 20
MOD = 10 ** 9 + 7


ni = lambda: int(sys.stdin.readline().rstrip())
ns = lambda: map(int, sys.stdin.readline().rstrip().split())
na = lambda: list(map(int, sys.stdin.readline().rstrip().split()))
na1 = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().rstrip().split()))




def main():
    n, k = ns()
    pos = []
    for _ in range(n):
        x, y = ns()
        pos.append((x, y))

    ans = INF
    for tmp in itertools.combinations_with_replacement(pos, 4):
        xl = max(tmp, key=lambda t: t[0])[0]
        xs = min(tmp, key=lambda t: t[0])[0]
        yl = max(tmp, key=lambda t: t[1])[1]
        ys = min(tmp, key=lambda t: t[1])[1]

        cnt = 0
        for xi, yi in pos:
            if xs <= xi <= xl and ys <= yi <= yl:
                cnt += 1
        if cnt >= k:
            ans = min(ans, (xl - xs) * (yl - ys))

    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
from itertools import combinations


N, K, *XY = map(int, open(0).read().split())
X = sorted(XY[::2])
Y = sorted(XY[1::2])

ans = 10 ** 20
for x1, x2 in combinations(X, 2):
    for y1 in Y[:-1]:
        y2s = sorted(y for x, y in zip(*[iter(XY)] * 2) if x1 <= x <= x2 and y1 <= y)
        if len(y2s) < K:
            continue
        ans = min(ans, (x2 - x1) * (y2s[K - 1] - y1))
print(ans)

Solution (Python):

import numpy as np

N, K, *XY = map(int, open(0).read().split())

X = XY[::2]
comp_X = {}
decomp_X = {}
for i, x in enumerate(sorted(set(X))):
    comp_X[x] = i
    decomp_X[i] = x

Y = XY[1::2]
comp_Y = {}
decomp_Y = {}
for i, y in enumerate(sorted(set(Y))):
    comp_Y[y] = i
    decomp_Y[i] = y

I = len(comp_X)
J = len(comp_Y)
comp_XY = [(comp_X[x], comp_Y[y]) for x, y in zip(X, Y)]
acc = np.zeros((I + 1, J + 1), np.int32)
for c_x, c_y in comp_XY:
    acc[c_x + 1][c_y + 1] += 1
acc = np.add.accumulate(acc, axis=0)
acc = np.add.accumulate(acc, axis=1)

ans = float("inf")
for i in range(1, I + 1):
    for j in range(1, J + 1):
        cur = acc[i:, j:] + acc[:-i, :-j] - acc[:-i, j:] - acc[i:, :-j]
        for k, row in enumerate(cur):
            for l, val in enumerate(row):
                if val >= K:
                    ans = min(
                        ans,
                        (decomp_X[k + i - 1] - decomp_X[k])
                        * (decomp_Y[l + j - 1] - decomp_Y[l]),
                    )
print(ans)

Solution (Python):
import numpy as np

N, K, *XY = map(int, open(0).read().split())

X = XY[::2]
comp_X = {}
decomp_X = {}
for i, x in enumerate(sorted(set(X))):
    comp_X[x] = i
    decomp_X[i] = x

Y = XY[1::2]
comp_Y = {}
decomp_Y = {}
for i, y in enumerate(sorted(set(Y))):
    comp_Y[y] = i
    decomp_Y[i] = y

I = len(comp_X)
J = len(comp_Y)
comp_XY = [(comp_X[x], comp_Y[y]) for x, y in zip(X, Y)]
acc = np.zeros((I + 1, J + 1), np.int32)
for c_x, c_y in comp_XY:
    acc[c_x + 1][c_y + 1] += 1
acc = np.add.accumulate(acc, axis=0)
acc = np.add.accumulate(acc, axis=1)

ans = float("inf")
for i in range(1, I + 1):
    for j in range(1, J + 1):
        cur = acc[i:, j:] + acc[:-i, :-j] - acc[:-i, j:] - acc[i:, :-j]
        for k, row in enumerate(cur):
            for l, val in enumerate(row):
                if val >= K:
                    ans = min(
                        ans,
                        (decomp_X[k + i - 1] - decomp_X[k])
                        * (decomp_Y[l + j - 1] - decomp_Y[l]),
                    )
print(ans)

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

ans = 10**20+1
for a in range(n):
    for b in range(a+1,n):
        axy = xyl[a]
        bxy = xyl[b]
        ax,ay = axy
        bx,by = bxy
        l = min(ax,bx)
        r = max(ax,bx)
        t = max(ay,by)
        bo = min(ay,by)
        v = 0
        for x,y in xyl:
            if l <= x <= r and bo <= y <= t:
                v += 1
        if v >= k:
            area = (r-l)*(t-bo)
            ans = min(ans, area)

        for c in range(b+1,n):
            cxy = xyl[c]
            cx,cy = cxy
            l = min(ax,bx,cx)
            r = max(ax,bx,cx)
            t = max(ay,by,cy)
            bo = min(ay,by,cy)
            v = 0
            for x,y in xyl:
                if l <= x <= r and bo <= y <= t:
                    v += 1
            if v >= k:
                area = (r-l)*(t-bo)
                ans = min(ans, area)

            for d in range(c+1,n):
                dxy = xyl[d]
                dx,dy = dxy
                left = min(ax,bx,cx,dx)
                right = max(ax,bx,cx,dx)
                top = max(ay,by,cy,dy)
                bottom = min(ay,by,cy,dy)
                cnt = 0
                for x,y in xyl:
                    if left <= x <= right and bottom <= y <= top:
                        cnt += 1
                if cnt >= k:
                    area = (right-left)*(top-bottom)
                    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()

ans = float('inf')
for l in range(N-1):
    for r in range(l+1,N):
        w = xs[r] - xs[l]
        for d in range(N-1):
            for u in range(d+1,N):
                h = ys[u] - ys[d]
                if ans <= w*h: continue
                c = 0
                for x,y in XY:
                    if xs[l] <= x <= xs[r] and ys[d] <= y <= ys[u]:
                        c += 1
                        if c >= K:
                            ans = w*h
                            break
print(ans)

Solution (Python):
from itertools import groupby, accumulate, product, permutations, combinations
def compress(arr):
    *XS, = set(arr)
    XS.sort()
    return {e: i+1 for i, e in enumerate(XS)},{i+1: e for i, e in enumerate(XS)}

def solve():
  ans = float('inf')
  N, K = map(int, input().split())
  X,Y = [0]*N,[0]*N
  for i in range(N):
    X[i],Y[i] = map(int, input().split())
  x_c,x_r = compress(X)
  y_c,y_r = compress(Y)
  n_x = len(x_c)
  n_y = len(y_c)
  num = [[0]*(N+1) for _ in range(N+1)]
  for i in range(N):
    X[i] = x_c[X[i]]
    Y[i] = y_c[Y[i]]
    num[X[i]][Y[i]] += 1
  cum2 = [[0]*(N+1) for _ in range(N+1)]
  for i in range(1,N+1):
    for j in range(1,N+1):
      cum2[i][j] = cum2[i-1][j]+cum2[i][j-1]-cum2[i-1][j-1]+num[i][j]
  for x1,x2 in combinations(range(1,n_x+1),2):
    x_l = x_r[x2]-x_r[x1]
    for y1,y2 in combinations(range(1,n_y+1),2):
      k = cum2[x2][y2]+cum2[x1-1][y1-1]-cum2[x1-1][y2]-cum2[x2][y1-1]
      if k>=K:
        y_l = y_r[y2]-y_r[y1]
        ans = min(ans,x_l*y_l)
  return ans
print(solve())

Solution (Python):
n,k=map(int,input().split())
x=[]
y=[]
xy=[]
for _ in range(n):
  xx,yy=map(int,input().split())
  xy.append((xx,yy))
  x.append(xx)
  y.append(yy)
xx=sorted(x)
yy=sorted(y)
ans=10**20
for sxi in range(n-1):
  for syi in range(n-1):
    for tyi in range(1,n):
      sx,sy,ty=xx[sxi],yy[syi],yy[tyi]
      ax=sorted([xxx for xxx,yyy in xy if sx<=xxx and sy<=yyy<=ty])
      if len(ax)<k:continue
      tx=ax[k-1]
      ans=min(ans,(tx-sx)*(ty-sy))
print(ans)

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

ans = float('inf')
for i in range(N):
  for j in range(N):
    for k in range(N):
      for l in range(N):
        x1= xy[i][0]
        x2 = xy[j][0]
        y1 = xy[k][1]
        y2 = xy[l][1]
        cnt = 0
        if x1 < x2 and y1 < y2:
          for n in range(N):
            if x1 <= xy[n][0] <= x2 and y1 <= xy[n][1] <= y2:
              cnt += 1

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

Solution (Python):
n, k = map(int, input().split())
f = [list(map(int, input().split())) for _ in range(n)]
f.sort()
ans = 1145141919810893364364
for i in range(n - k + 1):
    for j in range(i + k - 1, n):
        a = [f[l][1] for l in range(i, j + 1)]
        a.sort()
        for l in range(j - i - k + 2):
            ans = min(ans, (f[j][0] - f[i][0]) * (a[l + k - 1] - a[l]))
print(ans)

Solution (Python):
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


def main():

    N, K = in_nn()

    X = []
    Y = []
    for i in range(N):
        x, y = in_nn()
        X.append(x)
        Y.append(y)

    sort_x = sorted(set(X))
    sort_y = sorted(set(Y))

    nx = len(sort_x)
    ny = len(sort_y)

    total_sum = [[0 for _ in range(nx + 1)] for _ in range(ny + 1)]

    for i in range(N):
        x, y = X[i], Y[i]
        ix = sort_x.index(x)
        iy = sort_y.index(y)
        total_sum[iy + 1][ix + 1] += 1

    for y in range(ny + 1):
        for x in range(nx):
            total_sum[y][x + 1] += total_sum[y][x]

    for x in range(nx + 1):
        for y in range(ny):
            total_sum[y + 1][x] += total_sum[y][x]

    def calc_area(u, d, l, r):
        return total_sum[d][r] - total_sum[u][r] - total_sum[d][l] + total_sum[u][l]

    ans = 10**19
    for y1 in range(ny + 1):
        for y2 in range(y1 + 2, ny + 1):
            for x1 in range(nx + 1):
                for x2 in range(x1 + 2, nx + 1):
                    if calc_area(y1, y2, x1, x2) >= K:
                        area = (sort_x[x2 - 1] - sort_x[x1]) * (sort_y[y2 - 1] - sort_y[y1])
                        ans = min(ans, area)

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
def main():
    N,K=mi()
    G = []

    X=[]
    Y=[]
    for i in range(N):
        x,y = mi()
        G.append((x,y))
        X.append(x)
        Y.append(y)

    def count(downx,upx,downy,upy):
        _count = 0
        for i in range(N):
            x,y = G[i]
            if downx<=x<=upx and downy<=y<=upy:
                _count += 1
        
        return _count

    ans = INF
    for downx in X:
        for upx in X:
            if upx <= downx: continue
            for downy in Y:
                for upy in Y:
                    if upy <= downy: continue

                    if count(downx,upx,downy,upy) >= K:
                        ans = min(ans,abs(upx-downx) * abs(upy-downy))
                        



    print(ans)

            



if __name__ == "__main__":
    main()

Solution (Python):
N, K, *XY = [int(_) for _ in open(0).read().split()]
XY = sorted(zip(XY[::2], XY[1::2]))
ans = float('inf')
for i in range(N):
    for j in range(i + K - 1, N):
        xlen = XY[j][0] - XY[i][0]
        Y = sorted(y for x, y in XY[i:j + 1])
        ylen = min(y2 - y1 for y1, y2 in zip(Y, Y[K - 1:]))
        ans = min(ans, xlen * ylen)
print(ans)

Solution (Python):
import numpy as np
from numba import njit
N, K, *XY = [int(_) for _ in open(0).read().split()]
XY = np.array(XY, dtype=np.int64).reshape((N, 2)).T
X = np.sort(XY[0])
Y = np.sort(XY[1])

@njit
def solve(XY, X, Y):
    v = 4 * 10**18 + 1
    ans = np.array([0, 0, 0, 0], dtype=np.int64)
    for i1 in range(N - 1):
        x1=X[i1]
        for i2 in range(i1 + 1, N):
            x2=X[i2]
            for j1 in range(N - 1):
                y1=Y[j1]
                for j2 in range(j1 + 1, N):
                    y2 = Y[j2]
                    if np.sum((x1 <= XY[0]) * (XY[0] <= x2) * (y1 <= XY[1]) * (XY[1] <= y2)) < K:
                        continue
                    v2 = (x2 - x1) * (y2 - y1)
                    v = min(v, v2)
    return v

ans = solve(XY, X, Y)
print(ans)

Solution (Python):
N, K = map(int, input().split())
xy = [tuple(map(int, input().split())) for _ in range(N)]
xy.sort(key=lambda t: t[0])
ans = 10**20

for i in range(N):
    for j in range(i+K-1, N):
        xlen = xy[j][0]-xy[i][0]
        ys = []
        
        for k in range(i, j+1):
            ys.append(xy[k][1])
            
        ys.sort()
        ylen = 10**20
        
        for k in range(len(ys)-K+1):
            ylen = min(ylen, ys[k+K-1]-ys[k])
        
        ans = min(ans, xlen*ylen)
    
print(ans)

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




def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))


def main():
	n,k=MI()
	li=[LI() for _ in range(n)]
	

	ans=10**20

	X=[]
	Y=[]

	for x,y in li:
		X.append(x)
		Y.append(y)
	X.sort()
	Y.sort()
	

	for i in range(n):
		for ii in range(i+1,n):
			for j in range(n):
				for jj in range(j+1,n):
					cnt=0
					for x,y in li:
						if X[i]<=x<=X[ii] and Y[j]<=y<=Y[jj]:
							cnt+=1
					
					if cnt>=k:
						ans=min(ans,(X[ii]-X[i])*(Y[jj]-Y[j]))

	print(ans)












if __name__ == "__main__":
	main()

Solution (Python):
import itertools

n,k = map(int,input().split())
x = []
y = []
xy = []
for i in range(n):
  x0,y0 = map(int,input().split())
  x.append(x0)
  y.append(y0)
  xy.append((x0,y0))
x.sort()
y.sort()
xs = {}
ys = {}
for i in range(n):
  xs[x[i]] = i
  ys[y[i]] = i
m = [[0 for _ in range(n+1)] for _ in range(n+1)]
for x0,y0 in xy:
  m[ys[y0]+1][xs[x0]+1] += 1
for i in range(n):
  for j in range(n):
    m[i+1][j+1] += m[i][j+1]+m[i+1][j]-m[i][j]

ans = float('INF')
for x1,x2 in itertools.combinations(range(n),2):
  for y1,y2 in itertools.combinations(range(n),2):
    if k <= m[y2+1][x2+1]-m[y2+1][x1]-m[y1][x2+1]+m[y1][x1]:
      
      ans = min((x[x2]-x[x1])*(y[y2]-y[y1]),ans)
print(ans)

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

def main():
  n, k = map(int, input().split())
  point = [[int(x) for x in input().split()] for _ in range(n)]
  
  ans = pow(10, 18)*4
  for a in range(n):
    for b in range(a+1):
      for c in range(b+1):
        for d in range(c+1):
          x, y = [point[a][0], point[b][0], point[c][0], point[d][0]], [point[a][1], point[b][1], point[c][1], point[d][1]]
          x1, x2, y1, y2 = min(x), max(x), min(y), max(y)
          count = 0
          for e in range(n):
            if x1 <= point[e][0] <= x2 and y1 <= point[e][1] <= y2:
              count += 1
          if count < k:
            continue
          sub = (x2-x1)*(y2-y1)
          if ans > sub:
            ans = sub
  
  print(ans)
  
  
if __name__ == "__main__":
  main()

Solution (Python):
from collections import defaultdict
def main():
  n,k=map(int,input().split())
  xy=[list(map(int,input().split())) for _ in range(n)]
  x=[p[0] for p in xy]
  y=[p[1] for p in xy]
  x.sort()
  y.sort()
  
  s1=[[0]*n for _ in range(n)]
  s2=[[0]*n for _ in range(n)]
  s3=[[0]*n for _ in range(n)]
  s4=[[0]*n for _ in range(n)]
  for i in range(n):
    for j in range(n):
        for p in xy:
            if p[0]<=x[i] and p[1]<=y[j]:
              s1[i][j]+=1
              s2[i][j]+=(p[0]<x[i])
              s3[i][j]+=(p[1]<y[j])
              s4[i][j]+=(p[0]<x[i])*(p[1]<y[j])
  ans=float('inf')
  for s in range(n):
    for t in range(s+1,n):
      for u in range(n):
        for v in range(u+1,n):
          if s1[t][v]-s3[t][u]-s2[s][v]+s4[s][u]>=k:
            ans=min(ans,(x[t]-x[s])*(y[v]-y[u]))
  print(ans)

if __name__=='__main__':
  main()

Solution (Python):
import sys
from bisect import bisect_left
from itertools import accumulate

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, K, *XY = map(int, read().split())

    X = set()
    Y = set()
    for i, (x, y) in enumerate(zip(*[iter(XY)] * 2)):
        X.add(x)
        Y.add(y)

    X = sorted(X)
    Y = sorted(Y)

    P, Q = len(X), len(Y)

    ans = -1
    for i, x1 in enumerate(X):
        for x2 in X[i + 1 :]:
            for j, y1 in enumerate(Y):
                for y2 in Y[j + 1 :]:
                    p = 0
                    for x, y in zip(*[iter(XY)] * 2):
                        if x1 <= x <= x2 and y1 <= y <= y2:
                            p += 1

                    if p >= K and (ans > (x2 - x1) * (y2 - y1) or ans == -1):
                        ans = (x2 - x1) * (y2 - y1)

    print(ans)
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from bisect import bisect_left
from itertools import accumulate

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, K, *XY = map(int, read().split())

    X = set()
    Y = set()
    for i, (x, y) in enumerate(zip(*[iter(XY)] * 2)):
        X.add(x - 1)
        Y.add(y - 1)

    X = sorted(X)
    Y = sorted(Y)

    P, Q = len(X), len(Y)

    G = [[0] * Q for _ in range(P)]
    for x, y in zip(*[iter(XY)] * 2):
        G[bisect_left(X, x - 1)][bisect_left(Y, y - 1)] = 1

    csum = [[0] * (Q + 1) for _ in range(P + 1)]
    for i in range(P):
        for j in range(Q):
            csum[i + 1][j + 1] = csum[i + 1][j] + csum[i][j + 1] - csum[i][j] + G[i][j]

    ans = -1
    for x1 in range(P):
        for x2 in range(x1, P + 1):
            for y1 in range(Q):
                for y2 in range(y1, Q + 1):
                    if csum[x2][y2] - csum[x1][y2] - csum[x2][y1] + csum[x1][y1] >= K:
                        if ans > (X[x2 - 1] - X[x1]) * (Y[y2 - 1] - Y[y1]) or ans == -1:
                            ans = (X[x2 - 1] - X[x1]) * (Y[y2 - 1] - Y[y1])

    print(ans)
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys
def MI(): return map(int,sys.stdin.readline().rstrip().split())

N,K = MI()
xy = [tuple(MI()) for i in range(N)]

xy.sort()

from operator import itemgetter

ans = 10**19
for i in range(N-1):
    for j in range(i+1,N):
        a = xy[j][0]-xy[i][0]
        A = xy[i:j+1]
        if len(A) >= K:
            A = sorted(A, key=itemgetter(1))
            b = 10**18
            for k in range(len(A)-K+1):
                b = min(b,A[k+K-1][1]-A[k][1])
            ans = min(ans,a*b)

print(ans)

Solution (Python):
import sys
import itertools

input = sys.stdin.readline


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

    xset = set()
    yset = set()

    for x, y in XY:
        xset.add(x)
        yset.add(y)

    xlist = list(xset)
    ylist = list(yset)

    ans = float("inf")

    for a, b in itertools.combinations(range(len(xlist)), 2):
        maxx = max(xlist[a], xlist[b])
        minx = min(xlist[a], xlist[b])

        for c, d in itertools.combinations(range(len(ylist)), 2):
            maxy = max(ylist[c], ylist[d])
            miny = min(ylist[c], ylist[d])

            cnt = 0
            for x, y in XY:
                if minx <= x <= maxx and miny <= y <= maxy:
                    cnt += 1

            if cnt >= K:
                ans = min(ans, (maxx - minx) * (maxy - miny))

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, k = map(int, input().split())
    X, Y = [], []
    XY = []
    for _ in range(n):
        x, y = map(int, input().split())
        X.append(x)
        Y.append(y)
        XY.append([x, y])
    X.sort()
    Y.sort()

    res = f_inf
    for x1 in range(n):
        left = X[x1]
        for x2 in range(x1 + 1, n):
            right = X[x2]
            for y1 in range(n):
                bottom = Y[y1]
                for y2 in range(y1 + 1, n):
                    up = Y[y2]
                    cnt = 0
                    for x, y in XY:
                        if left <= x <= right and bottom <= y <= up:
                            cnt += 1
                        if cnt >= k:
                            area = (right - left) * (up - bottom)
                            res = min(res, area)
                            break
    print(res)


if __name__ == '__main__':
    resolve()

Solution (Python):
n,K=list(map(int,input().split()))
xy=sorted([list(map(int,input().split())) for _ in range(n)],key=lambda x:x[0])

dp=[[[] for _ in range(n)] for _ in range(n)]
for i in range(n):
    for j in range(i+1,n):
        for k in range(i,j+1):
            dp[i][j].append(xy[k][1])
        
        dp[i][j].sort()

ans=10**19

for x in range(K,n+1):
    for i in range(n-x+1):
        left=xy[i][0]
        right=xy[i+x-1][0]

        for j in range(len(dp[i][i+x-1])-K+1):
            down=dp[i][i+x-1][j]
            up=dp[i][i+x-1][j+K-1]

            ans=min(ans,(right-left)*(up-down))

print(ans)

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

def main():
    N, K = map(int, input().split())
    points = []
    X = set()
    Y = set()
    for _ in range(N):
        x, y = map(int, input().split())
        points.append((x, y))
        X.add(x)
        Y.add(y)
    X = list(X)
    Y = list(Y)
    X.sort()
    Y.sort()

    mapX = {} 
    mapY = {} 
    for i, x in enumerate(X): mapX[x] = i + 1
    for i, y in enumerate(Y): mapY[y] = i + 1

    
    h, w = len(mapX), len(mapY)
    grid = [[0] * (w + 1) for _ in range(h + 1)]
    for x, y in points:
        grid[mapY[y]][mapX[x]] = 1
    sum_grid = [list(accumulate(grid[y])) for y in range(h + 1)]
    for y in range(1, h + 1):
        for x in range(1, w + 1):
            sum_grid[y][x] += sum_grid[y - 1][x]

    ans = 10**20
    for sx in range(1, w + 1):
        for sy in range(1, h + 1):
            for ex in range(sx, w + 1):
                for ey in range(sy, h + 1):
                    cnt = sum_grid[ey][ex] - sum_grid[ey][sx-1] - sum_grid[sy-1][ex] + sum_grid[sy-1][sx-1]
                    if cnt < K: continue
                    area = (X[ex - 1] - X[sx - 1]) * (Y[ey - 1] - Y[sy - 1])
                    ans = min(ans, area)
    print(ans)


if __name__ == "__main__":
    main()

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

x_index=set([])
y_index=set([])

for (x,y) in xy:
    x_index.add(x)
    y_index.add(y)
    


x_index=list(x_index)
y_index=list(y_index)

x_index.sort()
y_index.sort()
ans=0
for xl in range(len(x_index)-1):
    for xr in range(xl+1,len(x_index)):
        for yl in range(len(y_index)-1):
            for yr in range(yl+1,len(y_index)):
                cnt=0
                for (x,y) in xy:
                    if x_index[xl]<=x and x<=x_index[xr] and y_index[yl]<=y and y<=y_index[yr]:
                        cnt+=1
                if cnt==k:
                    tmp=(x_index[xr]-x_index[xl])*(y_index[yr]-y_index[yl])
                    if ans==0:
                        ans=tmp
                    else:
                        ans=min(ans,tmp)
print(ans)