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:
from bisect import bisect_left
N, K = map(int, input().split())
Points = [list(map(int, input().split())) for i in range(N)]


# 座標圧縮
def point_compress(points):
    x_points = sorted([x for x, y in points])
    y_points = sorted([y for x, y in points])
    points_compressed = []
    for x, y in points:
        points_compressed.append([bisect_left(x_points, x), bisect_left(y_points, y)])
    return points_compressed


Points_compressed = point_compress(Points)


class Ruisekiwa2D:
    def __init__(self, h, w):
        self.H = h
        self.W = w
        self.G = [[0] * w for _ in range(h)]

    def load(self, points):
        # 問題によってイメージしやすいよう書き換えてください
        for x, y in points:
            self.G[x][y] += 1

    def load_imos(self, points):
        # pointsは[[左上h, 左上w, 右下h, 右下w], ...]であること
        for i1, j1, i2, j2 in points:
            self.G[i1][j1] += 1  # 左上
            if j2 + 1 < self.W:  # 右上
                self.G[i1][j2+1] -= 1
            if i2 + 1 < self.H:
                self.G[i2+1][j1] -= 1  # 左下
            if j2 + 1 < self.W and i2 + 1 < self.H:  # 右下
                self.G[i2+1][j2+1] += 1

    def calc(self):
        for y in range(self.W):
            for x in range(1, self.H):
                self.G[x][y] += self.G[x-1][y]

        for y in range(1, self.W):
            for x in range(self.H):
                self.G[x][y] += self.G[x][y-1]

    def get(self, i1, j1, i2, j2):
        if i1 > i2 or j1 > j2 or i1 < 0 or j1 < 0 or i2 < 0 or j2 < 0:
            return 0
        elif i1 > 0 and j1 > 0:
            return self.G[i2][j2] - self.G[i1-1][j2] - self.G[i2][j1-1] + self.G[i1-1][j1-1]
        elif i1 <= 0 < j1:
            return self.G[i2][j2] - self.G[i2][j1-1]
        elif j1 <= 0 < i1:
            return self.G[i2][j2] - self.G[i1 - 1][j2]
        else:
            return self.G[i2][j2]


# 二次元累積和
R2D = Ruisekiwa2D(N, N)
R2D.load(Points_compressed)
R2D.calc()


ans = float('inf')
for yi in range(N):
    for yj in range(N):
        for xi in range(N):
            for xj in range(N):
                cx1, cx2 = Points_compressed[xi][0], Points_compressed[xj][0]
                cy1, cy2 = Points_compressed[yi][1], Points_compressed[yj][1]

                x1, x2 = Points[xi][0], Points[xj][0]
                y1, y2 = Points[yi][1], Points[yj][1]

                # 二次元累積和で高速に長方形内部に含まれる点の数を数える
                inside = R2D.get(cx1, cy1, cx2, cy2)
                if inside >= K:
                    ans = min(ans,  abs(x2 - x1) * abs(y2 - y1))

print(ans)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
xy = sorted([tuple(map(int, input().split())) for i in range(n)])
ans = float("INF")
en = tuple(enumerate(xy))
for i, (a, b) in en[:n - k + 1]:
    for j, (c, d) in en[i + k - 1:]:
        r = sorted(y for x, y in xy[i:j + 1])
        r2 = r[k - 1:]
        for i2, j2 in zip(r, r2):
            if i2 <= b and d <= j2:
                ans = min(ans, (c - a) * (j2 - i2))
print(ans)

Submission status: Accepted

Solution code:
import itertools
N, K = [int(_) for _ in input().split()]
XY = [[int(_) for _ in input().split()] for _ in range(N)]
X, Y = [x for x, y in XY], [y for x, y in XY]
X_s, Y_s = sorted(X), sorted(Y)
ans = float('inf')
for x1, x2 in itertools.combinations(X_s, 2):
    for y1, y2 in itertools.combinations(Y_s, 2):
        k = sum([x1 <= X[i] <= x2 and y1 <= Y[i] <= y2 for i in range(N)])
        if k >= K:
            ans = min(ans, (x2 - x1) * (y2 - y1))
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from collections import defaultdict
from pprint import pprint as pp
import itertools

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

rui = defaultdict(lambda: defaultdict(int))
sumnum = defaultdict(lambda: defaultdict(int))

for x,y in xy:
    rui[x][y] += 1

xlist = list(sorted(rui.keys()))
ylist = []
for x in xlist:
    ylist.extend(list(rui[x].keys()))
ylist = sorted(list(set(ylist)))

for x in xlist:
    tmp = 0
    for y in ylist:
        tmp += rui[x][y]
        sumnum[x][y] = tmp

for y in ylist:
    tmp = 0
    for x in xlist:
        tmp += sumnum[x][y]
        sumnum[x][y] = tmp

xdict = {v: i for i, v in enumerate(xlist)}
ydict = {v: i for i, v in enumerate(ylist)}

sqmin = -1
exy = list(itertools.product(xlist, ylist))
# print(f"len(exy)={len(exy)}")
for i, (x1, y1) in enumerate(exy[:-1]):
    # print(f"x1={x1},y1={y1}")
    # print(f"len(exy[i+1:])={len(exy[i+1:])}")
    for x2, y2 in exy[i+1:]:
        if x1 < x2 and y1 < y2:
            xd1 = xdict[x1] - 1
            yd1 = ydict[y1] - 1
            if xd1 < 0:
                xb = (10**9 + 1)*(-1)
            else:
                xb = xlist[xd1]
            if yd1 < 0:
                yb = (10**9 + 1)*(-1)
            else:
                yb = ylist[yd1]
            tmp = sumnum[x2][y2] - sumnum[xb][y2] - sumnum[x2][yb] + sumnum[xb][yb]
            if tmp >= K:
                area = abs(x2 - x1)*abs(y2 - y1)
                if sqmin > area or sqmin == -1:
                    sqmin = area

print(sqmin)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from itertools import combinations

n,k = map(int, input().split())

xl = []
yl = []
xy = []
for _ in range(n):
    x,y = map(int, input().split())
    xl.append(x)
    yl.append(y)
    xy.append((x,y))
yl.sort()
xy.sort(key=lambda x:x[1])

res = None
for cx in combinations(xl, 2):
    x1,x2 = cx
    if x2>x1:
        x1,x2 = x2,x1

    for y2 in yl:
        cnt = 0
        for c in xy:
            x,y = c
            if x1>=x>=x2 and y>=y2:
                cnt += 1

            if cnt==k:
                y1 = y
                s = (x1-x2)*(y1-y2)
                if res is None:
                    res = s
                else:
                    res = min(res, s)
                break

print(res)

Submission status: Accepted

Solution code:
N, K = map( int, input().split())
X = [0]*N
Y = [0]*N
for i in range(N):
    x, y = map( int, input().split())
    X[i] = x
    Y[i] = y
SX = sorted(X)
SY = sorted(Y)
ans = 10**19
for xleft in range(N-1):
    a = SX[ xleft]
    for xright in range(xleft, N):
        b = SX[ xright]
        for yunder in range(N-1):
            c = SY[ yunder]
            for yabove in range(yunder, N):
                d = SY[ yabove]
                cnt = 0
                for i in range(N):
                    if a <= X[i] and X[i] <= b and c <= Y[i] and Y[i] <= d:
                        cnt += 1
                if cnt >= K:
                    ans = min( ans, (b-a)*(d-c))
print(ans)

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
X,Y = [],[]
p = []
for i in range(N):
    x,y = map(int,input().split())
    X.append(x)
    Y.append(y)
    p.append([x,y])
X.sort(),Y.sort()
ans = abs(X[N-1]-X[0])*abs(Y[N-1]-Y[0])
for xi in range(N):
    for xj in range(xi+1,N):
        for yi in range(N):
            for yj in range(yi+1,N):
                lx,rx = X[xi],X[xj]
                dy,uy = Y[yi],Y[yj]
                num = 0
                for x,y in p:
                    if lx<=x and x<=rx and dy<=y and y<=uy:
                        num += 1
                if K==num:
                    ans = min(abs(rx-lx)*abs(uy-dy),ans)
print(ans)

Submission status: Accepted

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

N, K=map(int,input().strip().split(' '))
x=[]
y=[]
point=[]
for i in range(N):
    xt,yt=map(int,input().strip().split(' '))
    x.append(xt)
    y.append(yt)
    point.append([xt,yt])
ans=10**20
x.sort()
y.sort()
point.sort(key=lambda x:x[1])


for i in range(N):
    for j in range(i+1,N):
        xmin=x[i]
        xmax=x[j]
        for k in range(N):
            ymin=y[k]
#            ymax=y[l]
#            
            ct=0
            for p in point:
                if xmin<=p[0] and p[0]<=xmax and ymin<=p[1]:
                    ct+=1
                if ct==K:
                    A=(xmax-xmin)*(p[1]-ymin)
                    ans=min(ans,A)
                    break
print(ans)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
s = []
for i in range(n):#h:高さ
    s.append([int(m) for m in input().split()])
s.sort(key=lambda x:(x[0]))
count = 0
recli = []
if k == 2:
    for i in range(n):
        for j in range(i + 1, n):
            larx = max(s[i][0], s[j][0])
            smax = min(s[i][0], s[j][0])
            lary = max(s[i][1], s[j][1])
            smay = min(s[i][1], s[j][1])
            rec = (larx - smax) * (lary - smay)
            for l in range(n):
                if smax <= s[l][0] <= larx and smay <= s[l][1] <= lary:
                    count += 1
            if count >= k:
                recli.append(rec)
            count = 0

elif k == 3:
    for i in range(n):
        for j in range(i + 1, n):
            for p in range(j + 1, n):
                larx = max(s[i][0], s[j][0], s[p][0])
                smax = min(s[i][0], s[j][0], s[p][0])
                lary = max(s[i][1], s[j][1], s[p][1])
                smay = min(s[i][1], s[j][1], s[p][1])
                rec = (larx - smax) * (lary - smay)
                for l in range(n):
                    if smax <= s[l][0] <= larx and smay <= s[l][1] <= lary:
                        count += 1
                if count >= k:
                    recli.append(rec)
                count = 0
else:
    for i in range(n):
        for j in range(i + 1, n):
            for p in range(j + 1, n):
                for q in range(p + 1, n):
                    larx = max(s[i][0], s[j][0], s[p][0], s[q][0])
                    smax = min(s[i][0], s[j][0], s[p][0], s[q][0])
                    lary = max(s[i][1], s[j][1], s[p][1], s[q][1])
                    smay = min(s[i][1], s[j][1], s[p][1], s[q][1])
                    rec = (larx - smax) * (lary - smay)
                    if q - i + 1 >= k:
                        if (recli == []) or (recli != [] and rec < min(recli)):
                            for l in range(i, q + 1):
                                if smax <= s[l][0] <= larx and smay <= s[l][1] <= lary:
                                    count += 1
                            if count >= k:
                                recli.append(rec)
                            count = 0

print(min(recli))

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
Points=[[int(i) for i in input().split()] for i in range(N)]
List_x=[Points[i][0] for i in range(N)]
List_x.sort(key=lambda x:x)
List_y=[Points[i][1] for i in range(N)]
List_y.sort(key=lambda x:x)
n=0
Y=0
S=(List_x[-1]-List_x[0])*(List_y[-1]-List_y[0])
for x1 in range(N-1):
  for x2 in range(x1+K-1,N):
    for y1 in range(N-1):
      for y2 in range(max([y1+K-1,Y]),N):
        for p in Points:
          if List_x[x1]<=p[0]<=List_x[x2] and List_y[y1]<=p[1]<=List_y[y2]:
            n+=1
          if n==K:
            x_delta=List_x[x2]-List_x[x1]
            y_delta=List_y[y2]-List_y[y1]
            if x_delta*y_delta<S:
               S=x_delta*y_delta
            break
        if n>=K:
          n=0
          Y=y2
          break  
        n=0
    Y=0    
print(S)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
Points=[[int(i) for i in input().split()] for i in range(N)]
List_x=[Points[i][0] for i in range(N)]
List_x.sort(key=lambda x:x)
List_y=[Points[i][1] for i in range(N)]
List_y.sort(key=lambda x:x)
n=0
Y=0
S=[]
for x1 in range(N-1):
  for x2 in range(x1+K-1,N):
    for y1 in range(N-1):
      for y2 in range(max([y1+K-1,Y]),N):
        for p in Points:
          if List_x[x1]<=p[0]<=List_x[x2] and List_y[y1]<=p[1]<=List_y[y2]:
            n+=1
          if n==K:
            x_delta=List_x[x2]-List_x[x1]
            y_delta=List_y[y2]-List_y[y1]
            S.append(x_delta*y_delta)
            break
        if n>=K:
          n=0
          Y=y2
          break  
        n=0
    Y=0    
print(min(S))

Submission status: Accepted

Solution code:
n,K=map(int,input().split())
data=[]
for i in range(n):
    x,y=map(int,input().split())
    data.append((x,y))
y_sorted=sorted(data,key=lambda x:x[1])
x_sorted=sorted(data,key=lambda x:x[0])


ans=10**20
len_data=len(data)
for i in range(len_data):
    left=x_sorted[i]
    for j in range(len_data):
        down=y_sorted[j]
        if(left[1] < down[1] or down[0] < left[0]):
             continue
        for k in range(j+1,len_data):
            upp=y_sorted[k]
            if(upp[1] < left[1] or upp[0] < left[0]):
                continue
            for l in range(i+1,len_data):
                right=x_sorted[l]
                if( ans <=(right[0] - left[0]) * (upp[1] -down[1])):
                    break
                if((right[0] - left[0]) * (upp[1] -down[1])==0):
                    continue
                if(right[1] < down[1] or right[1] > upp[1] \
                 or right[0] < down[0] or right[0] < upp[0]):
                    continue
                tmp=0
                for m in range(len_data):
                    now=x_sorted[m]
                    if(down[1] <= now[1] <= upp[1] and left[0] <= now[0] <= right[0]):
                        tmp+=1
                        if(tmp==K):
                            ans= min( [ans, (right[0] - left[0]) * (upp[1] -down[1])])
                            break




print(ans)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
x = []
for i in range(N):
    x.append(list(map(int, input().split())))
ans = []
for i in range(N):
    for j in range(i+1, N):
        for l in range(N):
            for m in range(l+1, N):
                count = 0
                x1 = min(x[i][0], x[j][0])
                x2 = max(x[i][0], x[j][0])
                y1 = min(x[l][1], x[m][1])
                y2 = max(x[l][1], x[m][1])

                for k in range(N):
                    if x1 <= x[k][0] and x[k][0] <= x2 and y1 <= x[k][1] and x[k][1] <= y2:
                        count += 1
                if count >= K:
                    ans.append((x2 - x1) * (y2 - y1))
print(min(ans))

Submission status: Accepted

Solution code:
def inpl(): return [int(i) for i in input().split()]
from collections import defaultdict

N, K = inpl()
inf = 10**19+1
x = [inf for _ in range(N+1)]
y = [inf for _ in range(N+1)]
H = defaultdict(lambda: 0)

for i in range(N):
    x[i], y[i] = inpl()
    H[(x[i],y[i])] = 1
    

x.sort()
y.sort()

for i in range(N-1):
    for j in range(N):
        H[(x[i+1],y[j])] = H[(x[i],y[j])] + H[(x[i+1],y[j])]

for j in range(N-1):
    for i in range(N):
        H[(x[i],y[j+1])] = H[(x[i],y[j])] + H[(x[i],y[j+1])]

for i in range(N+1):
    H[(x[i],inf)] = H[(inf,y[i])] = 0
H[(inf,inf)] = 0

ans = inf
for i in range(N):
    for j in range(N):
        for t in range(i):
            if i-t+1 < K:
                break
            for s in range(j):
                if j-s+1 < K:
                    break
                if H[(x[i],y[j])] - H[(x[t-1],y[j])] -\
                H[(x[i],y[s-1])] + H[(x[t-1],y[s-1])] != K:
                    continue
                ans = min(ans,(x[i]-x[t])*(y[j]-y[s]))
print(ans)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())

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

min_x = min(x)
min_y = min(y)
for i in range(n):
    x[i] -= min_x
    y[i] -= min_y

sx = sorted(x)
sy = sorted(y)

if n == k:
    print(sx[n - 1] * sy[n - 1])
    exit()

d = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
for i in range(n):
    d[sx.index(x[i]) + 1][sy.index(y[i]) + 1] = 1

for i in range(n + 1):
    for j in range(1, n + 1):
        d[i][j] += d[i][j - 1]

for i in range(n + 1):
    for j in range(1, n + 1):
        d[j][i] += d[j - 1][i]

#sx = [0] + sx
#sy = [0] + sy

a = 0
b = 1
ans = sx[n - 1] * sy[n - 1]
temp = 0
for p in range(n):
    for q in range(p + 1, n):
        for a in range(n):
            for b in range(a + 1, n):
                count = 0
                if d[b + 1][q + 1] - d[b + 1][p] - d[a][q + 1] + d[a][p] >= k:
                    ans = min(ans, (sx[b] - sx[a]) * (sy[q] - sy[p]))

print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate
import numpy as np
N,K=list(map(int,input().split()))
point=[]
x_set=set()
y_set=set()

for i in range(N):
    x,y=list(map(int,input().split()))
    point.append((x,y))
    x_set.add(x)
    y_set.add(y)
x_arr=sorted(list(x_set))
y_arr=sorted(list(y_set))

x_dic={}
y_dic={}
for i,x in enumerate(x_arr):
    x_dic[x]=i
for i,y in enumerate(y_arr):
    y_dic[y]=i

square=[[0 for _ in range(len(x_arr)+1)] for _ in range(len(y_arr)+1)]
for p in point:
    j=x_dic[p[0]]
    i=y_dic[p[1]]
    square[i+1][j+1]+=1
square=np.array(square)

for i,line in enumerate(square):
    square[i]=list(accumulate(line))
for i,row in enumerate(square.T):
    square[:,i]=list(accumulate(row))

h=1
ans=float('inf')
W=len(square[0])
H=len(square)
for i in range(1,H):
    for j in range(i,H):
        h=1
        for k in range(1,W): 
            num=square[j][k]-square[i-1][k]-square[j][h-1]+square[i-1][h-1]
            while num>=K:
                S=max(y_arr[j-1]-y_arr[i-1],1)*max(x_arr[k-1]-x_arr[h-1],1)
                ans=min(ans,S)
                h+=1
                num=square[j][k]-square[i-1][k]-square[j][h-1]+square[i-1][h-1]
print(int(ans))

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
z = [0]*N
for i in range(N):
    x,y = map(int,input().split())
    z[i] = (x,y)
z.sort(key=lambda x:x[1])
H = z[N-1][1]-z[0][1]
z.sort()
W = z[N-1][0]-z[0][0]
ans = H*W
for i in range(N-K+1):
    for j in range(i+K-1,N):
        z_ = z[i:j+1].copy()
        W = z_[-1][0]-z_[0][0]
        z_.sort(key=lambda x:x[1])
        for k in range(len(z_)-K+1):
            H = z_[k+K-1][1]-z_[k][1]
            if H*W < ans:
                ans = H*W
print(ans)

Submission status: Accepted

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

X = sorted(X)
Y = sorted(Y)
num = 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):
                tmp = 0
                for m in range(N):
                    if X[i] <= D[m][0] <= X[j] and Y[k] <= D[m][1] <= Y[l]:
                        tmp += 1
                if tmp >= K:
                    num = min(num, (X[j] - X[i]) * (Y[l] - Y[k]))

print(num)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
xy=[list(map(int,input().split())) for _ in range(n)]
x=[t[0] for t in xy]
y=[t[1] for t in xy]

res=[]
for i in range(n-1):
    for j in range(i+1,n):
        for a in range(n-1):
            for b in range(a+1,n):
                l=min(x[i],x[j])
                r=max(x[i],x[j])
                d=min(y[a],y[b])
                u=max(y[a],y[b])
                tk=0
                for t in xy:
                    if l<=t[0]<=r and d<=t[1]<=u:
                        tk+=1
                if tk>=k:
                    res.append((r-l)*(u-d))
print(min(res))

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
p = [list(map(int, input().split())) for _ in range(N)]
x = sorted(list(zip(*p))[0])
y = sorted(list(zip(*p))[1])
dic_x = {v: i + 1 for i, v in enumerate(x)}
dic_y = {v: i + 1 for i, v in enumerate(y)}
cum_sum = [[0] * (N + 1) for _ in range(N + 1)]
for i, j in p:
    cum_sum[dic_y[j]][dic_x[i]] = 1

for i in range(1, N + 1):
    for j in range(N):
        cum_sum[i][j + 1] += cum_sum[i][j]

for i in range(1, N + 1):
    for j in range(N):
        cum_sum[j + 1][i] += cum_sum[j][i]

ans = 10 ** 20
for l in range(N):
    for r in range(l + 1, N):
        for d in range(N):
            for u in range(d + 1, N):
                z = cum_sum[u + 1][r + 1] - cum_sum[d][r + 1] \
                     - cum_sum[u + 1][l] + cum_sum[d][l]
                if z >= K:
                    ans = min(ans, (x[r] - x[l]) * (y[u] - y[d]))
print(ans)

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from itertools import accumulate

n,k = li()
xs = []
ys = []
points = []
for _ in range(n):
    x,y = li()
    xs.append(x)
    ys.append(y)
    points.append((x,y))
    
xs.sort()
ys.sort()

rank_x = {}
rank_y = {}
for i, x in enumerate(xs):
    rank_x.update({x:i+1})
for i, y in enumerate(ys):
    rank_y.update({y:i+1})

field = [[0 for _ in range(n+1)] for _ in range(n+1)]
for px,py in points:
    field[rank_y[py]][rank_x[px]] = 1
    
for row in range(n+1):
    field[row] = list(accumulate(field[row]))
    
for col in range(n+1):
    for row in range(n):
        field[row+1][col] += field[row][col]

ans = float("inf")
for xst in range(n):
    for xed in range(xst+1,n):
        for yst in range(n):
            for yed in range(yst+1,n):
                if field[yed+1][xed+1] + field[yst][xst] \
                    -field[yed+1][xst] - field[yst][xed+1]>= k:
                    ans = min(ans, (xs[xed]-xs[xst])*(ys[yed]-ys[yst]))

print(ans)

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

n,k = li()
xs = []
ys = []
points = []
for _ in range(n):
    x,y = li()
    xs.append(x)
    ys.append(y)
    points.append((x,y))
    
xs.sort()
ys.sort()

ans = float("inf")
for xst in range(n):
    for xed in range(xst+1,n):
        for yst in range(n):
            for yed in range(yst+1, n):
                cnt = 0
                for px,py in points:
                    if xs[xst] <= px <= xs[xed] and ys[yst] <= py <= ys[yed]:
                        cnt += 1
                        
                if cnt >= k:
                    ans = min(ans, (xs[xed]-xs[xst])*(ys[yed]-ys[yst]))
                    
print(ans)

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

n,k = li()
x = []
y = []
points = [tuple(li()) for _ in range(n)]
for i in range(n):
    x.append(points[i][0])
    y.append(points[i][1])
    
x.sort()
y.sort()

ans = (x[-1]-x[0]) * (y[-1]-y[0])
for u,xs in enumerate(x[:-1]):
    for xt in x[u+1:]:
        for v,ys in enumerate(y[:-1]):
            for yt in y[v+1:]:
                area = (xt-xs) * (yt-ys)
                inner = 0
                for xi,yi in points:
                    if xs<=xi<=xt and ys<=yi<=yt:
                        inner += 1
                        
                if inner >= k:
                    ans = min(ans,area)
                    
                    
print(ans)

Submission status: Accepted

Solution code:
from itertools import product

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

xary = sorted(x)
yary = sorted(y)

ans = float('inf')
for i, j, k, l in product(range(N), repeat=4):
    if i >= j or k >= l:
        continue
    x1, x2 = xary[i], xary[j]
    y1, y2 = yary[k], yary[l]
    cnt = 0
    for xx, yy in zip(x, y):
        if x1 <= xx <= x2 and y1 <= yy <= y2:
            cnt += 1
    if cnt >= K:
        s = abs(x1 - x2) * abs(y1 - y2)
        ans = min(ans, s)
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())

N,K = inpl()
xys = []
xx = set()
for i in range(N):
    x,y = inpl()
    xys.append([x,y])
    xx.add(x)

ans = INF
xx = sorted(list(xx))
Lx = len(xx)
xys.sort(key = lambda x: x[1])
for i1 in range(Lx):
    x1 = xx[i1]
    for i2 in range(i1,Lx):
        x2 = xx[i2]
        yy = []
        for x,y in xys:
            if x1 <= x <= x2:
                yy.append(y)
        Ly = len(yy)
        if Ly < K:
            continue
        else:
            for l in range(Ly-K+1):
                r = l+K-1
                ans = min((yy[r]-yy[l])*(x2-x1),ans)

print(ans)

Submission status: Accepted

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

xs, ys = tuple(zip(*xy))
cmpx = sorted(xs)
cmpy = sorted(ys)

x2cmp = dict((x, i) for i,x in enumerate(cmpx))
y2cmp = dict((x, i) for i,x in enumerate(cmpy))

sm = [[0] * (N + 1) for _ in range(N + 1)]
for x, y in xy:
    sm[x2cmp[x]][y2cmp[y]] = 1

for i in range(N):
    for j in range(N):
        sm[i][j] += sm[i][j - 1]
for j in range(N):
    for i in range(N):
        sm[i][j] += sm[i - 1][j]

ans = float('inf')
for x1 in range(N):
    for y1 in range(N):
        for x2 in range(x1 + 1, N):
            for y2 in range(y1 + 1, N):
                k = sm[x2][y2] - sm[x2][y1 - 1] - sm[x1 - 1][y2] + sm[x1 - 1][y1 - 1]
                if k == K:
                    area = (cmpx[x2] - cmpx[x1]) * (cmpy[y2] - cmpy[y1])
                    ans = min(ans, area)

print(ans)

Submission status: Accepted

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

xy = sorted(xy)
ans = 4*10**18
for i in range(n-k+1):
    x_left = xy[i][0]
    for j in range(i+k-1, n):
        x_right = xy[j][0]
        y_mid = sorted([y for x, y in xy[i:j+1]])
        for k_ in range(len(y_mid)-k+1):
            y_bottom = y_mid[k_]
            y_top = y_mid[k_+k-1]
            ans = min(ans, (x_right-x_left)*(y_top-y_bottom))
print(ans)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
xy = [list(map(int,input().split())) for _ in range(n)]
sx = sorted(xy)
nx = list(enumerate(sx))

ans = float('inf')
for i,[x1,y1] in nx:
    for j,[x2,y2]in nx:
        if i>j:
            continue
        sy = sorted(y for x,y in sx[i:j+1])
        for l in range(len(sy)-k+1):
            y3,y4 = sy[l],sy[l+k-1]
            if y3<=y1<=y4 and y3<=y2<=y4:
                ans = min(ans, (x2-x1)*(y4-y3))
print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations
n, k = map(int, input().split())
dots = sorted([list(map(int, input().split())) for _ in range(n)])

ans = float("inf")
for x1, x2 in combinations(range(n), 2):
	wid = dots[x2][0] - dots[x1][0]
	dots_cand = sorted(dots[x1: x2 + 1], key=lambda x: x[1])
	for y1, y2 in combinations(range(x2 + 1 - x1), 2):
		if y2 - y1 + 1 >= k:
			area = (dots_cand[y2][1] - dots_cand[y1][1]) * wid
			if area < ans:
				ans = area

print(ans)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
pos = []
for i in range(n):
    x, y = map(int, input().split())
    pos.append((x, y))

pos.sort()
minSq = 4000000000000000000

for l in range(n):
    lx, ly = pos[l]
    que = []
    for r in range(l, n):
        rx, ry = pos[r]
        que.append(ry)
        sizes = sorted(que)
        n_sizes = len(que)
        if n_sizes < k:
            continue
        for i_top in range(k - 1, n_sizes):
            top = sizes[i_top]
            bottom = sizes[i_top - k + 1]
            minSq = min(minSq, (top - bottom) * (rx - lx))

print(minSq)

Submission status: Accepted

Solution code:
from itertools import combinations as comb
n,k=map(int,input().split())
f=lambda x,y:(min(x,y),max(x,y))
o=[tuple(map(int,input().split())) for _ in range(n)]

v=float("inf")
for (a,b) in comb(range(n),2):
  for (c,d) in comb(range(n),2):
    lx,rx=f(o[a][0],o[b][0])
    dy,uy=f(o[c][1],o[d][1])
    cnt=0
    for i in o:
      if lx<=i[0]<=rx and dy<=i[1]<=uy:
        cnt+=1
    if cnt>=k:
      v=min(v,(rx-lx)*(uy-dy))
print(v)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
#L=[tuple(map(int,input().split())) for i in range(N)]
L = []
for i in range(N):
    li = list(map(int,input().split()))
    L.append(li)
    
#print(L)

L.sort()

#print(L)

ans=10**37
for i in range(N):
    for j in range(i+1,N):
        t=L[j][0]-L[i][0]
        S=sorted(x[1] for x in L[i:j+1])
        for k in range(len(S)-K+1):
            u=S[K+k-1]-S[k]
            ans=min(ans,u*t)
print(ans)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
L=[tuple(map(int,input().split())) for i in range(N)]
L.sort()
ans=10**37
for i in range(N):
    for j in range(i+1,N):
        t=L[j][0]-L[i][0]
        S=sorted(x[1] for x in L[i:j+1])
        for k in range(len(S)-K+1):
            u=S[K+k-1]-S[k]
            ans=min(ans,u*t)
print(ans)

Submission status: Accepted

Solution code:
import itertools
n,k = map(int,input().split())
x = []
a = []
b = []
for i in range(n):
    x1,y1=[int(i) for i in input().split()]
    x.append([x1,y1])
    a.append(x1)
    b.append(y1)
ue = list(itertools.combinations(a,2))
mi = list(itertools.combinations(b,2))
e = len(ue)
ue.extend(mi)
ans = float("inf")
for i in range(e):
  u = ue[i]
  if u[0] > u[1]:
    UP = u[0]
    DO = u[1]
  else:
    UP = u[1]
    DO = u[0]
  for j in range(e):
    kazu = 0
    m = ue[j+e]
    if m[0] > m[1]:
      RI = m[0]
      LE = m[1]
    else:
      RI = m[1]
      LE = m[0]
    for i in  x:
      c = i[0]
      d = i[1]
      if (UP >= c and c>= DO and RI >= d and d >= LE):
        kazu += 1
    if kazu >= k:
      ans = min(ans,(UP-DO)*(RI-LE))
print(ans)