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

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

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

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

    ans = 10**20
    for u in range(N):
        for d in range(u+K-1,N):
            l = 0
            r = K-1
            dY = iY[d]-iY[u]
            cd = c[d+1]
            cu = c[u]
            while 1:
                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
                    if r==N:break

    print(ans)
main()

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

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

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

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

    print(ans)
main()

Solution (Python):
def main():
    N,K = map(int,input().split())
    XY = [list(map(int,input().split())) for _ in [0]*N]
    
    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 = K-1
            dY = iY[d]-iY[u]
            cd = c[d+1]
            cu = c[u]
            while r<N:
                if cd[r+1]+cu[l]-cu[r+1]-cd[l] >=K:
                    ans = min(ans, (iX[r] - iX[l])*dY)
                    l+=1
                else:r+=1

    print(ans)
main()

Solution (Python):
def main():
    N,K = map(int,input().split())
    XY = [list(map(int,input().split())) for _ in [0]*N]
    
    iX = 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 = 0
            dY = iY[d]-iY[u]
            cd = c[d+1]
            cu = c[u]
            while r<N:
                if cd[r+1]+cu[l]-cu[r+1]-cd[l] >=K:
                    ans = min(ans, (iX[r] - iX[l])*dY)
                    l+=1
                else:r+=1

    print(ans)
main()

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

Solution (Python):
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+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)

Solution (Python):
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):
    for j in range(N):
        c[i+1][j+1] += c[i+1][j]
for i in range(N):
    for j in range(N):
        c[i+1][j+1] += c[i][j+1]

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

print(ans)

Solution (Python):
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):
    for j in range(N):
        c[i+1][j+1] += c[i+1][j]
for i in range(N):
    for j in range(N):
        c[i+1][j+1] += c[i][j+1]

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

print(ans)

Solution (Python):
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):
    for j in range(N):
        c[i+1][j+1] += c[i+1][j]
for i in range(N):
    for j in range(N):
        c[i+1][j+1] += c[i][j+1]

ans = 10**20
for l in range(N):
    for u in range(N):
        for r in range(l+1,N):
            for d in range(u+1,N):
                if c[d+1][r+1]+c[u][l]-c[u][r+1]-c[d+1][l] >=K:
                    ans = min(ans,
                             (iX[r]-iX[l])*(iY[d]-iY[u]))
                    break

print(ans)

Solution (Python):
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):
    for j in range(N):
        c[i+1][j+1] += c[i+1][j]
for i in range(N):
    for j in range(N):
        c[i+1][j+1] += c[i][j+1]

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

print(ans)

Solution (Python):
n,k=map(int,input().split())
point=[]
for i in range(n):
    x,y=map(int,input().split())
    point.append((x,y))
point.sort()
ans=10**20
for i in range(n):
    for j in range(i+1,n):
        y_list=[]
        for p in range(i,j+1):
            y_list.append(point[p][1])
        y_list.sort()
        yl=len(y_list)
        y_d=10**10
        if yl<k:
            continue
        else:
            for p in range(yl-k+1):
                y_d=min(y_d,y_list[p+k-1]-y_list[p])
        x_d=point[j][0]-point[i][0]
        temp=x_d*y_d
        ans=min(ans,temp)
print(ans)

Solution (Python):
import itertools

n,k = map(int, input().split())
z = [list(map(int, input().split())) for i in range(n)]

a = [i for i in range(n)]
c = list(itertools.combinations(a,2))
ans = float('inf')


for x in c:
    for y in c:
        d = 0
        x1 = max(z[x[0]][0],z[x[1]][0])
        x2 = min(z[x[0]][0],z[x[1]][0])
        y1 = max(z[y[0]][1],z[y[1]][1])
        y2 = min(z[y[0]][1],z[y[1]][1])
        for i in range(n):
            if x2 <= z[i][0] <= x1 and y2 <= z[i][1] <= y1:
                d += 1
        if d == k:
            ans = min(ans, (x1-x2)*(y1-y2))

print(ans)

Solution (Python):
N, K = map(int, input().split())
xy = [list(map(int, input().split())) for i in range(N)]
ans = 10**20
xy.sort()
for l in range(N-K+1):
    for r in range(l+K, N+1):
        y = sorted(xy[l:r], key = lambda v: v[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())
l=[list(map(int,input().split())) for i in range(n)]
l.sort(key=lambda x:x[0])
ans=float('inf')
for i in range(n-k+1):
    for j in range(i+k-1,n):
        x=l[j][0]-l[i][0]
        tl=sorted(l[i:j+1],key=lambda x:x[1])
        y=float('inf')
        for a in range(j-i+2-k):
            y=min(y,tl[a+k-1][1]-tl[a][1])
        ans=min(ans,x*y)
print(ans)

Solution (Python):
from itertools import combinations

N, K = map(int, input().split())
coord = sorted([tuple(map(int, input().split())) for _ in range(N)])
ans = float('inf')
for left, right in combinations(range(N), 2):
    n_points = right - left + 1
    if n_points < K: continue
    width = coord[right][0] - coord[left][0]
    y_coords = sorted([y for _, y in coord[left: right+1]])
    for i in range(n_points - K + 1):
        height = y_coords[i+K-1] - y_coords[i]
        ans = min(ans, width*height)
print(ans)

Solution (Python):
import itertools
N,K = map(int,input().split())
zahyou = []
for i in range(N):
  zahyou.append(list(map(int,input().split())))
ans = float('inf')
X = []
Y = []
for i in range(N):
  X.append(zahyou[i][0])
  Y.append(zahyou[i][1])
P = list(itertools.combinations(X,2))
Q = list(itertools.combinations(Y,2))
for i in range(len(P)):
  for j in range(len(Q)):
    x1 = min(P[i][0],P[i][1])
    x2 = max(P[i][0],P[i][1])
    y1 = min(Q[j][0],Q[j][1])
    y2 = max(Q[j][0],Q[j][1])
    cnt = 0
    for k in range(N):
      if x1 <= zahyou[k][0] <= x2 and y1 <= zahyou[k][1] <= y2:
        cnt += 1
    if cnt >= K:
      if ans >= (x2-x1)*(y2-y1):
        ans = (x2-x1)*(y2-y1)
print(ans)

Solution (Python):
ab = lambda a,b:abs(a-b)
area = lambda a,b:ab(a[1],b[1])*ab(a[0],b[0])

N, K = map(int, input().split())
A = []
x_lst = []
y_lst = []
for i in range(N):
    a,b = map(int, input().split())
    A.append([a,b])
    x_lst.append(a)
    y_lst.append(b)

x_lst.sort()
y_lst.sort()
mn = float('INF')
for x in range(N-1):
    for x_ in range(x,N):
        for y in range(N-1):
            for y_ in range(y,N):
                cnt = 0
                for a,b in A:
                    if x_lst[x] <= a <= x_lst[x_] and y_lst[y] <= b <= y_lst[y_]:
                        cnt += 1
                if cnt >= K:
                    mn = min(mn, area([x_lst[x],y_lst[y]], [x_lst[x_], y_lst[y_]]))
print(mn)

Solution (Python):
n,c=map(int,input().split())
xpos=[]
ypos=[]
pos=[]
for _ in range(n):
  x,y=map(int,input().split())
  xpos.append(x)
  ypos.append(y)
  pos.append([x,y])
xpos=sorted(xpos)
ypos=sorted(ypos)
ans=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):
        lx,rx=xpos[i],xpos[j]
        ly,ry=ypos[k],ypos[l]
        cnt=0
        for tx,ty in pos:
          if lx<=tx<=rx and ly<=ty<=ry:
            cnt+=1
        if cnt>=c:
          ans=min(ans,(rx-lx)*(ry-ly))
print(ans)

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

    ans = float('INF')
    for l in range(N):
        for r in range(l + 1, N):
            for d in range(N):
                for t in range(d + 1, N):
                    lx = X[l]
                    rx = X[r]
                    ty = Y[t]
                    dy = Y[d]
                    c = 0
                    for x, y in XY:
                        if lx <= x <= rx and dy <= y <= ty:
                            c += 1
                    if c >= K:
                        ans = min(ans, abs(rx - lx) * abs(ty - dy))
    print(ans)


main()

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

xys = {}
xs = []
ys = []
for i in range(n):
  x, y = map(int, input().split())
  xys[i] = (x, y)
  xs.append(x)
  ys.append(y)
xs = sorted(xs)
ys = sorted(ys)
min_area = float('inf')

for li in range(n):
  for ri in range(li+1, n):
    left = xs[li]
    right = xs[ri]
    for bi in range(n):
      for ti in range(bi+1, n):
        bottom = ys[bi]
        top = ys[ti]
        area = (top - bottom) * (right - left)
        cnt = 0
        for i in range(n):
          xi, yi = xys[i]
          if (left <= xi <= right) and (bottom <= yi <= top):
            cnt += 1
            if cnt >= k:
              break
        if cnt >= k:
          min_area = min([min_area, area])

print(min_area)

Solution (Python):
import itertools

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

XY = [[int(x) for x in input().split()] for _ in range(N)]
XY.sort()
X,Y = zip(*XY)

min_area = 5*10**18

for left,right in itertools.combinations(range(N),2):
  width = X[right] - X[left]
  pts = sorted(XY[left:right+1], key = lambda xy: xy[1])
  for D in range(len(pts)):
    if D + K - 1 >= len(pts):
      break
    y_max = pts[D+K-1][1]
    y_min = pts[D][1]
    area = (y_max - y_min) * width
    if area < min_area:
      min_area = area
    
print(min_area)

Solution (Python):
from collections import defaultdict

def main():
    num, in_num = map(int, input().split())
    data = [list(map(int, input().split())) for i in range(num)]
    x_jiku, y_jiku = set(), set()

    for x, y in data:
        x_jiku.add(x)
        y_jiku.add(y)

    x_jiku = list(x_jiku)
    y_jiku = list(y_jiku)
    x_jiku.sort()
    y_jiku.sort()

    ans = 10 ** 20
    for x_kagen in x_jiku:
        for x_jogen in x_jiku[::-1]:
            if x_kagen >= x_jogen:
                break
            for y_kagen in y_jiku:
                for y_jogen in y_jiku[::-1]:
                    if y_kagen >= y_jogen:
                        break

                    if checl(x_kagen, x_jogen, y_kagen, y_jogen, data, in_num, num):
                        kari = (x_jogen - x_kagen) * (y_jogen - y_kagen)
                        if kari < ans:
                            ans = kari

    print(ans)

def checl(x_kagen, x_jogen, y_kagen, y_jogen, data, in_num, num):
    count = 0
    for i in range(num):
        if x_kagen <= data[i][0] <= x_jogen and y_kagen <= data[i][1] <= y_jogen:
            count += 1
    if count >= in_num:
        return 1
    else:
        return 0




if __name__ == '__main__':
    main()

Solution (Python):
import sys

N,K=map(int, sys.stdin.readline().split())
X=[]
Y=[]
XY=[]

for _ in range(N):
	x,y=map(int, sys.stdin.readline().split())
	X.append(x)
	Y.append(y)
	XY.append( (x,y) )

ans=float("inf")
for x1 in X:
	for y1 in Y:
		for x2 in X:
			for y2 in Y:
				if x1<x2 and y1<y2:
					cnt=0
					for x, y in XY:
						if x1<=x<=x2 and y1<=y<=y2:
							cnt+=1
	
					menseki=abs(x1-x2)*abs(y1-y2)
					if K<=cnt:
						ans=min(ans, menseki)
			
print ans

Solution (Python):
from itertools import combinations
N,K=map(int,input().split())

xs = set()
ys = set()
inl = []

for i in range(N):
    x,y=map(int,input().split())
    inl.append((x,y))
    xs.add(x)
    ys.add(y)

xs = list(xs)
ys = list(ys)
xs.sort()
ys.sort()

res = 9223372036854775807
for xlow, xhi in combinations(xs,2):
    for ylow, yhi in combinations(ys,2):
        cnt = 0
        for x, y in inl:
            cnt += (x >= xlow and x <= xhi and y >= ylow and y <= yhi)
        if cnt == K:
            res = min(res,(xhi - xlow) * (yhi - ylow))
print(res)

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

xy.sort()
ans = 10**20
for l in range(N - K + 1):
  for r in range(l + K - 1, N):
    tb = xy[l: r + 1]
    tb.sort(key = lambda x: x[1])
    for b in range(len(tb) - K + 1):
      t = b + K - 1
      ans = min(ans, (xy[r][0] - xy[l][0]) * (tb[t][1] - tb[b][1]))

print(ans)

Solution (Python):
import bisect
def count_generate(h,w,a):
    count = [[0]*w for j in range(h)]
    count[0][0] = a[0][0]
    for i in range(1,w):
        count[0][i] = count[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]
            count[i][j] = count[i-1][j]+cnt_w
    return count

def da_calc(p,q,x,y, da):
    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())
a = []
b = []
for i in range(N):
    ai, bi = map(int, input().split())
    a.append(ai)
    b.append(bi)
    
a_sorted = sorted(set(a))
b_sorted = sorted(set(b))
h = len(a_sorted)
w = len(b_sorted)

Map = [[0]*w for _ in range(h)]

for i in range(N):
    ai = bisect.bisect_left(a_sorted, a[i])
    bi = bisect.bisect_left(b_sorted, b[i])
    Map[ai][bi]+=1

count = count_generate(h, w, Map)
ans = float('inf')
for i in range(h):
    for j in range(i+1, h):
        for k in range(w):
            for l in range(k+1, w):
                
                if da_calc(i, k, j, l, count)>=K:
                    
                    ans = min(ans, (a_sorted[j]-a_sorted[i])
                              *(b_sorted[l]-b_sorted[k]))
print(ans)

Solution (Python):
n,k = map(int,input().split())
x_y = [list(map(int,input().split())) for _ in range(n)]
x_y = sorted(x_y,key=lambda x:(x[0],x[1]))
ans = float('inf')
for i in range(n-1):
    for j in range(i+1,n):
        if j-i+1<k:
            continue
        dis_x = x_y[j][0]-x_y[i][0]
        y_x = x_y[i:j+1]
        y_x = sorted(y_x,key=lambda x:x[1])
        for l in range(len(y_x)-1):
            for m in range(l+1,len(y_x)):
                if m-l+1<k:
                    continue
                dis_y = y_x[m][1]-y_x[l][1]
                ans = min(ans,dis_x*dis_y)
print(ans)

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

X = []
Y = []
Z = []
for i in range(N):
    x,y = list(map(int,input().split()))
    X.append(x)
    Y.append(y)
    Z.append([x,y])

X.sort()
Y.sort()

min_rec=10**27

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):
                count=0
                for n in range(N):
                    if Z[n][0]>=X[i] and Z[n][0]<=X[j] and Z[n][1]>=Y[k] and Z[n][1]<=Y[l]:
                        count+=1
                if count==K:
                    min_rec = min(min_rec,(X[j]-X[i])*(Y[l]-Y[k]))

print(min_rec)

Solution (Python):
n,k=map(int,input().split())
l=[list(map(int,input().split())) for i in range(n)]
x=[l[i][0] for i in range(n)]
x.sort()
y=[l[i][1] for i in range(n)]
y.sort()
ans=[]
for i1 in range(n):
  for i2 in range(i1+1,n):
    for i3 in range(n):
      for i4 in range(i3+1,n):
        ct=0
        for i5 in range(n):
          if x[i1]<=l[i5][0]<=x[i2] and y[i3]<=l[i5][1]<=y[i4]:ct+=1
        if ct>=k:
          ans.append(abs(x[i1]-x[i2])*abs(y[i3]-y[i4]))
print(min(ans))

Solution (Python):
import heapq
n,k=map(int,input().split())
l=[list(map(int,input().split())) for i in range(n)]
x=[l[i][0] for i in range(n)]
x.sort()
y=[l[i][1] for i in range(n)]
y.sort()
ans=[]
for i1 in range(n):
  for i2 in range(i1+1,n):
    for i3 in range(n):
      for i4 in range(i3+1,n):
        ct=0
        for i5 in range(n):
          if x[i1]<=l[i5][0]<=x[i2] and y[i3]<=l[i5][1]<=y[i4]:ct+=1
        if ct>=k:
          ans.append(abs(x[i1]-x[i2])*abs(y[i3]-y[i4]))
heapq.heapify(ans)
print(heapq.heappop(ans))

Solution (Python):
n,k=map(int,input().split())
l=[list(map(int,input().split())) for i in range(n)]
x=[l[i][0] for i in range(n)]
x.sort()
y=[l[i][1] for i in range(n)]
y.sort()
ans=[]
for i1 in range(n):
  for i2 in range(i1,n):
    for i3 in range(n):
      for i4 in range(i3,n):
        ct=0
        for i5 in range(n):
          if min(x[i1],x[i2])<=l[i5][0]<=max(x[i1],x[i2]) and min(y[i3],y[i4])<=l[i5][1]<=max(y[i3],y[i4]):ct+=1
        if ct>=k:
          ans.append(abs(x[i1]-x[i2])*abs(y[i3]-y[i4]))
print(min(ans))

Solution (Python):
from itertools import combinations as cc
l = []
n,k = map(int, input().split())
xs,ys = set(),set()
t = 10**24
for _ in range(n):
  x,y = map(int, input().split())
  xs.add(x)
  ys.add(y)
  l.append((x,y))
xs = sorted(list(xs))
ys = sorted(list(ys))
for xl,xr in cc(xs,2):
  for yl,yr in cc(ys,2):
    cnt = 0
    for x,y in l:
      if xl<=x<=xr and yl<=y<=yr:
        cnt += 1
      if cnt >= k:
        s = (xr-xl)*(yr-yl)
        if t > s:
          t = s
print(t)

Solution (Python):
N,K=map(int,input().split())
xy=[]
X=[]
Y=[]
for i in range(N):
    x,y=map(int,input().split())
    xy.append([x,y])
xy.sort()
X=[i[0] for i in xy]
Y=[i[1] for i in xy]
ans=10**30
for i in range(K,N+1):
    for j in range(N+1-i):
        X_=X[j:j+i]
        Y_=Y[j:j+i]
        Y_.sort()
        a=max(X_)-min(X_)
        for k in range(i-K+1):
            z=Y_[k:k+K]
            b=max(z)-min(z)
            ans=min(ans,a*b)
print(ans)

Solution (Python):
import itertools
import sys

import numpy as np

sys.setrecursionlimit(10000)
INF = float('inf')

N, K = list(map(int, next(sys.stdin).split()))
XY = np.array([list(map(int, next(sys.stdin).split())) for _ in range(N)])

X = XY[:, 0]
Y = XY[:, 1]
X = X[Y.argsort()]
Y = Y[Y.argsort()]

ans = INF
for xi, xj in itertools.combinations(range(N), r=2):
    L, r = min(X[xi], X[xj]), max(X[xi], X[xj])
    xconds = (L <= X) & (X <= r)

    yi = 0
    yj = 1
    while yj < N:
        if np.sum(xconds[yi:yj + 1]) >= K:
            b, u = min(Y[yi], Y[yj]), max(Y[yi], Y[yj])
            ans = min(ans, (r - L) * (u - b))
            yi += 1
        else:
            yj += 1
        if yi == yj:
            yj += 1
print(ans)

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

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


dots = XY[:]

import sys
INT_MAX = sys.maxsize


def sub_f(x, ans_list):
    right_x, left_x = x[0], x[1]
    ans = INT_MAX
    for ((_, under_y), (_, top_y)) in itertools.combinations(dots, 2):
        if under_y > top_y:
            under_y, top_y = top_y, under_y
        counter = 0
        for d_x, d_y in dots:
            if  (left_x <= d_x) and (d_x <= right_x) and (under_y <= d_y) and (d_y <= top_y):
                counter += 1

        if counter >= K:
            area = (top_y-under_y) * (right_x-left_x)
            ans = min(ans, area)
    
    ans_list.append(ans)

import itertools
multiprocessing_inputs = []
for ((left_x, _), (right_x, _)) in itertools.combinations(dots, 2):
    if left_x > right_x:
        left_x, right_x = right_x, left_x
    
    multiprocessing_inputs.append((right_x, left_x))
    


import threading
ans_list = []
threadlist = []
for x in multiprocessing_inputs:
    
    th = threading.Thread(target=sub_f, args=(x, ans_list))
    threadlist.append(th)
for th in threadlist:
    th.start()
for th in threadlist:
    th.join()

ans = min(ans_list)
print(ans)

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

XY = []
for _ in range(N):
    x, y = map(int, input().split())
    XY.append((x, y))
    
dots = XY[:]

import sys
INT_MAX = sys.maxsize

ans = INT_MAX

import itertools
for ((left_x, _), (right_x, _)) in itertools.combinations(dots, 2):
    if left_x > right_x:
        left_x, right_x = right_x, left_x
    for ((_, under_y), (_, top_y)) in itertools.combinations(dots, 2):
        if under_y > top_y:
            under_y, top_y = top_y, under_y
        counter = 0
        for d_x, d_y in dots:
            if  (left_x <= d_x) and (d_x <= right_x) and (under_y <= d_y) and (d_y <= top_y):
                counter += 1
                
        if counter >= K:
            area = (top_y-under_y) * (right_x-left_x)
            if ans > area:
                ans = area
            
print(ans)

Solution (Python):
N,K=map(int, input().split())
X,Y=map(list,zip(*[list(map(int,input().split())) for i in range(N)]))
x=sorted(X)
y=sorted(Y)
c=[[0]*(N+1) for i in range(N+1)]
for i in range(N):
    c[x.index(X[i])+1][y.index(Y[i])+1]=1
for i in range(N):
    for j in range(N):
        c[i+1][j+1]+=c[i][j+1]+c[i+1][j]-c[i][j]
ans=5*10**18
for t in range(1,N):
    for b in range(t+1,N+1):
        for l in range(1,N):
            for r in range(l+1,N+1):
                count=c[b][r]-c[b][l-1]-c[t-1][r]+c[t-1][l-1]
                if count>=K:
                    ans=min(ans,(y[r-1]-y[l-1])*(x[b-1]-x[t-1]))
                    break
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
import itertools
n,k=map(int,input().split())
X,Y,XY=[0]*n,[0]*n,[0]*n
for i in range(n):
  x,y=map(int,input().split())
  X[i],Y[i],XY[i]=x,y,[x,y]
X.sort()
Y.sort()
def count(x1,x2,y1,y2):
  ct=0
  for x,y in XY:
    if x1<=x<=x2 and y1<=y<=y2:
      ct+=1
  return ct
ans=float("inf")
for x1,x2 in itertools.combinations(X,2):
  for y1,y2 in itertools.combinations(Y,2):
    if count(x1,x2,y1,y2)==k:
      ans=min(ans,abs((x1-x2)*(y1-y2)))
print(ans)

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

N,K=[int(val) for val in input().split()]

list_x=list()
list_y=list()
list_z=list()

ans=float('inf')

for i in range(N):
  x,y=(int(val) for val in input().split())
  list_x.append(x)
  list_y.append(y)
  list_z.append((x,y))


list_x.sort()
list_y.sort()

for i in list_y:
  for j in list_y:
    if i<=j:
      break
    else:
      for k in list_x:
        for l in list_x:
          if k<=l:
            break
          else:
            cnt=0
            for m in range(len(list_z)):
              if l<=list_z[m][0]<=k and j<=list_z[m][1]<=i:
                cnt+=1
              if K <= cnt:
                tmp=(i-j)*(k-l)
                if tmp < ans:
                  ans=tmp
                break

print(ans)

Solution (Python):
N,K = [ int(it) for it in input().split() ]
li = [ [ int(it) for it in input().split() ]  for i in range(N) ]

lix = [0]*N
liy = [0]*N
for i in range(N):
  x,y = li[i]
  lix[i] = [x,i,0]
  liy[i] = [y,i,0]
lix.sort( key = lambda x:x[0] )
liy.sort( key = lambda x:x[0] )
for i in range(N):
  lix[i][2]=i
  liy[i][2]=i
lix.sort( key = lambda x:x[1] )
liy.sort( key = lambda x:x[1] )

lim = [ [0]*(N+1) for i in range(N+1) ]
for i in range(N):
  lim[ 1+lix[i][2] ][ 1+liy[i][2] ] = 1
for i in range(1,N+1):
  for j in range(1,N+1):
    lim[i][j]+=lim[i-1][j]+lim[i][j-1]-lim[i-1][j-1]

lix.sort( key = lambda x:x[2] )
liy.sort( key = lambda x:x[2] )

ma = 1000000000000000000000000000000000000000
for xi in range(N):
  for xj in range(xi+1,N+1):
    for yi in range(N):
      for yj in range(yi+1,N+1):
        if ( lim[xj][yj] - lim[xj][yi] - lim[xi][yj] + lim[xi][yi]  >= K ):
          s = (lix[xj-1][0]-lix[xi][0])*(liy[yj-1][0]-liy[yi][0])
          ma = min(s,ma)
print ( ma )

Solution (Python):
from itertools import*
from math import*
from collections import deque
from collections import defaultdict
from itertools import permutations
from heapq import*
from collections import Counter
from itertools import*
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf = 10**18
mod = 10**9+7
from functools import reduce
import sys
sys.setrecursionlimit(10**7)

n,k = map(int,input().split())
f = lambda x,y :(min(x,y),max(x,y))
xy = [tuple(map(int,input().split())) for _ in range(n)]
S = float("inf")
for (a,b) in combinations(range(n),2):
    for(c,d) in combinations(range(n),2):
        lx,rx = f(xy[a][0],xy[b][0])
        dy,uy = f(xy[c][1],xy[d][1])
        cnt = 0
        for i in xy:
            if lx<=i[0]<=rx and dy<=i[1]<=uy:
                cnt += 1
        if cnt >= k:
            S = min(S,(rx-lx)*(uy-dy))
print(S)