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 math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

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

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

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

def count_inside(p1, p2, points):
    cnt = 0
    min_x = min(p1[0], p2[0])
    min_y = min(p1[1], p2[1])
    max_x = max(p1[0], p2[0])
    max_y = max(p1[1], p2[1])
    for p in points:
        if min_x <= p[0] <= max_x and min_y <= p[1] <= max_y:
            cnt += 1
    return cnt

def main():
    N, K = LI()
    points = []
    X, Y = [], []
    for i, _ in enumerate(range(N)):
        x, y = LI()
        points.append((x, y))
        X.append((x, i))
        Y.append((y, i))
    X = sorted(X, key=lambda x: x[0])
    Y = sorted(Y, key=lambda x: x[0])
    mapOrder2x = {}
    mapOrder2y = {}

    zaatsu_X = [-1 for _ in range(N)]
    zaatsu_Y = [-1 for _ in range(N)]

    for order, (x, i) in enumerate(X):
        zaatsu_X[i] = order
        mapOrder2x[order] = x

    for order, (y, i) in enumerate(Y):
        zaatsu_Y[i] = order
        mapOrder2y[order] = y

    assert(-1 not in zaatsu_X)
    assert(-1 not in zaatsu_Y)

    G = [[0 for _ in range(N)] for __ in range(N)]
    cumsum = [[0 for _ in range(N+1)] for __ in range(N+1)]

    for x, y in zip(zaatsu_X, zaatsu_Y):
        G[x][y] = 1

    for x in range(N):
        for y in range(N):
            cumsum[x+1][y+1] = cumsum[x+1][y] + cumsum[x][y+1] - cumsum[x][y] + G[x][y]

    def query_cumsum2d(s, r1, r2, c1, c2):
        if c2 < c1:
            c1, c2 = c2, c1
        if r2 < r1:
            r1, r2 = r2, r1
        return s[r2][c2] - s[r2][c1] - s[r1][c2] +s[r1][c1]

    def calc_area(x1, x2, y1, y2, mapx, mapy):
        return abs(mapx[x1] - mapx[x2]) * abs(mapy[y1] - mapy[y2])

    area = inf
    for r1 in range(0, N):
        for r2 in range(r1, N+1):
            for c1 in range(0, N):
                for c2 in range(c1, N+1):
                    if K == query_cumsum2d(cumsum, r1, r2, c1, c2):
                        
                        _area = calc_area(r1, r2-1, c1, c2-1, mapOrder2x, mapOrder2y)
                        area = min(area, _area)
    print(area)
main()

Solution (Python):
N, K = map(int, input().split())
x = [0] * N
y = [0] * N
for i in range(N):
    x[i], y[i] = map(int, input().split())
ans = float('inf')
for x1 in x:
    for x2 in x:
        if x1 > x2:
            continue
        for y1 in y:
            for y2 in y:
                if y1 > y2:
                    continue
                area = (x2 - x1) * (y2 - y1)
                if area >= ans:
                    continue
                cnt = 0
                for i in range(N):
                    if x1 <= x[i] <= x2 and y1 <= y[i] <= y2:
                        cnt += 1
                if cnt >= K:
                    ans = area
print(ans)

Solution (Python):
n, kosuu = 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 = sorted(X, reverse=True)
Y = sorted(Y, reverse=True)

s_min = 10**20
for i in range(n):
    for j in range(n):
        for k in range(n):
            for l in range(n):
                count = 0
                x_max = X[i]
                x_min = X[-1*(j+1)]
                if x_max <= x_min:
                    continue
                y_max = Y[k]
                y_min = Y[-1*(l+1)]
                if y_max <= y_min:
                    continue

                s = abs(x_max-x_min)*abs(y_max-y_min)

                for m in range(n):
                    x = XY[m][0]
                    y = XY[m][1]
                    if (x <= x_max and x >= x_min) and (y <= y_max and y >= y_min):
                        count += 1
                if count >= kosuu:
                    s_min = min(s, s_min)

print(s_min)

Solution (Python):

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N,K=MI()
    xy=[[0,0] for _ in range(N)]
    y=[0]*N
    
    for i in range(N):
        xy[i][0],xy[i][1]=MI()
        y[i]=xy[i][1]
        
    xy.sort()
    y.sort()
    
    def count(l,r,d,u):
        cnt=0
        for i in range(N):
            if l<=xy[i][0]<=r:
                if d<=xy[i][1]<=u:
                    cnt+=1
        return cnt
    
    ans=10**20
    for i in range(N):
        for j in range(i+1,N):
            for ii in range(N):
                for jj in range(ii+1,N):
                    l=xy[i][0]
                    r=xy[j][0]
                    d=y[ii]
                    u=y[jj]
                    if count(l,r,d,u)==K:
                        ans=min(ans,(r-l)*(u-d))
    print(ans)

main()

Solution (Python):

import sys
from itertools import combinations

def _solve(y1, y2, sorted_points, K):
    y1, y2 = tuple(sorted([y1, y2]))
    x = tuple(x for x, y in sorted_points if y1 <= y <= y2)
    if len(x) < K:
        return float('inf')
    return min((y2 - y1) * (x2 - x1) for x1, x2 in zip(x, x[K-1:]))

def solve(N: int, K: int, x: "List[int]", y: "List[int]"):
    sorted_points = tuple(sorted(zip(x, y)))
    return min(_solve(y1, y2, sorted_points, K) for y1, y2 in combinations(y, 2))


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

if __name__ == '__main__':
    main()

Solution (Python):
n, k = map(int, input().split())
x_y = []
x = []
y = []
for i in range(n):
    a,b = map(int, input().split())
    x.append(a)
    y.append(b)
    x_y.append([a,b])
ans = 10**19
def check(a,b,c,d):
    count = 0
    for i in range(n):
        s,t = x_y[i]
        if a <= s <= b and c <= t <= d:
            count += 1
    if count >= k:
        return True
    else:
        return False
x.sort()
y.sort()
for x_1 in range(n):
    for x_2 in range(x_1+1,n):
        for y_1 in range(n):
            for y_2 in range(y_1+1,n):
                if check(x[x_1],x[x_2],y[y_1],y[y_2]):
                    rect_area = (x[x_2] - x[x_1]) * (y[y_2] - y[y_1])
                    ans = min(ans, rect_area)
print(ans)

Solution (Python):
from itertools import accumulate
n, k = map(int, input().split())
XY = [list(map(int, input().split())) for _ in range(n)]
X, Y = zip(*XY)
def compress(arr):
    *XS, = set(arr)
    XS.sort()
    return {e: i+1 for i, e in enumerate(XS)}
Xlabel = compress(X)
Ylabel = compress(Y)
rX = {j:i for i,j in Xlabel.items()}
rY = {j:i for i,j in Ylabel.items()}
lX = len(Xlabel)
lY = len(Ylabel)
F = [[0]*(lX+1) for _ in range(lY+1)]
for x, y in XY:
  F[Ylabel[y]][Xlabel[x]] = 1
for i in range(lY):
  F[i+1] = list(accumulate(F[i+1]))
F = list(zip(*F))
for j in range(lY):
  F[j+1] = list(accumulate(F[j+1]))
F = list(zip(*F))
ans = float("inf")
for y1 in range(lY):
  for y2 in range(y1+1, lY+1):
    for x1 in range(lX):
      for x2 in range(x1+1, lX+1):
        count = F[y2][x2] - F[y1][x2] - F[y2][x1] + F[y1][x1]
        if count >= k:
          temp = (rX[x2]-rX[x1+1]) * (rY[y2]-rY[y1+1])
          ans = min(ans, temp)
print(ans)

Solution (Python):
from itertools import accumulate
n, k = map(int, input().split())
XY = [list(map(int, input().split())) for _ in range(n)]
X, Y = zip(*XY)
def compress(arr):
    *XS, = set(arr)
    XS.sort()
    return {e: i+1 for i, e in enumerate(XS)}
Xlabel = compress(X)
Ylabel = compress(Y)
rX = {j:i for i,j in Xlabel.items()}
rY = {j:i for i,j in Ylabel.items()}
lX = len(Xlabel)
lY = len(Ylabel)
F = [[0]*(lX+1) for _ in range(lY+1)]
for x, y in XY:
  F[Ylabel[y]][Xlabel[x]] = 1
for i in range(lY):
  F[i+1] = list(accumulate(F[i+1]))
F = list(zip(*F))
for j in range(lY):
  F[j+1] = list(accumulate(F[j+1]))
F = list(zip(*F))
ans = float("inf")
for y1 in range(lY):
  for y2 in range(y1+1, lY+1):
    for x1 in range(lX):
      for x2 in range(x1+1, lX+1):
        count = F[y2][x2] - F[y1][x2] - F[y2][x1] + F[y1][x1]
        if count >= k:
          temp = (rX[x2]-rX[x1+1]) * (rY[y2]-rY[y1+1])
          ans = min(ans, temp)
print(ans)

Solution (Python):

import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from functools import lru_cache
import bisect
import re
import queue


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [input() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [int(input()) for i in range(n)]


class Math():
    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

    @staticmethod
    def roundUp(a, b):
        return -(-a // b)

    @staticmethod
    def toUpperMultiple(a, x):
        return Math.roundUp(a, x) * x

    @staticmethod
    def toLowerMultiple(a, x):
        return (a // x) * x

    @staticmethod
    def nearPow2(n):
        if n <= 0:
            return 0
        if n & (n - 1) == 0:
            return n
        ret = 1
        while(n > 0):
            ret <<= 1
            n >>= 1
        return ret

    @staticmethod
    def sign(n):
        if n == 0:
            return 0
        if n < 0:
            return -1
        return 1

    @staticmethod
    def isPrime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3, d + 1, 2):
            if n % i == 0:
                return False
        return True


class PriorityQueue:
    def __init__(self, l=[]):
        self.__q = l
        heapq.heapify(self.__q)
        return

    def push(self, n):
        heapq.heappush(self.__q, n)
        return

    def pop(self):
        return heapq.heappop(self.__q)


sys.setrecursionlimit(1000000)
MOD = int(1e09) + 7
INF = int(1e30)


def main():
    
    N, K = Scanner.map_int()
    X = [0] * N
    Y = [0] * N
    for i in range(N):
        x, y = Scanner.map_int()
        X[i] = x
        Y[i] = y
    sx = sorted(X)
    sy = sorted(Y)
    ans = INF
    for l in range(N-1):
        for r in range(l+1, N):
            for b in range(N-1):
                for t in range(b+1, N):
                    left = sx[l]
                    right = sx[r]
                    bottom = sy[b]
                    top = sy[t]
                    cnt = 0
                    for i in range(N):
                        if left <= X[i] <= right and bottom <= Y[i] <= top:
                            cnt += 1
                    if cnt >= K:
                        ans = min(ans, (right-left)*(top-bottom))
    print(ans)
    return


if __name__ == "__main__":
    main()

Solution (Python):
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def MI(N,num):
    if N<=0:
        return [[] for _ in range(num)]
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [LI() for _ in range(N)]
        return map(list, zip(*read_all))



from bisect import bisect_left
from itertools import product,combinations

from operator import itemgetter
def index_sort(A):
    A_sort = sorted(enumerate(A),key=itemgetter(1))
    index = [a[0] for a in A_sort]
    sorted_A = [a[1] for a in A_sort]
    return index, sorted_A

N,K = LI()
x,y = MI(N,2)

index,_ = index_sort(x)
x2 = [x[i] for i in index]
y2 = [y[i] for i in index]

A = list(product(combinations(range(N),2),repeat=2))
ans = float('inf')
for a in A:
    xmin = min(x[a[0][0]],x[a[0][1]])
    xmax = max(x[a[0][0]],x[a[0][1]])
    ymin = min(y[a[1][0]],y[a[1][1]])
    ymax = max(y[a[1][0]],y[a[1][1]])
    S = (xmax-xmin)*(ymax-ymin)
    if S >= ans:
        continue
    l = bisect_left(x2,xmin)
    r = bisect_left(x2,xmax)
    num = 0
    for i in range(l,r+1):
        if ymin <= y2[i] <= ymax:
            num += 1
    if num >= K:
        ans = S

print(ans)

Solution (Python):
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def MI(N,num):
    if N<=0:
        return [[] for _ in range(num)]
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [LI() for _ in range(N)]
        return map(list, zip(*read_all))



from bisect import bisect_left
from itertools import product,combinations

from operator import itemgetter
def index_sort(A):
    A_sort = sorted(enumerate(A),key=itemgetter(1))
    index = [a[0] for a in A_sort]
    sorted_A = [a[1] for a in A_sort]
    return index, sorted_A

N,K = LI()
x,y = MI(N,2)

index,_ = index_sort(x)
x2 = [x[i] for i in index]
y2 = [y[i] for i in index]

A = list(product(combinations(range(N),2),repeat=2))
ans = float('inf')
for a in A:
    xmin = min(x[a[0][0]],x[a[0][1]])
    xmax = max(x[a[0][0]],x[a[0][1]])
    ymin = min(y[a[1][0]],y[a[1][1]])
    ymax = max(y[a[1][0]],y[a[1][1]])
    S = (xmax-xmin)*(ymax-ymin)
    if S >= ans:
        continue
    l = bisect_left(x2,xmin)
    r = bisect_left(x2,xmax)
    num = 0
    for i in range(l,r+1):
        if ymin <= y2[i] <= ymax:
            num += 1
    if num >= K:
        ans = S

print(ans)

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

ans = 1e30
for lx in range(N):
    for rx in range(lx+K, N+1):
        Q = sorted(P[lx:rx], key=lambda x:x[1])
        for ly in range(len(Q)):
            R = Q[ly:ly+K]
            if len(R)>=K: ans = min(ans, (P[rx-1][0]-P[lx][0])*(R[-1][1]-R[0][1]))
print(ans)

Solution (Python):
N, K = map(int, input().split())
ls = []
for i in range(N):
  x, y = map(int, input().split())
  ls += [(x,y)]
m = -1
for i in range(N):
  for j in range(i+1,N):
    for p in range(N):
      for q in range(p+1,N):
        
        x1, y1 = ls[i]
        x2, y2 = ls[j]
        x3, y3 = ls[p]
        x4, y4 = ls[q]
        cnt = 0
        flag = False
        X1 = min(x1, x2)
        X2 = max(x1, x2)
        Y1 = min(y3, y4)
        Y2 = max(y3, y4)
        for a in range(N):
          x, y = ls[a]
          """
          print('"""""""')
          print(cnt)
          print(X1,X2,x)
          print(Y1,Y2,y)
          """
          if X1<=x<=X2 and Y1<=y<=Y2:
            cnt += 1
          if cnt>=K:
            n = (X2-X1)*(Y2-Y1)
            if m==-1 or n<m:
              m = n
            break
print(m)

Solution (Python):
n, k = map(int, input().split())
XY = [list(map(int, input().split())) for _ in [0] * n]
a = XY.sort()
ans = float("inf")
for i in range(n - k + 1):
    for j in range(i + k, 1 + n):
        x = XY[j - 1][0] - XY[i][0]
        now = XY[i:j]
        now.sort(key=lambda x: x[1])
        for w in range(j - i - k + 1):
            ans = min(ans, x * (now[w + k - 1][1] - now[w][1]))

print(ans)

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


def check(l, r, b, t):
    cnt = 0
    for x, y in XY:
        if r >= x and x >= l and t >= y and b >= y:
            cnt += 1
    return cnt >= K


ans = 10**20

for i in range(N - K + 1):
    xl = x_sort[i][0]
    for j in range(i + K - 1, N):
        dx = x_sort[j][0] - xl

        points = sorted(x_sort[i: j+1], key=lambda x: x[1])

        rest = j - i + 1
        for p in range(rest - K + 1):
            yd = points[p][1]
            for q in range(p + K - 1, rest):
                dy = points[q][1] - yd
                ans = min(ans, dx*dy)

print(ans)

Solution (Python):
from sys import stdout
printn = lambda x: stdout.write(str(x))
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True 
BIG = 10**19
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

n,k = inm()
x = []
y = []
for i in range(n):
    xx,yy = inm()
    x.append(xx)
    y.append(yy)
mn = BIG
for i in range(n-1):
    for j in range(i+1,n):
        xn = min(x[i],x[j])
        xx = max(x[i],x[j])
        for ii in range(n-1):
            for jj in range(ii+1,n):
                yn = min(y[ii],y[jj])
                yx = max(y[ii],y[jj])
                cnt = 0
                for m in range(n):
                    if xn<=x[m]<=xx and yn<=y[m]<=yx:
                        cnt += 1
                if cnt>=k:
                    mn = min(mn, (xx-xn)*(yx-yn))
print(mn)

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

def main():
    N,K = map(int,input().split())
    INF = float('inf')
    dot = []
    for _ in range(N):
        x,y = map(int,input().split())
        dot.append((x,y))
    
    dot.sort(key = itemgetter(0,1))
    ans = INF
    for xdown in range(N):
        for xup in range(N):
            if xup - xdown + 1 < K:
                continue
            else:
                use = dot[xdown:xup+1]
                a,b = use[-1][0],use[0][0]
                use.sort(key = itemgetter(1))
                l = len(use)
                for udown in range(l):
                    for uup in range(l):
                        if uup - udown + 1 == K:
                            two = use[udown:uup+1]
                            c,d = two[-1][1],two[0][1]
                            S = (a-b)*(c-d)
                            ans = min(ans,S)
                            
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
import sys
import itertools

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, K = lr()
XY = [lr() for _ in range(N)]
XY.sort()
answer = float('inf')

for i, j in itertools.combinations(range(N), 2):
    xleft = XY[i][0]
    xright = XY[j][0]
    candidate = sorted(XY[i:j+1], key=lambda xy: xy[1])
    if len(candidate) < K:
        continue
    for s in range(len(candidate) - K + 1):
        yup = candidate[s+K-1][1]
        ylow = candidate[s][1]
        area = (xright - xleft) * (yup - ylow)
        if area < answer:
            answer = area

print(answer)

Solution (Python):
import sys
import itertools

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, K = lr()
XY = [lr() for _ in range(N)]
XY.sort()
answer = float('inf')

for left,right in itertools.combinations(range(N),2):
  xleft = XY[left][0]
  xright = XY[right][0]
  pts = sorted(XY[left:right+1], key = lambda xy: xy[1])
  if len(pts) < K:
    continue
  for D in range(len(pts) - K + 1):
    y_max = pts[D+K-1][1]
    y_min = pts[D][1]
    area = (y_max - y_min) * (xright - xleft)
    if area < answer:
      answer = area
    
print(answer)

Solution (Python):
import sys
import itertools

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, K = lr()
XY = [lr() for _ in range(N)]
XY.sort()
answer = float('inf')

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

Solution (Python):
import sys
import itertools

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, K = lr()
XY = [lr() for _ in range(N)]
XY.sort()
answer = float('inf')

for left,right in itertools.combinations(range(N),2):
  width = XY[right][0] - XY[left][0]
  pts = sorted(XY[left:right+1], key = lambda xy: xy[1])
  if len(pts) < K:
    continue
  for D in range(len(pts) - K + 1):
    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 < answer:
      answer = area
    
print(answer)

Solution (Python):
import sys
import itertools

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, K = lr()
XY = [lr() for _ in range(N)]
XY.sort()
answer = float('inf')

for left,right in itertools.combinations(range(N),2):
  width = XY[right][0] - XY[left][0]
  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 < answer:
      answer = area
    
print(answer)

Solution (Python):
n, m = map(int, input().split())
x = [0]*n
y = [0]*n
for i in range(n):
    a, b = map(int, input().split())
    x[i] = a
    y[i] = b

ans = 10**30
for i in range(n):
    for j in range(i):
        for k in range(n):
            for l in range(k):

                left = min(x[i], x[j])
                right = max(x[i], x[j])
                down = min(y[k], y[l])
                up = max(y[k], y[l])

                if left == right or up == down:
                    continue

                cnt = 0
                for r in range(n):
                    if left <= x[r] and x[r] <= right and down <= y[r] and y[r] <= up:
                        cnt += 1
                if cnt >= m:
                    ans = min(ans, (right - left) * (up - down))
print(ans)

Solution (Python):
def main():
    n,k=map(int,input().split())
    xy=[list(map(int,input().split())) for i in range(n)]
    x,y=[[xy[i][0],i] for i in range(n)],[[xy[i][1],i] for i in range(n)]
    x.sort()
    y.sort()
    ans=10**18*4
    for i1 in range(n):
        i1_sub=n-i1
        x_sub1=x[i1][0]
        for l1 in range(i1_sub,1,-1):
            x_sub2=x[i1+l1-1][0]
            for i2 in range(n):
                i2_sub=n-i2
                y_sub1=y[i2][0]
                x_subsub=x_sub2-x_sub1
                for l2 in range(i2_sub,1,-1):
                    y_sub2=y[i2+l2-1][0]
                    z=0
                    for i in range(n):
                        if x_sub1<=xy[i][0]<=x_sub2 and y_sub1<=xy[i][1]<=y_sub2:
                            z+=1
                        if z>=k:
                            ans=min(x_subsub*(y_sub2-y_sub1),ans)
                            break
                    else:
                        break
    print(ans)
main()

Solution (Python):
n,k=map(int,input().split())
xy=[list(map(int,input().split())) for i in range(n)]
x,y=[[xy[i][0],i] for i in range(n)],[[xy[i][1],i] for i in range(n)]
x.sort()
y.sort()
ans=10**18*4
for i1 in range(n):
    i1_sub=n-i1
    x_sub1=x[i1][0]
    for l1 in range(i1_sub,1,-1):
        x_sub2=x[i1+l1-1][0]
        for i2 in range(n):
            i2_sub=n-i2
            y_sub1=y[i2][0]
            x_subsub=x_sub2-x_sub1
            for l2 in range(i2_sub,1,-1):
                y_sub2=y[i2+l2-1][0]
                z=0
                for i in range(n):
                    if x_sub1<=xy[i][0]<=x_sub2 and y_sub1<=xy[i][1]<=y_sub2:
                        z+=1
                    if z>=k:
                        ans=min(x_subsub*(y_sub2-y_sub1),ans)
                        break
                else:
                    break
print(ans)

Solution (Python):
n,k=map(int,input().split())
x,y=[[0,0] for i in range(n)],[[0,0] for i in range(n)]
xy=[list(map(int,input().split())) for i in range(n)]
for i in range(n):
    x_sub,y_sub=xy[i]
    x[i][0]=x_sub
    x[i][1]=i
    y[i][0]=y_sub
    y[i][1]=i
x.sort()
y.sort()
ans=(10**18)*5
for i1 in range(n):
    for l1 in range(n-i1,1,-1):
        for i2 in range(n):
            for l2 in range(n-i2,1,-1):
                x_sub1=x[i1][0]
                x_sub2=x[i1+l1-1][0]
                y_sub1=y[i2][0]
                y_sub2=y[i2+l2-1][0]
                z=[0]*n
                for i in range(n):
                    if x_sub1<=xy[i][0]<=x_sub2 and y_sub1<=xy[i][1]<=y_sub2:
                        z[i]=1
                if sum(z)>=k:
                    ans=min((x_sub2-x_sub1)*(y_sub2-y_sub1),ans)
print(ans)

Solution (Python):
n,k=map(int,input().split())
x,y=[[0,0] for i in range(n)],[[0,0] for i in range(n)]
xy=[list(map(int,input().split())) for i in range(n)]
for i in range(n):
    x_sub,y_sub=xy[i]
    x[i][0]=x_sub
    x[i][1]=i
    y[i][0]=y_sub
    y[i][1]=i
x.sort()
y.sort()
ans=(10**18)*5
for i1 in range(n):
    for l1 in range(n-i1,1,-1):
        for i2 in range(n):
            for l2 in range(n-i2,1,-1):
                x_sub1=x[i1][0]
                x_sub2=x[i1+l1-1][0]
                y_sub1=y[i2][0]
                y_sub2=y[i2+l2-1][0]
                z=[0]*n
                for i in range(n):
                    if x_sub1<=xy[i][0]<=x_sub2 and y_sub1<=xy[i][1]<=y_sub2:
                        z[i]=1
                if sum(z)>=k:
                    ans=min((x_sub2-x_sub1)*(y_sub2-y_sub1),ans)
                else:
                    break
print(ans)

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

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

XY.sort()


answer = []
for i in range(N):
  for k in range(K, N + 1):
    if i + k - 1 >= N:
      break
    dx = XY[i + k - 1][0] - XY[i][0]
    Y = []
    for x, y in XY[i: i + k]:
      Y.append(y)
    Y.sort()
    lenY = len(Y)
    for j in range(k):
      if j + K - 1 == lenY:
        break
      dy = Y[j + K - 1] - Y[j]
      answer.append(dx * dy)

print(min(answer))

Solution (Python):
N,K=map(int,input().split())
XY=[list(map(int,input().split())) for i in range(N)]
XY=sorted(XY,key=lambda x:x[0])
Mlst=[]

if N>=2:
    for s1 in range(N-1):
        for s2 in range(s1+1,N):
            x1,y1=XY[s1]
            x2,y2=XY[s2]
            y1,y2=min(y1,y2),max(y1,y2)
            count=2
            for i in range(s1+1,s2):
                count+=y1<=XY[i][1]<=y2
            if count>=K:
                Mlst.append((y2-y1)*(x2-x1))
if N>=3:
    for s1 in range(N-2):
        for s2 in range(s1+1,N-1):
            for s3 in range(s2+1,N):
                x1,y1=XY[s1]
                x2,y2=XY[s2]
                x3,y3=XY[s3]
                x1,x2=x1,x3
                y1,y2=min(y1,y2,y3),max(y1,y2,y3)
                count=2
                for i in range(s1+1,s3):
                    count+=y1<=XY[i][1]<=y2
                if count>=K:
                    Mlst.append((y2-y1)*(x2-x1))
if N>=4:
    for s1 in range(N-3):
        for s2 in range(s1+1,N-2):
            for s3 in range(s2+1,N-1):
                for s4 in range(s3+1,N):
                    x1,y1=XY[s1]
                    x2,y2=XY[s2]
                    x3,y3=XY[s3]
                    x4,y4=XY[s4]
                    x1,x2=x1,x4
                    y1,y2=min(y1,y2,y3,y4),max(y1,y2,y3,y4)
                    count=2
                    for i in range(s1+1,s4):
                        count+=y1<=XY[i][1]<=y2
                    if count>=K:
                        Mlst.append((y2-y1)*(x2-x1))
print(min(Mlst))

Solution (Python):

N, K = map(int, input().split(' '))
points = [list(map(int, input().split(' '))) for i in range(N)]

X = list(set([x for x, y in points]))
Y = list(set([y for x, y in points]))

X.sort()
Y.sort()

ans = float('inf')
for i, min_x in enumerate(X):
    for max_x in X[i+1:]:
        for j, min_y in enumerate(Y):
            for max_y in Y[j + 1:]:
                m = (max_x - min_x) * (max_y - min_y)
                internal_points = [(x, y) for x, y in points if min_x <= x <= max_x and min_y <= y <= max_y]
                if len(internal_points) >= K:
                    ans = min(ans, m)

print(ans)

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

pts.sort()
ys.sort()

ans = 10**20
for i, y1 in enumerate(ys):
    for y2 in ys[i+1:]:
        for j, (x1, _) in enumerate(pts):
            num = 0
            for x, y in pts[j:]:
                if y1 <= y <= y2:
                    num += 1
                if num >= K:
                    area = (x-x1) * (y2-y1)
                    ans = min(ans, area)
                    break

print(ans)