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 collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

def main():
    n,k = inpl()
    xary = []; yary = []
    a = []
    x_append = xary.append
    y_append = yary.append
    a_append = a.append
    for i in range(n):
        x,y = inpl()
        xary += [x]
        yary += [y]
        a += [[x,y]]
    xary.sort(); yary.sort()
    res = INF
    for xi in range(n-1):
        for xj in range(xi+1,n):
            for yi in range(n-1):
                for yj in range(yi+1,n):
                    cnt = 0
                    l = xary[xi]; r = xary[xj]
                    d = yary[yi]; u = yary[yj]
                    # print(l,r,d,u)
                    for i in range(n):
                        x,y = a[i]
                        if l<=x<=r and d<=y<=u:
                            cnt += 1
                    if cnt >= k:
                        res = min(res, (r-l)*(u-d))
    print(res)
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

def main():
    n,k = inpl()
    xary = []; yary = []
    a = []
    x_append = xary.append
    y_append = yary.append
    a_append = a.append
    for i in range(n):
        x,y = inpl()
        x_append(x)
        y_append(y)
        a_append((x,y))
    xary.sort(); yary.sort()
    res = INF
    for xi in range(n-1):
        for xj in range(xi+1,n):
            for yi in range(n-1):
                for yj in range(yi+1,n):
                    cnt = 0
                    l = xary[xi]; r = xary[xj]
                    d = yary[yi]; u = yary[yj]
                    # print(l,r,d,u)
                    for i in range(n):
                        x,y = a[i]
                        if l<=x<=r and d<=y<=u:
                            cnt += 1
                    if cnt >= k:
                        res = min(res, (r-l)*(u-d))
    print(res)
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from itertools import combinations
N, K = map(int, input().split())
dots = sorted([tuple(map(int, input().split())) for _ in range(N)], key=lambda x: x[0])

ans = 10 ** 37
for i in range(N):
    for j in range(i+K-1, N):
        width = dots[j][0] - dots[i][0]
        y = sorted([l for _, l in dots[i:j+1]])
        for a, b in zip(y, y[K-1:]):
            height = b - a
            ans = min(ans, width*height)

print(ans)

Submission status: Accepted

Solution code:
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)
    X_s = sorted(X)
    Y_s = sorted(Y)
    f_inf = float("inf")
    res = f_inf

    for x1 in range(n):
        for x2 in range(x1 + 1, n):
            for y1 in range(n):
                for y2 in range(y1 + 1, n):
                    lx, rx = X_s[x1], X_s[x2]
                    by, uy = Y_s[y1], Y_s[y2]
                    cnt = 0
                    for i in range(n):
                        if lx <= X[i] <= rx and by <= Y[i] <= uy:
                            cnt += 1
                    if cnt >= k:
                        res = min(res, (rx - lx) * (uy - by))
    print(res)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
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)
    X_s = sorted(X)
    Y_s = sorted(Y)
    f_inf = float("inf")
    res = f_inf

    for x1 in range(n):
        for x2 in range(x1 + 1, n):
            for y1 in range(n):
                for y2 in range(y1 + 1, n):
                    lx, rx = X_s[x1], X_s[x2]
                    by, uy = Y_s[y1], Y_s[y2]
                    cnt = 0
                    for i in range(n):
                        if lx <= X[i] <= rx and by <= Y[i] <= uy:
                            cnt += 1
                    if cnt >= k:
                        res = min(res, abs(rx - lx) * abs(uy - by))
    print(res)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions
from decimal import Decimal
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n,K = inpl()
a = [inpl() for _ in range(n)]
res = INF
a.sort(key=lambda x:x[0])
for j in range(n-1):
    for k in range(j+1,n):
        l = a[j][0]
        r = a[k][0]
        b = [a[j],a[k]]
        cnt = 2
        for _ in range(n):
            if _ == j or _ == k:
                continue
            if l < a[_][0] < r:
                cnt += 1
                b += [a[_]]
        if cnt < K: continue
        b.sort(key=lambda x:x[1])
        for _ in range(cnt-K+1):
            u = max(x[1] for x in b[_:_+K])
            d = min(x[1] for x in b[_:_+K])
            res = min(res, (r-l)*(u-d))
            # print(res)
print(res)

Submission status: Accepted

Solution code:
from itertools import accumulate
def compress(arr):
    *XS, = set(arr)
    XS.sort()
    return {e: i for i, e in enumerate(XS)}
n, k = map(int, input().split())
XY = [list(map(int, input().split())) for _ in range(n)]
X, Y = zip(*XY)
comp_X = compress(X)
comp_Y = compress(Y)
len_X = len(comp_X)
len_Y = len(comp_Y)
rev_X = {j:i for i, j in comp_X.items()}
rev_Y = {j:i for i, j in comp_Y.items()}
C = [[0]*(len_Y+1) for _ in range(len_X+1)]
for x, y in XY:
  C[comp_X[x]+1][comp_Y[y]+1] = 1
for i in range(1, len_X+1):
  C[i] = list(accumulate(C[i]))
C = list(zip(*C))
for j in range(1, len_Y+1):
  C[j] = list(accumulate(C[j]))
C = list(zip(*C))
def test(x1, x2, y1, y2):
  cnt = C[x2][y2] - C[x1][y2] - C[x2][y1] + C[x1][y1]
  if cnt >= k:
    temp = (rev_X[x2-1] - rev_X[x1]) * (rev_Y[y2-1] - rev_Y[y1])
    return temp
  return float("inf")
ans = float("inf")
for x1 in range(len_X):
  for x2 in range(x1+1, len_X+1):
    for y1 in range(len_Y):
      for y2 in range(y1+1, len_Y+1):
        ans = min(ans, test(x1, x2, y1, y2))
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions
from decimal import Decimal
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n,K = inpl()
a = [inpl() for _ in range(n)]
res = INF
for i in range(1):
    a.sort(key=lambda x:x[i])
    for j in range(n-1):
        for k in range(j+1,n):
            l = a[j][i]
            r = a[k][i]
            b = [a[j],a[k]]
            cnt = 2
            for _ in range(n):
                if _ == j or _ == k:
                    continue
                if l < a[_][i] < r:
                    cnt += 1
                    b += [a[_]]
            if cnt < K: continue
            b.sort(key=lambda x:x[i^1])
            # print(j,k,b,i)
            for _ in range(cnt-K+1):
                u = max(x[i^1] for x in b[_:_+K])
                d = min(x[i^1] for x in b[_:_+K])
                res = min(res, (r-l)*(u-d))
                # print(res)
print(res)

Submission status: Accepted

Solution code:
from collections import deque
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    n,k=MI()
    xx=set()
    yy=set()
    xy=[]
    for _ in range(n):
        x,y=MI()
        xy.append((x,y))
        xx.add(x)
        yy.add(y)
    xy.sort()
    xx=list(sorted(xx))
    yy = list(sorted(yy))
    xn=len(xx)
    yn=len(yy)
    ans=10**20
    for t in range(yn):
        y2=yy[t]
        for b in range(t):
            y1=yy[b]
            r=-1
            s=0
            i=j=0
            for l,x1 in enumerate(xx):
                while i<n and xy[i][0]<x1:
                    if y1 <= xy[i][1] <= y2: s -= 1
                    i += 1
                while s<k and r+1<xn:
                    r+=1
                    x2=xx[r]
                    while j<n and xy[j][0]<=x2:
                        if y1<=xy[j][1]<=y2:s+=1
                        j+=1
                if s>=k:
                    cur=(x2-x1)*(y2-y1)
                    if cur<ans:ans=cur
    print(ans)

main()

Submission status: Accepted

Solution code:
def main():
    from itertools import combinations
    import bisect
    N, K = map(int, input().split())
    xy = [tuple(map(int, input().split())) for i in range(N)]
    xy.sort(key=lambda x: x[0])
    X = [x[0] for x in xy]

    ans = 40**18
    for a, b in combinations(range(N), 2):
        A, B = max(xy[a][0], xy[b][0]), min(xy[a][0], xy[b][0])
        r = bisect.bisect_right(X, A)
        l = bisect.bisect_left(X, B)
        for c, d in combinations(range(N), 2):
            tmp = 0
            C, D = max(xy[c][1], xy[d][1]), min(xy[c][1], xy[d][1])

            for i in range(l, r):
                if xy[i][1] <= C and xy[i][1] >= D:
                    tmp += 1
            #     print(xy[i][1], C, D)

            if tmp >= K and ans > (A-B) * (C - D):
                ans = (A-B) * (C - D)

    print(ans)
main()

Submission status: Accepted

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

n,k=map(int,input().split())
xy=[tuple(map(int,input().split())) for _ in range(n)]
X=sorted(set(xy[i][0] for i in range(n)))
Y=sorted(set(xy[i][1] for i in range(n)))


from itertools import combinations

ans=10**20
for x1,x2 in combinations(X,2):
    for y1,y2 in combinations(Y,2):
        c=0
        for x,y in xy:
            if x1<=x<=x2 and y1<=y<=y2:
                c+=1
        if c>=k:
            ans=min(ans,(x2-x1)*(y2-y1))
print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate, combinations

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())
cx_to_x = sorted(list(set(X)))
x_to_cx = {k : i for i, k in enumerate(cx_to_x)}
cy_to_y = sorted(list(set(Y)))
y_to_cy = {k : i for i, k in enumerate(cy_to_y)}
nx = len(cx_to_x)
ny = len(cy_to_y)
points = [[0] * nx for _ in range(ny)]
for x, y in zip(X, Y):
    points[y_to_cy[y]][x_to_cx[x]] += 1
cum = [[0] * (nx+1)] + [list(accumulate([0] + row)) for row in points]
for i in range(1, ny+1):
    for j in range(nx+1):
        cum[i][j] += cum[i-1][j]
ans = float('inf')
for x1, x2 in combinations(range(nx), 2):
    for y1, y2 in combinations(range(ny), 2):
        cnt = cum[y2+1][x2+1] - cum[y2+1][x1] - cum[y1][x2+1] + cum[y1][x1]
        if cnt >= K:
            area = (cx_to_x[x2] - cx_to_x[x1]) * (cy_to_y[y2] - cy_to_y[y1])
            ans = min(ans, area)
print(ans)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
XY=[[0]*2 for i in range(n)]
X=[0]*n
Y=[0]*n
Z=[i for i in range(1,n+1)]
for i in range(n):
  X[i],Y[i]=map(int,input().split())
  XY[i]=[X[i],Y[i]]
X.sort()
Y.sort()
XX=dict(zip(X,Z))
YY=dict(zip(Y,Z))
XXX=dict(zip(Z,X))
YYY=dict(zip(Z,Y))
A=[[0]*n for i in range(n)]
for i in range(n):
  A[XX[XY[i][0]]-1][YY[XY[i][1]]-1]+=1
C=[[0]*(n+1) for i in range(n+1)]
for i in range(1,n+1):
  for j in range(1,n+1):
    C[i][j]=C[i-1][j]+C[i][j-1]-C[i-1][j-1]+A[i-1][j-1]
ans=10**20
for i in range(1,n):
  for j in range(i+1,n+1):
    for s in range(1,n):
      for t in range(s+1,n+1):
        if C[j][t]-C[j][s-1]-C[i-1][t]+C[i-1][s-1]<k:
          continue
        a=(XXX[j]-XXX[i])*(YYY[t]-YYY[s])
        if a<ans:
          ans=a
print(ans)

Submission status: Accepted

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

v.sort()

ans=10**20
for i in range(0,N-1):
    for j in range(i+1,N):
        data=[]
        for k in range(i,j+1):
            x,y=v[k]
            data.append(y)
        data.sort()
        if K>len(data):
            continue
        else:
            for k in range(0,len(data)-K+1):
                w=v[j][0]-v[i][0]
                h=data[k+K-1]-data[k]
                test=w*h
                if ans>test:
                    ans=test

print(ans)

Submission status: Accepted

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

ans = float('inf')
for i in range(N - K + 1):
    for j in range(i + K - 1, N):
        x = P[j][0] - P[i][0]
        if x == 0:
            continue

        Q = P[i: j + 1]
        Q.sort(key=lambda q: q[1])
        y = Q[-1][1] - Q[0][1]
        for k in range(0, len(Q) - K + 1):
            for l in range(k + K - 1, len(Q)):
                ny = Q[l][1] - Q[k][1]
                if ny == 0:
                    continue
                y = min(y, ny)
        ans = min(ans, x * y)

print(ans)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc075/tasks/abc075_d
# 座標圧縮して二次元累積和に打ち込めば良さそう

# はじめての座圧...?

import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols
    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])
    return ret


class cumsum2d:  # 二次元累積和クラス pypyでも使えるよ
    def __init__(self, ls: list):
        '''
        2次元のリストを受け取る
        '''
        from itertools import product
        H = len(ls)
        W = len(ls[0])
        self.ls_accum = [[0] * (W + 1)]
        for l in ls:
            self.ls_accum.append([0] + l)

        # 縦に累積
        for i, j in product(range(1, H + 1), range(1, W + 1)):
            self.ls_accum[i][j] += self.ls_accum[i - 1][j]
        # 横に累積
        for i, j in product(range(1, H + 1), range(1, W + 1)):
            self.ls_accum[i][j] += self.ls_accum[i][j - 1]

    def total(self, i1, j1, i2, j2):
        '''
        点(i1,j1),(i1,j2),(i2,j1),(i2,j2)の4点が成す四角の中の合計を取り出す
        ただし i1<=i2, j1<=j2
        ただし、i軸に関しては[i1,i2),j軸に関しては[j1,j2)の半開区間である
        '''
        return self.ls_accum[i2][j2] - self.ls_accum[i1][j2] \
            - self.ls_accum[i2][j1] + self.ls_accum[i1][j1]


class ZaAtu:
    def __init__(self, ls):
        # 座標圧縮クラス(仮) #どうしたら使いやすくなるのか知らんけど
        self.i_to_orig = sorted(set(ls))
        self.orig_to_i = {}
        for i, zahyou in enumerate(self.i_to_orig):
            self.orig_to_i[zahyou] = i
        self.len = len(self.i_to_orig)

    def __len__(self):
        return len(self.i_to_orig)


from itertools import product

N, K = read_ints()
X_ori, Y_ori = read_col(N, 2)
X = ZaAtu(X_ori)
Y = ZaAtu(Y_ori)
table = [[0] * Y.len for _ in range(X.len)]  # 二次元累積和を作る
for x, y in zip(X_ori, Y_ori):
    i = X.orig_to_i[x]
    j = Y.orig_to_i[y]
    table[i][j] += 1

table = cumsum2d(table)
# 怒りの全探索
ans = (2 * 10**9)**2 + 114514
for i, j in product(range(X.len), range(Y.len)):  # 始点
    for ii, jj in product(range(i, X.len + 1), range(j, Y.len + 1)):  # 終点
        if table.total(i, j, ii, jj) >= K:
            S = (X.i_to_orig[ii - 1] - X.i_to_orig[i]) * \
                (Y.i_to_orig[jj - 1] - Y.i_to_orig[j])
            ans = min(ans, S)
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8

# 11:50-
# 50min: give up
# 15:15-15:58 done


def main():
    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())
    
    points = [[i, x[i], y[i]] for i in range(N)]
    points_ysort = sorted(points, key=lambda p: p[2], reverse=True)
    points_ysort_rev = list(reversed(points_ysort))
    points_xsort = sorted(points, key=lambda p: p[1], reverse=False)
    points_xsort_rev = list(reversed(points_xsort))
    
    min_area = 4 * (10**18)
    outsides_top = []
    
    t = 0
    while t <= N-K:
        # n_inside = N - t

        top_i, top_x, top_y = points_ysort[t]

        outsides_bottom = []
        b = 0
        while b < N:
            # n_inside -= b

            bottom_i, bottom_x, bottom_y = points_ysort_rev[b]

            if bottom_i == top_i:
                break

            # outsides_left = []
            n_outsides_left = 0
            l = 0
            while l < N:
                left_i, left_x, left_y = points_xsort[l]

                if left_x > top_x:
                    break

                if left_i in outsides_top or left_i in outsides_bottom:
                    l += 1
                    continue
                
                # outsides_right = []
                n_outsides_right = 0
                r = 0
                while r < N:
                    if N - t - b - n_outsides_left - n_outsides_right < K:
                        break

                    right_i, right_x, right_y = points_xsort_rev[r]

                    if right_i == left_i:
                        break
                    
                    if right_x < top_x:
                        break
                    
                    if right_i in outsides_top or right_i in outsides_bottom:
                        r += 1
                        continue

                    area = (top_y - bottom_y) * (right_x - left_x)
                    if area < min_area:
                        min_area = area
                    
                    # outsides_right.append(right_i)
                    n_outsides_right += 1
                    r += 1
                
                # outsides_left.append(left_i)
                n_outsides_left += 1
                l += 1
            
            outsides_bottom.append(bottom_i)
            b += 1
        
        outsides_top.append(top_i)
        t += 1

    return min_area


print(main())

Submission status: Accepted

Solution code:
n,K = map(int,input().split())
X, Y = [], []
dots = []
for _ in range(n):
    x,y = map(int,input().split())
    dots.append((x,y))
    X.append(x)
    Y.append(y)
X.sort()
Y.sort()
ans = float('inf')
for i in range(n):
    for j in range(i+1, n):
        for k in range(n):
            for l in range(k+1, n):
                x1,x2 = X[i], X[j]
                y1,y2 = Y[k], Y[l]
                cnt = 0
                for dot in dots:
                    if x1<=dot[0]<=x2 and y1<=dot[1]<=y2:
                        cnt += 1
                if cnt >= K:
                    ans = min(ans, (x2-x1)*(y2-y1))
print(ans)

Submission status: Accepted

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

xy.sort()
ans = 10**20

for i in range(n):
    for j in range(i,n):
        xy_tmp = xy[i:j+1]
        if len(xy_tmp) >= k:
            l1 = xy_tmp[0][0]
            r1 = xy_tmp[-1][0]
            xy_tmp.sort(key = lambda x: x[1])
            for jj in range(len(xy_tmp) - k + 1):
                ans = min(ans, (r1-l1) * (xy_tmp[k+jj-1][1] - xy_tmp[jj][1]))

print(ans)

Submission status: Accepted

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

    ans = 10 ** 20

    for i in range(n):
        for j in range(i+1, n):
            for ii in range(n):
                for jj in range(ii+1, n):
                    l = min(xy[i][0], xy[j][0])
                    r = max(xy[i][0], xy[j][0])
                    d = min(xy[ii][1], xy[jj][1])
                    u = max(xy[ii][1], xy[jj][1])
                    cnt = 0
                    for x,y in xy:
                        if l <= x <= r and d <= y <= u:
                            cnt += 1
                    if cnt >= k:
                        ans = min(ans, (r-l) * (u - d))

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
l = [list(map(int,input().split())) for i in range(n)]
l.sort()
l1 = sorted(l,key=lambda x:x[1])
ans = float("INF")

for i in l:
    for j in l:
        if i[0] >= j[0]:
            continue
        for s in l1:
            count = 0
            for w,h in l1:
                if i[0] <= w <= j[0] and s[1] <= h:
                    count += 1
                if count==k:
                    ans = (min(ans,(j[0]-i[0])*(h-s[1])))
                    break
                
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from itertools import combinations
import sys
try:
    from typing import List
except ImportError:
    pass


def solve(N: int, K: int, x: "List[int]", y: "List[int]"):
    pts = sorted(zip(x, y))
    ys = sorted(y)
    ans = float("inf")
    for y1, y2 in combinations(ys, 2):
        xs = [x for x, y in pts if y1 <= y <= y2]
        if len(xs) >= K:
            ans = min(
                ans,
                (y2 - y1) * min(x2 - x1 for x1, x2 in zip(xs, xs[K - 1:]))
            )
    print(ans)


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:
N,K = map(int,input().split())

P = []

for i in range(N):
    P.append(list(map(int,input().split())))

x = []
y = []
for i in range(N):
    x.append(P[i][0])
    y.append(P[i][1])

x.sort()
y.sort()

num = [[0]*len(y) for i in range(len(x))]
data = [[0]*len(y) for i in range(len(x))]

for i in range(N):
    for j in range(len(x)):
        if P[i][0] == x[j]:
            x0 = j
            break
    for j in range(len(y)):
        if P[i][1] == y[j]:
            y0 = j
            break
    data[x0][y0] += 1

num[0][0] = data[0][0]

for i in range(1,len(x)):
    num[i][0] = num[i-1][0] + data[i][0]

for i in range(1,len(y)):
    num[0][i] = num[0][i-1] + data[0][i]

for i in range(1,len(x)):
    for j in range(1,len(y)):
        num[i][j] = num[i-1][j] + num[i][j-1] - num[i-1][j-1] + data[i][j]

can = []
for i in range(1,len(x)-1):
    for j in range(i+1,len(x)):
        for k in range(1,len(y)-1):
            for l in range(k+1,len(y)):
                if num[j][l] - num[j][k-1] - num[i-1][l] + num[i-1][k-1] >= K:
                    can.append((x[j]-x[i])*(y[l]-y[k]))
for i in range(len(x)):
    for j in range(1,len(y)-1):
        for k in range(j+1,len(y)):
            if num[i][k] - num[i][j-1] >= K:
                can.append((x[i]-x[0])*(y[k]-y[j]))

for i in range(1,len(x)-1):
    for j in range(i+1,len(x)):
        for k in range(len(y)):
            if num[j][k] - num[i-1][k] >= K:
                can.append((x[j]-x[i])*(y[k]-y[0]))

for i in range(len(x)):
    for j in range(len(y)):
        if num[i][j] >= K:
            can.append((x[i]-x[0])*(y[j]-y[0]))


#print("x",x)
#print("y",y)
#print("data",data)
#print("num",num)
#print("can",can)
print(min(can))

Submission status: Accepted

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

xy.sort()

ans = float("inf")
for i in range(n):
    for j in range(i + k - 1, n):
        width = xy[j][0] - xy[i][0]
        y = [e for _, e in xy[i:j+1]]
        y.sort()
        for e1, e2 in zip(y, y[k-1:]):
            height = e2 - e1
            area = width * height
            ans = min(ans, area)

print(ans)

Submission status: Accepted

Solution code:
N, K= map(int, input().split())
li = [list(map(int, input().split())) for i in range(N)]
xx = [p[0] for p in li]
yy = [p[1] for p in li]
xx.sort()
yy.sort()
Min = (xx[N-1]-xx[0])*(yy[N-1]-yy[0])
for xi in range(N-1):
    for xj in range(xi+1, N):
        for yi in range(N-1):
            for yj in range(yi+1, N):
                cnt = 0
                for p in li:
                    [x, y] = p
                    if xx[xi] <= x <= xx[xj] and yy[yi] <= y <= yy[yj]:
                        cnt += 1
                if cnt >= K:
                    Min = min(Min, (xx[xj]-xx[xi])*(yy[yj]-yy[yi]))
print(Min)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
INF = 10**20
MOD = 10**9 + 7
from bisect import insort_left

def main():
    n,k = map(int,input().split())
    XY = [tuple(map(int,input().split())) for _ in range(n)]  
    XY.sort(key = lambda x:x[0])
    
    ans = INF
    for l in range(n - k + 1):
        Y = [XY[i][1] for i in range(l,l + k - 1)]
        Y.sort()
        dif = -1
        for r in range(l + k - 1, n):
            dif += 1
            insort_left(Y,XY[r][1])
            w = INF
            for i in range(dif + 1):
                w = min(w, Y[i + k - 1] - Y[i])
            ans = min(ans, w * (XY[r][0] - XY[l][0]))
    
    print(ans)   

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
N,K=map(int,input().split())
s=[tuple(map(int,input().split())) for i in range(N)]
lx,ly=[],[]
for i in s:
    lx.append(i[0])
    ly.append(i[1])
lx.sort()
ly.sort()
a=10**20
t=N-K
for i in range(N-1):
    for j in range(i+1,N):
        for k in range(N-1):
            for m in range(k+1,N):
                S=(lx[j]-lx[i])*(ly[m]-ly[k])
                if S>=a:
                    continue
                c=0
                for n in s:
                    if lx[i]<=n[0]<=lx[j] and ly[k]<=n[1]<=ly[m]:
                        continue
                    c+=1
                    if c>t:
                        break
                else:
                    a=S
print(a)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
points=[]
for _ in range(n):
    x,y=map(int,input().split())
    points.append((x,y))
points.sort()
ans=float('inf')
for i in range(n-k+1):
    for j in range(i+k-1,n):
        y_sorted=sorted(points[i:j+1],key=lambda x:x[1])
        height_min=float('inf')
        for l in range(j-i-k+2):
            height_min=min(height_min,y_sorted[l+k-1][1]-y_sorted[l][1])
            ans=min(ans,(points[j][0]-points[i][0])*height_min)
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
N,K=map(int,input().split())

point=[]
for _ in range(N):
    point.append(list(map(int,input().split())))

point.sort(key=lambda x: x[0])

shin=10**200
able=N-K
for i in range(able+1):
    temp_high=point[:N-i]
    for j in range(able+1-i):
        temp_low=temp_high[j:]
        for k in range(able+1-i-j):
            temp_left=temp_low[:]
            temp_left.sort(key=lambda x: x[1])
            temp_left=temp_left[k:len(temp_left)-(able+1-i-j)+k+1]
            #print(i,j,k)
            #print(temp_left)
            if temp_left:
                ans=temp_left[:]
            elif temp_low:
                ans=temp_low[:]
            else:
                ans=temp_high[:]
            x=[]
            y=[]
            for item in ans:
                x.append(item[0])
                y.append(item[1])
            #print(x)
            #print(y)
            num=((max(x)-min(x))*(max(y)-min(y)))
            shin=min(shin,num)

print(shin)

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 = 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:
from itertools import combinations

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

ans = 10**18*5

for x in combinations(range(N), 2):
    u = max(P[x[0]][0], P[x[1]][0])
    d = min(P[x[0]][0], P[x[1]][0])
    for y in combinations(range(N), 2):
        r = max(P[y[0]][1], P[y[1]][1])
        l = min(P[y[0]][1], P[y[1]][1])
        count = 0
        for i in range(N):
            if d <= P[i][0] <= u and l <= P[i][1] <= r:
                count += 1
        if count >= K:
            ans = min(ans, (u - d) * (r - l))

print(ans)

Submission status: Accepted

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

points.sort()
ans = float('inf')

for i in range(n-k+1):
  for j in range(i+k-1,n):
    y_sorted = sorted(points[i:j+1], key = lambda x:x[1])
    height_min = float('inf')
    for l in range(j-i-k+2):
      height_min = min(height_min,y_sorted[l+k-1][1] - y_sorted[l][1])
    ans = min(ans, (points[j][0]-points[i][0])*height_min)
print(ans)