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.  



Sample input:
4 4
1 4
3 3
6 2
8 1


Sample output:
21

Submission status: Time Limit Exceeded

Solution code:
N, K = (int(x) for x in input().split())
Plot = [tuple(int(x) for x in input().split()) for _ in range(N)]
X = [p[0] for p in Plot]
Y = [p[1] for p in Plot]
X.sort()
Y.sort()
#全2点間で長方形の辺を作り、その内内部点がK個のものだけ面積を比較する。
#2点p,qが頂点にある長方形は確かに最小の長方形を成す
#2点が頂点でない場合、内部点の個数が変わらないように適当な2点p,qを取って頂点とすることでより小さい長方形を形成できる
ans = 10e20
while len(X) != 0:
    x1 = X[0]
    X.pop(0)
    for x2 in X:
        Ycopy = Y.copy()
        while len(Ycopy) != 0:
            y1 = Ycopy[0]
            Ycopy.pop(0)
            for y2 in Ycopy:
                    S = (x2-x1)*(y2-y1)
                    cnt = 0
                    for p in Plot:
                        if x1 <= p[0] <= x2 and y1 <= p[1] <= y2:
                            cnt += 1
                    if cnt == K and S != 0:
                        ans = min(ans, S)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, K = (int(x) for x in input().split())
Plot = [tuple(int(x) for x in input().split()) for _ in range(N)]
X = [p[0] for p in Plot]
Y = [p[1] for p in Plot]
#全2点間で長方形の辺を作り、その内内部点がK個のものだけ面積を比較する。
#2点p,qが頂点にある長方形は確かに最小の長方形を成す
#2点が頂点でない場合、内部点の個数が変わらないように適当な2点p,qを取って頂点とすることでより小さい長方形を形成できる
ans = 10e20
for x1 in X:
    for x2 in X:
        if x1 < x2:
            minx, maxx = x1, x2
        else:
            minx, maxx = x2, x1
        for y1 in Y:
            for y2 in Y:
                if y1 < y2:
                    miny, maxy = y1, y2
                else:
                    miny, maxy = y2, y1
                S = (maxx-minx)*(maxy-miny)
                cnt = 0
                for r in Plot:
                    if minx <= r[0] <= maxx and miny <= r[1] <= maxy:
                        cnt += 1
                if cnt == K and S != 0:
                    ans = min(ans, S)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations


N, K, *XY = map(int, open(0).read().split())
X = sorted(XY[::2])
Y = sorted(XY[1::2])

ans = 10 ** 20
for x1, x2 in combinations(X, 2):
    for y1, y2 in combinations(Y, 2):
        in_rect = [
            (x, y) for x, y in zip(*[iter(XY)] * 2) if x1 <= x <= x2 and y1 <= y <= y2
        ]
        if len(in_rect) < K:
            continue
        ans = min(ans, (x2 - x1) * (y2 - y1))
print(ans)

Submission status: Time Limit Exceeded

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

ans = float('inf')
for i in range(N):
  for j in range(N):
    for k in range(N):
      for l in range(N):
        x1= xy[i][0]
        x2 = xy[j][0]
        y1 = xy[k][1]
        y2 = xy[l][1]
        cnt = 0
        if x1 < x2 and y1 < y2:
          for n in range(N):
            if x1 <= xy[n][0] <= x2 and y1 <= xy[n][1] <= y2:
              cnt += 1

          if cnt >= K:
            ans = min(ans, (x2-x1)*(y2-y1))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
import numpy as np
N, K, *XY = [int(_) for _ in open(0).read().split()]
X = sorted(XY[::2])
Y = sorted(XY[1::2])
XY = np.array(XY, dtype=np.int64).reshape((N, 2)).T
ans = float('inf')
for x, y in itertools.product(itertools.combinations(X, 2), itertools.combinations(Y, 2)):
    F = (x[0] <= XY[0]) * (XY[0] <= x[1]) * (y[0] <= XY[1]) * (XY[1] <= y[1])
    if sum(F) < K:
        continue
    ans = min(ans, (x[1] - x[0]) * (y[1] - y[0]))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
import math
N,K = map(int, input().split())
xy=[list(map(int, input().split())) for i in range(N)]
S = math.inf
for j in  itertools.combinations_with_replacement(xy,4):
    x_r = max(j)[0]
    x_l = min(j)[0]
    y_c = max(j,key=lambda x:x[1])[1]
    y_f = min(j, key=lambda x:x[1])[1]
    count=0
    for k in xy:
        if x_l<=k[0]<=x_r and y_f<=k[1]<=y_c:
            count +=1
    if count >= K:
        S = min(S, (x_r - x_l)*(y_c - y_f))
print(S)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
def main():
  n,k=map(int,input().split())
  xy=[list(map(int,input().split())) for _ in range(n)]
  xwl=dict((c[0],i) for i,c in enumerate(xy))
  ywl=dict((c[1],i) for i,c in enumerate(xy))
  x=list(xwl.keys())
  y=list(ywl.keys())
  x.sort()
  y.sort()
  
  xdict=dict()
  ydict=dict()
  xdict[x[0]]=[1<<xwl[x[0]],0]
  ydict[y[0]]=[1<<ywl[y[0]],0]
  size=lambda x:sum(x>>i&1 for i in range(n))
  minus=lambda x,y:(x|y)^y
  for i in range(1,n):
    xdict[x[i]]=[xdict[x[i-1]][0]|(1<<xwl[x[i]]), xdict[x[i-1]][1]|(1<<xwl[x[i-1]])]
    ydict[y[i]]=[ydict[y[i-1]][0]|(1<<ywl[y[i]]), ydict[y[i-1]][1]|(1<<ywl[y[i-1]])]
  ans=float('inf')
  diter=[(i,j) for i in range(n) for j in range(n) if i<j]
  
  for s,t in diter: 
    for u,v in diter:
      if size(minus(xdict[x[t]][0],xdict[x[s]][1])&\
                  minus(ydict[y[v]][0],ydict[y[u]][1]))>=k:
        ans=min(ans,(x[t]-x[s])*(y[v]-y[u]))
  print(ans)

if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
def main():
  n,k=map(int,input().split())
  xy=[list(map(int,input().split())) for _ in range(n)]
  xwl=dict((c[0],i) for i,c in enumerate(xy))
  ywl=dict((c[1],i) for i,c in enumerate(xy))
  x=list(xwl.keys())
  y=list(ywl.keys())
  x.sort()
  y.sort()
  
  xdict=dict()
  ydict=dict()
  xdict[x[0]]=[1<<xwl[x[0]],0]
  ydict[y[0]]=[1<<ywl[y[0]],0]
  size=lambda x:sum(x>>i&1 for i in range(n))
  minus=lambda x,y:(x|y)^y
  for i in range(1,n):
    xdict[x[i]]=[xdict[x[i-1]][0]|(1<<xwl[x[i]]), xdict[x[i-1]][1]|(1<<xwl[x[i-1]])]
    ydict[y[i]]=[ydict[y[i-1]][0]|(1<<ywl[y[i]]), ydict[y[i-1]][1]|(1<<ywl[y[i-1]])]
  ans=float('inf')
  for s in range(n):
    for t in range(s+1,n):
      for u in range(n):
        for v in range(u+1,n):
          if size(minus(xdict[x[t]][0],xdict[x[s]][1])&\
                  minus(ydict[y[v]][0],ydict[y[u]][1]))>=k:
            ans=min(ans,(x[t]-x[s])*(y[v]-y[u]))
  print(ans)

if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
n,k=map(int,input().split())
xy=[list(map(int,input().split())) for _ in range(n)]
xwl=dict((c[0],i) for i,c in enumerate(xy))
ywl=dict((c[1],i) for i,c in enumerate(xy))
x=list(xwl.keys())
y=list(ywl.keys())
x.sort()
y.sort()

xdict=dict()
ydict=dict()
xdict[x[0]]=[1<<xwl[x[0]],0]
ydict[y[0]]=[1<<ywl[y[0]],0]
size=lambda x:sum(x>>i&1 for i in range(n))
minus=lambda x,y:(x|y)^y
for i in range(1,n):
  xdict[x[i]]=[xdict[x[i-1]][0]|(1<<xwl[x[i]]), xdict[x[i-1]][1]|(1<<xwl[x[i-1]])]
  ydict[y[i]]=[ydict[y[i-1]][0]|(1<<ywl[y[i]]), ydict[y[i-1]][1]|(1<<ywl[y[i-1]])]

cand=[(x[t]-x[s])*(y[v]-y[u]) for s in range(n) for t in range(n) \
 for u in range(n) for v in range(n) if size(minus(xdict[x[t]][0],xdict[x[s]][1])&\
                minus(ydict[y[v]][0],ydict[y[u]][1]))>=k and s<t and u<v]

print(min(cand))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
n,k=map(int,input().split())
xy=[list(map(int,input().split())) for _ in range(n)]
xwl=dict((c[0],i) for i,c in enumerate(xy))
ywl=dict((c[1],i) for i,c in enumerate(xy))
x=list(xwl.keys())
y=list(ywl.keys())
x.sort()
y.sort()

xdict=dict()
ydict=dict()
xdict[x[0]]=[1<<xwl[x[0]],0]
ydict[y[0]]=[1<<ywl[y[0]],0]
size=lambda x:sum(x>>i&1 for i in range(n))
minus=lambda x,y:(x|y)^y
for i in range(1,n):
  xdict[x[i]]=[xdict[x[i-1]][0]|(1<<xwl[x[i]]), xdict[x[i-1]][1]|(1<<xwl[x[i-1]])]
  ydict[y[i]]=[ydict[y[i-1]][0]|(1<<ywl[y[i]]), ydict[y[i-1]][1]|(1<<ywl[y[i-1]])]
ans=float('inf')
for s in range(n):
  for t in range(s+1,n):
    for u in range(n):
      for v in range(u+1,n):
        if size(minus(xdict[x[t]][0],xdict[x[s]][1])&\
                minus(ydict[y[v]][0],ydict[y[u]][1]))>=k:
          ans=min(ans,(x[t]-x[s])*(y[v]-y[u]))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from bisect import bisect_left
from itertools import accumulate

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, K, *XY = map(int, read().split())

    X = set()
    Y = set()
    for i, (x, y) in enumerate(zip(*[iter(XY)] * 2)):
        X.add(x)
        Y.add(y)

    X = sorted(X)
    Y = sorted(Y)

    P, Q = len(X), len(Y)

    ans = -1
    for i, x1 in enumerate(X):
        for x2 in X[i + 1 :]:
            for j, y1 in enumerate(Y):
                for y2 in Y[j + 1 :]:
                    p = 0
                    for x, y in zip(*[iter(XY)] * 2):
                        if x1 <= x <= x2 and y1 <= y <= y2:
                            p += 1

                    if p >= K and (ans > (x2 - x1) * (y2 - y1) or ans == -1):
                        ans = (x2 - x1) * (y2 - y1)

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import itertools

input = sys.stdin.readline


def main():
    N, K = [int(x) for x in input().split()]
    XY = [[int(x) for x in input().split()] for _ in range(N)]

    xset = set()
    yset = set()

    for x, y in XY:
        xset.add(x)
        yset.add(y)

    xlist = list(xset)
    ylist = list(yset)

    ans = float("inf")

    for a, b in itertools.combinations(range(len(xlist)), 2):
        maxx = max(xlist[a], xlist[b])
        minx = min(xlist[a], xlist[b])

        for c, d in itertools.combinations(range(len(ylist)), 2):
            maxy = max(ylist[c], ylist[d])
            miny = min(ylist[c], ylist[d])

            cnt = 0
            for x, y in XY:
                if minx <= x <= maxx and miny <= y <= maxy:
                    cnt += 1

            if cnt >= K:
                ans = min(ans, (maxx - minx) * (maxy - miny))

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
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
  #print(xm, xM, ym, yM, cnt)
  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])
          #rint(i,j,k,l,wk)
          ans = min(ans, wk)
      
print(ans)

Submission status: Time Limit Exceeded

Solution code:
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)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
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)

Submission status: Time Limit Exceeded

Solution code:
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
#mod = 998244353
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)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# hello worldと表示する
#float型を許すな
#numpyは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,x=MI()
lis=[LI() for i in range(n)]
lis.sort()
s=[]
for i in range(n):
    for j in range(n):
        for k in range(n):
            for l in range(n):
                xl=min(lis[i][0],lis[j][0])
                xu=max(lis[i][0],lis[j][0])
                yl=min(lis[k][1],lis[l][1])
                yu=max(lis[k][1],lis[l][1])
                count=0
                for m in range(n):
                    if xl<=lis[m][0]<=xu and yl<=lis[m][1]<=yu:
                        count+=1
                if count>=x:
                    s.append((xu-xl)*(yu-yl))
                    #print(i,j,k,l)
print(min(s))

Submission status: Time Limit Exceeded

Solution code:
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)

Submission status: Time Limit Exceeded

Solution code:
# 全縦線と全横線を全探索するとO(N^5)
# 50 ** 5 = 312500000
# 縦線の選び方は50 C 2だから2分の1になるのを考慮しても、78125000
# いや無理だろ……と思ったら公式がこの解法だった。衝撃。
# 二次元累積和を使うと各回の計算がO(1)になるので、O(N^4)となる。

# まず O(N^5)解法を作ってみよう。通るのかこれ?


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)

Submission status: Time Limit Exceeded

Solution code:
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)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
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
#print(pmap)
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:
          #print(xsort[x1],xsort[x2],xsort[y1],xsort[y2])
          b=abs(xsort[x1]-xsort[x2])*abs(ysort[y1]-ysort[y2])
          ans=min(ans,b)
print(ans)
#print(pmap)

Submission status: Time Limit Exceeded

Solution code:
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])
  
T = max(Y)
U = min(Y)
R = max(X)
L = min(X)
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]
        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)

Submission status: Time Limit Exceeded

Solution code:
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)