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:
import sys
import numpy as np
input = sys.stdin.readline

def main():
    N, K = map(int, input().split())
    xy = [list(map(int, input().split())) for i in range(N)]
    # 座標圧縮
    xs = []
    ys = []
    xy = sorted(xy, key=lambda x: x[0])
    for i in range(N):
        xs.append(xy[i][0])
        xy[i][0] = i+1
    xy = sorted(xy, key=lambda x: x[1])
    for i in range(N):
        ys.append(xy[i][1])
        xy[i][1] = i+1
    # 2次元累積和
    sum_ = np.zeros((N+1, N+1), dtype=int)
    for i in range(N):
        x, y = xy[i]
        sum_[y][x] = 1
    for i in range(1, N+1):
        sum_[i] += sum_[i-1]
    for i in range(1, N+1):
        sum_[:,i] += sum_[:,i-1]
    # 全探索
    ans = int(1e20)
    for l in range(1, N+1):
        no_three = True
        for r in range(N, l, -1):
            no_two = True
            for d in range(1, N+1):
                no_one = True
                for u in range(N, d, -1):
                    tmp = sum_[u][r] - sum_[d-1][r] - sum_[u][l-1] + sum_[d-1][l-1]
                    if tmp >= K:
                        tmp = (xs[r-1] - xs[l-1]) * (ys[u-1] - ys[d-1])
                        ans = min(ans, tmp)
                        no_one = False
                    else:
                        break
                if no_one:
                    break
                else:
                    no_two = False
            if no_two:
                break
            else:
                no_three = False
        if no_three:
            break
                

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
input = sys.stdin.readline

def main():
    N, K = map(int, input().split())
    xy = [list(map(int, input().split())) for i in range(N)]
    # 座標圧縮
    xs = []
    ys = []
    xy = sorted(xy, key=lambda x: x[0])
    for i in range(N):
        xs.append(xy[i][0])
        xy[i][0] = i+1
    xy = sorted(xy, key=lambda x: x[1])
    for i in range(N):
        ys.append(xy[i][1])
        xy[i][1] = i+1
    # 2次元累積和
    sum_ = np.zeros((N+1, N+1), dtype=int)
    for i in range(N):
        x, y = xy[i]
        sum_[y][x] = 1
    for i in range(1, N+1):
        sum_[i] += sum_[i-1]
    for i in range(1, N+1):
        sum_[:,i] += sum_[:,i-1]
    # 全探索
    ans = int(1e20)
    for l in range(1, N+1):
        for r in range(l+1, N+1):
            for d in range(1, N+1):
                for u in range(d+1, N+1):
                    tmp = sum_[u][r] - sum_[d-1][r] - sum_[u][l-1] + sum_[d-1][l-1]
                    if tmp >= K:
                        tmp = (xs[r-1] - xs[l-1]) * (ys[u-1] - ys[d-1])
                        ans = min(ans, tmp)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int,input().split())
xs = []
ys = []
points = []
for _ in range(n):
    x, y = map(int, input().split())
    xs.append(x)
    ys.append(y)
    points.append((x, y))

                
min_ = float('inf')
for leftx in xs:
    for rightx in xs:
        if leftx >= rightx:
            continue
        for downy in ys:
            for upy in ys:
                if downy >= upy:
                    continue
                cnt = 0
                for tx, ty in points:
                    if (leftx <= tx <= rightx) and (downy <= ty <= upy):
                        cnt += 1
                
                if cnt >= k:
                    yoko = rightx - leftx
                    tate = upy - downy
                    men = yoko*tate
                    if men < min_:
                        min_ = men
print(min_)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=sys.stdin.readline
def resolve():
    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=INF
    for a in range(n):
        for b in range(n):
            for c in range(a+1,n):
                for d in range(b+1):
                    x0,x1=sorted([X[a],X[c]])
                    y0,y1=sorted([Y[b],Y[d]])
                    if k<=sum((x0<=X[i]<=x1 and y0<=Y[i]<=y1) for i in range(n)):
                        ans=min(ans,(x1-x0)*(y1-y0))
    print(ans)
resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=sys.stdin.readline
def resolve():
    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=INF
    from itertools import product
    for a,b in product(range(n),repeat=2):
        for c,d in product(range(a+1,n),range(b+1,n)):
            x0,x1=sorted([X[a],X[c]])
            y0,y1=sorted([Y[b],Y[d]])
            if k<=sum((x0<=X[i]<=x1 and y0<=Y[i]<=y1) for i in range(n)):
                ans=min(ans,(x1-x0)*(y1-y0))
    print(ans)
resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=sys.stdin.readline
def resolve():
    n,k=map(int,input().split())
    xy=[tuple(map(int,input().split())) for _ in range(n)]
    ans=INF
    from itertools import product
    for a,b in product(range(n),repeat=2):
        for c,d in product(range(a+1,n),range(b+1,n)):
            x0,x1=sorted([xy[a][0],xy[c][0]])
            y0,y1=sorted([xy[b][1],xy[d][1]])
            if k<=sum((x0<=x<=x1 and y0<=y<=y1) for x,y in xy):
                ans=min(ans,(x1-x0)*(y1-y0))
    print(ans)
resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=sys.stdin.readline
def resolve():
    n,k=map(int,input().split())
    xy=[tuple(map(int,input().split())) for _ in range(n)]
    ans=INF
    for a in range(n):
        for b in range(n):
            for c in range(a+1,n):
                for d in range(b+1,n):
                    x0,x1=sorted([xy[a][0],xy[c][0]])
                    y0,y1=sorted([xy[b][1],xy[d][1]])
                    count=0
                    for x,y in xy:
                        count+=(x0<=x<=x1 and y0<=y<=y1)
                    if count>=k: ans=min(ans,(x1-x0)*(y1-y0))
    print(ans)
resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=sys.stdin.readline
def resolve():
    n,k=map(int,input().split())
    xy=[tuple(map(int,input().split())) for _ in range(n)]
    ans=INF
    from itertools import product
    for a,b,c,d in product(xy,repeat=4):
        x0=a[0]
        x1=b[0]
        y0=c[1]
        y1=d[1]
        count=0
        for x,y in xy: count+=(x0<=x<=x1 and y0<=y<=y1)
        if count>=k: ans=min(ans,(x1-x0)*(y1-y0))
    print(ans)
resolve()

Submission status: Time Limit Exceeded

Solution code:
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 i1 in range(n):
    for i2 in range(i1+1,n):
        for j1 in range(n):
            for j2 in range(j1+1,n):
                a,b=sorted([x[i1],x[i2]])
                c,d=sorted([y[j1],y[j2]])
                cnt=0
                for i in range(n):
                    if a<=x[i]<=b and c<=y[i]<=d:
                        cnt+=1
                if cnt>=k:
                    ans=min(ans,(b-a)*(d-c))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools

N,K = map(int,input().split())
List = [list(map(int,input().split())) for _ in range(N)]
count = 0
ans = ((10**9)*2)**2
X = []
Y = []
for i in itertools.combinations(List, K):
  X = []
  Y = []
  for j in i:
    x,y = j
    X.append(x)
    Y.append(y)
  ans = min(ans,abs(max(X)-min(X)) * abs(max(Y)-min(Y)))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools

N,K = map(int,input().split())
List = [list(map(int,input().split())) for _ in range(N)]
count = 0
ans = ((10**9)*2)**2
X = []
Y = []
for i in itertools.combinations(List, K):
  X = []
  Y = []
  for j in i:
    x,y = j
    X.append(x)
    Y.append(y)
  ans = min(ans,abs(max(X)-min(X)) * abs(max(Y)-min(Y)))
print(ans)

Submission status: Time Limit Exceeded

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

ans = float("inf")
import itertools
I = [i for i in range(N)]

for B in itertools.combinations(I,4):
    i,j,k,kk = B
    x1,y1 = XY[i]
    x2,y2 = XY[j]
    x3,y3 = XY[k]
    x4,y4 = XY[kk]
    u = max(y1,y2,y3,y4)
    d = min(y1,y2,y3,y4)
    r = max(x1,x2,x3,x4)
    l = min(x1,x2,x3,x4)
    num = 0
    for m in range(N):
        x,y = XY[m]
        if l<=x<=r and d<=y<=u:
            num += 1
    if num >= K:
        tmp = (u-d)*(r-l)
        if tmp < ans:
            ans = tmp
for B in itertools.combinations(I,3):
    i,j,k = B
    x1,y1 = XY[i]
    x2,y2 = XY[j]
    x3,y3 = XY[k]
    u = max(y1,y2,y3)
    d = min(y1,y2,y3)
    r = max(x1,x2,x3)
    l = min(x1,x2,x3)
    num = 0
    for m in range(N):
        x,y = XY[m]
        if l<=x<=r and d<=y<=u:
            num += 1
    if num >= K:
        tmp = (u-d)*(r-l)
        if tmp < ans:
            ans = tmp
for B in itertools.combinations(I,2):
    i,j = B
    x1,y1 = XY[i]
    x2,y2 = XY[j]
    u = max(y1,y2)
    d = min(y1,y2)
    r = max(x1,x2)
    l = min(x1,x2)
    num = 0
    for m in range(N):
        x,y = XY[m]
        if l<=x<=r and d<=y<=u:
            num += 1
    if num >= K:
        tmp = (u-d)*(r-l)
        if tmp < ans:
            ans = tmp
print(ans)

Submission status: Time Limit Exceeded

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

ans = float("inf")
for i in range(N):
    for j in range(i+1,N):
        for k in range(j+1,N):
            for kk in range(k+1,N):
                x1,y1 = XY[i]
                x2,y2 = XY[j]
                x3,y3 = XY[k]
                x4,y4 = XY[kk]
                u = max(y1,y2,y3,y4)
                d = min(y1,y2,y3,y4)
                r = max(x1,x2,x3,x4)
                l = min(x1,x2,x3,x4)
                num = 0
                for m in range(N):
                    x,y = XY[m]
                    if l<=x<=r and d<=y<=u:
                        num += 1
                if num >= K:
                    tmp = (u-d)*(r-l)
                    if tmp < ans:
                        ans = tmp
        for k in range(j+1,N):
            x1,y1 = XY[i]
            x2,y2 = XY[j]
            x3,y3 = XY[k]
            u = max(y1,y2,y3)
            d = min(y1,y2,y3)
            r = max(x1,x2,x3)
            l = min(x1,x2,x3)
            num = 0
            for m in range(N):
                x,y = XY[m]
                if l<=x<=r and d<=y<=u:
                    num += 1
            if num >= K:
                tmp = (u-d)*(r-l)
                if tmp < ans:
                    ans = tmp
        x1,y1 = XY[i]
        x2,y2 = XY[j]
        u = max(y1,y2)
        d = min(y1,y2)
        r = max(x1,x2)
        l = min(x1,x2)
        num = 0
        for m in range(N):
            x,y = XY[m]
            if l<=x<=r and d<=y<=u:
                num += 1
        if num >= K:
            tmp = (u-d)*(r-l)
            if tmp < ans:
                ans = tmp
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools

n, k = map(int, input().split())
p_list = [[0] * 2 for i in range(n)]

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

k_list = list(itertools.combinations(range(n), k))
min_area = ((10 ** 9) * 2) ** 2

for ki in k_list:
    x_list = []
    y_list = []
    for i in ki:
        x_list.append(p_list[i][0])
        y_list.append(p_list[i][1])
    x_max = max(x_list)
    x_min = min(x_list)
    y_max = max(y_list)
    y_min = min(y_list)
    area = abs(x_max - x_min) * abs(y_max - y_min)
    if area < min_area:
        min_area = area

print(min_area)

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
P=[list(map(int,input().split())) for _ in range(n)]
X=sorted(list(map(lambda x:x[0],P)))
Y=sorted(list(map(lambda x:x[1],P)))
s=(X[0]-X[-1])*(Y[0]-Y[-1])
ans=0
for r in range(n-1,0,-1):
  for l in range(r):
    for u in range(n-1,0,-1):
      for b in range(u):
        c=0
        for p in P:
          if X[l]<=p[0]<=X[r] and Y[b]<=p[1]<=Y[u]:
            c+=1
        if c>=k:
          s=min(s,(X[r]-X[l])*(Y[u]-Y[b]))
        else:break
    if u==n-1 and b==0 and c<k:
      break
print(s)

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
P=[list(map(int,input().split())) for _ in range(n)]
X=sorted(list(map(lambda x:x[0],P)))
Y=sorted(list(map(lambda x:x[1],P)))
s=(X[0]-X[-1])*(Y[0]-Y[-1])
ans=0
for r in range(n-1,0,-1):
  for l in range(r):
    for u in range(n-1,0,-1):
      for b in range(u):
        c=0
        for p in P:
          if X[l]<=p[0]<=X[r] and Y[b]<=p[1]<=Y[u]:
            c+=1
        if c>=k:
          s=min(s,(X[r]-X[l])*(Y[u]-Y[b]))
        else:break
print(s)

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
P=[list(map(int,input().split())) for _ in range(n)]
X=sorted(list(map(lambda x:x[0],P)))
Y=sorted(list(map(lambda x:x[1],P)))
s=(X[0]-X[-1])*(Y[0]-Y[-1])
ans=0
for r in range(1,n):
  for l in range(r):
    for u in range(1,n):
      for b in range(u):
        c=0
        for p in P:
          if X[l]<=p[0]<=X[r] and Y[b]<=p[1]<=Y[u]:
            c+=1
        if c>=k:
          s=min(s,(X[r]-X[l])*(Y[u]-Y[b]))
        else:break
print(s)

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
P=[list(map(int,input().split())) for _ in range(n)]
X=sorted(list(map(lambda x:x[0],P)))
Y=sorted(list(map(lambda x:x[1],P)))
s=(abs(X[0]-X[-1])*abs(Y[0]-Y[-1]))
ans=0
for r in range(1,n):
  for l in range(r):
    for u in range(1,n):
      for b in range(u):
        c=0
        for p in P:
          if X[l]<=p[0]<=X[r] and Y[b]<=p[1]<=Y[u]:
            c+=1
        if c>=k:
          s=min(s,abs(X[r]-X[l])*abs(Y[u]-Y[b]))
print(s)

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
xys = []
for i in range(N):
  x, y = map(int, input().split())
  xys.append((x, y))
xs = sorted(map(lambda xy: xy[0], xys))
ys = sorted(map(lambda xy: xy[1], xys))
rs = []
for i in range(N):
  for j in range(i+1, N):
    x1 = xs[i]
    x2 = xs[j]
    for k in range(N):
      for l in range(k+1, N):
        y1 = ys[k]
        y2 = ys[l]
        n = len([(x, y) for x, y in xys if x1 <= x <= x2 and y1 <= y <= y2])
        #xys2 = filter(lambda xy: x1 <= xy[0] <= x2 and y1 <= xy[1] <= y2, xys)
        if n >= K:
          r = (x2-x1)*(y2-y1)
          rs.append(r)
r = min(rs)
print(r)

Submission status: Time Limit Exceeded

Solution code:
import itertools
import sys
input = sys.stdin.readline

def main():
    N, K = map(int, input().split())
    X = []
    Y = []
    for _ in range(N):
        x, y = map(int, input().split())
        X.append(x)
        Y.append(y)
    
    ans = float('inf')
    for P in itertools.combinations(range(N), K):
        X_k = [X[p] for p in P]
        Y_k = [Y[p] for p in P]
        s = (max(X_k) - min(X_k)) * (max(Y_k) - min(Y_k))
        ans = min(ans, s)
    
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
XY = [[0, 0, 0] for _ in range(N)]
for i in range(N):
  x, y = map(int, input().split())
  XY[i] = [x, y, i]
X = sorted(XY)
Y = sorted(XY, key=lambda x: x[1])
rect = (X[-1][0] - X[0][0]) * (Y[-1][1] - Y[0][1])
for l in range(N - K + 1):
  for r in range(l + K - 1, N):
    for d in range(N - K + 1):
      for u in range(d + K - 1, N):
        if len([x for x in XY if X[l][0] <= x[0] <= X[r][0] and Y[d][1] <= x[1] <= Y[u][1]]) >= K:
          rect = min((X[r][0] - X[l][0]) * (Y[u][1] - Y[d][1]), rect)
print(rect)

Submission status: Time Limit Exceeded

Solution code:

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

xy = []
xlis = []
ylis = []

for i in range(N):

    x,y = map(int,input().split())

    xy.append([x,y])

    if x not in xlis:
        xlis.append(x)
    if y not in ylis:
        ylis.append(y)

ans = float("inf")
xlis.sort()
ylis.sort()

for rp in range(len(xlis)):

    right = xlis[rp]

    for lp in range(rp+1):

        left = xlis[lp]

        for upp in range(len(ylis)):

            up = ylis[upp]

            for dp in range(upp+1):

                down = ylis[dp]

                able = 0
                nable = 0
                for i in range(N):

                    nx = xy[i][0]
                    ny = xy[i][1]
                    if left <= nx and nx <= right and down <= ny and ny <= up:
                        able += 1
                    else:
                        nable += 1

                    if able >= K or nable > N-K:
                        break

                if able >= K:
                    now = max(1,right-left) * max(1,up-down)
                    ans = min(ans,now)

print (ans)

Submission status: Time Limit Exceeded

Solution code:

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

xy = []

for i in range(N):

    x,y = map(int,input().split())

    xy.append([x,y])

ans = float("inf")

for p1 in range(N):

    for p2 in range(N):

        for p3 in range(N):

            for p4 in range(N):


                left = min(xy[p1][0],xy[p2][0],xy[p3][0],xy[p4][0])
                down = min(xy[p1][1],xy[p2][1],xy[p3][1],xy[p4][1])
                right = max(xy[p1][0],xy[p2][0],xy[p3][0],xy[p4][0])
                up = max(xy[p1][1],xy[p2][1],xy[p3][1],xy[p4][1])

                able = 0
                nable = 0
                for i in range(N):

                    nx = xy[i][0]
                    ny = xy[i][1]
                    if left <= nx and nx <= right and down <= ny and ny <= up:
                        able += 1
                    else:
                        nable += 1

                    if able >= K or nable > N-K:
                        break

                if able >= K:
                    now = max(1,right-left) * max(1,up-down)
                    ans = min(ans,now)

print (ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations

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

ans = float('inf')
for cmb in list(combinations(pos_list,K)):
  pos_list = [a for a in zip(*cmb)]
  w = max(pos_list[0]) - min(pos_list[0])
  h = max(pos_list[1]) - min(pos_list[1])
  if w == 0:area = h
  elif h == 0:area = w
  else:area = w*h
  if ans > area: ans = area
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations

N,K = map(int,input().split())
pos_list = [list(map(int, input().split())) for _ in range(N)]
idx_list = [i for i in range(N)]
ans = float('inf')
for cmb in list(combinations(idx_list,K)):
  xlist, ylist = [], []
  for idx in cmb:
    xlist.append(pos_list[idx][0])
    ylist.append(pos_list[idx][1])
  if max(xlist) - min(xlist) == 0:
    area = max(ylist) - min(ylist)
  elif max(ylist) - min(ylist) == 0:
    area = max(xlist) - min(xlist)
  else:
    area = (max(xlist) - min(xlist))*(max(ylist) - min(ylist))
  if ans > area:ans = area
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys, itertools


def solve(N: int, K: int, x: "List[int]", y: "List[int]"):
    mn = 1e25
    for X in itertools.combinations(x, 2):
        for Y in itertools.combinations(y, 2):
            if len([xx for (xx, yy) in zip(x, y) if (X[0]-xx)*(X[1]-xx)<=0 and (Y[0]-yy)*(Y[1]-yy)<=0]) >= K:
                mn = min(mn, abs(X[0] - X[1]) * abs(Y[0] - Y[1]))
    print(mn)
    return


# Generated by 1.1.5 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    x = [int()] * (N)  # type: "List[int]"
    y = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        x[i] = int(next(tokens))
        y[i] = int(next(tokens))
    solve(N, K, x, y)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations
n,k=map(int,input().split())
L,X,Y=[],[],[]
for _ in range(n):
    x,y=map(int,input().split())
    L.append((x,y))
    X.append(x)
    Y.append(y)
ans=10**19
for p in permutations(X,2):
    for q in permutations(Y,2):
        u,d,l,r=max(p),min(p),min(q),max(q)
        cnt=0
        for i in L:
            if d<=i[0]<=u and l<=i[1]<=r:
                cnt+=1
        if cnt>=k:
            ans=min(ans,(u-d)*(r-l))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
import math


LIM = 50
N,K = list(map(int,input().split(" ")))

Xs = []
Ys = []

dots = []
for _ in range(N):
    x,y = (map(int,input().split(" ")))
    Xs.append(x)
    Ys.append(y)
    dots.append((x,y))

Xs.sort()
Ys.sort()

ans = -1
for x1 in range(N):
    for x2 in range(x1 + 1,N):
        for y1 in range(N):
            for y2 in range(y1 + 1,N):
                cot = 0
                underX = Xs[x1]
                upperX = Xs[x2]
                underY = Ys[y1]
                upperY = Ys[y2]

                for k in range(N):
                    if   underX<= dots[k][0] <= upperX and underY <= dots[k][1] <= upperY:
                        cot += 1
                if cot >= K:
                    S = (upperX - underX) * (upperY - underY)
                    if ans == -1:
                        ans = S
                    ans = min( ans ,S)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations

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)

X.sort()
Y.sort()
ans = float('inf')
for x1, x2 in combinations(X, 2):
    for y1, y2 in combinations(Y, 2):
        cnt = 0
        for x, y in XY:
            if x1 <= x <= x2 and y1 <= y <= y2:
                cnt += 1
        if K <= cnt:
            ans = min(ans, (x2 - x1) * (y2 - y1))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')
move = [(0, 1), (1, 1), (-1, 1), (0, -1), (1, -1), (-1, -1), (1, 0), (-1, 0)]
#A
def A():
    a, b, c = LI()
    if a == b:
        print(c)
    if b == c:
        print(a)
    if a == c:
        print(b)
    return

#B
def B():
    h, w = LI()
    s = SR(h)
    for y in range(h):
        for x in range(w):
            if s[y][x] == ".":
                b = 0
                for my, mx in move:
                    ym = my + y
                    xm = mx + x
                    if 0 <= ym < h and 0 <= xm < w:
                        if s[ym][xm] == "#":
                            b += 1
                s[y][x] = b
    for i in range(h):
        print("".join(map(str, s[i])))
    return

#C
def C():
    n, m = LI()
    edg = [[] for i in range(n)]
    ab = LIR_(m)
    for a,b in ab:
        edg[a].append(b)
        edg[b].append(a)
    ans = 0
    for a, b in ab:
        c = [True] * n
        ed = defaultdict(int)
        q = deque()
        q.append(0)
        c[0] = False
        ed[(a,b)] = True
        while q:
            now = q.pop()
            for e in edg[now]:
                if ed[(now,e)] or ed[(e,now)]:
                    continue
                ed[(now, e)] = True
                c[e] = False
                q.appendleft(e)
        if True in c:
            ans += 1
    print(ans)
    return

#D
def D():
    n, k = LI()
    xy = LIR(n)
    fullserch = itertools.combinations_with_replacement(range(n), 4)
    ans = inf
    for a, b, c, d in fullserch:
        minx = min(xy[a][0], xy[b][0], xy[c][0], xy[d][0])
        maxx = max(xy[a][0], xy[b][0], xy[c][0], xy[d][0])
        miny = min(xy[a][1], xy[b][1], xy[c][1], xy[d][1])
        maxy = max(xy[a][1], xy[b][1], xy[c][1], xy[d][1])
        b = 0
        for i in range(n):
            if minx <= xy[i][0] <= maxx and miny <= xy[i][1] <= maxy:
                b += 1

        if b >= k:
            ans = min(ans, (maxx - minx) * (maxy - miny))
    print(ans) 
    return

#Solve
if __name__ == '__main__':
    D()

Submission status: Time Limit Exceeded

Solution code:
def is_inside(p, down_left, up_right):
    return (down_left[0] <= p[0] and p[0] <= up_right[0]
        and down_left[1] <= p[1] and p[1] <= up_right[1])


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

xs = set(p[0] for p in points)
ys = set(p[1] for p in points)

min_area = 1e40
for x1 in xs:
    for x2 in xs:
        if x2 <= x1:
            continue

        for y1 in ys:
            for y2 in ys:
                if y2 <= y1:
                    continue

                inside = sum(is_inside(p, (x1, y1), (x2, y2)) for p in points)
                if inside >= k:
                    min_area = min(min_area, (x2 - x1) * (y2 - y1))

print(min_area)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
#ABC75 D

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))


n,K = LI()
xy = [LI() for _ in range(n)]
ans = inf
for _ , uy in xy:
    for _ , dy in xy:
        if uy < dy:
            continue
        for rx , _ in xy:
            for lx , _ in xy:
                if rx < lx:
                    continue
                cnt = 0
                for x,y in xy:
                    if lx <= x <= rx and dy <= y <= uy:
                        cnt += 1
                if cnt >= K:
                    S = (uy - dy)*(rx - lx)
                    ans = min(ans,S)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
#ABC75 D

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))


n,K = LI()
xy = []
X = []
Y = []
for _ in range(n):
    x,y = LI()
    xy.append([x,y])
    X.append(x)
    Y.append(y)
X.sort(reverse = True)
Y.sort(reverse = True)
ans = inf
for i in range(n):
    uy = Y[i]
    for dy in Y[i+1:]:
        for k in range(n):
            rx = X[k]
            for lx in X[k+1:]:
                cnt = 0
                for x,y in xy:
                    if lx <= x <= rx and dy <= y <= uy:
                        cnt += 1
                if cnt >= K:
                    S = (uy - dy)*(rx - lx)
                    ans = min(ans,S)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
#ABC75 D

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))


n,K = LI()
xy = []
X = []
Y = []
for _ in range(n):
    x,y = LI()
    xy.append([x,y])
    X.append(x)
    Y.append(y)
X.sort(reverse = True)
Y.sort(reverse = True)
ans = inf
for i in range(n):
    uy = Y[i]
    for j in range(i+1,n):
        dy = Y[j]
        for k in range(n):
            rx = X[k]
            for l in range(k+1,n):
                lx = X[l]
                cnt = 0
                for m in range(n):
                    x,y = xy[m]
                    if lx <= x <= rx and dy <= y <= uy:
                        cnt += 1
                if cnt >= K:
                    S = (uy - dy)*(rx - lx)
                    ans = min(ans,S)
print(ans)