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 sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
n,g = map(int,readline().split())
XY = []
for i in range(n):
    XY.append(list(map(int,readline().split())))
ans = 10**32

if g == 2:
    for i in range(n):
        for j in range(i+1,n):
            hidarisita = (min(XY[i][0],XY[j][0]),min(XY[i][1],XY[j][1]))
            migiue = (max(XY[i][0],XY[j][0]),max(XY[i][1],XY[j][1]))
            ans = min(ans,abs((migiue[0]-hidarisita[0])*(migiue[1]-hidarisita[1])))

elif g == 3:
    for i in range(n):
        for j in range(i+1,n):
            for k in range(j+1,n):
                hidarisita = (min(XY[i][0],XY[j][0],XY[k][0]),
                min(XY[i][1],XY[j][1],XY[k][1]))
                migiue = (max(XY[i][0],XY[j][0],XY[k][0]),
                max(XY[i][1],XY[j][1],XY[k][1]))
                ans = min(ans,abs((migiue[0]-hidarisita[0])*(migiue[1]-hidarisita[1])))
else:

    for i in range(n):
        for j in range(i+1,n):
            for k in range(j+1,n):
                for l in range(k+1,n):
                    hidarisita = (min(XY[i][0],XY[j][0],XY[k][0],XY[l][0]),
                    min(XY[i][1],XY[j][1],XY[k][1],XY[l][1]))
                    migiue = (max(XY[i][0],XY[j][0],XY[k][0],XY[l][0]),
                    max(XY[i][1],XY[j][1],XY[k][1],XY[l][1]))

                    res = 0
                    for m in range(n):
                        if hidarisita[0] <= XY[m][0] <= migiue[0] and \
                            hidarisita[1] <= XY[m][1] <= migiue[1]:
                            res += 1

                    if res >= g:
                        ans = min(ans,abs((migiue[0]-hidarisita[0])*(migiue[1]-hidarisita[1])))

print(ans)

Solution (Python):
N,K,*xy = map(int, open(0).read().split())
_x_ = sorted(xy[::2])
ans = 4 * 10 ** 18
for _x in _x_:
  for x_ in _x_[1:]:
    w = x_ - _x
    c = 0
    _h_ = []
    for x, y in zip(xy[::2], xy[1::2]):
      if _x <= x <= x_:
        c += 1
        _h_.append(y)
      if c >= K:
        _h_.sort()
        h = min(_h_[i + K - 1] - _h_[i] for i in range(c - K + 1))
        ans = min(ans, h * w)

print(ans)

Solution (Python):
import sys

N, K = map(int, sys.stdin.readline().split())
points = []
for _ in range(N):
    x, y = map(int, sys.stdin.readline().split())
    points.append((x, y))

area = float("inf")
x_sorted = sorted(points)
y_sorted = sorted(points, key = lambda x: x[1])
for i1 in range(N-1):
    for i2 in range(i1+1, N):
        for j1 in range(N-1):
            for j2 in range(j1+1, N):
                x_min = x_sorted[i1][0]
                x_max = x_sorted[i2][0]
                y_min = y_sorted[j1][1]
                y_max = y_sorted[j2][1]
                num = 0
                for i in range(N):
                    if x_min <= points[i][0] <= x_max and y_min <= points[i][1] <= y_max:
                        num += 1
                tmp_area = (x_max - x_min) * (y_max - y_min)
                if num >= K and tmp_area < area:
                    area = tmp_area
                
print(area)

Solution (Python):
import itertools
N, K = map(int, input().split())
xy = []
x, y = [], []
for i in range(N):
    a, b = map(int, input().split())
    xy.append([a, b])
    x.append(a)
    y.append(b)

ans = float('inf')
for sx, ex in itertools.combinations(x, 2):
    for sy, ey in itertools.combinations(y, 2):
        if ex < sx:
            sx, ex = ex, sx
        if ey < sy:
            sy, ey = ey, sy
        s = (ex-sx)*(ey-sy)
        if s == 0:
            continue

        c = 0
        for k in range(N):
            a, b = xy[k]
            if sx <= a and a <= ex and sy <= b and b <= ey:
                c += 1
        if c >= K and s < ans:
            ans = s

print(ans)

Solution (Python):
N,K = map(int, input().split())
P = []
for _ in range(N):
  a,b = map(int, input().split())
  P.append((a,b))
  
ans = 5 * 10 ** 18

def solve(xl,xr,yl,yr):
  xm, xM = min(xl[0], xr[0]), max(xl[0], xr[0])
  ym, yM = min(yl[1], yr[1]), max(yl[1], yr[1])
  cnt = 0
  for k in range(N):
    p,q = P[k]
    if xm <= p <= xM and ym <= q <= yM:
      cnt += 1
  
  return cnt >= K
    
def calc(xl,xr,yl,yr):
  return abs(xr[0] - xl[0]) * abs(yr[1] - yl[1])
  
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 solve(P[i], P[j], P[k], P[l]):
          wk = calc(P[i], P[j], P[k], P[l])
          
          ans = min(ans, wk)
      
print(ans)

Solution (Python):
from itertools import combinations
n, k = map(int, input().split())
xy = []
xx = []
yy = []
for _ in range(n):
    x, y = map(int, input().split())
    xy.append((x, y))
    xx.append(x)
    yy.append(y)
xx.sort()
yy.sort()
ans = 10**20
for x1, x2 in combinations(xx, 2):
    for y1, y2 in combinations(yy, 2):
        tmp = 0
        for x, y in xy:
            if x1<=x<=x2 and y1<=y<=y2:
                tmp += 1
        if tmp<k:
            continue
        ans = min(ans, (x2-x1)*(y2-y1))
print(ans)

Solution (Python):
N, K = map(int, input().split())
x = [None] * N
y = [None] * N

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

ans = 10**20
sx = sorted(x)
sy = sorted(y)

for i in range(N):
    for j in range(i+1,N):
        for k in range(N):
            for l in range(k+1,N):
                count = 0
                
                for m in range(N):
                    if sx[i] <= x[m] <= sx[j] and sy[k] <= y[m] <= sy[l]:
                        count += 1
                if count >= K:
                    ans = min(ans, (sx[j]-sx[i]) * (sy[l]-sy[k]))
print(ans)

Solution (Python):
def check(x1,x2,y1,y2):
  p1=x1
  p2=x2
  q1=y1
  q2=y2
  if x1<=x2:
    x1=p1
    x2=p2
  else:
    x1=p2
    x2=p1
  if y1<=y2:
    y1=q1
    y2=q2
  else:
    y1=q2
    y2=q1
  count=0
  for ttx,tty in xy:
    if x1<=ttx<=x2 and y1<=tty<=y2:
      count+=1
  if count>=k:
    res=True
  else:
    res=False
  return res

n,k=map(int,input().split())
x,y=[],[]
xy=[]
for i in range(n):
  a,b=map(int,input().split())
  x.append(a)
  y.append(b)
  xy.append((a,b))
from itertools import combinations
ans=10**20
for xx in combinations(x,2):
  for yy in combinations(y,2):
    if check(xx[0],xx[1],yy[0],yy[1]):
      tmp=abs(xx[0]-xx[1])*abs(yy[0]-yy[1])
      ans=min(ans,tmp)
print(ans)

Solution (Python):
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, K = mapint()
XY = [list(mapint()) for _ in range(N)]

from itertools import combinations_with_replacement as cwr

ans = 10**20
for p1, p2, p3, p4 in cwr(XY, 4):
    x1, y1 = p1
    x2, y2 = p2
    x3, y3 = p3
    x4, y4 = p4
    lx, rx = min(x1, x2, x3, x4), max(x1, x2, x3, x4)
    ly, ry = min(y1, y2, y3, y4), max(y1, y2, y3, y4)
    cnt = 0
    for x, y in XY:
        if lx<=x<=rx and ly<=y<=ry:
            cnt += 1
    if cnt>=K:
        ans = min(ans, (rx-lx)*(ry-ly))

print(ans)

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

ans = float('inf')
for l in range(N-1):
    for r in range(l+1,N):
        w = xs[r] - xs[l]
        for d in range(N-1):
            for u in range(d+1,N):
                h = ys[u] - ys[d]
                if w*h >= ans: continue
                cnt = 0
                for x,y in XY:
                    if xs[l] <= x <= xs[r] and ys[d] <= y <= ys[u]:
                        cnt += 1
                        if cnt==K: break
                if cnt==K:
                    ans = w*h
print(ans)

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, k = map(int, input().split())
    X, Y = [], []
    for _ in range(n):
        x, y = map(int, input().split())
        X.append(x)
        Y.append(y)
    X_s = sorted(X)
    Y_s = sorted(Y)
    
    res = f_inf
    for x1 in range(n):
        for x2 in range(x1 + 1, n):
            for y1 in range(n):
                for y2 in range(y1 + 1, n):
                    lx, rx = X_s[x1], X_s[x2]
                    by, uy = Y_s[y1], Y_s[y2]
                    cnt = 0
                    for i in range(n):
                        if lx <= X[i] <= rx and by <= Y[i] <= uy:
                            cnt += 1
                    if cnt >= k:
                        res = min(res, (rx - lx) * (uy - by))
    print(res)


if __name__ == '__main__':
    resolve()

Solution (Python):
from itertools import combinations

n, k = (int(x) for x in input().split())
XY = [tuple(int(x) for x in input().split()) for _ in range(n)]

ans = 10**20
X = []
Y = []
for x, y in XY:
    X.append(x)
    Y.append(y)

ans = 10**20
for ax, bx in combinations(X, 2):
    if ax > bx:
        ax, bx = bx, ax
    for ay, by in combinations(Y, 2):
        if ay > by:
            ay, by = by, ay
        count = 0
        for x, y in XY:
            if ax <= x <= bx and ay <= y <= by:
                count += 1
        if count >= k:
            ans = min(ans, (bx - ax) * (by - ay))

print(ans)

Solution (Python):
"""
座標圧縮
2D累積和
全探索
勝利
"""
n, k = map(int,input().split())
xs = set()
ys = set()
ps = []

for _ in range(n):
    x,y = map(int,input().split())
    ps.append((x,y))
    xs.add(x)
    ys.add(y)
xdic = {x:i for i,x in enumerate(sorted(list(xs)))}
ydic = {y:i for i,y in enumerate(sorted(list(ys)))}
rxdic = {i:x for i,x in enumerate(sorted(list(xs)))}
rydic = {i:y for i,y in enumerate(sorted(list(ys)))}


h = len(xdic)
w = len(ydic)
A = [[0 for i in range(w+1)] for j in range(h+1)]
Acum = [[0 for i in range(w+1)] for j in range(h+1)]

for x,y in ps:
    h = xdic[x]
    w = ydic[y]
    A[h][w] += 1

for i in range(len(xdic)):
    for j in range(len(ydic)):
        Acum[i+1][j+1] = Acum[i][j+1] + Acum[i+1][j] - Acum[i][j] + A[i][j]
      

ans = 1 << 100
h = len(xdic)
w = len(ydic)
for i1 in range(h+1):
    for i2 in range(i1+1,h+1):
        for j1 in range(w+1):
            for j2 in range(j1+1,w+1):
                num = Acum[i2][j2]-Acum[i1][j2]-Acum[i2][j1]+Acum[i1][j1]
                
                if num == k:
                    x1 = rxdic[i1]
                    x2 = rxdic[i2-1]
                    y1 = rydic[j1]
                    y2 = rydic[j2-1]
                    S = (x2-x1)*(y2-y1)
                    ans = min(ans, S)
print(ans)

Solution (Python):
N,K = map(int,input().split())
l = [list(map(int,input().split())) for i in range(N)]
l.sort()
ans = []
for i in range(N):
    for j in range(i+1,N+1):
        nl = l[i:j]
        h = nl[-1][0]-nl[0][0]
        if len(nl)< K: continue
        nl.sort(key = lambda x:x[1])
        v = len(nl)
        for m in range(v-K+1):
            ans.append(h*(nl[m+K-1][1]-nl[m][1]))
print(min(ans))

Solution (Python):
n, k = map(int, input().split())
xy = [list(map(int, input().split())) for i in range(n)]
xset = list(set([i[0] for i in xy]))
yset = list(set([i[1] for i in xy]))
xset.sort()
yset.sort()

W = len(xset)
H = len(yset)
ans = float('inf')
for ix in range(W):
    for jx in range(ix, W):
        for iy in range(H):
            for jy in range(iy, H):
                xmin = min(xset[ix], xset[jx])
                xmax = max(xset[ix], xset[jx])
                ymin = min(yset[iy], yset[jy])
                ymax = max(yset[iy], yset[jy])
                cnt = 0
                for x, y in xy:
                    if xmin<=x<=xmax and ymin<=y<=ymax:
                        cnt+=1
                if cnt>=k:
                    ans = min(ans, (xmax-xmin)*(ymax-ymin))
print(ans)

Solution (Python):
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7

INF = 10**20
eps = 10**-7

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

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

X = []
Y = []
for (xi,yi) in P:
    X.append(xi)
    Y.append(yi)
X.sort()
Y.sort()
from itertools import combinations

ans = INF
def count(xmin,xmax,ymin,ymax):
    ret = 0
    for (xi,yi) in P:
        if (xmin <= xi <= xmax) and (ymin <= yi <= ymax):
            ret += 1
    return ret

for (xmin,xmax) in combinations(X,2):
    for (ymin,ymax) in combinations(Y,2):
        if count(xmin,xmax,ymin,ymax) >= K:
            ans = min(ans,(xmax-xmin)*(ymax-ymin))
print(ans)

Solution (Python):




import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

n,k=MI()
lis=[LI() for i in range(n)]
lis.sort()
sq=[]
for i in range(n):
    for j in range(i+1,n+1):
        new_lis=lis[i:j]
        hor=new_lis[-1][0]-new_lis[0][0]
        
        if len(new_lis)<k:
            continue
        new_lis.sort(key=lambda x:x[1])
        
        u=len(new_lis)
        for i in range(u-k+1):
            sq.append(hor*(new_lis[i+k-1][1]-new_lis[i][1]))

print(min(sq))

Solution (Python):
N,K= map(int,input().split())
x=[0]*N
y=[0]*N
z=[0]*N
for i in range(N):
    x[i],y[i] = map(int,input().split())
    z[i] = (x[i],y[i])
    
ans=float("inf")
for s in x:
    for t in x:
        for u in y:
            for v in y:
                cnt=0
                for zz in z:
                    if s<= zz[0]<=t and u<=zz[1]<=v:
                        cnt +=1
                if cnt >=K:
                    tmp = (t-s)*(v-u)
                    ans = min(ans,tmp)
print(ans)

Solution (Python):
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7






N, K = getNM()
query = [getList() for i in range(N)]


x_axis = set()
y_axis = set()
for i in query:
    x_axis.add(i[0])
    y_axis.add(i[1])
x_axis = sorted(list(x_axis))
y_axis = sorted(list(y_axis))


dp = [[0] * len(x_axis) for i in range(len(y_axis))]
for i in query:
    x = x_axis.index(i[0])
    y = y_axis.index(i[1])
    dp[y][x] += 1

dp_n = [[0] * len(x_axis) for i in range(len(y_axis))]


def bi_cumul_sum(dp_n, dp_bef, h, w):
    
    for i in range(h):
        dp_n[i][0] = dp_bef[i][0]
    for i in range(h):
        for j in range(1, w):
            dp_n[i][j] = dp_n[i][j - 1] + dp_bef[i][j]
    
    for i in range(1, h):
        for j in range(w):
            dp_n[i][j] += dp_n[i - 1][j]

bi_cumul_sum(dp_n, dp, len(y_axis), len(x_axis))


def judge(sx, ex, sy, ey, dp):
    mother = dp[ey][ex]
    minus1 = 0
    minus2 = 0
    plus = 0
    if sx > 0:
        minus1 = dp[ey][sx - 1]
    if sy > 0:
        minus2 = dp[sy - 1][ex]
    if sx > 0 and sy > 0:
        plus = dp[sy - 1][sx - 1]
    return mother - minus1 - minus2 + plus

ans = float('inf')
for sy in range(len(y_axis)):
    for ey in range(sy, len(y_axis)):
        for sx in range(len(x_axis)):
            for ex in range(sx, len(x_axis)):
                if judge(sx, ex, sy, ey, dp_n) >= K:
                    opt = (x_axis[ex] - x_axis[sx]) * (y_axis[ey] - y_axis[sy])
                    ans = min(ans, opt)
print(ans)

Solution (Python):
n,t=map(int, input().split())
x=[]
y=[]
m=[]
for i in range(n):
    a,b=map(int, input().split())
    x.append(a)
    y.append(b)
    m.append([a,b])
x.sort()
y.sort()
ans=float('inf')
for i in range(n-1):
    for j in range(i+1,n):
        for k in range(n-1):
            for l in range(k+1,n):
                count=0
                for a,b in m:
                    if x[i]<=a<=x[j] and y[k]<=b<=y[l]:
                        count+=1
                if count>=t:
                    ans=min(ans,(x[j]-x[i])*(y[l]-y[k]))
print(ans)

Solution (Python):
n,t=map(int, input().split())
x=[]
y=[]
m=[]
for i in range(n):
    a,b=map(int, input().split())
    x.append(a)
    y.append(b)
    m.append([a,b])
x.sort()
y.sort()
ans=float('inf')
for i in range(n-1):
    for j in range(i,n):
        if i>=j:continue
        for k in range(n-1):
            for l in range(k,n):
                if k>=l:continue
                count=0
                for a,b in m:
                    if x[i]<=a<=x[j] and y[k]<=b<=y[l]:
                        count+=1
                if count>=t:
                    ans=min(ans,(x[j]-x[i])*(y[l]-y[k]))
print(ans)

Solution (Python):
def main():
    n, k, *xy = map(int, open(0).read().split())
    _x_ = sorted(xy[::2])
    ans = 4 * 10 ** 18
    for _x in _x_:
        for x_ in _x_[1:]:
            w = x_ - _x
            c = 0
            _h_ = []
            for x, y in zip(xy[::2], xy[1::2]):
                if _x <= x <= x_:
                    c += 1
                    _h_.append(y)

            if c >= k:
                _h_.sort()
                h = min(_h_[i + k - 1] - _h_[i] for i in range(c - k + 1))
                ans = min(ans, h * w)

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    n, k, *xy = map(int, open(0).read().split())
    _x_ = sorted(xy[::2])
    ans = 4 * 10 ** 18
    for _x in _x_:
        for x_ in _x_[1:]:
            w = x_ - _x
            c = 0
            _h_ = []
            for x, y in zip(xy[::2], xy[1::2]):
                if _x <= x <= x_:
                    c += 1
                    _h_.append(y)

            if c >= k:
                _h_.sort()
                h = min(_h_[i + k - 1] - _h_[i] for i in range(c - k + 1))
                ans = min(ans, h * w)

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
N,K=map(int,input().split())
x,y=[],[]
p=[]
for i in range(N):
    a,b=map(int,input().split())
    x.append(a);y.append(b)
    p.append((a,b))
x.sort()
y.sort()
ans=10**30
for r in range(N):
    for l in range(r):
        for u in range(N):
            for d in range(u):
                R,L,U,D=x[r],x[l],y[u],y[d]
                cnt=0
                m=(R-L)*(U-D)
                for i in range(N):
                    if p[i][0]>=L and p[i][0]<=R and p[i][1]>=D and p[i][1]<=U:
                        cnt+=1
                if cnt>=K:
                    ans=min(ans,m)
print(ans)

Solution (Python):
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from itertools import combinations
    from operator import itemgetter
    n, k = map(int, readline().split())
    points = [list(map(int, readline().split())) for _ in range(n)]

    points.sort(key=itemgetter(0))
    for i in range(n):
        points[i].append(i)
    points.sort(key=itemgetter(1))
    for i in range(n):
        points[i].append(i)

    points.sort(key=itemgetter(2))

    ans = INF

    for first, last in combinations(range(n), 2):
        if (last - first + 1) < k:
            continue
        for p, q in combinations(range(first, last + 1), 2):
            gn = max(points[p][3],points[q][3])
            ln = min(points[p][3],points[q][3])
            count = 0

            for x, y, xn, yn in points:
                if first <= xn <= last and ln <= yn <= gn:
                    count += 1
            if count >= k:
                width = abs(points[last][0] - points[first][0])
                height = abs(points[p][1] - points[q][1])
                area = width * height
                ans = min(ans, area)
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    N, K = map(int, input().split())
    dots = [tuple(map(int, input().split())) for _ in range(N)]
    
    xs = set()
    ys = set()
    for x, y in dots:
        xs.add(x)
        ys.add(y)
    
    xs = sorted(xs)
    ys = sorted(ys)

    def isOK(l, r, d, u):
        num = sum([l <= x and x <= r and d <= y and y <= u for x, y in dots])
        return num >= K

    ans = 4 * 10 ** 18
    for i, x1 in enumerate(xs):
        for x2 in xs[i+1:]:
            for j, y1 in enumerate(ys):
                for y2 in ys[j+1:]:
                    area = (x2-x1)*(y2-y1)
                    if isOK(x1, x2, y1, y2):
                        ans = min(ans, area)
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):









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

ans = (3 * 10 ** 9) ** 2
for ix1, x1 in enumerate(coords):
    for x2 in coords[ix1+1:]:
        for iy1, y1 in enumerate(coords):
            for y2 in coords[iy1+1:]:
                point_in_rect = 0
                for c in coords:
                    
                    if (c[0] - x1[0]) * (c[0] - x2[0]) <= 0 and (c[1] - y1[1]) * (c[1] - y2[1]) <= 0:
                        point_in_rect += 1
                if point_in_rect >= k:
                    ans = min(ans, abs((x1[0] - x2[0]) * (y1[1] - y2[1])))

print(ans)

Solution (Python):









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

ans = (3 * 10 ** 9) ** 2
for ix1, x1 in enumerate(coords):
    for ix2, x2 in enumerate(coords[ix1+1:]):
        for iy1, y1 in enumerate(coords):
            for iy2, y2 in enumerate(coords[iy1+1:]):
                point_in_rect = 0
                for c in coords:
                    
                    if (c[0] - x1[0]) * (c[0] - x2[0]) <= 0 and (c[1] - y1[1]) * (c[1] - y2[1]) <= 0:
                        point_in_rect += 1
                if point_in_rect >= k:
                    ans = min(ans, abs((x1[0] - x2[0]) * (y1[1] - y2[1])))

print(ans)

Solution (Python):
n, K = map(int, input().split())
point = []
x_list = []
y_list = []
for _ in range(n):
    x, y = map(int, input().split())
    point.append((x, y))
    x_list.append(x)
    y_list.append(y)
x_list.sort()
y_list.sort()

ans = 4 * (10 ** 18)
for i in range(len(x_list)):
    for j in range(i + 1, len(x_list)):
        for k in range(len(y_list)):
            for l in range(k + 1, len(y_list)):
                num = 0
                for x, y in point:
                    if (x_list[i] <= x <= x_list[j]) & (y_list[k] <= y <= y_list[l]):
                        num += 1
                if num >= K:
                    ans = min(ans, abs((x_list[j] - x_list[i]) * (y_list[l] - y_list[k])))
print(ans)

Solution (Python):
def resolve():
    N, K = list(map(int, input().split()))
    XY = []
    X = []
    Y = []
    for _ in range(N):
        x, y = list(map(int, input().split()))
        XY.append((x, y))
        X.append(x)
        Y.append(y)
    
    X.sort()
    Y.sort()
    
    ans = float("inf")
    for i in range(N-1):
        for j in range(i+1, N):
            for k in range(N-1):
                for l in range(k+1, N):
                    cnt = 0
                    xmin, xmax, ymin, ymax = X[i], X[j], Y[k], Y[l]
                    for x, y in XY:
                        if xmin <= x <= xmax and ymin <= y <= ymax:
                            cnt += 1
                    if cnt >= K:
                        ans = min(ans, abs(xmax-xmin)*abs(ymax-ymin))
    print(ans)




if '__main__' == __name__:
    resolve()

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

x,y=zip(*xy)
xsort=list(x)
ysort=list(y)
xsort.sort()
ysort.sort()
from bisect import bisect_left
x=[bisect_left(xsort,xi) for xi in x]
y=[bisect_left(ysort,yi) for yi in y]
xy=list(zip(x,y))
pmap=[[0]*(n) for _ in range(n)]
for x,y in xy:
  pmap[x][y]+=1

for i in range(n):
  tmp=0
  for j in range(n):
    tmp+=pmap[i][j]
    pmap[i][j]=tmp
    if i!=0:
      pmap[i][j]+=pmap[i-1][j]
def func(x1,y1,x2,y2):
  if x1==x2 or y1==y2:return 0
  if x1>x2:x1,x2=x2,x1
  if y1>y2:y1,y2=y2,y1
  if x1==0 and y1==0:
    return pmap[x2][y2]
  elif x1==0:
    return pmap[x2][y2]-pmap[x2][y1-1]
  elif y1==0:
    return pmap[x2][y2]-pmap[x1-1][y2]
  else:
    return pmap[x2][y2]-pmap[x1-1][y2]-pmap[x2][y1-1]+pmap[x1-1][y1-1]

ans=float('inf')
for x1 in range(n-1):
  for x2 in range(x1+1,n):
    for y1 in range(n-1):
      for y2 in range(1,n):
        c=func(x1,y1,x2,y2)
        if func(x1,y1,x2,y2)>=k:
          
          b=abs(xsort[x1]-xsort[x2])*abs(ysort[y1]-ysort[y2])
          ans=min(ans,b)
print(ans)

Solution (Python):
from itertools import product
from operator import itemgetter
import sys
def main(N, K, P):
    X = sorted(map(itemgetter(0), P))
    Y = sorted(map(itemgetter(1), P))
    Xd, Yd = dict(), dict()
    for i, (x, y) in enumerate(zip(X, Y)):
        Xd[x] = i
        Yd[y] = i

    C = [[0] * (N + 1) for _ in range(N + 1)]
    for x, y in P:
        i, j = Xd[x] + 1, Yd[y] + 1
        C[i][j] += 1
    for i in range(1, N + 1):
        for j in range(N):
            C[i][j + 1] += C[i][j]
    for j in range(1, N + 1):
        for i in range(N):
            C[i + 1][j] += C[i][j]

    ans = 10**20
    for x1, y1 in product(range(N), repeat=2):
        for x2, y2 in product(range(x1, N), range(y1, N)):
            c = C[x2 + 1][y2 + 1] - C[x1][y2 + 1] - C[x2 + 1][y1] + C[x1][y1]
            if c >= K:
                s = (X[x2] - X[x1]) * (Y[y2] - Y[y1])
                assert s >= 0
                if s != 0:
                    ans = min(ans, s)
    print(ans)

if __name__ == '__main__':
    input = sys.stdin.readline
    N, K = map(int, input().split())
    P = [tuple(map(int, input().split())) for _ in range(N)]
    main(N, K, P)

Solution (Python):
from sys import stdin
def main():
    
    readline=stdin.readline
    inf=10**20
    n,k=map(int,readline().split())
    co=[list(map(int,readline().split())) for _ in range(n)]
    
    co.sort()
    
    x_range=[]
    for i in range(n-1):
        for j in range(i+1,n):
            x_range.append((co[i][0],co[j][0]))

    co.sort(key=lambda x:x[1])
    ans=inf
    for x in x_range:
        x_min=x[0]
        x_max=x[1]
        y_min=0
        y_max=0
        for under in range(n):
            cnt=0
            for i in range(under,n):
                if x_min<=co[i][0]<=x_max:
                    if cnt==0:
                        y_min=co[i][1]
                        cnt+=1
                    else:
                        y_max=co[i][1]
                        cnt+=1
                if cnt==k:
                    break
            if cnt==k:
                ans=min(ans,(x_max-x_min)*(y_max-y_min))

    print(ans)

if __name__=="__main__":
    main()

Solution (Python):
n,K = map(int,input().split())
d = [[int(i) for i in input().split()] for _ in range(n)]
x = sorted(d,key=lambda x:x[0])
y = sorted(d,key=lambda x:x[1])
ans = float("inf")

for i in range(n):
    for j in range(i+1,n):
        for k in range(n):
            cnt = 0
            for l in range(k,n):
                if x[i][0] <= y[l][0] <= x[j][0]: cnt += 1
                if cnt == K:
                    dx = x[j][0]-x[i][0]
                    dy = y[l][1]-y[k][1]
                    ans = min(ans, dx*dy)
                    break
print(ans)

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

X = []
Y = []
Z = []

for i in range(N):
  x,y = map(int,input().split())
  X.append(x)
  Y.append(y)
  Z.append([x,y])
  
Y.sort()
X.sort()
ans = 10**100

for t in range(N):
  for u in range(N):
    for r in range(N):
      for l in range(N):
        T = Y[N-t-1]
        U = Y[u]
        R = X[N-r-1]
        L = X[l]
        
        if T <= U or R <= L:
          continue
        
        cnt = 0
        for i in range(N):
          xi = Z[i][0]
          yi = Z[i][1]
          if xi >= L and xi <= R and yi >= U and yi <= T:
            cnt += 1
        if cnt >= K:
          M = int( (T-U) * (R-L) )
          ans = min(ans,M)
          
print(ans)

Solution (Python):
N,K=map(int,input().split())
A=[list(map(int, input().split())) for i in range(N)]
B,C=zip(*A)
S=10**36
for left in B:
  for right in B:
    for up in C:
      for down in C:
        if left<right and down<up:
          cnt=0
          for x,y in A:
            if left<=x<=right and down<=y<=up:
              cnt+=1
          if cnt>=K:
            S=min(S,(right-left)*(up-down))
print(S)