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

Solution (Python):
from itertools import accumulate
from operator import add

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

iXs = list(range(N))
iXs.sort(key=lambda iX: xs[iX])
odrXs = [0]*(N)
for odrX, iX in enumerate(iXs):
    odrXs[iX] = odrX
iYs = list(range(N))
iYs.sort(key=lambda iY: ys[iY])
odrYs = [0]*(N)
for odrY, iY in enumerate(iYs):
    odrYs[iY] = odrY

Ass = [[0]*(N) for _ in range(N)]
for odrX, odrY in zip(odrXs, odrYs):
    Ass[odrX][odrY] = 1

def getAccAss(Ass):
    accAss = [[0] * (len(Ass[0])+1)] + [accumulate([0] + As) for As in Ass]
    for x in range(1, len(accAss)):
        accAss[x] = list(map(add, accAss[x], accAss[x-1]))
    return accAss
def getRangeSum2D(accAss, xFr, xTo, yFr, yTo):
    return accAss[xTo+1][yTo+1] - accAss[xTo+1][yFr] - accAss[xFr][yTo+1] + accAss[xFr][yFr]

accAss = getAccAss(Ass)

ans = 10**20
for xFr in range(N-1):
    for xTo in range(xFr+1, N):
        for yFr in range(N-1):
            for yTo in range(yFr+1, N):
                num = getRangeSum2D(accAss, xFr, xTo, yFr, yTo)
                if num >= K:
                    area = (xs[iXs[xTo]]-xs[iXs[xFr]]) * (ys[iYs[yTo]]-ys[iYs[yFr]])
                    ans = min(ans, area)

print(ans)

Solution (Python):
n,k = map(int,input().split())
x = []
y = []
xx = []
yy = []
for i in range(n):
    a,b = map(int,input().split())
    x.append(a)
    y.append(b)
    xx.append(a)
    yy.append(b)
ans = 10 ** 40
x.sort()
y.sort()
for i in range(n):
    for j in range(i+1,n):
        for l in range(n):
            for h in range(l+1,n):
                lx = x[i]
                rx = x[j]
                uy = y[h]
                dy = y[l]
                cnt = 0
                for ii in range(n):
                    if lx <= xx[ii] <= rx and dy <= yy[ii] <= uy:
                        cnt += 1
                if cnt >= k:
                    if (rx-lx) * (uy-dy) != 0:
                        ans = min(ans,(rx-lx)*(uy-dy))
print(ans)

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

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, K = MAP()
xy = [LIST() for _ in range(N)]
ans = INF
xy.sort()
for l in range(N-K+1):  
    for r in range(l+K, N+1):  
        y = sorted(xy[l:r], key = lambda x: x[1])  
        for i in range(r-l-K+1):
            sq = (xy[r-1][0] - xy[l][0]) * (y[i+K-1][1] - y[i][1])  
            ans = min(ans, sq)
print(ans)

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

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, K = MAP()
xy = [LIST() for _ in range(N)]
ans = INF
xy.sort()
for l in range(N-K+1):  
    for r in range(l+K, N+1):  
        y = sorted(xy[l:r], key = lambda x: x[1])  
        for i in range(r-l-K+1):
            sq = (xy[r-1][0] - xy[l][0]) * (y[i+K-1][1] - y[i][1])  
            ans = min(ans, sq)
print(ans)

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

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, K = MAP()
xy = [LIST() for _ in range(N)]
X = sorted([x[0] for x in xy])
Y = sorted([x[1] for x in xy])

ans = INF
for p in combinations(X, 2):
	x_min = p[0]
	x_max = p[1]
	for q in combinations(Y, 2):
		y_min = q[0]
		y_max = q[1]
		
		cnt = 0
		for x, y in xy:
			if x_min <= x <= x_max and y_min <= y <= y_max:
				cnt += 1
		if cnt >= K:
			ans = min(ans, (x_max-x_min)*(y_max-y_min))
print(ans)

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

Y.sort()
X.sort()
ans = []
for sx in range(n):
    for ex in range(n-1, sx, -1):
        for sy in range(n):
            for ey in range(n-1, sy, -1):
                x1, x2, y1, y2 = X[sx], X[ex], Y[sy], Y[ey]
                count = len([True for x, y in graph if x1 <= x <= x2 and y1 <= y <= y2])
                if count >= k:
                    ans.append((x2-x1)*(y2-y1))
                else:
                    break

print(min(ans))

Solution (Python):
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations,groupby
import sys
import bisect
import string
import math
import time
import random
def S_():
    return input()
def LS():
    return [i for i in input().split()]
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)]
        rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()

input=lambda: sys.stdin.readline().rstrip()

def ran_input():
    import random
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

show_flg=False
show_flg=True

ans=1

n,k=LI()
a=[]

for i in range(n):
    x,y=LI()
    a.append((x,y))

a.sort()

ans=inf

for lx in range(n):
    for rx in range(lx+1,n):
        for ly in range(n):
            for ry in range(ly+1,n):
                c=0
                x1,x2,y1,y2=a[lx][0],a[rx][0],a[ly][1],a[ry][1]
                if y1>y2:
                    y1,y2=y2,y1
                for i in range(lx,rx+1):
                    x,y=a[i]
                    if x1<=x<=x2 and y1<=y<=y2:
                        c+=1
                

                if c>=k:
                    ans=min(ans,(x2-x1)*(y2-y1))

print(ans)

Solution (Python):
n,k = map(int, input().split())
a = [list(map(int, input().split())) for i in range(n)]
ax = sorted(a)
ans = 10**19
for i in range(n-1):
    for j in range(i+1,n):
        a_use = ax[i:j+1]
        xnum = len(a_use)
        sx = a_use[-1][0]-a_use[0][0]
        a_use.sort(key = lambda x:x[1])
        if xnum<k:
            continue
        for y1 in range(xnum-k+1):
            y2 = y1+k-1
            s = sx*(a_use[y2][1]-a_use[y1][1])
            ans = min(ans,s)
print(ans)

Solution (Python):




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

p = []
x = []
y = []
for i in range(n):
    xi,yi = map(int, input().split( ))
    p.append((xi,yi))
    x.append(xi)
    y.append(yi)

y = list(set(y))
x = list(set(x))
x.sort()
y.sort()
lx = len(x)
ly = len(y)
ans = 10**20
for xi,xj in itertools.combinations(x,2):
    for yi,yj in itertools.combinations(y,2):
        cnt = 0
        for xk,yk in p:
            if xi <= xk and xk<=xj and yi <=yk and yk<=yj:
                        cnt += 1
        if cnt >= k:
            ans = min(ans, (xj-xi)*(yj-yi))
print(ans)

Solution (Python):
import sys

inf = float('inf')

n, k, *xy = map(int, sys.stdin.read().split())
xy = list(zip(*[iter(xy)] * 2))

def main():
    xy.sort(key=lambda x: x[0])
    x = []
    y = []
    for i in range(n):
        x.append(xy[i][0])
        y.append(xy[i][1])
    
    area = inf
    for l in range(n-k+1):
        for r in range(l+k-1, n):
            dx = x[r] - x[l]
            seq_y = sorted(y[l:r+1])
            m = r - l + 1
            for d in range(m-k+1):
                for u in range(d+k-1, m):
                    dy = seq_y[u] - seq_y[d]
                    area = min(area, dx * dy)

    return area

if __name__ == '__main__':
    ans = main()
    print(ans)

Solution (Python):
n,k,*L=map(int,open(0).read().split())
X=[];Y=[]
for x,y in sorted((x,y) for x,y in zip(*[iter(L)]*2)):
	X.append(x)
	Y.append(y)
ans=float("inf")
for i in range(n-k+1):
	for j in range(i+k-1,n):
		w=X[j]-X[i]
		l=sorted(Y[i:j+1])
		h=min(My-my for my,My in zip(l,l[k-1:]))
		ans=min(ans,w*h)
print(ans)

Solution (Python):
n,k,*L=map(int,open(0).read().split())
X=[];Y=[]
for x,y in sorted((x,y) for x,y in zip(*[iter(L)]*2)):
	X.append(x)
	Y.append(y)
ans=float("inf")
for i in range(n-k+1):
	for j in range(i+k-1,n):
		w=X[j]-X[i]
		l=sorted(Y[i:j+1])
		h=min(My-my for my,My in zip(l,l[k-1:]))
		ans=min(ans,w*h)
print(ans)

Solution (Python):
import itertools
N,K=map(int,input().split())
XY=[list(map(int,input().split())) for i in range(N)]
ans=float("inf")

for xv in itertools.combinations( [xy[0] for xy in XY] ,2):
  for yv in itertools.combinations( [xy[1] for xy in XY] ,2):
    xmax=max(xv[0],xv[1])
    xmin=min(xv[0],xv[1])
    ymax=max(yv[0],yv[1])
    ymin=min(yv[0],yv[1])

    k=0
    for xy in XY:
      x,y=xy[0],xy[1]
      if xmin<=x and x<=xmax:
        if ymin<=y and y<=ymax:
          k+=1    
    if k>=K:
      ans=min(ans,(xmax-xmin)*(ymax-ymin))
print(ans)

Solution (Python):
n,h=map(int,input().split())
p,x,y=[],[],[]
z=float("inf")
for i in range(n):
  a,b=map(int,input().split())
  p.append((a,b))
  x.append(a)
  y.append(b)
x.sort()
y.sort()
for i in range(n-1):
  for j in range(i,n):
    for k in range(n-1):
      lx,rx,dy=x[i],x[j],y[k]
      c=0
      t=[]
      for a,b in p:
        if x[i]<=a<=x[j] and y[k]<=b:c+=1;t.append(b)
      if h<=c:z=min(z,(x[j]-x[i])*(sorted(t)[h-1]-y[k]))
print(z)

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

ans = 10 ** 20
for xl in range(N):
    for xr in range(xl + 1, N):
        Ysub = sorted([y for x, y in XY[xl:xr + 1]])
        for i in range(xr - xl - K + 2):
            Yk = Ysub[i:i + K] + [XY[xr][1], XY[xl][1]]
            ans = min(ans, (XY[xr][0] - XY[xl][0]) * (max(Yk) - min(Yk)))

print(ans)

Solution (Python):
import sys
from itertools import combinations
read = sys.stdin.read

N, K, *xy = map(int, read().split())
xy = sorted(zip(*[iter(xy)] * 2))
X, Y = zip(*xy)
answer = 10 ** 20

for left, right in combinations(range(N), 2):
    width = X[right] - X[left]
    tmp_Y = sorted(Y[left:right + 1])
    h = len(tmp_Y)
    for i in range(h):
        if i + K > h:
            break

        S = width * (tmp_Y[i + K - 1] - tmp_Y[i])
        if S < answer:
            answer = S

print(answer)

Solution (Python):

import sys
import itertools

def solve(N: int, K: int, x: "List[int]", y: "List[int]"):
    answer = 10**19

    x_set = sorted(list(set(x)))
    y_set = sorted(list(set(y)))
    x_combination = list(itertools.combinations(x_set,2))
    y_combination = list(itertools.combinations(y_set,2))

    
    for x_l, x_u in x_combination:
        for y_l, y_u in y_combination:
            count = 0
            for i in range(N):
                if y_l <= y[i] <= y_u and x_l <= x[i] <= x_u:
                    count +=1
            if count >= K:
                answer = min(answer,(y_u-y_l)*(x_u-x_l))

    print(answer)
    return


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

if __name__ == '__main__':
    main()

Solution (Python):
n,bod = map(int,input().split())
points = []
x = []
y = []
for i in range(n):
    a,b = map(int,input().split())
    x.append(a)
    y.append(b)
    points.append([a,b])

x.sort()
y.sort()


ans = 1e20

for i in range(n):
    for j in range(1,n-i):
        for k in range(n):
            for l in range(1,n-k):
                lef = x[i]
                rig = x[-j]
                bot = y[k]
                top = y[-l]

                cnt = 0
                for m in range(n):
                    if lef <= points[m][0] <= rig and bot <= points[m][1] <= top:
                        cnt += 1
                if cnt >= bod:
                    area = (rig-lef)*(top-bot)
                    if area < ans:
                        ans = area


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())
X = []
Y = []
XY = []
for _ in range(N):
    x, y = map(int, input().split())
    X.append(x)
    Y.append(y)
    XY.append((x, y))

X = sorted(X)
Y = sorted(Y)
mi = 1<<200
for i in range(N):
    for j in range(i+1, N):
        for k in range(N):
            for l in range(k+1, N):
                s = 0
                for x, y in XY:
                    if X[i] <= x <= X[j] and Y[k] <= y <= Y[l]:
                        s += 1
                if s >= K:
                    mi = min(mi, (X[j] - X[i]) * (Y[l] - Y[k]))

print(mi)

Solution (Python):
def main():
    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 i in range(N):
        for j in range(N):
            for k in range(N):
                for l in range(N):
                    if x[i] < x[j] and y[k] < y[l]:
                        right = x[j]
                        left = x[i]
                        bottom = y[k]
                        top = y[l]

                        cnt = 0

                        for n in range(N):
                            if left <= x[n] <= right and bottom <= y[n] <= top:
                                cnt += 1

                        if cnt >= K:
                            ans = min(ans, (top - bottom) * (right - left))
    print(ans)



if __name__ == "__main__":
    main()

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):
import itertools
n,k=map(int,input().split())
l=[]
for i in range(n):
    l.append(list(map(int,input().split())))
c=itertools.combinations(range(n),2)
d=itertools.combinations(range(n),2)
ans=10**25
for i0 in range(n):
    for i1 in range(i0,n):
        for j0 in range(n):
            for j1 in range(j0,n):
                i=[i0,i1]
                j=[j0,j1]
                
                lx=min(l[i[0]][0],l[i[1]][0])
                rx=max(l[i[0]][0],l[i[1]][0])
                dy=min(l[j[0]][1],l[j[1]][1])
                uy=max(l[j[0]][1],l[j[1]][1])
                tk=0
                for p in l:
                    if lx<=p[0]<=rx and dy<=p[1]<=uy:
                        tk+=1
                if tk>=k:
                    ans=min(ans,(uy-dy)*(rx-lx))
print(ans)

Solution (Python):
import sys

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

def main():
    n, k = MI()
    xy = []
    xx = []
    yy = []
    for _ in range(n):
        x, y = MI()
        xy.append([x, y])
        xx.append(x)
        yy.append(y)
    xx.sort()
    yy.sort()
    
    
    xtoi = {x: i for i, x in enumerate(xx)}
    ytoj = {y: j for j, y in enumerate(yy)}
    cs2d = [[0] * (n + 1) for _ in range(n + 1)]
    for x, y in xy:
        i, j = xtoi[x], ytoj[y]
        cs2d[i + 1][j + 1] = 1
    
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            cs2d[i][j] += cs2d[i][j - 1]
    for j in range(1, n + 1):
        for i in range(1, n + 1):
            cs2d[i][j] += cs2d[i-1][j]
    
    ans = 10 ** 20
    for ri in range(n):
        r = xx[ri]
        for li in range(ri):
            l = xx[li]
            for ti in range(n):
                t = yy[ti]
                for bi in range(ti):
                    b = yy[bi]
                    cnt = cs2d[ri+1][ti+1]-cs2d[ri+1][bi]-cs2d[li][ti+1]+cs2d[li][bi]
                    if cnt >= k:
                        s = (r - l) * (t - b)
                        if s < ans: ans = s
    print(ans)

main()

Solution (Python):
N, K = map(int, input().split())
P = [tuple(map(int, input().split())) for _ in range(N)]
X = sorted([p[0] for p in P])
Y = sorted([p[1] for p in P])

ans = 10**20
for i in range(N-1):
    for j in range(i+1, N):
        x0 = X[i]
        x1 = X[j]

        for k in range(N-1):
            for l in range(k+1, N):
                y0 = Y[k]
                y1 = Y[l]

                c = 0
                for m in range(N):
                    if x0 <= P[m][0] <= x1 and y0 <= P[m][1] <= y1:
                        c += 1

                if c >= K:
                    ans = min(ans, (x1-x0)*(y1-y0))

print(ans)

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

P.sort()

ans = 10**20
for i in range(N-K+1):
    X = P[i+K-1][0]
    x = P[i][0]
    Y = []
    for j in range(i, K+i):
        Y.append(P[j][1])
    Y.sort()
    ans = min(ans, (X-x)*(Y[-1]-Y[0]))
    for j in range(K+i, N):
        Y.append(P[j][1])
        Y.sort()
        for k in range(len(Y)-K+1):
            ans = min(ans, (P[j][0]-x)*(Y[k+K-1]-Y[k]))
            
print(ans)

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


l = []
n, k = LI()
X = []
Y = []
ans = INF
for _ in range(n):
  x, y = LI()
  X += [x]
  Y += [y]
  l.append((x,y))

X.sort()
Y.sort()
for xl,xr in combinations(X, 2):
  for yl,yr in combinations(Y, 2):
    cnt = 0
    for x,y in l:
      if xl<=x<=xr and yl<=y<=yr:
        cnt += 1
      if cnt >= k and ans > (xr - xl) * (yr - yl):
         ans = (xr - xl) * (yr - yl)
print(ans)

Solution (Python):
n,k=map(int,input().split())
xy=[list(map(int,input().split())) for _ in range(n)]
x=[xy[i][0] for i in range(n)]
y=[xy[i][1] for i in range(n)]
res = 10**20
for i in range(n):
    xl = xy[i][0]
    for j in range(n):
        xr = xy[j][0]
        if xr<xl:continue
        for p in range(n):
            yl = xy[p][1]
            for q in range(n):
                yr = xy[q][1]
                if yr<yl:continue
                tres = 0
                for sxy in xy:
                    if sxy[0] >= xl and sxy[0] <= xr and sxy[1] >= yl and sxy[1] <= yr:
                        tres += 1
                if tres >= k:
                    res = min(res,(xr-xl)*(yr-yl))
print(res)

Solution (Python):
import copy
import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
mod = 10**9 + 7
inf = float('inf')
ans = int(0)

N, K = LI()
x = [0]*N; y = [0]*N
for i in range(N):
    x[i], y[i] = LI()

X = copy.deepcopy(x); Y = copy.deepcopy(y)
X.sort(); Y.sort()

Xcandi = [0]*2; Ycandi = [0]*2
ylower = 0; yupper = N-1; ycur = (ylower+yupper)//2
ansC = []
for i in range(N-1):
    Xcandi[0] = X[i]
    for j in range(i+1,N):
        Xcandi[1] = X[j]
        for k in range(N-1):
            ylower = k+1; yupper = N - 1; ycur = (ylower + yupper) // 2
            Ycandi[0] = Y[k]
            while(True):
                cur = int(0)
                Ycandi[1] = Y[ycur]
                for l in range(N):
                    if Xcandi[0] <= x[l] <= Xcandi[1] and Ycandi[0] <= y[l] <= Ycandi[1]:
                        cur += 1
                if yupper - ylower >= 2:
                    if cur < K:
                        ylower = ycur
                        ycur = (ycur + yupper) // 2
                    else:
                        yupper = ycur
                        ycur = (ycur + ylower) // 2
                else:
                    cur = int(0)
                    Ycandi[1] = Y[yupper]
                    for l in range(N):
                        if Xcandi[0] <= x[l] <= Xcandi[1] and Ycandi[0] <= y[l] <= Ycandi[1]:
                            cur += 1
                    if cur < K:
                        break
                    else:
                        cur = int(0)
                        Ycandi[1] = Y[ylower]
                        for l in range(N):
                            if Xcandi[0] <= x[l] <= Xcandi[1] and Ycandi[0] <= y[l] <= Ycandi[1]:
                                cur += 1
                        if cur < K:
                            Ycandi[1] = Y[ylower+1]
                    cur = (Xcandi[1] - Xcandi[0])*(Ycandi[1] - Ycandi[0])
                    ansC.append(cur)

                    break



print(min(ansC))

Solution (Python):
import heapq

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

Y = [[j for j in i] for i in X]
Z = [[j for j in i] for i in X]

X.sort()
Y.sort(key=lambda x:x[1])

ans = float("inf")
for i in range(n):
    x0 = X[i][0]
    for j in range(n):
        y0 = Y[j][1]
        Q = []
        x1_ind = 0
        for p in range(n):
            if len(Q) == k:
                break
            else:
                if X[p][0] >= x0 and X[p][1] >= y0:
                    heapq.heappush(Q, [-X[p][1], X[p][0], X[p][1]])
                    x1_ind = p
        if len(Q) == k:
            x1 = X[x1_ind][0]
            pop = heapq.heappop(Q)
            y1 = -pop[0]
            heapq.heappush(Q, pop)
            ans = min(ans, (x1-x0) * (y1-y0))
            st = x1_ind
            for p in range(st+1, n):
                if X[p][0] >= x0 and X[p][1] >= y0:
                    heapq.heappush(Q, [-X[p][1], X[p][0], X[p][1]])
                    x1 = X[p][0]
                    heapq.heappop(Q)
                    pop = heapq.heappop(Q)
                    y1 = -pop[0]
                    heapq.heappush(Q, pop)
                    ans = min(ans, (x1-x0) * (y1-y0))
print(ans)

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

X=sorted([i[0] for i in xy])
Y=sorted([i[1] for i in xy])

ans=[]
for i in range(N-1):
  lx=X[i]
  for j in range(i+1,N):
    rx=X[j]
    for k in range(N-1):
      dy=Y[k]
      for l in range(k+1,N):
        uy=Y[l]
        cnt=0
        for x,y in xy:
          if lx<=x and x<=rx and dy<=y and y<=uy:
            cnt+=1
        if cnt>=K:
          ans.append((rx-lx)*(uy-dy))
          
          
print(min(ans))

Solution (Python):
n,K=map(int,input().split())
xy=[]
x=[]
y=[]
for i in range(n):
    a,b=map(int,input().split())
    x.append(a)
    y.append(b)
    xy.append([a,b])
x.sort()
y.sort()
data=[[0]*(n+1) for i in range(n+1)]
for u in xy:
    a,b=u
    X=x.index(a)
    Y=y.index(b)
    data[X][Y]=1
for i in range(n):
    for j in range(1,n):
        data[i][n-1-j]+=data[i][n-j]
for i in range(1,n):
    for j in range(n):
        data[n-i-1][j]+=data[n-i][j]
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):
                if data[i][k]+data[j+1][l+1]-data[i][l+1]-data[j+1][k]>=K:
                    ans=min(ans,(x[j]-x[i])*(y[l]-y[k]))
print(ans)

Solution (Python):
import sys
import heapq
INF = 1e20
n, k = [int(i) for i in sys.stdin.readline().split()]
ls = []
for i in range(n):
    x, y = [int(i) for i in sys.stdin.readline().split()]
    ls.append((x, y))
ls.sort(key=lambda x:x[0])
x_ls, y_ls = zip(*ls)
best = INF

x_ls = sorted(list(x_ls))
y_ls = sorted(list(y_ls))
for left_ind in range(n - k + 1):
    left = x_ls[left_ind]
    for right_ind in range(left_ind + k - 1, n):
        right = x_ls[right_ind]
        for down_ind in range(n - k + 1):
            down = y_ls[down_ind]
            for up_ind in range(down_ind + k - 1, n):
                up = y_ls[up_ind]
                cnt = 0
                for i in range(n):
                    x, y = ls[i]
                    if left <= x <= right and up >= y >= down:
                        cnt += 1
                if cnt >= k:
                    best = min(best, (up - down) * (right - left))
print(max(1,best))

Solution (Python):




def solve():
    from collections import namedtuple
    from operator import attrgetter
    import sys

    input = sys.stdin.readline

    Coordinates = namedtuple('Coordinates', ('x', 'y'))

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

    e = []
    for _ in range(n):
        x, y = map(int, input().split())
        e.append(Coordinates(x=x, y=y))
    x_asc = tuple(sorted(e, key=attrgetter('x')))  
    y_asc = tuple(sorted(e, key=attrgetter('y')))  

    
    

    tbl = tuple([0] * (n + 1) for _ in range(n + 1))
    for yi, py in enumerate(y_asc, 1):
        for xi, px in enumerate(x_asc, 1):
            tbl[xi][yi] = tbl[xi - 1][yi] + tbl[xi][yi - 1] - tbl[xi - 1][yi - 1] + (1 if py == px else 0)

    ans = float('inf')

    for left in range(1, n - (k - 1) + 1):
        for top in range(1, n - (k - 1) + 1):
            for right in range(left + k - 1, n + 1):
                for bottom in range(top + k - 1, n + 1):
                    if tbl[right][bottom] - tbl[left - 1][bottom] - tbl[right][top - 1] + tbl[left - 1][top - 1] >= k:
                        ans = min(ans,
                                  (y_asc[bottom - 1].y - y_asc[top - 1].y) * (x_asc[right - 1].x - x_asc[left - 1].x))
    print(ans)


if __name__ == '__main__':
    solve()

Solution (Python):




from collections import namedtuple
from operator import attrgetter

Coordinates = namedtuple('Coordinates', ('ind', 'x', 'y'))

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

e = []
for ind in range(n):
    x, y = map(int, input().split())
    e.append(Coordinates(ind=ind, x=x, y=y))
x_asc = sorted(e, key=attrgetter('x'))  
y_asc = sorted(e, key=attrgetter('y'))  




tbl = [[0] * (n + 1) for _ in range(n + 1)]
for yi, py in enumerate(y_asc, 1):
    for xi, px in enumerate(x_asc, 1):
        tbl[xi][yi] = tbl[xi - 1][yi] + tbl[xi][yi - 1] - tbl[xi - 1][yi - 1] + (1 if py == px else 0)

ans = float('inf')

for left in range(1, n - (k - 1) + 1):
    for top in range(1, n - (k - 1) + 1):
        for right in range(left + k - 1, n + 1):
            for bottom in range(top + k - 1, n + 1):
                if tbl[right][bottom] - tbl[left - 1][bottom] - tbl[right][top - 1] + tbl[left - 1][top - 1] >= k:
                    ans = min(ans, (y_asc[bottom - 1].y - y_asc[top - 1].y) * (x_asc[right - 1].x - x_asc[left - 1].x))
print(ans)