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: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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: Accepted

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

Submission status: Accepted

Solution code:
"""
座標圧縮
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)))}

# 2D累積和
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]
                # print((i1,i2),(j1,j2),num)
                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)

Submission status: Accepted

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

Submission status: Accepted

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,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]
        #print(new_lis)
        if len(new_lis)<k:
            continue
        new_lis.sort(key=lambda x:x[1])
        #print(new_lis)
        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(sq)
print(min(sq))

Submission status: Accepted

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


#############
# Main Code #
#############

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

# x軸, y軸を作る
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)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

# まず O(N^5)解法を作ってみよう。通るのかこれ?
# Python 3.8.2 ではTLE、PyPyではAC(1.2秒)

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)

Submission status: Accepted

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: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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])
  
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)

Submission status: Accepted

Solution code:
import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
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()

Submission status: Accepted

Solution code:
import math
#import sys
#input = sys.stdin.readline

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)

    # divisors.sort()
    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]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

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))

# a = list(map(int, input().split()))

#################################################
#################################################
#################################################
#################################################



#46-

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

#print(xs)
#print(ys)

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]
            #print(i2,i1,li,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
            #print('count',count,K)
            if(count == K):
                ans = min(ans,(r-l)*(yu-yd))
                
            if(count<K):
                #print('ri',ri)
                if(ri == n-1):
                    #print('b')
                    break
                else:
                    ri+=1
                    continue
            elif(count >= K):
                li += 1
                #print('li',li)
                continue

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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