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:
N, K = map(int, input().split())
x_list = [0]*N
y_list = [0]*N
for i in range(N):
    x_list[i], y_list[i] = map(int, input().split())

x_element = sorted(x_list)
y_element = sorted(y_list)
ans = float("inf")

for i in range(len(x_element)):
    for j in range(len(y_element)):
        for k in range(i+1, len(x_element)):
            for l in range(j+1, len(y_element)):
                num = 0
                for m in range(N):
                    if x_element[i] <= x_list[m] <= x_element[k] and y_element[j] <= y_list[m] <= y_element[l]:
                        num += 1
                if num >= K:
                    ans = min((x_element[k] - x_element[i]) * (y_element[l] - y_element[j]), ans)

print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations

n,k = map(int,input().split())
Px = sorted([list(map(int,input().split())) for i in range(n)])
Py = sorted(Px,key=lambda p:p[1])

area = float('inf')

for x1 in range(n-1):
    for x2 in range(x1+1,n):
        for y1 in range(n-1):

            point = 0
            for y in range(y1,n):
                if Px[x1][0]<=Py[y][0]<=Px[x2][0]:
                    point += 1
                    if point == k:
                        area = min(area,(Px[x2][0]-Px[x1][0])*(Py[y][1]-Py[y1][1]))
                        break

print(area)

Submission status: Accepted

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

ans = float("Inf")
for i in range(n-k+1):
    for j in range(k,n-i+1):
        xmin = ary[i][0]
        xmax = ary[i+j-1][0]
        ary_y = sorted(ary[i:i+j], key=lambda x: (x[1]))
        for l in range(len(ary_y)-k+1):
            ymin = ary_y[l][1]
            ymax = ary_y[l+k-1][1]
            ans = min(ans,(xmax - xmin) * (ymax - ymin))
print(ans)

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
A = [list(map(int,input().split())) for _ in range(N)]
s = 10**19
B = sorted(A,key=lambda x:x[0])
for i in range(N-K+1):
    for j in range(K,N-i+1):
        xmin = B[i][0]
        xmax = B[i+j-1][0]
        By = sorted(B[i:i+j],key=lambda x:x[1])
        for k in range(len(By)-K+1):
            ymin = By[k][1]
            ymax = By[k+K-1][1]
            s = min(s,(xmax-xmin)*(ymax-ymin))
print(s)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
x_list = []
y_list = []
xy_list = []
for _ in range(N):
    x, y = map(int, input().split())
    x_list.append(x)
    y_list.append(y)
    xy_list.append((x, y))
x_dict = {}
x_dict_rev = {}
y_dict = {}
y_dict_rev = {}
x_list.sort()
y_list.sort()
for i, xi in enumerate(x_list):
    x_dict[xi] = i
    x_dict_rev[i] = xi
for i, yi in enumerate(y_list):
    y_dict[yi] = i
    y_dict_rev[i] = yi
xy_c = [[0 for _ in range(N)] for _ in range(N)]
for x, y in xy_list:
    xy_c[x_dict[x]][y_dict[y]] = 1

cs = [[0 for _ in range(N+1)] for _ in range(N+1)]
for i in range(N):
    for j in range(N):
        cs[i+1][j+1] = cs[i+1][j] + cs[i][j+1] - cs[i][j] + xy_c[i][j]

ans = float('inf')
for x_min in range(1, N+1):
    for x_max in range(1, N+1):
        for y_min in range(1, N+1):
            for y_max in range(1, N+1):
                if cs[x_max][y_max] - cs[x_min-1][y_max] - cs[x_max][y_min-1] + cs[x_min-1][y_min-1] >= K:
                    ans = min(ans, (x_dict_rev[x_max-1] - x_dict_rev[x_min-1]) * (y_dict_rev[y_max-1] - y_dict_rev[y_min-1]))


print(ans)

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_left
input = sys.stdin.readline

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

x = [p[i][0] for i in range(n)]
x.sort()
y = [p[i][1] for i in range(n)]
y.sort()

coord = [[0] * n for i in range(n)]
for i in range(n):
    x_idx = bisect_left(x, p[i][0])
    y_idx = bisect_left(y, p[i][1])
    coord[x_idx][y_idx] += 1

coord_cs = [[0] * (n+1) for i in range(n+1)]
for i in range(n):
    for j in range(n):
        coord_cs[i+1][j+1] = coord[i][j]
for i in range(n):
    for j in range(n+1):
        coord_cs[i+1][j] += coord_cs[i][j]
for i in range(n+1):
    for j in range(n):
        coord_cs[i][j+1] += coord_cs[i][j]

# print(*coord, sep='\n')
# print(*coord_cs, sep='\n')

ans = (x[-1] - x[0]) * (y[-1] - y[0])
for xi in range(n):
    for xj in range(xi+1, n+1):
        for yi in range(n):
            for yj in range(yi+1, n+1):
                if coord_cs[xj][yj] - coord_cs[xi][yj] - coord_cs[xj][yi] + coord_cs[xi][yi] == k:
                    cand = (x[xj-1] - x[xi]) * (y[yj-1] - y[yi])
                    ans = min(ans, cand)

print(ans)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
x_list = [0]*N
y_list = [0]*N
for i in range(N):
    x_list[i], y_list[i] = map(int, input().split())

x_element = sorted(set(x_list))
y_element = sorted(set(y_list))
ans = float("inf")

for i in range(len(x_element)):
    for j in range(len(y_element)):
        for k in range(i+1, len(x_element)):
            for l in range(j+1, len(y_element)):
                num = 0
                for m in range(N):
                    if x_element[i] <= x_list[m] <= x_element[k] and y_element[j] <= y_list[m] <= y_element[l]:
                        num += 1
                if num >= K:
                    ans = min((x_element[k] - x_element[i]) * (y_element[l] - y_element[j]), ans)

print(ans)

Submission status: Accepted

Solution code:
n,h=map(int,input().split())
p,x,y=[],[],[]
z=float("inf")
for i in range(n):
  a,b=map(int,input().split())
  p.append((a,b))
  x.append(a)
  y.append(b)
x.sort()
y.sort()
for i in range(n-1):
  for j in range(i,n):
    for k in range(n-1):
      lx,rx,dy=x[i],x[j],y[k]
      c=0
      t=[]
      for a,b in p:
        if x[i]<=a<=x[j] and y[k]<=b:c+=1;t.append(b)
      if h<=c:z=min(z,(x[j]-x[i])*(sorted(t)[h-1]-y[k]))
print(z)

Submission status: Accepted

Solution code:
n, k = map(int,input().split())
ps = [tuple(map(int,input().split())) for i in range(n)]

sx = sorted(ps,key = lambda x: x[0]) # x座標でソート
nx = list(enumerate(sx)) # 頂点番号を付加
ans = 5e18

for f, (x1,y1) in nx[:n-k+1]: # 左辺の頂点
    for e, (x2,y2) in nx[f+k-1:]: # 右辺の頂点
        dx = x2 - x1 # 横
        sy = sorted(y for x,y in sx[f:e+1]) # 含まれる頂点をy座標でソート
        for y3,y4 in zip(sy,sy[k-1:]): # y3=下辺の頂点，y4=上辺の頂点
            if y3 <= y1 and y4 >= y2: # 左右辺の頂点を含むこと
                ans = min(ans, dx * (y4 - y3))

print(ans)

Submission status: Accepted

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(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)
                        no_one = False
                        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: Accepted

Solution code:
INF = float("inf")

N, K, *XY = map(int, open(0).read().split())

X, Y = zip(*sorted(zip(*[iter(XY)] * 2)))

ans = INF
for k in range(K, N + 1):
    for i in range(N - k + 1):
        dx = X[i + k - 1] - X[i]
        YY = sorted(Y[i:i + k])
        for j in range(k - K + 1):
            dy = YY[j + K - 1] - YY[j]
            if ans > dx * dy:
                ans = dx * dy

print(ans)

Submission status: Accepted

Solution code:
N, K, *XY = map(int, open(0).read().split())

X, Y = zip(*sorted(zip(*[iter(XY)] * 2)))

cand = []
for k in range(K, N + 1):
    for i in range(N - k + 1):
        dx = X[i + k - 1] - X[i]
        YY = sorted(Y[i:i + k])
        cand += [min(dx * (YY[j + K - 1] - YY[j]) for j in range(k - K + 1))]

print(min(cand))

Submission status: Accepted

Solution code:
N, K, *XY = map(int, open(0).read().split())

X, Y = zip(*sorted(zip(*[iter(XY)] * 2)))

cand = []
for k in range(K, N + 1):
    for i in range(N - k + 1):
        dx = X[i + k - 1] - X[i]
        YY = sorted(Y[i:i + k])
        cand.append(min(dx * (YY[j + K - 1] - YY[j]) for j in range(k - K + 1)))

print(min(cand))

Submission status: Accepted

Solution code:
N, K, *XY = map(int, open(0).read().split())

X, Y = zip(*sorted(zip(*[iter(XY)] * 2)))

ans = 1e20
for k in range(K, N + 1):
    for i in range(N - k + 1):
        dx = X[i + k - 1] - X[i]
        YY = sorted(Y[i:i + k])
        ans = min(ans, min(dx * (YY[j + K - 1] - YY[j]) for j in range(k - K + 1)))

print(ans)

Submission status: Accepted

Solution code:
N, K, *XY = map(int, open(0).read().split())

X, Y = zip(*sorted(zip(*[iter(XY)] * 2)))

cand = []
for k in range(K, N + 1):
    for i in range(N - k + 1):
        dx = X[i + k - 1] - X[i]
        YY = sorted(Y[i:i + k])
        cand += [dx * (YY[j + K - 1] - YY[j]) for j in range(k - K + 1)]

print(min(cand))

Submission status: Accepted

Solution code:
INF = float("inf")

N, K, *XY = map(int, open(0).read().split())

X, Y = zip(*sorted(zip(*[iter(XY)] * 2)))

ans = INF
for k in range(K, N + 1):
    for i in range(N - k + 1):
        dx = X[i + k - 1] - X[i]
        YY = sorted(Y[i:i + k])
        for j in range(k - K + 1):
            dy = YY[j + K - 1] - YY[j]
            ans = min(ans, dx * dy)

print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=sys.stdin.readline
def resolve():
    from itertools import product
    n,k=map(int,input().split())
    X=[0]*n
    Y=[0]*n
    XY=[0]*n
    for i in range(n):
        x,y=map(int,input().split())
        X[i]=x
        Y[i]=y
        XY[i]=(x,y)
    # 2-dim cumsum (pivot=(-inf,-inf))
    S=[[0]*n for _ in range(n)]
    X.sort(); Y.sort()
    for i,j in product(range(n),repeat=2):
        for x,y in XY:
            if x<=X[i] and y<=Y[j]: S[i][j]+=1
    # calculate
    ans=INF
    for i0,j0 in product(range(n),repeat=2):
        for i1,j1 in product(range(i0+1,n),range(j0+1,n)):
            count=S[i1][j1]
            if i0>0: count-=S[i0-1][j1]
            if j0>0: count-=S[i1][j0-1]
            if i0>0 and j0>0: count+=S[i0-1][j0-1]
            if count>=k:
                ans=min(ans,(X[i1]-X[i0])*(Y[j1]-Y[j0]))
    print(ans)
resolve()

Submission status: Accepted

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]])
                    count=0
                    for i in range(n):
                        if x0<=X[i]<=x1 and y0<=Y[i]<=y1:
                            count+=1
                    if count>=k:
                        ans=min(ans,(x1-x0)*(y1-y0))
    print(ans)
resolve()

Submission status: Accepted

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):
    x1,y1 = XY[i]
    for j in range(i+1,N):
        x2,y2 = XY[j]
        u2 = max(y1,y2)
        d2 = min(y1,y2)
        r2 = max(x1,x2)
        l2 = min(x1,x2)
        for k in range(j+1,N):
            x3,y3 = XY[k]
            u3 = max(u2,y3)
            d3 = min(d2,y3)
            r3 = max(r2,x3)
            l3 = min(l2,x3)
            for kk in range(k+1,N):
                x4,y4 = XY[kk]
                u4 = max(u3,y4)
                d4 = min(d3,y4)
                r4 = max(r3,x4)
                l4 = min(l3,x4)
                num = 0
                for m in range(N):
                    x,y = XY[m]
                    if l4<=x<=r4 and d4<=y<=u4:
                        num += 1
                if num >= K:
                    tmp = (u4-d4)*(r4-l4)
                    if tmp < ans:
                        ans = tmp
            num = 0
            for m in range(N):
                x,y = XY[m]
                if l3<=x<=r3 and d3<=y<=u3:
                    num += 1
            if num >= K:
                tmp = (u3-d3)*(r3-l3)
                if tmp < ans:
                    ans = tmp
        num = 0
        for m in range(N):
            x,y = XY[m]
            if l2<=x<=r2 and d2<=y<=u2:
                num += 1
        if num >= K:
            tmp = (u2-d2)*(r2-l2)
            if tmp < ans:
                ans = tmp
print(ans)

Submission status: Accepted

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

p_list.sort()
ans = float('inf')
for i in range(N - K + 1):
    for j in range(i + K - 1, N):
        x = abs(p_list[j][0] - p_list[i][0])
        y_list = []
        for k in range(i, j + 1):
            y_list.append((p_list[k][1]))
        y_list.sort()
        for k in range(len(y_list) - K + 1):
            ans = min(ans, x * abs(y_list[k + K - 1] - y_list[k]))

print(ans)

Submission status: Accepted

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 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
                    for p in range(N):
                        if min(X[i], X[j])<=X[p] and X[p]<=max(X[i], X[j]):
                            if min(Y[k], Y[l])<=Y[p] and Y[p]<=max(Y[k], Y[l]):
                                cnt += 1
                    if cnt>=K:
                        s = abs(X[i]-X[j]) * abs(Y[k]-Y[l])
                        if s!=0:
                            ans = min(ans, s)
    
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    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 i in range(N):
        for j in range(N):
            for k in range(N):
                for l in range(N):
                    if x[i] < x[j] and y[k] < y[l]:
                        cnt = 0
                        lx = x[i]
                        rx = x[j]
                        by = y[k]
                        uy = y[l]

                        for n in range(N):
                            if lx <= x[n] and x[n] <= rx and by <= y[n] and y[n] <= uy:
                                cnt += 1

                        if cnt >= K:
                            ans = min(ans, (rx - lx) * (uy - by))

    print(ans)

main()

Submission status: Accepted

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

P = []
X = []
Y = []

PAppend = P.append
XAppend = X.append
YAppend = Y.append
for i in range(N):
  PAppend([int(x) for x in input().split()])
  XAppend(P[i][0])
  YAppend(P[i][1])

X.sort()
Y.sort()

S = [[0] * N for _ in range(N)]
for i in range(N):
  for j in range(N):
    for k in P:
      if k[0] <= X[i] and k[1] <= Y[j]:
        S[i][j] += 1

ans = float('inf')
for i in range(N - 1):
  for j in range(N - 1):
    for k in range(i + 1, N):
      for l in range(j + 1, N):
        PCount = S[k][l]
        if i > 0:
          PCount -= S[i - 1][l]
        if j > 0:
          PCount -= S[k][j - 1]
        if i > 0 and j > 0:
          PCount += S [i - 1][j - 1]
        if PCount >= K:
          ans = min(ans, (X[k] - X[i]) * (Y[l] - Y[j]))

print(ans)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
P,X,Y=[],[],[]
for _ in range(n):
    x,y=map(int,input().split())
    P.append((x,y))
    X.append(x)
    Y.append(y)
ans=10**19
X.sort()
Y.sort()
for d in range(n-1):
    for u in range(d,n):
        for l in range(n-1):
            for r in range(n):
                D,U,L,R=X[d],X[u],Y[l],Y[r]
                cnt=0
                for i in P:
                    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: Accepted

Solution code:
def main():
 
    N, K = map(int, input().split())
    p = []
    for _ in range(N):
        x, y = map(int, input().split())
        p.append([x, y])
    p.sort(key = lambda x: x[0])
 
    min_area = float('inf')
    for i in range(N-1):
        for j in range(i+1, N):
            if j-i+1 >= K:
                x1 = p[i][0]
                x2 = p[j][0]
                ys = []
                for k in range(i, j+1):
                    ys.append(p[k][1])
                ys.sort()
                for k in range(len(ys)):
                    for l in range(k+K-1, len(ys)):
                        y1 = ys[k]
                        y2 = ys[l]
                        area = (x2-x1)*(y2-y1)
                        if area > 0:
                            min_area = min(min_area, area)
    return min_area
 
if __name__ == '__main__':
    print(main())

Submission status: Accepted

Solution code:
def main():

    N, K = map(int, input().split())
    p = []
    for _ in range(N):
        x, y = map(int, input().split())
        p.append([x, y])
    p.sort(key = lambda x: x[0])

    min_area = float('inf')
    for i in range(N-1):
        for j in range(i+1, N):
            if j-i+1 >= K:
                x1 = p[i][0]
                x2 = p[j][0]
                ys = []
                for k in range(i, j+1):
                    ys.append(p[k][1])
                ys.sort()
                for k in range(len(ys)):
                    for l in range(k+K-1, len(ys)):
                        y1 = ys[k]
                        y2 = ys[l]
                        area = (x2-x1)*(y2-y1)
                        if area > 0:
                            min_area = min(min_area, area)
    return min_area

if __name__ == '__main__':
    print(main())

Submission status: Accepted

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 = list(itertools.combinations(range(n), 2))
    ans = inf
    for a, b in fullserch:
        minx = min(xy[a][0], xy[b][0])
        maxx = max(xy[a][0], xy[b][0])
        for c, d in fullserch:
            miny = min(xy[c][1], xy[d][1])
            maxy = max(xy[c][1], xy[d][1])
            x = 0
            
            for i in range(n):
                if minx <= xy[i][0] <= maxx and miny <= xy[i][1] <= maxy:
                    x += 1

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

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

Submission status: Accepted

Solution code:
n, k =  [ int(v) for v in input().split() ] 
node_list = [] 
x_list = []
y_list = []

for i in range(n):
    x, y = [ int(v) for v in input().split() ]
    node_list.append((x,y))
    x_list.append(x)
    y_list.append(y)
x_list.sort()
y_list.sort()


x_list = [ (x_list[i],x_list[j]) for i in range(n-k+1) for j in range(i+k-1,n) ]
y_list = [ (y_list[i],y_list[j]) for i in range(n-k+1) for j in range(i+k-1,n) ]

def check(in_x,in_y):
    xl, xr, yu, yd = in_x[0], in_x[1], in_y[0], in_y[1]
    ok = 0
    for i in node_list:
        if xl <= i[0] <= xr and yu <= i[1] <= yd:
            ok += 1

    if ok >= k:
        return (xr-xl) * (yd-yu)
    else:
        return 10**19

ans = 10**19
for i in x_list:
    for j in y_list:
        ans = min(ans, check(i,j))
print(ans)

Submission status: Accepted

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

ret = float('inf')
for i in range(N) :
    for j in range(i, N) :
        for k in range(j, N) :
            for l in range(k, N) :
                x, y = zip(xy[i], xy[j], xy[k], xy[l])
                mx, Mx = min(x), max(x)
                my, My = min(y), max(y)
                
                counter = 0
                for m in range(N) :
                    if mx <= xy[m][0] <= Mx and my <= xy[m][1] <= My :
                        counter += 1
                if counter >= K :
                    ret = min(ret, (Mx-mx)*(My-my))
print(ret)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
point=[tuple(map(int,input().split())) for i in range(N)]
point.sort(key=lambda x:x[0])
ans=float('inf')
for i in range(1+N-K):
    for j in range(i+K,N+1):
        x=point[j-1][0]-point[i][0]
        now=point[i:j]
        now.sort(key=lambda x:x[1])
        for k in range(j-i-K+1):
            ans=min(x*(now[k+K-1][1]-now[k][1]),ans)
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline

#n = int(input())
#n,a = [int(i) for i in readline().split()]
n,k = [int(i) for i in readline().split()]
xy = [[int(i) for i in readline().split()] for i in range(n)]

xy.sort()
#print(xy)
ans = 4*10**18+10
for i in range(n):
    for j in range(i+k-1,n):
        dx = xy[j][0] - xy[i][0]
        y = sorted(xy[k][1] for k in range(i,j+1))
#        print(y,i,j)
        L = len(y)-k+1
        for i in range(L):
            dy = y[i+k-1]-y[i]
            ans = min(ans,dy*dx)
        


print(ans)

Submission status: Accepted

Solution code:
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()
ix = {v: i for i, v in enumerate(X)}
iy = {v: i for i, v in enumerate(Y)}
m = [[0] * (len(X) + 1) for _ in range(len(Y) + 1)]
for x, y in XY:
    m[iy[y] + 1][ix[x] + 1] += 1
for y in range(len(Y) + 1):
    for x in range(len(X)):
        m[y][x + 1] += m[y][x]
for x in range(len(X) + 1):
    for y in range(len(Y)):
        m[y + 1][x] += m[y][x]
ans = float("inf")
for x0 in range(len(X) - 1):
    for x1 in range(x0 + 1, len(X)):
        for y0 in range(len(Y) - 1):
            for y1 in range(y0 + 1, len(Y)):
                n = m[y1 + 1][x1 + 1] - m[y0][x1 + 1] - \
                    m[y1 + 1][x0] + m[y0][x0]
                if n >= K:
                    s = (X[x1] - X[x0]) * (Y[y1] - Y[y0])
                    ans = min(ans, s)
print(ans)

Submission status: Accepted

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 = []
for _ in range(n):
    x,y = LI()
    xy.append((x,y))
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:
                    ans = min(ans,(rx - lx)*(uy - dy))
print(ans)

Submission status: Accepted

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

Solution code:
N,K = map(int,input().split())
p = sorted([list(map(int,input().split())) for _ in range(N)])
x, y = zip(*p)
inf = float('inf')
ans = inf

for i in range(N-K+1):
    for j in range(K+i-1, N):
        Ys = sorted(y[i:j+1])
        for k in range(len(Ys)-K+1):
            ans = min(ans, (x[j]-x[i])*(Ys[k+K-1]-Ys[k]))
print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left
import sys
input = sys.stdin.readline


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

    Xs = []
    Ys = []
    for x, y in XY:
        Xs.append(x)
        Ys.append(y)
    Xs.sort()
    Ys.sort()
    points = [[0 for _ in range(N)] for _ in range(N)]

    for x, y in XY:
        ix = bisect_left(Xs, x)
        iy = bisect_left(Ys, y)
        points[ix][iy] += 1

    sumpoints = [[0 for _ in range(N+1)] for _ in range(N+1)]

    for ix in range(1, N+1):
        s = 0
        for iy in range(1, N+1):
            if ix == 1:
                sumpoints[ix][iy] = points[ix-1][iy-1]
            if points[ix-1][iy-1] == 1:
                s = 1
            sumpoints[ix][iy] = sumpoints[ix-1][iy] + s

    ans = int(8E18)
    for lx in range(N-1):
        for rx in range(lx+1, N):
            for ly in range(N-1):
                for ry in range(ly+1, N):
                    if sumpoints[rx+1][ry+1] - sumpoints[rx+1][ly] - sumpoints[lx][ry+1] + sumpoints[lx][ly] >= K:
                        s = (Xs[rx]-Xs[lx])*(Ys[ry]-Ys[ly])
                        ans = min(ans, s)
    print(ans)

if __name__ == "__main__":
    main()