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:
def main():
    N, K = map(int, input().split())
    XY = [tuple(map(int, input().split())) for _ in range(N)]
    XY.sort()
    XY = tuple(XY)

    def count(x_min, x_max, y_min, y_max, i, j):
        OK = 0
        # NG = 0
        for m, n in XY[i:j + 1]:
            if y_min <= n <= y_max:
                OK += 1
        if OK >= K:
            return True
        return False

    ans = 10 ** 20
    for i, val_i in enumerate(XY[:N - 1]):
        a = val_i[0]
        for j in range(i + K - 1, N):
            b = XY[j][0]
            e = b - a
            # print (e, i, j)
            for k, c in XY:
                # c = k[1]
                for l, d in XY:
                    # d = l[1]
                    if c < d:
                        if  e * (d - c) < ans and count(a, b, c, d, i, j):
                            # print ('A')
                            ans = e * (d - c)
                            # ans = min(ans, e * (d - c))
    print (ans)
    return

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#PythonだとTLEする
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

def count(x_min, x_max, y_min, y_max):
    cnt = 0
    for i in range(N):
        if x_min <= X[i] <= x_max and y_min <= Y[i] <= y_max:
            cnt += 1
    return cnt

ans = 10 ** 20
for i in range(N):
    for j in range(N):
        for k in range(N):
            for l in range(N):
                # print ('i, j , k, l = ', i, j, k, l)
                if X[i] < X[j] and Y[k] < Y[l]:
                    if count(X[i], X[j], Y[k], Y[l]) >= K:
                        # print ('A')
                        ans = min(ans, (X[j] - X[i]) * (Y[l] - Y[k]))
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()
X, Y = zip(*XY)
r = 10**20
for x0 in range(N - K + 1):
  for x1 in range(K + x0 - 1, N):
    Ys = sorted(Y[x0:x1 + 1])
    for y0 in range(len(Ys) - K + 1):
      r = min(r, (X[x1] - X[x0]) * (Ys[y0 + K - 1] - Ys[y0]))
print(r)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
XY = [list(map(int, input().split())) for _ in range(N)]
XY.sort()
X, Y = zip(*XY)
r = float('inf')
for x0 in range(N - K + 1):
  for x1 in range(K + x0 - 1, N):
    x = X[x1] - X[x0]
    Y_s = sorted(Y[x0:x1 + 1])
    for y0 in range(len(Y_s) - K + 1):
      y = Y_s[y0 + K - 1] - Y_s[y0]
      r = min(r, x * y)
print(r)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
XY = [list(map(int, input().split())) for _ in range(N)]
XY.sort()
X, Y = zip(*XY)
r = 10**20
for x0 in range(N - K + 1):
  for x1 in range(K + x0 - 1, N):
    x = X[x1] - X[x0]
    Y_s = sorted(Y[x0:x1 + 1])
    for y0 in range(len(Y_s) - K + 1):
      y = Y_s[y0 + K - 1] - Y_s[y0]
      r = min(r, x * y)
print(r)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
XY = [list(map(int, input().split())) for _ in range(N)]
XY.sort()
r = 10**20
for xi0 in range(N - K + 1):
  for xi1 in range(K + xi0 - 1, N):
    x = XY[xi1][0] - XY[xi0][0]
    XY_ys = sorted(XY[xi0:xi1 + 1], key=lambda a: a[1])
    for yi0 in range(len(XY_ys) - K + 1):
      y = XY_ys[yi0 + K - 1][1] - XY_ys[yi0][1]
      r = min(r, x * y)
print(r)

Submission status: Accepted

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 lx, _ in XY:
    for rx, _ in XY:
        if lx > rx:
            continue
        for _, dy in XY:
            for _, uy in XY:
                if dy > uy:
                    continue
                count = 0
                for x,y in XY:
                    if lx <= x <= rx and dy <= y <= uy:
                        count += 1
                if count >= K:
                    ans = min(ans,(rx-lx)*(uy-dy))
print(ans)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
xy=[]
for i in range(n):
    tmp=[int(j) for j in input().split()]
    xy.append((tmp[0],tmp[1]))
from operator import itemgetter
xy.sort(key=itemgetter(1))
xy.sort(key=itemgetter(0))
xy=tuple(xy)
l=tuple(enumerate(xy))
ans=10**100
for i,(a,b) in l[:n-k+1]:
    for j,(c,d) in l[i+k-1:]:
        l1=sorted(y for x,y in xy[i:j+1])
        l2=l1[k-1:]
        for p,q in zip(l1,l2):
            if p<=b and q>=d:
                ans=min(ans,(c-a)*(q-p))
print(ans)

Submission status: Accepted

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

ans = float('inf')
for lx, _ in point :
    for rx, _ in point :
        if lx > rx :
            continue
        for _, ly in point :
            for _, ry in point :
                if ly > ry :
                    continue
                count = 0
                for x, y in point :
                    if lx <= x <= rx and ly <= y <= ry :
                        count += 1
                if count >= K :
                    ans = min(ans, (rx - lx) * (ry - ly))

print(ans)

Submission status: Accepted

Solution code:
import math
import copy
from operator import mul
from functools import reduce
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
# 一次元累積和
from itertools import accumulate
from bisect import bisect_left, bisect_right

import re
# import numpy as np
# from scipy.misc import comb

# 再帰がやばいとき
# import sys
# sys.setrecursionlimit(10**9)

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W

# 四方向: 右, 下, 左, 上
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
 
def i_inpl(): return int(input())
def l_inpl(): return list(map(int, input().split()))
def line_inpl(x): return [i_inpl() for _ in range(x)]

INF = int(1e50)
MOD = int(1e9)+7 # 10^9 + 7

# field[H][W]
def create_grid(H, W, value = 0):
    return [[ value for _ in range(W)] for _ in range(H)]

########

def main():
    N, K = l_inpl()
    xy = []
    for _ in range(N):
        xi, yi = l_inpl()
        xy.append([xi, yi])

    ans = INF * INF
    xy.sort()

    for l, (xl, yl) in list(enumerate(xy))[:N-K+1]:
        for r, (xr, yr) in list(enumerate(xy))[l+K-1:]:
            ys = sorted([ y for _, y in xy[l:r+1]]) 
            for yd, yu in zip(ys, ys[K-1:]):
                if yd <= yl and yd <= yr and yl <= yu and yr <= yu:
                # if yd <= yl and yr <= yu:
                    ans = min(ans, (xr-xl) * (yu - yd))
    
    print(ans)
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import math
import copy
from operator import mul
from functools import reduce
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
# 一次元累積和
from itertools import accumulate
from bisect import bisect_left, bisect_right

import re
# import numpy as np
# from scipy.misc import comb

# 再帰がやばいとき
# import sys
# sys.setrecursionlimit(10**9)

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W

# 四方向: 右, 下, 左, 上
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
 
def i_inpl(): return int(input())
def l_inpl(): return list(map(int, input().split()))
def line_inpl(x): return [i_inpl() for _ in range(x)]

INF = int(1e18)
MOD = int(1e9)+7 # 10^9 + 7

# field[H][W]
def create_grid(H, W, value = 0):
    return [[ value for _ in range(W)] for _ in range(H)]

########

def main():
    N, K = l_inpl()
    xy = []
    for _ in range(N):
        xi, yi = l_inpl()
        xy.append([xi, yi])

    ans = INF * INF
    xy.sort()

    for l, (xl, yl) in list(enumerate(xy))[:N-K+1]:
        for r, (xr, yr) in list(enumerate(xy))[l+K-1:]:
            ys = sorted([ y for _, y in xy[l:r+1]]) 
            for yd, yu in zip(ys, ys[K-1:]):
                # if yd <= yl and yd <= yr and yl <= yu and yr <= yu:
                if yd <= yl and yr <= yu:
                    ans = min(ans, (xr-xl) * (yu - yd))
    
    print(ans)
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from itertools import product
INF = float("inf")


def solve(N: int, K: int, x: "List[int]", y: "List[int]"):
    sx = sorted(x)
    sy = sorted(y)
    m = INF

    for (i, x1), (j, y1) in product(enumerate(sx[:-K+1]), enumerate(sy[:-K+1])):
        # 始点を固定
        for x2 in sx[i+1:]:
            for y2 in sy[j+1:]:
                # 終点を固定
                counter = sum([1 for xx, yy in zip(x, y)
                               if (x1 <= xx <= x2) and (y1 <= yy <= y2)])
                if counter >= K:
                    area = abs((y2-y1)*(x2-x1))
                    m = min(m, area)
                    break   # これ以上yをあげたところで面積は増える一方なので抜ける
    print(m)
    return


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

Solution code:
import sys

if __name__ == '__main__':
    N, K = map(int, input().split())
    xy_list = [list(map(int, input().split())) for i in range(N)]

    all_x = sorted(list(set([xy[0] for xy in xy_list])))
    all_y = sorted(list(set([xy[1] for xy in xy_list])))

    answer = sys.maxsize
    for i in range(len(all_x)):
        x1 = all_x[i]
        for j in range(i+1, len(all_x)):
            x2 = all_x[j]
            for k in range(len(all_y)):
                y1 = all_y[k]
                for l in range(k+1, len(all_y)):
                    y2 = all_y[l]
                    if K <= len([xy for xy in xy_list if (x1 <= xy[0] <= x2) and (y1 <= xy[1] <= y2)]) and answer > (x2-x1) * (y2-y1):
                        answer = (x2-x1) * (y2-y1)

    print(answer)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
xy=[list(map(int,input().split())) for _ in [0]*n]
xy=sorted(xy,key=lambda x:x[0])
temp=[]
for i in range(n):
    for j in range(i+k-1,n):
        temp.append([xy[j][0]-xy[i][0]]+sorted([y for x,y in xy[i:j+1]]))
m=10**19      
for t in temp:
    l=len(t)-1
    for i in range(1,l-k+2):
        m=min(m,t[0]*(t[i+k-1]-t[i]))
print(m)

Submission status: Accepted

Solution code:
def main():
    N,K = map(int,input().split())
    XY = [list(map(int,input().split())) for _ in [0]*N]
    iX = [0]*N
    iY = [0]*N
    for i,xy in enumerate(XY):
        x,y = xy
        iX[i] = x
        iY[i] = y
    iX.sort()
    iY.sort()
    X = {x:i for i,x in enumerate(iX)}
    Y = {y:i for i,y in enumerate(iY)}

    c = [[0]*(N+1) for i in [0]*(N+1)]
    for x,y in XY:
        c[Y[y]+1][X[x]+1] = 1

    for i in range(N):
        ci1 = c[i+1]
        for j in range(N):
            ci1[j+1] += ci1[j]
    for i in range(N):
        c[i+1] = [ci1j+cij for ci1j,cij in zip(c[i+1],c[i])]

    ans = 10**20
    for u in range(N):
        for d in range(u+K-1,N):
            l = 0
            r = K-1
            dY = iY[d]-iY[u]
            cd = c[d+1]
            cu = c[u]
            while r<N:
                if cd[r+1]+cu[l]-cu[r+1]-cd[l] >=K:
                    ans = min(ans, (iX[r] - iX[l])*dY)
                    l+=1
                else:r+=1

    print(ans)
main()

Submission status: Accepted

Solution code:
def main():
    N,K = map(int,input().split())
    XY = [list(map(int,input().split())) for _ in [0]*N]
    iX = [0]*N
    iY = [0]*N
    for i,xy in enumerate(XY):
        x,y = xy
        iX[i] = x
        iY[i] = y
    iX.sort()
    iY.sort()
    X = {x:i for i,x in enumerate(iX)}
    Y = {y:i for i,y in enumerate(iY)}

    c = [[0]*(N+1) for i in [0]*(N+1)]
    for x,y in XY:
        c[Y[y]+1][X[x]+1] = 1

    for i in range(N):
        ci1 = c[i+1]
        for j in range(N):
            ci1[j+1] += ci1[j]
    for i in range(N):
        ci1 = c[i+1]
        ci = c[i]
        for j,cij in enumerate(ci[1:],1):
            ci1[j] += cij

    ans = 10**20
    for u in range(N):
        for d in range(u+K-1,N):
            l = 0
            r = K-1
            dY = iY[d]-iY[u]
            cd = c[d+1]
            cu = c[u]
            while r<N:
                if cd[r+1]+cu[l]-cu[r+1]-cd[l] >=K:
                    ans = min(ans, (iX[r] - iX[l])*dY)
                    l+=1
                else:r+=1

    print(ans)
main()

Submission status: Accepted

Solution code:
def main():
    N,K = map(int,input().split())
    XY = [list(map(int,input().split())) for _ in [0]*N]
    iX = [0]*N
    iY = [0]*N
    for i,xy in enumerate(XY):
        x,y = xy
        iX[i] = x
        iY[i] = y
    iX.sort()
    iY.sort()
    X = {x:i for i,x in enumerate(iX)}
    Y = {y:i for i,y in enumerate(iY)}

    c = [[0]*(N+1) for i in [0]*(N+1)]
    for x,y in XY:
        c[Y[y]+1][X[x]+1] = 1

    for i in range(N):
        ci1 = c[i+1]
        for j in range(N):
            ci1[j+1] += ci1[j]
    for i in range(N):
        ci1 = c[i+1]
        ci = c[i]
        for j in range(N):
            ci1[j+1] += ci[j+1]

    ans = 10**20
    for u in range(N):
        for d in range(u+K-1,N):
            l = 0
            r = K-1
            dY = iY[d]-iY[u]
            cd = c[d+1]
            cu = c[u]
            while r<N:
                if cd[r+1]+cu[l]-cu[r+1]-cd[l] >=K:
                    ans = min(ans, (iX[r] - iX[l])*dY)
                    l+=1
                else:r+=1

    print(ans)
main()

Submission status: Accepted

Solution code:
def main():
    N,K = map(int,input().split())
    XY = [list(map(int,input().split())) for _ in [0]*N]
    XY.sort()
    iX = [0]*N
    iY = [0]*N
    for i,xy in enumerate(XY):
        x,y = xy
        iX[i] = x
        iY[i] = y
    iY.sort()
    X = {x:i for i,x in enumerate(iX)}
    Y = {y:i for i,y in enumerate(iY)}

    c = [[0]*(N+1) for i in [0]*(N+1)]
    for x,y in XY:
        c[Y[y]+1][X[x]+1] = 1

    for i in range(N):
        ci1 = c[i+1]
        for j in range(N):
            ci1[j+1] += ci1[j]
    for i in range(N):
        ci1 = c[i+1]
        ci = c[i]
        for j in range(N):
            ci1[j+1] += ci[j+1]

    ans = 10**20
    for u in range(N):
        for d in range(u+K-1,N):
            l = 0
            r = K-1
            dY = iY[d]-iY[u]
            cd = c[d+1]
            cu = c[u]
            while r<N:
                if cd[r+1]+cu[l]-cu[r+1]-cd[l] >=K:
                    ans = min(ans, (iX[r] - iX[l])*dY)
                    l+=1
                else:r+=1

    print(ans)
main()

Submission status: Accepted

Solution code:
def main():
    N,K = map(int,input().split())
    XY = [list(map(int,input().split())) for _ in [0]*N]
    XY.sort()
    
    iX = [x for x,y in XY]
    iY = [y for x,y in XY]
    iY.sort()
    X = {x:i for i,x in enumerate(iX)}
    Y = {y:i for i,y in enumerate(iY)}

    c = [[0]*(N+1) for i in [0]*(N+1)]
    for x,y in XY:
        c[Y[y]+1][X[x]+1] = 1

    for i in range(N):
        ci1 = c[i+1]
        for j in range(N):
            ci1[j+1] += ci1[j]
    for i in range(N):
        ci1 = c[i+1]
        ci = c[i]
        for j in range(N):
            ci1[j+1] += ci[j+1]

    ans = 10**20
    for u in range(N):
        for d in range(u+K-1,N):
            l = 0
            r = K-1
            dY = iY[d]-iY[u]
            cd = c[d+1]
            cu = c[u]
            while r<N:
                if cd[r+1]+cu[l]-cu[r+1]-cd[l] >=K:
                    ans = min(ans, (iX[r] - iX[l])*dY)
                    l+=1
                else:r+=1

    print(ans)
main()

Submission status: Accepted

Solution code:
def main():
    N,K = map(int,input().split())
    XY = [list(map(int,input().split())) for _ in [0]*N]
    
    iX = [x for x,y in XY]
    iY = [y for x,y in XY]
    iX.sort()
    iY.sort()
    X = {x:i for i,x in enumerate(iX)}
    Y = {y:i for i,y in enumerate(iY)}

    c = [[0]*(N+1) for i in [0]*(N+1)]
    for x,y in XY:
        c[Y[y]+1][X[x]+1] = 1

    for i in range(N):
        ci1 = c[i+1]
        for j in range(N):
            ci1[j+1] += ci1[j]
    for i in range(N):
        ci1 = c[i+1]
        ci = c[i]
        for j in range(N):
            ci1[j+1] += ci[j+1]

    ans = 10**20
    for u in range(N):
        for d in range(u+K-1,N):
            l = 0
            r = K-1
            dY = iY[d]-iY[u]
            cd = c[d+1]
            cu = c[u]
            while 1:
                if cd[r+1]+cu[l]-cu[r+1]-cd[l] >=K:
                    ans = min(ans, (iX[r] - iX[l])*dY)
                    l+=1
                else:
                    r+=1
                    if r==N:break

    print(ans)
main()

Submission status: Accepted

Solution code:
def main():
    N,K = map(int,input().split())
    XY = [list(map(int,input().split())) for _ in [0]*N]
    
    iX = [x for x,y in XY]
    iY = [y for x,y in XY]
    iX.sort()
    iY.sort()
    X = {x:i for i,x in enumerate(iX)}
    Y = {y:i for i,y in enumerate(iY)}

    c = [[0]*(N+1) for i in [0]*(N+1)]
    for x,y in XY:
        c[Y[y]+1][X[x]+1] = 1

    for i in range(N):
        ci1 = c[i+1]
        for j in range(N):
            ci1[j+1] += ci1[j]
    for i in range(N):
        ci1 = c[i+1]
        ci = c[i]
        for j in range(N):
            ci1[j+1] += ci[j+1]

    ans = 10**20
    for u in range(N):
        for d in range(u+K-1,N):
            l = 0
            r = K-1
            dY = iY[d]-iY[u]
            cd = c[d+1]
            cu = c[u]
            while r<N:
                if cd[r+1]+cu[l]-cu[r+1]-cd[l] >=K:
                    ans = min(ans, (iX[r] - iX[l])*dY)
                    l+=1
                else:r+=1

    print(ans)
main()

Submission status: Accepted

Solution code:
def main():
    N,K = map(int,input().split())
    XY = [list(map(int,input().split())) for _ in [0]*N]
    
    iX = sorted(x for x,y in XY)
    iY = sorted(y for x,y in XY)
    X = {x:i for i,x in enumerate(iX)}
    Y = {y:i for i,y in enumerate(iY)}

    c = [[0]*(N+1) for i in [0]*(N+1)]
    for x,y in XY:
        c[Y[y]+1][X[x]+1] = 1

    for i in range(N):
        ci1 = c[i+1]
        for j in range(N):
            ci1[j+1] += ci1[j]
    for i in range(N):
        ci1 = c[i+1]
        ci = c[i]
        for j in range(N):
            ci1[j+1] += ci[j+1]

    ans = 10**20
    for u in range(N):
        for d in range(u+K-1,N):
            l = 0
            r = K-1
            dY = iY[d]-iY[u]
            cd = c[d+1]
            cu = c[u]
            while r<N:
                if cd[r+1]+cu[l]-cu[r+1]-cd[l] >=K:
                    ans = min(ans, (iX[r] - iX[l])*dY)
                    l+=1
                else:r+=1

    print(ans)
main()

Submission status: Accepted

Solution code:
def main():
    N,K = map(int,input().split())
    XY = [list(map(int,input().split())) for _ in [0]*N]
    
    iX = sorted(x for x,y in XY)
    iY = sorted(y for x,y in XY)
    X = {x:i for i,x in enumerate(iX)}
    Y = {y:i for i,y in enumerate(iY)}

    c = [[0]*(N+1) for i in [0]*(N+1)]
    for x,y in XY:
        c[Y[y]+1][X[x]+1] = 1

    for i in range(N):
        ci1 = c[i+1]
        for j in range(N):
            ci1[j+1] += ci1[j]
    for i in range(N):
        ci1 = c[i+1]
        ci = c[i]
        for j in range(N):
            ci1[j+1] += ci[j+1]

    ans = 10**20
    for u in range(N):
        for d in range(u+K-1,N):
            l = 0
            r = 0
            dY = iY[d]-iY[u]
            cd = c[d+1]
            cu = c[u]
            while r<N:
                if cd[r+1]+cu[l]-cu[r+1]-cd[l] >=K:
                    ans = min(ans, (iX[r] - iX[l])*dY)
                    l+=1
                else:r+=1

    print(ans)
main()

Submission status: Accepted

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

iX = sorted(x for x,y in XY)
iY = sorted(y for x,y in XY)
X = {x:i for i,x in enumerate(iX)}
Y = {y:i for i,y in enumerate(iY)}

c = [[0]*(N+1) for i in [0]*(N+1)]
for x,y in XY:
    c[Y[y]+1][X[x]+1] = 1

for i in range(N):
    ci1 = c[i+1]
    for j in range(N):
        ci1[j+1] += ci1[j]
for i in range(N):
    ci1 = c[i+1]
    ci = c[i]
    for j in range(N):
        ci1[j+1] += ci[j+1]

ans = 10**20
for u in range(N):
    for d in range(u+K-1,N):
        l = 0
        r = 1
        dY = iY[d]-iY[u]
        cd = c[d+1]
        cu = c[u]
        while r<N:
            if cd[r+1]+cu[l]-cu[r+1]-cd[l] >=K:
                ans = min(ans, (iX[r] - iX[l])*dY)
                l+=1
            else:r+=1

print(ans)

Submission status: Accepted

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

iX = sorted(x for x,y in XY)
iY = sorted(y for x,y in XY)
X = {x:i for i,x in enumerate(iX)}
Y = {y:i for i,y in enumerate(iY)}

c = [[0]*(N+1) for i in [0]*(N+1)]
for x,y in XY:
    c[Y[y]+1][X[x]+1] = 1

for i in range(N):
    ci1 = c[i+1]
    for j in range(N):
        ci1[j+1] += ci1[j]
for i in range(N):
    ci1 = c[i+1]
    ci = c[i]
    for j in range(N):
        ci1[j+1] += ci[j+1]

ans = 10**20
for u in range(N):
    for d in range(u+1,N):
        l = 0
        r = 1
        dY = iY[d]-iY[u]
        cd = c[d+1]
        cu = c[u]
        while r<N:
            if cd[r+1]+cu[l]-cu[r+1]-cd[l] >=K:
                ans = min(ans, (iX[r] - iX[l])*dY)
                l+=1
            else:r+=1

print(ans)

Submission status: Accepted

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

iX = sorted(x for x,y in XY)
iY = sorted(y for x,y in XY)
X = {x:i for i,x in enumerate(iX)}
Y = {y:i for i,y in enumerate(iY)}

c = [[0]*(N+1) for i in [0]*(N+1)]
for x,y in XY:
    c[Y[y]+1][X[x]+1] = 1

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

ans = 10**20
for l in range(N):
    for r in range(l+1,N):
        u = 0
        d = 1
        dX = iX[r] - iX[l]
        while d<N:
            if c[d+1][r+1]+c[u][l]-c[u][r+1]-c[d+1][l] >=K:
                ans = min(ans, dX*(iY[d]-iY[u]))
                u+=1
            else:d+=1

print(ans)

Submission status: Accepted

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

iX = sorted(x for x,y in XY)
iY = sorted(y for x,y in XY)
X = {x:i for i,x in enumerate(iX)}
Y = {y:i for i,y in enumerate(iY)}

c = [[0]*(N+1) for i in [0]*(N+1)]
for x,y in XY:
    c[Y[y]+1][X[x]+1] = 1

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

ans = 10**20
for l in range(N):
    for r in range(l+1,N):
        u = 0
        d = 1
        while d<N:
            if c[d+1][r+1]+c[u][l]-c[u][r+1]-c[d+1][l] >=K:
                ans = min(ans,
                         (iX[r]-iX[l])*(iY[d]-iY[u]))
                u+=1
            else:d+=1

print(ans)

Submission status: Accepted

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

iX = sorted(x for x,y in XY)
iY = sorted(y for x,y in XY)
X = {x:i for i,x in enumerate(iX)}
Y = {y:i for i,y in enumerate(iY)}

c = [[0]*(N+1) for i in [0]*(N+1)]
for x,y in XY:
    c[Y[y]+1][X[x]+1] = 1

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

ans = 10**20
for l in range(N):
    for u in range(N):
        for r in range(l+1,N):
            for d in range(u+1,N):
                if c[d+1][r+1]+c[u][l]-c[u][r+1]-c[d+1][l] >=K:
                    ans = min(ans,
                             (iX[r]-iX[l])*(iY[d]-iY[u]))
                    break

print(ans)

Submission status: Accepted

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

iX = sorted(x for x,y in XY)
iY = sorted(y for x,y in XY)
X = {x:i for i,x in enumerate(iX)}
Y = {y:i for i,y in enumerate(iY)}

c = [[0]*(N+1) for i in [0]*(N+1)]
for x,y in XY:
    c[Y[y]+1][X[x]+1] = 1

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

ans = 10**20
for l in range(N):
    for r in range(l+1,N):
        for u in range(N):
            for d in range(u+1,N):
                if c[d+1][r+1]+c[u][l]-c[u][r+1]-c[d+1][l] >=K:
                    ans = min(ans,
                             (iX[r]-iX[l])*(iY[d]-iY[u]))

print(ans)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
point=[]
for i in range(n):
    x,y=map(int,input().split())
    point.append((x,y))
point.sort()
ans=10**20
for i in range(n):
    for j in range(i+1,n):
        y_list=[]
        for p in range(i,j+1):
            y_list.append(point[p][1])
        y_list.sort()
        yl=len(y_list)
        y_d=10**10
        if yl<k:
            continue
        else:
            for p in range(yl-k+1):
                y_d=min(y_d,y_list[p+k-1]-y_list[p])
        x_d=point[j][0]-point[i][0]
        temp=x_d*y_d
        ans=min(ans,temp)
print(ans)

Submission status: Accepted

Solution code:
import itertools

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

a = [i for i in range(n)]
c = list(itertools.combinations(a,2))
ans = float('inf')


for x in c:
    for y in c:
        d = 0
        x1 = max(z[x[0]][0],z[x[1]][0])
        x2 = min(z[x[0]][0],z[x[1]][0])
        y1 = max(z[y[0]][1],z[y[1]][1])
        y2 = min(z[y[0]][1],z[y[1]][1])
        for i in range(n):
            if x2 <= z[i][0] <= x1 and y2 <= z[i][1] <= y1:
                d += 1
        if d == k:
            ans = min(ans, (x1-x2)*(y1-y2))

print(ans)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
xy = [list(map(int, input().split())) for i in range(N)]
ans = 10**20
xy.sort()
for l in range(N-K+1):
    for r in range(l+K, N+1):
        y = sorted(xy[l:r], key = lambda v: v[1])
        for i in range(r-l-K+1):
            sq = (xy[r-1][0] - xy[l][0]) * (y[i+K-1][1] - y[i][1])
            ans = min(ans, sq)
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(key=lambda x:x[0])
ans=float('inf')
for i in range(n-k+1):
    for j in range(i+k-1,n):
        x=l[j][0]-l[i][0]
        tl=sorted(l[i:j+1],key=lambda x:x[1])
        y=float('inf')
        for a in range(j-i+2-k):
            y=min(y,tl[a+k-1][1]-tl[a][1])
        ans=min(ans,x*y)
print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations

N, K = map(int, input().split())
coord = sorted([tuple(map(int, input().split())) for _ in range(N)])
ans = float('inf')
for left, right in combinations(range(N), 2):
    n_points = right - left + 1
    if n_points < K: continue
    width = coord[right][0] - coord[left][0]
    y_coords = sorted([y for _, y in coord[left: right+1]])
    for i in range(n_points - K + 1):
        height = y_coords[i+K-1] - y_coords[i]
        ans = min(ans, width*height)
print(ans)

Submission status: Accepted

Solution code:
import itertools
N,K = map(int,input().split())
zahyou = []
for i in range(N):
  zahyou.append(list(map(int,input().split())))
ans = float('inf')
X = []
Y = []
for i in range(N):
  X.append(zahyou[i][0])
  Y.append(zahyou[i][1])
P = list(itertools.combinations(X,2))
Q = list(itertools.combinations(Y,2))
for i in range(len(P)):
  for j in range(len(Q)):
    x1 = min(P[i][0],P[i][1])
    x2 = max(P[i][0],P[i][1])
    y1 = min(Q[j][0],Q[j][1])
    y2 = max(Q[j][0],Q[j][1])
    cnt = 0
    for k in range(N):
      if x1 <= zahyou[k][0] <= x2 and y1 <= zahyou[k][1] <= y2:
        cnt += 1
    if cnt >= K:
      if ans >= (x2-x1)*(y2-y1):
        ans = (x2-x1)*(y2-y1)
print(ans)

Submission status: Accepted

Solution code:
n,c=map(int,input().split())
xpos=[]
ypos=[]
pos=[]
for _ in range(n):
  x,y=map(int,input().split())
  xpos.append(x)
  ypos.append(y)
  pos.append([x,y])
xpos=sorted(xpos)
ypos=sorted(ypos)
ans=10**20
for i in range(n):
  for j in range(i+1,n):
    for k in range(n):
      for l in range(k+1,n):
        lx,rx=xpos[i],xpos[j]
        ly,ry=ypos[k],ypos[l]
        cnt=0
        for tx,ty in pos:
          if lx<=tx<=rx and ly<=ty<=ry:
            cnt+=1
        if cnt>=c:
          ans=min(ans,(rx-lx)*(ry-ly))
print(ans)

Submission status: Accepted

Solution code:
import itertools

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

XY = [[int(x) for x in input().split()] for _ in range(N)]
XY.sort()
X,Y = zip(*XY)

min_area = 5*10**18

for left,right in itertools.combinations(range(N),2):
  width = X[right] - X[left]
  pts = sorted(XY[left:right+1], key = lambda xy: xy[1])
  for D in range(len(pts)):
    if D + K - 1 >= len(pts):
      break
    y_max = pts[D+K-1][1]
    y_min = pts[D][1]
    area = (y_max - y_min) * width
    if area < min_area:
      min_area = area
    
print(min_area)