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

Solution (Python):
N,K = map(int, input().split())
xy = []
for _ in range(N):
    xy.append( tuple(map(int, input().split())) )
xs,ys = map(list, zip(*xy))
xs.sort()
ys.sort()
grid = [[0]*(N+1) for _ in range(N+1)] 


for x,y in xy:
    i = xs.index(x)
    j = ys.index(y)
    grid[j+1][i+1] = 1
    



for h in range(N+1):
    for w in range(1,N+1):
        grid[h][w] += grid[h][w-1]
for w in range(N+1):
    for h in range(1,N+1):
        grid[h][w] += grid[h-1][w]


ans = float('inf')
for l in range(N):
    for r in range(l+1,N):
        for b in range(N):
            for t in range(b+1,N):
                cnt = grid[t+1][r+1] - grid[b][r+1] - grid[t+1][l] \
                      + grid[b][l]
                xl,xr = xs[l],xs[r]
                yb,yt = ys[b],ys[t]
                if cnt>=K:
                    ans = min(ans, (xr-xl)*(yt-yb))
print(ans)

Solution (Python):

N,K = map(int, input().split())
xy = []
for _ in range(N):
    xy.append( tuple(map(int, input().split())) )
xs,ys = map(list, zip(*xy))
xs.sort()
ys.sort()
ans = float('inf')
for l in range(N):
    for r in range(l+1,N):
        for b in range(N):
            for t in range(b+1,N):
                xl,xr = xs[l],xs[r]
                yb,yt = ys[b],ys[t]
                cnt = 0
                for xi,yi in xy:
                    if xl<=xi<=xr and yb<=yi<=yt: 
                        cnt += 1
                if cnt>=K:
                    ans = min(ans, (xr-xl)*(yt-yb))
print(ans)

Solution (Python):
def acc2(grid):
    H = len(grid); W = len(grid[0])
    for i in range(H):
        for j in range(W-1):
            grid[i][j+1] += grid[i][j]
    for j in range(W):
        for i in range(H-1):
            grid[i+1][j] += grid[i][j]
    ngrid = [[0]*(W+1)]
    for i in range(H):
        line = [0] + grid[i]
        ngrid.append(line)
    return ngrid

from bisect import bisect_left
N,K = map(int,input().split())
X = []; Y = []; info = []
for i in range(N):
    x,y = map(int,input().split())
    X.append(x); Y.append(y); info.append([x,y])
X.sort(); Y.sort()

acc = [[0]*(N) for i in range(N)]
for x, y in info:
    j = bisect_left(X,x)
    i = bisect_left(Y,y)
    acc[i][j] += 1

acc = acc2(acc)

ans = float('inf')
for t in range(N-1):
    for b in range(t+1,N):
        for l in range(N-1):
            for r in range(l+1,N):
                num = acc[b+1][r+1] - acc[b+1][l] - acc[t][r+1] + acc[t][l]
                if num < K: continue
                S = (Y[b] - Y[t]) * (X[r] - X[l])
                if S < ans:
                    ans = S

print(ans)

Solution (Python):
N,K = map(int,input().split())
X = []; Y = []; info = []
for i in range(N):
    x,y = map(int,input().split())
    X.append(x); Y.append(y); info.append([x,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):
                cnt = 0
                for x, y in info:
                    if X[i] <= x <= X[j] and Y[k] <= y <= Y[l]:
                        cnt += 1
                if cnt < K:
                    continue
                S = (Y[l]-Y[k])*(X[j]-X[i])
                if S < ans:
                    ans = S
print(ans)

Solution (Python):
from bisect import bisect_left
N,K = map(int,input().split())
X = []; Y = []; info = []
for i in range(N):
    x,y = map(int,input().split())
    X.append(x); Y.append(y); info.append([x,y])
X.sort(); Y.sort()

acc = [[0]*(N+1) for i in range(N+1)]
for x, y in info:
    j = bisect_left(X,x)
    i = bisect_left(Y,y)
    acc[i+1][j+1] += 1

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

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

ans = float('inf')
for t in range(N-1):
    for b in range(t+1,N):
        for l in range(N-1):
            for r in range(l+1,N):
                num = acc[b+1][r+1] - acc[b+1][l] - acc[t][r+1] + acc[t][l]
                if num < K: continue
                S = (Y[b] - Y[t]) * (X[r] - X[l])
                if S < ans:
                    ans = S

print(ans)

def debug():
    for line in acc:
        print(line)

Solution (Python):
from itertools import product
from operator import itemgetter
N, K = map(int, input().split())
XY = []
X, Y = [], []
for _ in range(N):
    x, y = map(int, input().split())
    X.append(x)
    Y.append(y)
    XY.append([x, y])
X.sort()
Y.sort()
XY.sort(key=itemgetter(1))

ans = 10 ** 19
for l, r, t in product(X, X, Y):
    if l > r:
        continue
    cnt = -K
    for x, y in XY:
        if y < t:
            continue
        if l <= x <= r:
            cnt += 1
            if cnt >= 0:
                area = (r - l) * (y - t)
                if area < ans:
                    ans = area
                break

print(ans)

Solution (Python):
from itertools import combinations

N,K=map(int,input().split())
o=[tuple(map(int,input().split())) for _ in range(N)]
ans=float("inf")

for i,j in combinations(o,2):
    x1,y1=i
    x2,y2=j
    xmax,xmin=max(x1,x2),min(x1,x2)

    for k,l in combinations(o,2):
        x3,y3=k
        x4,y4=l
        ymax,ymin=max(y3,y4),min(y3,y4)

        v=0
        for m in o:
            x5,y5=m
            if xmin<=x5<=xmax and ymin<=y5<=ymax:
                v+=1
        
        if v>=K:
            ans=min(ans,(ymax-ymin)*(xmax-xmin))


print(ans)

Solution (Python):
n,k=map(int,input().split())
z=[tuple(map(int,input().split()))for _ in range(n)]
x=[i for i,_ in z]
y=[j for _,j in z]
x.sort()
y.sort()
a=10**20
for i,l in enumerate(x):
    for r in x[i+1:]:
        for v,d in enumerate(y):
            for u in y[v+1:]:
                if sum([1for i,j in z if l<=i<=r and d<=j<=u])>=k:
                    a=min(a,(r-l)*(u-d))
print(a)

Solution (Python):
n,k=map(int,input().split())
z=[list(map(int,input().split()))for _ in range(n)]
x=[]
y=[]
for i,j in z:
    x.append(i)
    y.append(j)
x.sort()
y.sort()
a=10**20
for i,l in enumerate(x):
    for r in x[i+1:]:
        for v,d in enumerate(y):
            for u in y[v+1:]:
                if sum([1for i,j in z if l<=i<=r and d<=j<=u])>=k:
                    a=min(a,(r-l)*(u-d))
print(a)

Solution (Python):
N,K=map(int,input().split())
z=[tuple(map(int,input().split()))for _ in range(N)]
x=[i for i,_ in z]
y=[j for _,j in z]
x.sort()
y.sort()
a=10**20
for i in range(N):
    for j in range(i+1,N):
        for k in range(N):
            for l in range(k+1,N):
                l,r,d,u=x[i],x[j],y[k],y[l]
                if sum([1for v,w in z if l<=v<=r and d<=w<=u])>=K:
                    a=min(a,(r-l)*(u-d))
print(a)

Solution (Python):
I=lambda:list(map(int,input().split()))
n,k=I()
z=[I()for _ in[0]*n]
z.sort()
a=10**20
for i in range(n):
 for j in range(i+k-1,n):l=sorted(t[1]for t in z[i:j+1]);a=min(a,*[(z[j][0]-z[i][0])*(v-u)for u,v in zip(l,l[k-1:])])
print(a)

Solution (Python):
I=lambda:list(map(int,input().split()))
n,k=I()
z=[I()for _ in[0]*n]
z.sort()
a=10**20
for i in range(n):
 for j in range(i+k-1,n):l=sorted(t[1]for t in z[i:j+1]);a=min(a,*[(z[j][0]-z[i][0])*(v-u)for u,v in zip(l,l[k-1:])])
print(a)

Solution (Python):
n,k=map(int,input().split())
z=[list(map(int,input().split()))for _ in range(n)]
z.sort()
a=10**20
for i in range(n):
    for j in range(i+1,n):
        x=z[j][0]-z[i][0]
        l=sorted(t[1]for t in z[i:j+1])
        for u,v in zip(l,l[k-1:]):
            a=min(a,x*(v-u))
print(a)

Solution (Python):
n,k=map(int,input().split())
z=[list(map(int,input().split()))for _ in range(n)]
z.sort()
a=10**20
for i in range(n):
    for j in range(i+1,n):
        x=z[j][0]-z[i][0]
        l=sorted(t[1]for t in z[i:j+1])
        for u,v in zip(l,l[k-1:]):
            a=min(a,x*(v-u))
print(a)

Solution (Python):
N,K=map(int,input().split())
D=[]
X=[]
Y=[]
 
for i in range(N):
    x,y=map(int,input().split())
    D.append([x,y])
    X.append(x)
    Y.append(y)
    
X.sort()
Y.sort()
ans=10**20
for a in range(len(X)):
    for b in range(len(X)-a):
        for c in range(len(Y)):
            for d in range(len(Y)-c):
                cnt=0
                for e in range(N):
                    if X[a]<=D[e][0]<=X[len(X)-1-b] and Y[c]<=D[e][1]<=Y[len(Y)-1-d]:
                        cnt+=1
                if cnt>=K and ans>abs(X[a]-X[len(X)-1-b])*abs(Y[c]-Y[len(Y)-1-d]):
                    ans=abs(X[a]-X[len(X)-1-b])*abs(Y[c]-Y[len(Y)-1-d])
print(ans)

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

for i in range(N):
    x,y=map(int,input().split())
    D.append([x,y])
    X.append(x)
    Y.append(y)
    
X.sort()
Y.sort()
D.sort()
ans=10**20
for a in range(len(X)):
    for b in range(len(X)-a):
        if len(X)-b-a<K:
            break
        for c in range(len(Y)):
            for d in range(len(Y)-c):
                cnt=0
                for e in range(a,len(X)-b):
                    if X[a]<=D[e][0]<=X[len(X)-1-b] and Y[c]<=D[e][1]<=Y[len(Y)-1-d]:
                        cnt+=1
                if cnt>=K and ans>abs(X[a]-X[len(X)-1-b])*abs(Y[c]-Y[len(Y)-1-d]):
                    ans=abs(X[a]-X[len(X)-1-b])*abs(Y[c]-Y[len(Y)-1-d])
print(ans)

Solution (Python):
N, K = map(int, input().split())
X = []
Y = []
for _ in range(N):
    x, y = map(int, input().split())
    X.append(x)
    Y.append(y)
Xs = sorted(X)
Ys = sorted(Y)
ans = float('inf')
for left in range(N - 1):
    for right in range(left + 1, N):
        for down in range(N - 1):
            for up in range(down + 1, N):
                count = 0
                for i in range(N):
                    if Xs[left] <= X[i] <= Xs[right] and Ys[down] <= Y[i] <= Ys[up]:
                            count += 1
                if count >= K:
                    ans = min(ans, (Xs[right] - Xs[left]) * (Ys[up] - Ys[down]))
print(ans)

Solution (Python):
n,k_num = map(int,input().split())
info =[list(map(int,input().split())) for i in range(n)]
li_x = []
li_y = []

for i in range(n):
 
    li_x.append(info[i][0])
 
    li_y.append(info[i][1])

li_x = sorted(li_x)
li_y = sorted(li_y)

bunpu = [[0]*n for i in range(n)]
for i in range(n):
  for j in range(n):
    if info[i][0]==li_x[j]:
      zahyo_x=j
      break
  for k in range(n):
    if info[i][1]==li_y[k]:
      zahyo_y=k
      break
  bunpu[zahyo_x][zahyo_y]=1

ruiseki = [[0]*n for i in range(n)]


for i in range(0,n):
  for j in range(0,n):
    ruiseki[i][j] = bunpu[i][j]

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

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




ans = float("inf")

for i in range(len(li_x)):
  for j in range(i,len(li_x)):
    for k in range(len(li_y)):
      for l in range(k,len(li_y)):
        count = ruiseki[j][l]
        if 0<=k-1:
          count -= ruiseki[j][k-1]
        if 0<=i-1:
          count -= ruiseki[i-1][l]
        if 0<=k-1 and 0<=i-1:
          count += ruiseki[i-1][k-1]      
        if count ==k_num:
          ans = min(ans,(li_x[j]-li_x[i])*(li_y[l]-li_y[k]))
print(ans)

Solution (Python):
N, K = map(int, input().split())
p = [list(map(int, input().split())) for _ in range(N)]
x = sorted(list(zip(*p))[0])
y = sorted(list(zip(*p))[1])
dic_x = {v: i + 1 for i, v in enumerate(x)}
dic_y = {v: i + 1 for i, v in enumerate(y)}
cum_sum = [[0] * (N + 1) for _ in range(N + 1)]
for i, j in p:
    cum_sum[dic_y[j]][dic_x[i]] = 1

for i in range(1, N + 1):
    for j in range(N):
        cum_sum[i][j + 1] += cum_sum[i][j]

for i in range(1, N + 1):
    for j in range(N):
        cum_sum[j + 1][i] += cum_sum[j][i]

ans = 10 ** 20
for l in range(N):
    for r in range(l + 1, N):
        for d in range(N):
            for u in range(d + 1, N):
                z = cum_sum[u + 1][r + 1] - cum_sum[d][r + 1] \
                     - cum_sum[u + 1][l] + cum_sum[d][l]
                if z >= K:
                    ans = min(ans, (x[r] - x[l]) * (y[u] - y[d]))
print(ans)

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

x,y = [],[]
xx,yy = [],[]

for i in range(n):
    X,Y = map(int,input().split())

    x.append(X)
    xx.append(X)
    y.append(Y)
    yy.append(Y)



xx.sort()
yy.sort()
ans = 10**20

for i in range(n):
    for j in range(i):
        lx,rx = xx[j],xx[i]

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

        for k in range(n):
            if lx <= x[k] <= rx:
                num[yy.index(y[k])+1] += 1

        for k in range(n):
            num[k+1] += num[k]


        for k in range(n):
            for l in range(k):
                by,ty = yy[l],yy[k]

                if num[k+1] - num[l] >= K:
                    ans = min(ans,(rx-lx)*(ty-by))



print(ans)

Solution (Python):
n, k = map(int, input().split())
points = []
xMin = yMin = 10 ** 10
xMax = yMax = -10 ** 10
xKeys = set((-10 ** 10, 10 ** 10))
yKeys = set((-10 ** 10, 10 ** 10))
for _ in range(n):
    x, y = map(int, input().split())
    xMin = min(xMin, x)
    xMax = max(xMax, x)
    yMin = min(yMin, y)
    yMax = max(yMax, y)
    xKeys.add(x)
    yKeys.add(y)
    points.append((x, y))

xKeyToI = {}
xIToKey = {}
for i, key in enumerate(sorted(list(xKeys))):
    xKeyToI[key] = i
    xIToKey[i] = key

yKeyToI = {}
yIToKey = {}
for i, key in enumerate(sorted(list(yKeys))):
    yKeyToI[key] = i
    yIToKey[i] = key

xLen = len(xKeyToI)
yLen = len(yKeyToI)

mp = [[0] * (xLen + 2) for _ in range(yLen + 2)]
for x, y in points:
    ix, iy = xKeyToI[x], yKeyToI[y]
    mp[iy][ix] += 1


for y in range(1, yLen + 1):
    for x in range(xLen + 1):
        mp[y][x + 1] += mp[y][x]
        mp[y][x] += mp[y - 1][x]

ans = 10 ** 20
for py in range(1, yLen):
    for px in range(1, xLen):
        for h in range(yLen - py):
            for w in range(xLen - px):
                score = mp[py + h][px + w] - mp[py - 1][px + w] -\
                        mp[py + h][px - 1] + mp[py - 1][px - 1]
                if score >= k:
                    ans = min(ans, (xIToKey[px + w] - xIToKey[px]) * (yIToKey[py + h] - yIToKey[py])) 

print(ans)

Solution (Python):
import bisect
from operator import itemgetter
N, K = map(int, input().split())
XY = [list(map(int, input().split())) for _ in range(N)]

XY.sort(key=itemgetter(0))
x, y = list(zip(*XY))

ans = 10**19
for l in range(N):
    for r in range(l, N):
        n = bisect.bisect_right(x, x[r]) - bisect.bisect_left(x, x[l])
        if n >= K:
            dx = x[r]-x[l]
            tmp = sorted(y[l:r+1])
            for i in range(n-K+1):
                dy = tmp[i+K-1] - tmp[i]
                ans = min(ans, dx*dy)
print(ans)

Solution (Python):
from itertools import combinations
N, K = (list)(map(int, input().split()))
pos_x = []
pos_y = []

for _ in range(N):
    a, b = map(int, input().split())
    pos_x.append(a)
    pos_y.append(b)


def count_point(x, y):
    ret = 0
    x_min = min(x)
    x_max = max(x)
    y_min = min(y)
    y_max = max(y)
    for i in range(N):
        if x_min <= pos_x[i] <= x_max and y_min <= pos_y[i] <= y_max:
            ret += 1
    return ret


def calc_area(x, y):
    ret = (x[1]-x[0])*(y[1]-y[0])
    return (abs)(ret)


set_x = set(pos_x)
set_y = set(pos_y)


area = float('inf')
for cand_x in combinations(set_x, 2):
    for cand_y in combinations(set_y, 2):
        if count_point(cand_x, cand_y) == K:
            area = min(area, calc_area(cand_x, cand_y))
print(area)

Solution (Python):
from itertools import combinations
N, K = (list)(map(int, input().split()))
pos_x = []
pos_y = []

for _ in range(N):
    a, b = map(int, input().split())
    pos_x.append(a)
    pos_y.append(b)


def count_point(x, y):
    ret = 0
    x_min = min(x)
    x_max = max(x)
    y_min = min(y)
    y_max = max(y)
    for i in range(N):
        if x_min <= pos_x[i] <= x_max and y_min <= pos_y[i] <= y_max:
            ret += 1
    return ret


def calc_area(x, y):
    ret = (x[1]-x[0])*(y[1]-y[0])
    return (abs)(ret)


set_x = set(pos_x)
set_y = set(pos_y)


area = float('inf')
for cand_x in combinations(set_x, 2):
    for cand_y in combinations(set_y, 2):
        if count_point(cand_x, cand_y) >= K:
            area = min(area, calc_area(cand_x, cand_y))
print(area)

Solution (Python):
inf = 10 ** 20


def func(n, _k, pos):
    x = [pos[i][0] for i in range(len(pos))]
    y = [pos[i][1] for i in range(len(pos))]
    x.sort()
    y.sort()
    imos = [[0 for _ in range(n)] for _ in range(n)]
    for i in range(n):
        for j in range(n):
            for k in range(n):
                if pos[i][0] == x[j] and pos[i][1] == y[k]:
                    imos[j][k] += 1
    for i in range(n):
        for j in range(1, n):
            imos[i][j] += imos[i][j - 1]
    for i in range(1, n):
        for j in range(n):
            imos[i][j] += imos[i - 1][j]
    
        

    def getImos(_right, _left, _upper, _bottom):
        _sum = imos[_right][_upper]
        if _bottom > 0:
            _sum -= imos[_right][_bottom - 1]
        if _left > 0:
            _sum -= imos[_left - 1][_upper]
        if _bottom > 0 and _left > 0:
            _sum += imos[_left - 1][_bottom - 1]
        return _sum

    _min = inf
    for left in range(len(x) - 1):
        for right in range(left + 1, len(x)):
            for bottom in range(len(y) - 1):
                for upper in range(bottom + 1, len(y)):
                    """
                    print("{} {} {} {} :{}poi s:{}".format(right, left, bottom, upper,
                                                        getImos(right, left, upper, bottom),
                                                        (x[right] - x[left]) * (y[upper] - y[bottom])))
                    """
                    if getImos(right, left, upper, bottom) >= _k:
                        _min = min(_min, (x[right] - x[left]) * (y[upper] - y[bottom]))
                        
    return _min
    """
    out = inf
    for i in range(n):
        
        box = [[pos[i][0], pos[i][1]] for _ in range(4)]
        used = [False for _ in range(n)]
        used[i] = True
        minS = 0
        for _k in range(k-1):
            minS = inf
            using = -1
            for j in range(n):
                if not used[j]:
                    s = (max(box[1][0], pos[j][0]) - min(box[0][0], pos[j][0])) \
                        * (max(box[1][1], pos[j][1]) - min(box[2][1], pos[j][1]))
                    if s < minS:
                        minS = s
                        using = j
            used[using] = True
            right = max(box[1][0], pos[using][0])
            left = min(box[0][0], pos[using][0])
            upper = max(box[1][1], pos[using][1])
            botom = min(box[2][1], pos[using][1])
            box = [[left, upper], [right, upper], [right, botom], [left, botom]]
            
        
            
        out = min(out, minS)
    return out
    """


n, k = [int(i) for i in input().split()]
pos = [[0, 0] for _ in range(n)]
for i in range(n):
    pos[i] = [int(i) for i in input().split()]
print(func(n, k, pos))
"""
print("21 vs " + str(func(4, 4, [[1, 4], [3, 3], [6, 2], [8, 1]])))
print("1 vs " + str(func(4, 2, [[0, 0], [1, 1], [2, 2], [3, 3]])))
print("3999999996000000001 vs " + str(func(4, 3, [[-1000000000, -1000000000], [1000000000, 1000000000],
                                                  [-999999999, 999999999], [999999999, -999999999]])))
"""

Solution (Python):


"""
参考：https://img.atcoder.jp/abc075/editorial.pdf
・自力ACしたのがO(N^4)でこれはO(N^5)の愚直解
・制約からして何とかなりそうだし、こっちのが実装全然軽いし実戦向きぽいね。
　→O(N^5)=50^5=3億1250万はpypyでも無理だったわ。
・添字見づらくなったけど定数倍改善。多分半分で約1憶5000万かと。
"""

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

X2 = sorted(set(X))
Y2 = sorted(set(Y))

ans = float('inf')

for i in range(len(X2)):
    for j in range(len(Y2)):
        for k in range(i+1, len(X2)):
            for l in range(j+1, len(Y2)):
                cnt = 0
                
                for m in range(N):
                    if X2[i] <= X[m] <= X2[k] and Y2[j] <= Y[m] <= Y2[l]:
                        cnt += 1
                if cnt >= K:
                    ans = min((X2[k] - X2[i]) * (Y2[l] - Y2[j]), ans)
print(ans)

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

xy.sort()
ans = float("inf")
for i in range(N):
    for j in range(i + 1, N):
        x = xy[j][0] - xy[i][0]
        y_list = [xy[1] for xy in xy[i:j + 1]]
        y_list.sort()
        for k in range(len(y_list)-K+1):
            y = y_list[k + K -1] - y_list[k]
            tmp = x * y
            if ans > tmp:
                ans = tmp

print(ans)

Solution (Python):


"""
・座標圧縮
・2次元累積和
"""

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


zip_x, zip_y, unzip_x, unzip_y = {}, {}, {}, {}
X2 = sorted(set(X))
Y2 = sorted(set(Y))

for i in range(len(X2)):
    zip_x[X2[i]] = i+1
    unzip_x[i+1] = X2[i]
for i in range(len(Y2)):
    zip_y[Y2[i]] = i+1
    unzip_y[i+1] = Y2[i]


grid = [[0] * (len(X2)+1) for _ in range(len(Y2)+1)]
for i in range(N):
    grid[zip_y[Y[i]]][zip_x[X[i]]] += 1


for i in range(len(Y2)+1):
    for j in range(1, len(X2)+1):
        grid[i][j] += grid[i][j-1]
for i in range(1, len(Y2)+1):
    for j in range(len(X2)+1):
        grid[i][j] += grid[i-1][j]

ans = float('inf')
for i in range(1, len(Y2)+1):
    for j in range(1, len(X2)+1):
        
        if grid[i][j] >= K:
            for k in range(i):
                for l in range(j):
                    
                    if grid[i][j] - grid[i][l] - grid[k][j] + grid[k][l] >= K:
                        
                        ans = min((unzip_x[j]-unzip_x[l+1]) * (unzip_y[i]-unzip_y[k+1]), ans)
print(ans)

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

import numpy as np
xy = np.zeros((n, 2), dtype=int)

for i in range(n):
	buf = input().split()
	xy[i][0] = int(buf[0])
	xy[i][1] = int(buf[1])

index = np.argsort(xy.T[0])
xysort = xy[index]

area = -1
for i in range(n-k+1):
	num = k+i
	for j in range(n-(k+i)+1):
		y = np.sort(xysort[j: j+(k+i)].T[1])
		w = xysort[j+k+i-1][0] - xysort[j][0]
		hmin = y[k-1]-y[0]
		for p in range(i+1):
			if(y[p+k-1]-y[p] < hmin):
				hmin = y[p+k-1]-y[p]
		if(area == -1):
			area = w*hmin
		elif(w*hmin < area):
			area = w*hmin
			
print(area)

Solution (Python):
from bisect import bisect_left
N, K = map(int, input().split())
Points = [list(map(int, input().split())) for i in range(N)]



def point_compress(points):
    x_points = sorted([x for x, y in points])
    y_points = sorted([y for x, y in points])
    points_compressed = []
    for x, y in points:
        points_compressed.append([bisect_left(x_points, x), bisect_left(y_points, y)])
    return points_compressed


Points_compressed = point_compress(Points)


class Ruisekiwa2D:
    def __init__(self, h, w):
        self.H = h
        self.W = w
        self.G = [[0] * w for _ in range(h)]

    def load(self, points):
        
        for x, y in points:
            self.G[x][y] += 1

    def load_imos(self, points):
        
        for i1, j1, i2, j2 in points:
            self.G[i1][j1] += 1  
            if j2 + 1 < self.W:  
                self.G[i1][j2+1] -= 1
            if i2 + 1 < self.H:
                self.G[i2+1][j1] -= 1  
            if j2 + 1 < self.W and i2 + 1 < self.H:  
                self.G[i2+1][j2+1] += 1

    def calc(self):
        for y in range(self.W):
            for x in range(1, self.H):
                self.G[x][y] += self.G[x-1][y]

        for y in range(1, self.W):
            for x in range(self.H):
                self.G[x][y] += self.G[x][y-1]

    def get(self, i1, j1, i2, j2):
        if i1 > i2 or j1 > j2 or i1 < 0 or j1 < 0 or i2 < 0 or j2 < 0:
            return 0
        elif i1 > 0 and j1 > 0:
            return self.G[i2][j2] - self.G[i1-1][j2] - self.G[i2][j1-1] + self.G[i1-1][j1-1]
        elif i1 <= 0 < j1:
            return self.G[i2][j2] - self.G[i2][j1-1]
        elif j1 <= 0 < i1:
            return self.G[i2][j2] - self.G[i1 - 1][j2]
        else:
            return self.G[i2][j2]



R2D = Ruisekiwa2D(N, N)
R2D.load(Points_compressed)
R2D.calc()


ans = float('inf')
for yi in range(N):
    for yj in range(N):
        for xi in range(N):
            for xj in range(N):
                cx1, cx2 = Points_compressed[xi][0], Points_compressed[xj][0]
                cy1, cy2 = Points_compressed[yi][1], Points_compressed[yj][1]

                x1, x2 = Points[xi][0], Points[xj][0]
                y1, y2 = Points[yi][1], Points[yj][1]

                
                inside = R2D.get(cx1, cy1, cx2, cy2)
                if inside >= K:
                    ans = min(ans,  abs(x2 - x1) * abs(y2 - y1))

print(ans)

Solution (Python):
from bisect import bisect_left
N, K = map(int, input().split())
Points = []
X, Y = [], []
for i in range(N):
    x, y = map(int, input().split())
    Points.append([x, y])
    X.append(x)
    Y.append(y)


X.sort()
Y.sort()
Points_compressed = []
for x, y in Points:
    cx, cy = bisect_left(X, x), bisect_left(Y, y)
    Points_compressed.append([cx, cy])


class Ruisekiwa2D:
    def __init__(self, h, w):
        self.H = h
        self.W = w
        self.G = [[0] * w for _ in range(h)]

    def load(self, points):
        
        for x, y in points:
            self.G[x][y] += 1

    def load_imos(self, points):
        
        for i1, j1, i2, j2 in points:
            self.G[i1][j1] += 1  
            if j2 + 1 < self.W:  
                self.G[i1][j2+1] -= 1
            if i2 + 1 < self.H:
                self.G[i2+1][j1] -= 1  
            if j2 + 1 < self.W and i2 + 1 < self.H:  
                self.G[i2+1][j2+1] += 1

    def calc(self):
        for y in range(self.W):
            for x in range(1, self.H):
                self.G[x][y] += self.G[x-1][y]

        for y in range(1, self.W):
            for x in range(self.H):
                self.G[x][y] += self.G[x][y-1]

    def get(self, i1, j1, i2, j2):
        if i1 > i2 or j1 > j2 or i1 < 0 or j1 < 0 or i2 < 0 or j2 < 0:
            return 0
        elif i1 > 0 and j1 > 0:
            return self.G[i2][j2] - self.G[i1-1][j2] - self.G[i2][j1-1] + self.G[i1-1][j1-1]
        elif i1 <= 0 < j1:
            return self.G[i2][j2] - self.G[i2][j1-1]
        elif j1 <= 0 < i1:
            return self.G[i2][j2] - self.G[i1 - 1][j2]
        else:
            return self.G[i2][j2]



R2D = Ruisekiwa2D(N, N)
R2D.load(Points_compressed)
R2D.calc()


ans = float('inf')
for yi in range(N):
    for yj in range(N):
        for xi in range(N):
            for xj in range(N):
                cx1, cx2 = Points_compressed[xi][0], Points_compressed[xj][0]
                cy1, cy2 = Points_compressed[yi][1], Points_compressed[yj][1]

                x1, x2 = Points[xi][0], Points[xj][0]
                y1, y2 = Points[yi][1], Points[yj][1]

                
                inside = R2D.get(cx1, cy1, cx2, cy2)
                if inside >= K:
                    ans = min(ans,  abs(x2 - x1) * abs(y2 - y1))

print(ans)

Solution (Python):
n, k = map(int, input().split())
xy = sorted([tuple(map(int, input().split())) for i in range(n)])
ans = float("INF")
en = tuple(enumerate(xy))
for i, (a, b) in en[:n - k + 1]:
    for j, (c, d) in en[i + k - 1:]:
        r = sorted(y for x, y in xy[i:j + 1])
        r2 = r[k - 1:]
        for i2, j2 in zip(r, r2):
            if i2 <= b and d <= j2:
                ans = min(ans, (c - a) * (j2 - i2))
print(ans)

Solution (Python):
import itertools

n, k = map(int, input().split())
xy = [tuple(map(int, input().split())) for i in range(n)]
ans = float("INF")
for a, b in itertools.combinations(xy, 2):
    for c, d in itertools.combinations(xy, 2):
        x1, x2 = sorted([a[0], b[0]])
        y1, y2 = sorted([c[1], d[1]])
        count = 0
        for x, y in xy:
            if x1 <= x <= x2 and y1 <= y <= y2:
                count += 1
        if count >= k:
            ans = min(ans, (x2 - x1) * (y2 - y1))
print(ans)

Solution (Python):
import itertools

n, k = map(int, input().split())
xy = [tuple(map(int, input().split())) for i in range(n)]
ans = float("INF")
for a, b in itertools.combinations(xy, 2):
    for c, d in itertools.combinations(xy, 2):
        x1, x2 = a[0], b[0]
        y1, y2 = c[1], d[1]
        count = 0
        for x, y in xy:
            if min(x1, x2) <= x <= max(x1, x2) and min(y1, y2) <= y <= max(y1, y2):
                count += 1
        if count >= k:
            ans = min(ans, abs(x1 - x2) * abs(y1 - y2))
print(ans)

Solution (Python):
import itertools
N, K = [int(_) for _ in input().split()]
XY = [[int(_) for _ in input().split()] for _ in range(N)]
X, Y = [x for x, y in XY], [y for x, y in XY]
X_s, Y_s = sorted(X), sorted(Y)
ans = float('inf')
for x1, x2 in itertools.combinations(X_s, 2):
    for y1, y2 in itertools.combinations(Y_s, 2):
        k = sum([x1 <= X[i] <= x2 and y1 <= Y[i] <= y2 for i in range(N)])
        if k >= K:
            ans = min(ans, (x2 - x1) * (y2 - y1))
print(ans)

Solution (Python):

from collections import defaultdict
from pprint import pprint as pp
import itertools

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

rui = defaultdict(lambda: defaultdict(int))
sumnum = defaultdict(lambda: defaultdict(int))

for x,y in xy:
    rui[x][y] += 1

xlist = list(sorted(rui.keys()))
ylist = []
for x in xlist:
    ylist.extend(list(rui[x].keys()))
ylist = sorted(list(set(ylist)))

for x in xlist:
    tmp = 0
    for y in ylist:
        tmp += rui[x][y]
        sumnum[x][y] = tmp

for y in ylist:
    tmp = 0
    for x in xlist:
        tmp += sumnum[x][y]
        sumnum[x][y] = tmp

xdict = {v: i for i, v in enumerate(xlist)}
ydict = {v: i for i, v in enumerate(ylist)}

sqmin = -1
exy = list(itertools.product(xlist, ylist))

for i, (x1, y1) in enumerate(exy[:-1]):
    
    
    for x2, y2 in exy[i+1:]:
        if x1 < x2 and y1 < y2:
            xd1 = xdict[x1] - 1
            yd1 = ydict[y1] - 1
            if xd1 < 0:
                xb = (10**9 + 1)*(-1)
            else:
                xb = xlist[xd1]
            if yd1 < 0:
                yb = (10**9 + 1)*(-1)
            else:
                yb = ylist[yd1]
            tmp = sumnum[x2][y2] - sumnum[xb][y2] - sumnum[x2][yb] + sumnum[xb][yb]
            if tmp >= K:
                area = abs(x2 - x1)*abs(y2 - y1)
                if sqmin > area or sqmin == -1:
                    sqmin = area

print(sqmin)