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

import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit


ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n,k = map(int,ipt().split())
    dx = dict()
    dy = dict()
    xs = []
    ys = []
    for _ in range(n):
        x,y = map(int,ipt().split())
        dx[x] = y
        dy[y] = x
        xs.append(x)
        ys.append(y)
    xs.sort()
    ys.sort()
    sm = [[0]*(n+1) for i in range(n+1)]
    f = False
    ly = dx[xs[n-1]]
    for i,yi in enumerate(ys[::]):
        if f:
            sm[n-1][i] = 0
        else:
            sm[n-1][i] = 1
        if ly == yi:
            f = True
    for i,xi in enumerate(xs[n-2::-1]):
        f = False
        smx = sm[n-i-2]
        smpx = sm[n-i-1]
        ly = dx[xi]
        for j,yj in enumerate(ys):
            if f:
                smx[j] = smpx[j]
            else:
                smx[j] = smpx[j]+1
            if ly == yj:
                f = True
    ma = 4*10**18+1
    for xl,xli in enumerate(xs[:n-1:]):
        smxl = sm[xl]
        for xr,xri in enumerate(xs[xl+1::]):
            smxr = sm[xl+xr+2]
            for yd,ydi in enumerate(ys[:n-1:]):
                for yu,yui in enumerate(ys[yd+1::]):
                    sk = smxl[yd]+smxr[yu+yd+2]-smxl[yu+yd+2]-smxr[yd]
                    if sk == k:
                        ss = (yui-ydi)*(xri-xli)
                        if ss < ma:
                            ma = ss
    print(ma)

    return

if __name__ == '__main__':
    main()

Solution (Python):
import math



def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    
    return divisors

def ValueToBits(x,digit):
    res = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        res[i]=now%2
        now = now >> 1
    return res

def BitsToValue(arr):
    n = len(arr)
    ans = 0
    for i in range(n):
        ans+= arr[i] * 2**i
    return ans

def ZipArray(a):
    aa = [[a[i],i]for i in range(n)]

    aa.sort(key = lambda x : x[0])
    for i in range(n):
        aa[i][0]=i+1
    aa.sort(key = lambda x : x[1])
    b=[aa[i][0] for i in range(len(a))]
    return b

def ValueToArray10(x, digit):
    ans = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        ans[digit-i-1] = now%10
        now = now //10
    return ans

def Zeros(a,b):
    if(b<=-1):
        return [0 for i in range(a)]
    else:
        return [[0 for i in range(b)] for i in range(a)]

def AddV2(v,w):
    return [v[0]+w[0],v[1]+w[1]]

dir4 = [[1,0],[0,1],[-1,0],[0,-1]]


def clamp(x,y,z):
    return max(y,min(z,x))

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
            

def Zaatsu(a):
    a.sort()
    now = a[0][0]
    od = 0
    for i in range(n):
        if(now==a[i][0]):
            a[i][0]=od
        else:
            now = a[i][0]
            od+=1
            a[i][0] = od
    
    a.sort(key = lambda x : x[1])
    return a

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)

    
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    
    def same_check(self, x, y):
        return self.find(x) == self.find(y)


'''
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 2
N = 10 ** 6 + 2
fact = [1, 1]  
factinv = [1, 1]  
inv = [0, 1]  

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

'''

def rl(x):
    return range(len(x))












n,K = list(map(int, input().split()))

xy = []

xs = {}
ys = {}

for i in range(n):
    xy.append(list(map(int, input().split())))
    xs[xy[-1][0]]=1
    ys[xy[-1][1]]=1

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

nx = len(xs)
ny = len(ys)

ans = 10**19




for i1 in range(ny):
    for i2 in range(i1):
        yd = ys[i2]
        yu = ys[i1]
        li = 0
        ri = 1
        t=0
        while(True):
            count = 0
            t+=1
            l = xs[li]
            r = xs[ri]
            
            for j in range(n):
                if(xy[j][0]>=l and xy[j][0]<=r and xy[j][1]>=yd and xy[j][1] <= yu):
                    count += 1
            
            if(count == K):
                ans = min(ans,(r-l)*(yu-yd))
                
            if(count<K):
                
                if(ri == n-1):
                    
                    break
                else:
                    ri+=1
                    continue
            elif(count >= K):
                li += 1
                
                continue

print(ans)

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


xy.sort()
ans = 2000000000 * (xy[-1][0] - xy[0][0])
for i in range(K-1, N):
  for j in range(N-i):
    xnow = xy[j+i][0] - xy[j][0]
    ylst = [xy[k][1] for k in range(j, j+i+1)]
    ylst.sort()
    ynow = min([ylst[k+K-1]-ylst[k] for k in range(i+2-K)])
    ans = min(ans, xnow*ynow)
    
print(ans)

Solution (Python):
import itertools

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

ans = 10**20
x2 = list(itertools.combinations(X, 2))
y2 = list(itertools.combinations(Y, 2))

for xi, xj in x2:
  if xj < xi:
    xi, xj = xj, xi
  for yi, yj in y2:
    if yj < yi:
      yi, yj = yj, yi
    n = 0
    for x, y in xy:
      if xi<=x<=xj and yi<=y<=yj:
        n += 1
    if n >= K:
      ans = min(ans, (xj-xi)*(yj-yi))

print(ans)

Solution (Python):


import sys

























from operator import itemgetter              




def main():
    mod = 1000000007                
    inf = float('inf')              
    
    sys.setrecursionlimit(10**6)    
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    
    

    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
        
    
    
    
    
    
    
            
    
    
    
    
    
    
    
    
    
    
    
    
    
        
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
        
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    

    def count_inner_points(points, sx, tx, sy, ty):
        cnt = 0
        for x, y in points:
            if sx <= x <= tx and sy <= y <= ty:
                cnt += 1
        return cnt
    

    n, num_of_points = mi()
    points = [lmi() for _ in range(n)]
    x_sorted_p = sorted(points, key=itemgetter(0))
    y_sorted_p = sorted(points, key=itemgetter(1))
    

    area = inf
    for i in range(n-1):
        for j in range(i+1, n):
            sx, tx = x_sorted_p[i][0], x_sorted_p[j][0]
            
            
            
            if count_inner_points(points, sx, tx, y_sorted_p[0][1], y_sorted_p[-1][1]) < num_of_points:
                continue
            for k in range(n-1):
                for l in range(k+1, n):
                    sy, ty = y_sorted_p[k][1], y_sorted_p[l][1]
                    
                    
                    
                    cnt = count_inner_points(points, sx, tx, sy, ty)
                    
                    
                    if cnt == num_of_points:
                        area = min(area, abs(tx - sx) * abs(ty - sy))
    print(area)
    


if __name__ == "__main__":
    main()

Solution (Python):


import sys

























from operator import itemgetter              




def main():
    mod = 1000000007                
    inf = float('inf')              
    
    sys.setrecursionlimit(10**6)    
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    
    

    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
        
    
    
    
    
    
    
            
    
    
    
    
    
    
    
    
    
    
    
    
    
        
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
        
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    

    def count_inner_points(points, sx, tx, sy, ty):
        cnt = 0
        for x, y in points:
            if sx <= x <= tx and sy <= y <= ty:
                cnt += 1
        return cnt
    

    n, num_of_points = mi()
    points = [lmi() for _ in range(n)]
    x_sorted_p = sorted(points, key=itemgetter(0))
    y_sorted_p = sorted(points, key=itemgetter(1))
    

    area = inf
    for i in range(n-1):
        for j in range(i+1, n):
            sx, tx = x_sorted_p[i][0], x_sorted_p[j][0]
            
            
            
            if count_inner_points(points, sx, tx, y_sorted_p[0][1], y_sorted_p[-1][1]) < num_of_points:
                continue
            for k in range(n-1):
                for l in range(k+1, n):
                    sy, ty = y_sorted_p[k][1], y_sorted_p[l][1]
                    
                    
                    
                    cnt = count_inner_points(points, sx, tx, sy, ty)
                    if cnt > num_of_points:
                        continue
                    elif cnt == num_of_points:
                        area = min(area, abs(tx - sx) * abs(ty - sy))
    print(area)
    


if __name__ == "__main__":
    main()

Solution (Python):
def main():
    N, K = map(int, input().split())
    XY = [tuple(map(int, input().split())) for _ in range(N)]
    X, Y = [], []
    for x, y in XY:
        X.append(x)
        Y.append(y)
    X.sort()
    Y.sort()
    Xm = {x: i for i, x in enumerate(X)}
    Ym = {y: i for i, y in enumerate(Y)}
    Xr = {i: x for i, x in enumerate(X)}
    Yr = {i: y for i, y in enumerate(Y)}
    cXY = [(Xm[x], Ym[y]) for x, y in XY]
    m = 10 ** 40
    for l in range(N):
        for r in range(l + 1, N):
            for b in range(N):
                for t in range(b + 1, N):
                    k = 0
                    for x, y in cXY:
                        if l <= x <= r and b <= y <= t:
                            k += 1
                    if k >= K:
                        m = min(m, (Xr[r] - Xr[l]) * (Yr[t] - Yr[b]))
    return m
print(main())

Solution (Python):
def main():
    N, K = map(int, input().split())
    l = []
    xl = []
    yl = []
    for _ in range(N):
        x, y = map(int, input().split())
        l.append((x, y))
        xl.append(x)
        yl.append(y)
    xl.sort()
    yl.sort()
    xd = {}
    dx = {}
    t = 0
    p = xl[0]
    for i in xl:
        if i != p:
            t += 1
        xd[i] = t
        dx[t] = i
        p = i
    yd = {}
    dy = {}
    t = 0
    p = yl[0]
    for i in yl:
        if i != p:
            t += 1
        yd[i] = t
        dy[t] = i
        p = i
    l2 = []
    for x, y in l:
        l2.append((xd[x], yd[y]))
    m = 10**100
    for si in range(len(xd)-1):
        for ei in range(si+1, len(xd)):
            for sj in range(len(yd)-1):
                for ej in range(sj+1, len(yd)):
                    t = 0
                    for x, y in l2:
                        if si <= x <= ei and sj <= y <= ej:
                            t += 1
                    if t >= K:
                        m = min(m, (dx[ei]-dx[si]) * (dy[ej]-dy[sj]))
    return m
print(main())

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

xs.sort()
ys.sort()
ans = float('inf')
for a in range(n-1):
    for b in range(a+1, n):
        for c in range(n-1):
            for d in range(c+1, n):
                xl = xs[a]
                xr = xs[b]
                yl = ys[c]
                yu = ys[d]
                cnt = 0
                for x, y in XY:
                    if xl <= x <= xr and yl <= y <= yu:
                        cnt += 1
                if cnt >= k:
                    ans = min(ans, (xr-xl)*(yu-yl))
print(ans)

Solution (Python):
from itertools import combinations

N, K = map(int,input().split())
points = []
X = []
Y = []

for _ in range(N):
    x, y = map(int,input().split())
    points.append((x, y))
    X.append(x)
    Y.append(y)

X.sort()
Y.sort()

ans = float('inf')

for x1, x2 in combinations(X, 2):
    for y1, y2 in combinations(Y, 2):
        cnt = 0
        for point in points:
            if x1 <= point[0] <= x2 and y1 <= point[1] <= y2:
                cnt += 1
        if cnt >= K:
            ans = min(ans, (x2 - x1) * (y2 - y1))

print(ans)

Solution (Python):
def main():
    N, K = list(map(int, input().split(' ')))
    points = [list(map(int, input().split(' '))) for _ in range(N)]
    points.sort(key=lambda p: p[1])
    ans = 10**19
    for b in range(N):
        bottom = points[b][1]
        for t in range(b + K - 1, N):
            top = points[t][1]
            target_points = points[b:(t+1)].copy()
            target_points.sort(key=lambda p: p[0])
            M = len(target_points)
            for left in range(M):
                right = left + K - 1
                if right >= M:
                    break
                width = target_points[right][0] - target_points[left][0]
                ans = min([ans, width * (top - bottom)])
    print(ans)


if __name__ == '__main__':
    main()

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

def main():
    n,k = map(int,input().split())
    xy = []
    X = []
    Y = []
    for _ in range(n):
        x,y = map(int,input().split())
        xy.append((x,y))
        X.append(x)
        Y.append(y)
    ans = 10**20
    for i in range(n-1):
        for j in range(i+1,n):
            for a in range(n-1):
                for b in range(a+1,n):
                    xl,xr = X[i],X[j]
                    yd,yu = Y[a],Y[b]
                    if xl > xr:
                        xr,xl = xl,xr
                    if yd > yu:
                        yd,yu = yu,yd
                    area = (xr-xl)*(yu-yd)
                    if ans < area:
                        continue
                    cnt = 0
                    for c in range(n):
                        if xl <= xy[c][0] and xy[c][0] <= xr and yd <= xy[c][1] and xy[c][1] <= yu:
                            cnt += 1
                    if cnt >= k:
                        ans = min(ans,area)
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
n,K=map(int,input().split())
xy=[]
x=[]
y=[]
for _ in range(n):
	X,Y=map(int,input().split())
	x.append(X+10**9)
	y.append(Y+10**9)
	xy.append((X+10**9,Y+10**9))
x.sort();y.sort();xy.sort()
num=[[0]*(n+1)for _ in range(n+1)]
for xx in xy:
	for i in range(n):
		if x[i]==xx[0]:
			break
	for j in range(n):
		if y[j]==xx[1]:
			break
	num[i+1][j+1]+=1
for i in range(n):
	for j in range(n):
		num[i+1][j+1]+=num[i+1][j]
for i in range(n):
	for j in range(n):
		num[i+1][j+1]+=num[i][j+1]
ans=10**20
for i in range(n):
	for j in range(n):
		for k in range(i+1,n+1):
			for l in range(j+1,n+1):
				if num[k][l]-num[i][l]-num[k][j]+num[i][j]>=K:
					r=(y[l-1]-y[j])*(x[k-1]-x[i])
					ans=min(ans,r)
print(ans)

Solution (Python):


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

Xs = set()
Ys = set()
for x,y in XY:
    Xs.add(x)
    Ys.add(y)


Xs = list(Xs)
Xs.sort()

Ys = list(Ys)
Ys.sort()

LX = len(Xs)
LY = len(Ys)
ans = 10**20

for i in range(LX):
    for j in range(i+1, LX):
        for k in range(LY):
            for l in range(k+1, LY):
                cnt = 0
                for x,y in XY:
                    if Xs[i] <= x <= Xs[j] and Ys[k] <= y <= Ys[l]:
                        cnt += 1

                if cnt >= K:
                    ans = min(ans, (Xs[j] - Xs[i])*(Ys[l] - Ys[k]))


print(ans)

Solution (Python):
n, k = map(int, input().split())
point = []
xarray = []
yarray = []
for _ in range(n):
    x, y = map(int, input().split())
    point.append([x, y])
    xarray.append(x)
    yarray.append(y)

xarray.sort()
yarray.sort()

ans = 4*(10**18)+10
for xi in range(n):
    for xj in range(xi+1, n):
        for yi in range(n):
            for yj in range(yi+1, n):
                lx, rx = xarray[xi], xarray[xj]
                by, ay = yarray[yi], yarray[yj]
                num = 0
                for i in range(n):
                    x, y = point[i]
                    if lx <= x <= rx and by <= y <= ay:
                        num += 1
                if num >= k:
                    ans = min(ans, (rx-lx)*(ay-by))
print(ans)

Solution (Python):


import sys
readline = sys.stdin.readline

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

P = [None] * N
for i in range(N):
  P[i] = list(map(int,readline().split()))

ans = 10 ** 18 * 4 + 1
for ix in range(N-1):
  for jx in range(ix,N):
    
    left = P[ix][0]
    right = P[jx][0]
    if left > right:
      left,right = right,left
    for iy in range(N-1):
      for jy in range(iy,N):
        up = P[iy][1]
        down = P[jy][1]
        if up < down:
          up,down = down,up
        d = abs(up - down) * abs(right - left)
        if d > ans:
          continue
        cnt = 0
        for i in range(N):
          if left <= P[i][0] <= right and down <= P[i][1] <= up:
            cnt += 1
        if cnt >= K:
          ans = d
print(ans)

Solution (Python):
n,K = map(int,input().split())
xy = [[int(i) for i in input().split()] for j in range(n)]

ans = 10**20

for i in range(n):
    for j in range(i+1,n):
        if K == 2:
            ans = min(ans,abs(xy[i][0]-xy[j][0])*abs(xy[i][1]-xy[j][1]))
        for k in range(j+1,n):
            if K == 2:
                break
            max_x_old = max(xy[i][0],xy[j][0],xy[k][0])
            min_x_old = min(xy[i][0],xy[j][0],xy[k][0])
            max_y_old = max(xy[i][1],xy[j][1],xy[k][1])
            min_y_old = min(xy[i][1],xy[j][1],xy[k][1])
            if K == 3:
                
                
                
                
                ans = min(ans,abs(max_x_old-min_x_old)*abs(max_y_old-min_y_old))
            for l in range(k+1,n):
                if K == 2 or K == 3:
                    break
                cnt = 0
                max_x = max(max_x_old,xy[l][0])
                min_x = min(min_x_old,xy[l][0])
                max_y = max(max_y_old,xy[l][1])
                min_y = min(min_y_old,xy[l][1])
                for m in range(n):
                    if xy[m][0] >= min_x and xy[m][0] <= max_x\
                       and xy[m][1] >= min_y and xy[m][1] <= max_y:
                           cnt += 1
                if cnt >= K:
                    
                    ans = min(ans,(max_x-min_x)*(max_y-min_y))
                
print(ans)

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

XY.sort(key=lambda x: x[0])

ans = float("INF")
for i in range(N):
    for j in range(i+K-1, N):
        W = XY[j][0] - XY[i][0]
        Y = [XY[x][1] for x in range(i, j+1)]
        Y.sort()
        for k in range(len(Y)-K+1):
            H = Y[k+K-1] - Y[k]
            ans = min(ans, W*H)

print(ans)

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

XY.sort(key=lambda x: x[0])

ans = float("INF")
for i in range(N):
    for j in range(i+K-1, N):
        W = XY[j][0] - XY[i][0]
        Y = [XY[x][1] for x in range(i, j+1)]
        Y.sort()
        for l, k in zip(Y, Y[K-1:]):
                H = k - l
                ans = min(ans, W*H)

print(ans)

Solution (Python):

import sys
from itertools import combinations,product
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N,K=map(int,input().split())
    x,y=[0]*N,[0]*N
    for i in range(N):
        x[i],y[i]=map(int,input().split())
    unique_x,unique_y=list(sorted(list(set(x)))),list(sorted(list(set(y))))
    d_x={z:i for i,z in enumerate(unique_x)}
    d_y={z:i for i,z in enumerate(unique_y)}
    xx=[d_x[z] for z in x]
    yy=[d_y[z] for z in y]
    c=[[0]*N for _ in range(N)]
    for i,j in zip(yy,xx):
        c[i][j]+=1
    s=[[0]*(N+1) for _ in range(N+1)]
    for i in range(N):
        for j in range(N):
            s[i+1][j+1]+=s[i][j+1]+s[i+1][j]-s[i][j]+c[i][j]
    xx.sort()
    yy.sort()
    ans=INF*10
    for (x0,x1),(y0,y1) in product(combinations(xx,2),combinations(yy,2)):
        if s[y1+1][x1+1]-s[y1+1][x0]-s[y0][x1+1]+s[y0][x0]>=K:
            ans=min(ans,(unique_y[y1]-unique_y[y0])*(unique_x[x1]-unique_x[x0]))
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

n, k = map(int, readline().split())
xy = []
xx = []
yy = []
for _ in range(n):
    x, y = map(int, readline().split())
    xx.append(x)
    yy.append(y)
    xy.append((x, y))
xx.sort()
yy.sort()
ans = float('inf')
for i, ix in enumerate(xx):
    for jx in xx[i + 1:]:
        for j, iy in enumerate(yy):
            for jy in yy[j + 1:]:
                cnt = 0
                for x, y in xy:
                    if ix <= x <= jx and iy <= y <= jy:
                        cnt += 1
                if cnt >= k:
                    ans = min(ans, (jx - ix) * (jy - iy))
print(ans)

Solution (Python):



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

"""
辺の上に点が乗っていても四角形の中に含まれると見なされるので、辺はいずれかの点の上を通るように引くと面積を小さくできる
各点のx,yをsetで持っておいて、全探索できるか？
→ N <= 50なので4つの辺の選び方が50**4、この範囲にK個以上入っているかでさらに *50なので間に合うか微妙？
小さい値で ^5 なので、間に合うかも
"""

LR = [] 
TB = [] 
for x,y in XY:
    LR.append(x)
    TB.append(y)


LR = list(set(LR))
LR.sort()
TB = list(set(TB))
TB.sort()


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

ans = float("inf")
for p in range(len(LR)):
    for q in range(p+1, len(LR)):
        for r in range(len(TB)):
            for s in range(r+1, len(TB)):

                if more_than_K(LR[p], LR[q], TB[s], TB[r]):
                    ans = min(ans, (LR[q] - LR[p]) * (TB[s] - TB[r]))


print(ans)

Solution (Python):
n, k = map(int, input().split())
XY = [list(map(int, input().split())) for _ in range(n)]
XY.sort(key=lambda x: x[0])
XY = [xy + [x] for x, xy in enumerate(XY)]
XY.sort(key=lambda x: x[1])
XY = [xy + [y] for y, xy in enumerate(XY)]

gr = [[0] * n for _ in range(n)]
for _, _, i, j in XY:
  gr[i][j] = 1
  
rui = [[0] * (n + 1) for _ in range(n + 1)]
for i in range(n):
  for j in range(n):
    rui[i + 1][j + 1] = rui[i + 1][j] + rui[i][j + 1] - rui[i][j] + gr[i][j]
    

ans = 10 ** 21
for i in range(n - 1):
  for j in range(i + 1, n):
    x = [XY[m][0] for m in [i, j]]
    y = [XY[m][1] for m in [i, j]]
    ii = [XY[m][2] for m in [i, j]]
    jj = [XY[m][3] for m in [i, j]]
    innerPoints = rui[max(ii) + 1][max(jj) + 1] \
                + rui[min(ii)][min(jj)] \
                - rui[min(ii)][max(jj) + 1] \
                - rui[max(ii) + 1][min(jj)]
    if innerPoints >= k:
      area = (max(x) - min(x)) * (max(y) - min(y)) 
      if area < ans:
        ans = area

if n > 2:
  for i in range(n - 2):
    for j in range(i + 1, n - 1):
      for l in range(j + 1, n):
        x = [XY[m][0] for m in [i, j, l]]
        y = [XY[m][1] for m in [i, j, l]]
        ii = [XY[m][2] for m in [i, j, l]]
        jj = [XY[m][3] for m in [i, j, l]]
        innerPoints = rui[max(ii) + 1][max(jj) + 1] \
                    + rui[min(ii)][min(jj)] \
                    - rui[min(ii)][max(jj) + 1] \
                    - rui[max(ii) + 1][min(jj)]
        if innerPoints >= k:
          area = (max(x) - min(x)) * (max(y) - min(y)) 
          if area < ans:
            ans = area

if n > 3:
  for i in range(n - 3):
    for j in range(i + 1, n - 2):
      for l in range(j + 1, n - 1):
        for o in range(l + 1, n):
          x = [XY[m][0] for m in [i, j, o, l]]
          y = [XY[m][1] for m in [i, j, o, l]]
          ii = [XY[m][2] for m in [i, j, o, l]]
          jj = [XY[m][3] for m in [i, j, o, l]]
          innerPoints = rui[max(ii) + 1][max(jj) + 1] \
                      + rui[min(ii)][min(jj)] \
                      - rui[min(ii)][max(jj) + 1] \
                      - rui[max(ii) + 1][min(jj)]
          if innerPoints >= k:
            area = (max(x) - min(x)) * (max(y) - min(y)) 
            if area < ans:
              ans = area

print(ans)

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

ans = float('inf')
for i in range(N):
    for j in range(i + K - 1, N):
        xmin, xmax = points[i][0], points[j][0]
        que = []
        for k in range(N):
            if xmin <= points[k][0] <= xmax:
                que.append(points[k][1])
        if len(que) >= K:
            que.sort()
            for k in range(len(que) - K + 1):
                ans = min(ans, (max(que[k: k + K]) - min(que[k: k + K])) * (xmax - xmin))
print(ans)

Solution (Python):
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**19
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    N,K = LI()
    px = [LI() for _ in range(N)]
    px.sort()

    ans = INF
    for k in range(K,N+1):
        for i in range(N-k+1):
            w = px[i+k-1][0] - px[i][0]
            py = []
            for _,y in px[i:i+k]:
                py.append(y)
            py.sort()
            min_y = INF
            for j in range(k-K+1):
                min_y = min(min_y,py[K+j-1]-py[j])
            ans = min(ans,w * min_y)
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 8)
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N, K = map(int, input().split())
coords = []
for i in range(N):
    x, y = map(int, input().split())
    coords.append((x, y))
coords.sort()


def solve():
    minarea = 1 << 62
    for t in range(N):
        _, yt = coords[t]
        for b in range(N):
            _, yb = coords[b]
            if yb < yt:
                continue
            h = yb - yt
            xs = []
            for i in range(N):
                xi, yi = coords[i]
                if yi < yt or yi > yb:
                    continue
                xs.append(xi)
            for i in range(K - 1, len(xs)):
                w = xs[i] - xs[i - K + 1]
                a = w * h
                minarea = min(minarea, a)
    return minarea


if __name__ == "__main__":
    print(solve())

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 8)
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N, K = map(int, input().split())
coords = []
for i in range(N):
    x, y = map(int, input().split())
    coords.append((x, y))
coords.sort()


def solve():
    minarea = 1 << 62
    for t in range(N):
        _, yt = coords[t]
        for b in range(N):
            _, yb = coords[b]
            if yb < yt:
                continue
            h = yb - yt
            xs = []
            for i in range(N):
                xi, yi = coords[i]
                if yi < yt or yi > yb:
                    continue
                xs.append(xi)
            for i in range(K - 1, len(xs)):
                w = xs[i] - xs[i - K + 1]
                a = w * h
                minarea = min(minarea, a)
    return minarea


if __name__ == "__main__":
    print(solve())

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

def check(x1,y1,x2,y2):
    cnt=0
    for node in xy:
        x,y=node
        if x1<=x<=x2 and y1<=y<=y2:
            cnt+=1
    return cnt

xlis=[]
ylis=[]
for itm in xy:
    x,y=itm
    xlis.append(x)
    ylis.append(y)
xlis.sort()
ylis.sort()

ans=10**20
from itertools import *
for tmp1 in combinations(xlis,2):
    for tmp2 in combinations(ylis,2):
        x1,x2=tmp1
        y1,y2=tmp2
        ret = check(x1,y1,x2,y2)
        if ret==k:
            ans=min(ans,(x2-x1)*(y2-y1))

print(ans)