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 defaultdict

def main():
    num, in_num = map(int, input().split())
    data = [list(map(int, input().split())) for i in range(num)]
    x_jiku, y_jiku = set(), set()

    for x, y in data:
        x_jiku.add(x)
        y_jiku.add(y)

    x_jiku = list(x_jiku)
    y_jiku = list(y_jiku)
    x_jiku.sort()
    y_jiku.sort()

    ans = 10 ** 20
    for x_kagen in x_jiku:
        for x_jogen in x_jiku[::-1]:
            if x_kagen >= x_jogen:
                break
            for y_kagen in y_jiku:
                for y_jogen in y_jiku[::-1]:
                    if y_kagen >= y_jogen:
                        break

                    if checl(x_kagen, x_jogen, y_kagen, y_jogen, data, in_num, num):
                        kari = (x_jogen - x_kagen) * (y_jogen - y_kagen)
                        if kari < ans:
                            ans = kari

    print(ans)

def checl(x_kagen, x_jogen, y_kagen, y_jogen, data, in_num, num):
    count = 0
    for i in range(num):
        if x_kagen <= data[i][0] <= x_jogen and y_kagen <= data[i][1] <= y_jogen:
            count += 1
    if count >= in_num:
        return 1
    else:
        return 0




if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

N,K=map(int, sys.stdin.readline().split())
X=[]
Y=[]
XY=[]

for _ in range(N):
	x,y=map(int, sys.stdin.readline().split())
	X.append(x)
	Y.append(y)
	XY.append( (x,y) )

ans=float("inf")
for x1 in X:
	for y1 in Y:
		for x2 in X:
			for y2 in Y:
				if x1<x2 and y1<y2:
					cnt=0
					for x, y in XY:
						if x1<=x<=x2 and y1<=y<=y2:
							cnt+=1
	
					menseki=abs(x1-x2)*abs(y1-y2)
					if K<=cnt:
						ans=min(ans, menseki)
			
print ans

Submission status: Accepted

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

xy.sort()
ans = 10**20
for l in range(N - K + 1):
  for r in range(l + K - 1, N):
    tb = xy[l: r + 1]
    tb.sort(key = lambda x: x[1])
    for b in range(len(tb) - K + 1):
      t = b + K - 1
      ans = min(ans, (xy[r][0] - xy[l][0]) * (tb[t][1] - tb[b][1]))

print(ans)

Submission status: Accepted

Solution code:
import bisect
def count_generate(h,w,a):
    count = [[0]*w for j in range(h)]
    count[0][0] = a[0][0]
    for i in range(1,w):
        count[0][i] = count[0][i-1]+a[0][i]
    for i in range(1,h):
        cnt_w = 0
        for j in range(w):
            cnt_w += a[i][j]
            count[i][j] = count[i-1][j]+cnt_w
    return count

def da_calc(p,q,x,y, da):
    if p > x or q > y:
        return 0
    if p == 0 and q == 0:
        return da[x][y]
    if p == 0:
        return da[x][y]-da[x][q-1]
    if q == 0:
        return da[x][y]-da[p-1][y]
    return da[x][y]-da[p-1][y]-da[x][q-1]+da[p-1][q-1]

N, K = map(int, input().split())
a = []
b = []
for i in range(N):
    ai, bi = map(int, input().split())
    a.append(ai)
    b.append(bi)
    
a_sorted = sorted(set(a))
b_sorted = sorted(set(b))
h = len(a_sorted)
w = len(b_sorted)

Map = [[0]*w for _ in range(h)]

for i in range(N):
    ai = bisect.bisect_left(a_sorted, a[i])
    bi = bisect.bisect_left(b_sorted, b[i])
    Map[ai][bi]+=1

count = count_generate(h, w, Map)
ans = float('inf')
for i in range(h):
    for j in range(i+1, h):
        for k in range(w):
            for l in range(k+1, w):
                #print(i, j, k, l, da_calc(i, k, j, l, count))
                if da_calc(i, k, j, l, count)>=K:
                    #print(i, j, k, l)
                    ans = min(ans, (a_sorted[j]-a_sorted[i])
                              *(b_sorted[l]-b_sorted[k]))
print(ans)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
x_y = [list(map(int,input().split())) for _ in range(n)]
x_y = sorted(x_y,key=lambda x:(x[0],x[1]))
ans = float('inf')
for i in range(n-1):
    for j in range(i+1,n):
        if j-i+1<k:
            continue
        dis_x = x_y[j][0]-x_y[i][0]
        y_x = x_y[i:j+1]
        y_x = sorted(y_x,key=lambda x:x[1])
        for l in range(len(y_x)-1):
            for m in range(l+1,len(y_x)):
                if m-l+1<k:
                    continue
                dis_y = y_x[m][1]-y_x[l][1]
                ans = min(ans,dis_x*dis_y)
print(ans)

Submission status: Accepted

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

X = []
Y = []
Z = []
for i in range(N):
    x,y = list(map(int,input().split()))
    X.append(x)
    Y.append(y)
    Z.append([x,y])

X.sort()
Y.sort()

min_rec=10**27

for i in range(N-1):
    for j in range(i+1,N):
        for k in range(N-1):
            for l in range(k+1,N):
                count=0
                for n in range(N):
                    if Z[n][0]>=X[i] and Z[n][0]<=X[j] and Z[n][1]>=Y[k] and Z[n][1]<=Y[l]:
                        count+=1
                if count==K:
                    min_rec = min(min_rec,(X[j]-X[i])*(Y[l]-Y[k]))

print(min_rec)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
l=[list(map(int,input().split())) for i in range(n)]
x=[l[i][0] for i in range(n)]
x.sort()
y=[l[i][1] for i in range(n)]
y.sort()
ans=[]
for i1 in range(n):
  for i2 in range(i1+1,n):
    for i3 in range(n):
      for i4 in range(i3+1,n):
        ct=0
        for i5 in range(n):
          if x[i1]<=l[i5][0]<=x[i2] and y[i3]<=l[i5][1]<=y[i4]:ct+=1
        if ct>=k:
          ans.append(abs(x[i1]-x[i2])*abs(y[i3]-y[i4]))
print(min(ans))

Submission status: Accepted

Solution code:
import heapq
n,k=map(int,input().split())
l=[list(map(int,input().split())) for i in range(n)]
x=[l[i][0] for i in range(n)]
x.sort()
y=[l[i][1] for i in range(n)]
y.sort()
ans=[]
for i1 in range(n):
  for i2 in range(i1+1,n):
    for i3 in range(n):
      for i4 in range(i3+1,n):
        ct=0
        for i5 in range(n):
          if x[i1]<=l[i5][0]<=x[i2] and y[i3]<=l[i5][1]<=y[i4]:ct+=1
        if ct>=k:
          ans.append(abs(x[i1]-x[i2])*abs(y[i3]-y[i4]))
heapq.heapify(ans)
print(heapq.heappop(ans))

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
xy=[]
X=[]
Y=[]
for i in range(N):
    x,y=map(int,input().split())
    xy.append([x,y])
xy.sort()
X=[i[0] for i in xy]
Y=[i[1] for i in xy]
ans=10**30
for i in range(K,N+1):
    for j in range(N+1-i):
        X_=X[j:j+i]
        Y_=Y[j:j+i]
        Y_.sort()
        a=max(X_)-min(X_)
        for k in range(i-K+1):
            z=Y_[k:k+K]
            b=max(z)-min(z)
            ans=min(ans,a*b)
print(ans)

Submission status: Accepted

Solution code:
import itertools
import sys

import numpy as np

sys.setrecursionlimit(10000)
INF = float('inf')

N, K = list(map(int, next(sys.stdin).split()))
XY = np.array([list(map(int, next(sys.stdin).split())) for _ in range(N)])

X = XY[:, 0]
Y = XY[:, 1]
X = X[Y.argsort()]
Y = Y[Y.argsort()]

ans = INF
for xi, xj in itertools.combinations(range(N), r=2):
    L, r = min(X[xi], X[xj]), max(X[xi], X[xj])
    xconds = (L <= X) & (X <= r)

    yi = 0
    yj = 1
    while yj < N:
        if np.sum(xconds[yi:yj + 1]) >= K:
            b, u = min(Y[yi], Y[yj]), max(Y[yi], Y[yj])
            ans = min(ans, (r - L) * (u - b))
            yi += 1
        else:
            yj += 1
        if yi == yj:
            yj += 1
print(ans)

Submission status: Accepted

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

XY = []
for _ in range(N):
    x, y = map(int, input().split())
    XY.append((x, y))
    
dots = XY[:]

import sys
INT_MAX = sys.maxsize

ans = INT_MAX

import itertools
for ((left_x, _), (right_x, _)) in itertools.combinations(dots, 2):
    if left_x > right_x:
        left_x, right_x = right_x, left_x
    for ((_, under_y), (_, top_y)) in itertools.combinations(dots, 2):
        if under_y > top_y:
            under_y, top_y = top_y, under_y
        counter = 0
        for d_x, d_y in dots:
            if  (left_x <= d_x) and (d_x <= right_x) and (under_y <= d_y) and (d_y <= top_y):
                counter += 1
                
        if counter >= K:
            area = (top_y-under_y) * (right_x-left_x)
            if ans > area:
                ans = area
            
print(ans)

Submission status: Accepted

Solution code:
N,K=map(int, input().split())
X,Y=map(list,zip(*[list(map(int,input().split())) for i in range(N)]))
x=sorted(X)
y=sorted(Y)
c=[[0]*(N+1) for i in range(N+1)]
for i in range(N):
    c[x.index(X[i])+1][y.index(Y[i])+1]=1
for i in range(N):
    for j in range(N):
        c[i+1][j+1]+=c[i][j+1]+c[i+1][j]-c[i][j]
ans=5*10**18
for t in range(1,N):
    for b in range(t+1,N+1):
        for l in range(1,N):
            for r in range(l+1,N+1):
                count=c[b][r]-c[b][l-1]-c[t-1][r]+c[t-1][l-1]
                if count>=K:
                    ans=min(ans,(y[r-1]-y[l-1])*(x[b-1]-x[t-1]))
                    break
print(ans)

Submission status: Accepted

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

N,K=[int(val) for val in input().split()]

list_x=list()
list_y=list()
list_z=list()

ans=float('inf')

for i in range(N):
  x,y=(int(val) for val in input().split())
  list_x.append(x)
  list_y.append(y)
  list_z.append((x,y))
#  heapq.heappush(list_x, x)
#  heapq.heappush(list_y, y)
list_x.sort()
list_y.sort()

for i in list_y:
  for j in list_y:
    if i<=j:
      break
    else:
      for k in list_x:
        for l in list_x:
          if k<=l:
            break
          else:
            cnt=0
            for m in range(len(list_z)):
              if l<=list_z[m][0]<=k and j<=list_z[m][1]<=i:
                cnt+=1
              if K <= cnt:
                tmp=(i-j)*(k-l)
                if tmp < ans:
                  ans=tmp
                break

print(ans)

Submission status: Accepted

Solution code:
N,K = [ int(it) for it in input().split() ]
li = [ [ int(it) for it in input().split() ]  for i in range(N) ]

lix = [0]*N
liy = [0]*N
for i in range(N):
  x,y = li[i]
  lix[i] = [x,i,0]
  liy[i] = [y,i,0]
lix.sort( key = lambda x:x[0] )
liy.sort( key = lambda x:x[0] )
for i in range(N):
  lix[i][2]=i
  liy[i][2]=i
lix.sort( key = lambda x:x[1] )
liy.sort( key = lambda x:x[1] )

lim = [ [0]*(N+1) for i in range(N+1) ]
for i in range(N):
  lim[ 1+lix[i][2] ][ 1+liy[i][2] ] = 1
for i in range(1,N+1):
  for j in range(1,N+1):
    lim[i][j]+=lim[i-1][j]+lim[i][j-1]-lim[i-1][j-1]

lix.sort( key = lambda x:x[2] )
liy.sort( key = lambda x:x[2] )

ma = 1000000000000000000000000000000000000000
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 ( lim[xj][yj] - lim[xj][yi] - lim[xi][yj] + lim[xi][yi]  >= K ):
          s = (lix[xj-1][0]-lix[xi][0])*(liy[yj-1][0]-liy[yi][0])
          ma = min(s,ma)
print ( ma )

Submission status: Accepted

Solution code:
from itertools import*
from math import*
from collections import deque
from collections import defaultdict
from itertools import permutations
from heapq import*
from collections import Counter
from itertools import*
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf = 10**18
mod = 10**9+7
from functools import reduce
import sys
sys.setrecursionlimit(10**7)

n,k = map(int,input().split())
f = lambda x,y :(min(x,y),max(x,y))
xy = [tuple(map(int,input().split())) for _ in range(n)]
S = float("inf")
for (a,b) in combinations(range(n),2):
    for(c,d) in combinations(range(n),2):
        lx,rx = f(xy[a][0],xy[b][0])
        dy,uy = f(xy[c][1],xy[d][1])
        cnt = 0
        for i in xy:
            if lx<=i[0]<=rx and dy<=i[1]<=uy:
                cnt += 1
        if cnt >= k:
            S = min(S,(rx-lx)*(uy-dy))
print(S)

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:
from functools import reduce
import math

def main():
    # 文字列の2進数を数値にする
    # '101' → '5'
    # 文字列の頭に'0b'をつけてint()にわたす
    # binary = int('0b'+'101',0)

    # 2進数で立っているbitを数える
    # 101(0x5) → 2
    # cnt_bit = bin(5).count('1')
    
    # N! を求める
    # f = math.factorial(N)

    # N の逆元
    # N_inv = pow(N,MOD-2,MOD)

    # nCr
    # Nの階乗 * rの階乗の逆元 * n-rの階乗の逆元
    
    # 切り捨て
    # 4 // 3
    # 切り上げ
    #-(-4 // 3)
    
    # 初期値用:十分大きい数(100億)
    INF = float("inf")

    # 大きな素数
    MOD = 10**9+7
    
    # 1文字のみを読み込み
    # 入力:2
    # a = input().rstrip()
    # 変数:a='2'
    
    # スペース区切りで標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a, b, c, d = (int(_) for _ in input().split())  
    # 変数:a=2 b=4 c=5 d =7
    
    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a = list(int(_) for _ in input().split())
    # 変数:a = [2, 4, 5, 7]    

    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2457
    # a = list(int(_) for _ in input())
    # 変数:a = [2, 4, 5, 7]    
    N, K = (int(_) for _ in input().split())
    p = []
    for i in range(N):
        x,y = (int(_) for _ in input().split())
        p.append((x,y))
        
    ans = INF
    for i in range(N):
        for j in range(i+1,N):
            for h in range(N):
                for g in range(h+1,N):
                    x_start = min(p[i][0],p[j][0])
                    y_start = min(p[h][1],p[g][1])
                    x_end = max(p[i][0],p[j][0])
                    y_end = max(p[h][1],p[g][1])
                    area = (x_end - x_start) * (y_end - y_start)
                    cnt = 0
                    for k in range(N):
                        if p[k][0] >= x_start and p[k][1] >= y_start and p[k][0] <= x_end and p[k][1] <= y_end:
                            cnt += 1
                            if cnt == K:
                                ans = min(ans,area)
                                break
    print(ans)
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
import copy

n,k = getList()
buff = []
for i in range(n):
    buff.append(getList())

def calc(width, cutbuf, k):
    nn= len(cutbuf)
    cutbuf.sort(key=lambda x: x[1])
    ret = 10**19
    for ii in range(nn-k+1):
        tmptmp = abs(cutbuf[ii][1] - cutbuf[ii+k-1][1])
        #print("here")
        if ret > tmptmp:
            #print("here")
            ret = tmptmp
    #print(ret, cutbuf)
    return ret*width
buff.sort()
ans = 10**19
for i in range(n):
    for j in range(i+1, n):
        width = abs(buff[i][0] - buff[j][0])
        tmp = calc(width, buff[i:j+1], k)

        if ans > tmp:
            ans = tmp

print(ans)

Submission status: Accepted

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

xs=[x for x,_ in p]
ys=[y for _,y in p]
q=[(x,y) for x in xs for y in ys]

up=[set() for _ in range(len(q))]
dn=[set() for _ in range(len(q))]

for i in range(len(q)):
	xi,yi=q[i]
	for j in range(len(p)):
		xj,yj=p[j]
		if xj >= xi and yj >= yi:
			up[i].add(j)
		if xj <= xi and yj <= yi:
			dn[i].add(j)

ans=10**999

for i in range(len(q)):
	for j in range(len(q)):
		if len(up[i] & dn[j]) >= K:
			xi,yi=q[i]
			xj,yj=q[j]
			ans=min(ans, abs(xj-xi)*abs(yj-yi))

print(ans)

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
xy = sorted([list(map(int,input().split())) for _ in range(N)],key = lambda x:(x[0],x[1]))

ans = 10**20

for i in range(K,N+1):
    for j in range(0,N-i+1):
        xy2 = sorted(xy[j:j+i],key = lambda x:(x[1]))
        for k in range(0,i-K+1):
            xy3 = xy2[k:k+K]
            Y_wid = xy3[-1][1] - xy3[0][1]
            x3 = [tmp for tmp,_ in xy3]
            X_wid = max(x3) - min(x3)
            ans = min(ans,X_wid*Y_wid)
print(ans)

Submission status: Accepted

Solution code:
import sys, os

f = lambda:list(map(int,input().split()))
if 'local' in os.environ :
    sys.stdin = open('./input.txt', 'r')

def solve():
    n, k1 = f()

    pts = []
    sety = set()
    setx = set()
    for i in range(n):
        x, y = f()
        pts.append((x,y))
        setx.add(x)
        sety.add(y)
    
    minarea = int(1e19)

    xlist = list(setx)
    ylist = list(sety)
    xl = len(xlist)
    yl = len(ylist)

    ylist = sorted(ylist)
    xlist = sorted(xlist)

    xindx = dict(zip(xlist, range(xl)))

    for i in range(yl):
        for j in range(i+1, yl):
            cnt = [0] * xl
            for l in range(n):
                if pts[l][1] >= ylist[i] and pts[l][1]<=ylist[j]:
                    cnt[xindx[pts[l][0]]] += 1


            head = 0
            end = 0
            total = 0
            while end<xl:
                total += cnt[end]

                while total >= k1:
                    minarea = min(minarea, (ylist[j] - ylist[i]) * (xlist[end] - xlist[head]))
                    total -= cnt[head]
                    head += 1

                end += 1
    
    print(minarea)
                    








solve()

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
p = [list(map(int, input().split())) for i in range(N)]
t, b, l, r = 0, 0, 0, 0
area = []


for i in range(N):
  t = p[i][1]
  p1 = [a for a in p if a[1] <= t]
#  print(t, p1)
  for j in range(len(p1)):
    b = p1[j][1]
    p2 = [a for a in p1 if a[1] >= b]
#    print(b, p2)
    for k in range(len(p2)):
      r = p2[k][0]
      p3 = [a for a in p2 if a[0] <= r]
#      print(r, p3)
      for m in range(len(p3)):
        l = p3[m][0]
        p4 = [a for a in p3 if a[0] >= l]
#        print(l, p4)   
        if len(p4) >= K:
          tmp = (l-r)*(t-b)
          area.append(abs(tmp))
print(min(area))

Submission status: Accepted

Solution code:
def main():
	N, K = map(int,input().split())
	points = [0]*N
	max_x, max_y, min_x, min_y = -10**9, -10**9, 10**9, 10**9
	for i in range(N):
		points[i] = list(map(int, input().split()))
		max_x = max(max_x, points[i][0])
		min_x = min(min_x, points[i][0])
		max_y = max(max_y, points[i][1])
		min_y = min(min_y, points[i][1])

	points.sort(key=lambda x:x[0])
	ans = (max_x-min_x)*(max_y-min_y)
	for r in range(K, N+1):
		for l in range(N-r+1):
			w = points[r+l-1][0] - points[l][0]
			this_points = sorted(list(points[l:l+r]), key=lambda x:x[1])
			for b in range(r-K+1):
				h = this_points[b+K-1][1] - this_points[b][1]
				ans = min(ans, w*h)
	print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
 
inf = float('inf')
 
def solve(N: int, K: int, x: "List[int]", y: "List[int]"):
    V = [(x[i], y[i]) for i in range(N)]
    V.sort()
    X = [v[0] for v in V]
    Y = [v[1] for v in V]
    res = inf
    for k in range(K, N+1):
        for i in range(N-k+1):
            delta_x = X[i+k-1] - X[i]
            yy = sorted(Y[i:i+k])
            for j in range(k-K+1):
                delta_y = yy[j+K-1] - yy[j]
                s = delta_x * delta_y
                if s < res:
                    res = s
 
    print(res)
    return
 
 
# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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:
def solve():
    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())
    inf=1<<62
    ans=inf
    for x1 in X:
        for x2 in X:
            if x1 <= x2:
                for y1 in Y:
                    for y2 in Y:
                        if y1 <= y2:
                            cnt = 0
                            for i in range(N):
                                if x1 <= X[i] <= x2 and y1 <= Y[i] <= y2:
                                    cnt += 1
                            if cnt >= K:
                                ans = min(ans, (x2-x1)*(y2-y1))
    return ans

print(solve())

Submission status: Accepted

Solution code:
inf = float('inf')

N,K = map(int,input().split())
ans = inf
X = []
Y = []
XY = []
for _ in range(N):
    x,y = map(int,input().split())
    X.append(x)
    Y.append(y)
    XY.append((x,y))

X = sorted(X)
Y = sorted(Y)

for i, left in enumerate(X):
    for right in X[i+1:]:
        for j, bottom in enumerate(Y):
            for top in Y[j+1:]:
                cnt = 0
                for x, y in XY:
                    if left <= x <= right and bottom <= y <= top:
                        cnt += 1
                S = (right-left)*(top-bottom)
                if cnt >= K and S < ans:
                    ans = S

print(ans)

Submission status: Accepted

Solution code:
inf = float('inf')

N,K = map(int,input().split())
ans = inf
X = []
Y = []
XY = []
for _ in range(N):
    x,y = map(int,input().split())
    X.append(x)
    Y.append(y)
    XY.append((x,y))

X = sorted(X)
Y = sorted(Y)

for i, left in enumerate(X):
    for right in X[i+1:]:
        for j, bottom in enumerate(Y):
            for top in Y[j+1:]:
                cnt = 0
                for x, y in XY:
                    if left <= x <= right and bottom <= y <= top:
                        cnt += 1
                if cnt < K: continue
                S = (right-left)*(top-bottom)
                if S < ans:
                    ans = S

print(ans)

Submission status: Accepted

Solution code:
inf = float('inf')

N,K = map(int,input().split())
ans = inf
X = []
Y = []
XY = []
for _ in range(N):
    x,y = map(int,input().split())
    X.append(x)
    Y.append(y)
    XY.append((x,y))

X = sorted(X)
Y = sorted(Y)

for i in range(N):
    for j in range(i+1,N):
        for k in range(N):
            for l in range(k+1,N):
                cnt = 0
                for x, y in XY:
                    if X[i] <= x <= X[j] and Y[k] <= y <= Y[l]:
                        cnt += 1
                if cnt < K: continue
                S = (Y[l]-Y[k])*(X[j]-X[i])
                if S < ans:
                    ans = S

print(ans)

Submission status: Accepted

Solution code:
def count_inner(P, x1, y1, x2, y2):
    cnt = 0
    for p in P:
        if x1 <= p[0] <= x2 and y1 <= p[1] <= y2:
            cnt += 1
    return cnt


def main():
    N, K = map(int, input().split())
    P = [None] * N
    xs = [0] * N
    ys = [0] * N
    for i in range(N):
        x, y = map(int, input().split())
        P[i] = (x, y)
        xs[i] = x
        ys[i] = y
    xs.sort()
    ys.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):
                    if count_inner(P, xs[i], ys[k], xs[j], ys[l]) >= K:
                        ans = min(ans, (xs[j] - xs[i]) * (ys[l] - ys[k]))
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

def cum_2d(field:list):
    row = len(field)
    col = len(field[0])
    
    # 横方向に累積和
    for r in range(row):
        for c in range(col-1):
            field[r][c+1] += field[r][c]
    
    # 縦方向に累積和
    for c in range(col):
        for r in range(row-1):
            field[r+1][c] += field[r][c]
            
    return field

def compress(xy_row: list, x_compressor, y_compressor):
    xy_comped = []
    for xi, yi in xy_row:
        xy_comped.append((x_compressor[xi], y_compressor[yi]))
        
    return xy_comped

def decompress(comped: list, x_decomp, y_decomp):
    xy_decomped = []
    for xi, yi in comped:
        xy_decomped.append((x_decomp[xi], y_decomp[yi]))
        
    return xy_decomped

n,k = li()
xy_row = [tuple(li()) for _ in range(n)]

x_row = [x for x, _ in sorted(xy_row, key=lambda x:x[0])]
y_row = [y for _, y in sorted(xy_row, key=lambda y:y[1])]

x_compressor = {xi: i+1 for i, xi in enumerate(x_row)}
y_compressor = {yi: i+1 for i, yi in enumerate(y_row)}
x_decomp = {i+1: xi for i, xi in enumerate(x_row)}
y_decomp = {i+1: yi for i, yi in enumerate(y_row)}

xy_comped = compress(xy_row, x_compressor, y_compressor)


grid = [[0]*(len(xy_comped)+1) for _ in range(len(xy_comped)+1)]
for xi, yi in xy_comped:
    grid[xi][yi] += 1
    
grid = cum_2d(grid)

ans = float('inf')

for xleft in range(1,n+1):
    for xright in range(xleft, n+1):
        for ylow in range(1,n+1):
            for yhigh in range(ylow, n+1):
                if grid[xright][yhigh] - grid[xright][ylow-1] - grid[xleft-1][yhigh] + grid[xleft-1][ylow-1] < k:
                    continue
                
                xnw = x_decomp[xleft]
                xne = x_decomp[xright]
                
                yne = y_decomp[yhigh]
                yse = y_decomp[ylow]

                ans = min(ans, (xne-xnw)*(yne-yse))
                
print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations
 
n, k = [int(item) for item in input().split()]
xy = [[int(item) for item in input().split()] for _ in range(n)]
 
xsort = sorted(xy, key=lambda x: x[0])
ysort = sorted(xy, key=lambda x: x[1])
l = [i for i in range(n)]
 
cum = [[0 for _ in range(n+1)] for _ in range(n+1)]
for i in range(n):
    for j in range(n):
        cum[i+1][j+1] = cum[i+1][j] + cum[i][j+1] - cum[i][j] + ([xsort[i][0], ysort[j][1]] in xy)

def count_points_in_rec(x0, x1, y0, y1):
    point = cum[x1+1][y1+1] - cum[x0][y1+1] - cum[x1+1][y0] + cum[x0][y0]
    return point

ans = 5 * 10**18
comb = []
for a, b in combinations(l, 2):
    if b - a >= k-1:
        comb.append([a, b])
for a, b in comb:
    for c, d in comb:
        if count_points_in_rec(a, b, c, d) == k:
            ans = min(ans, (xsort[b][0]-xsort[a][0]) * (ysort[d][1]-ysort[c][1]))
print(ans)

Submission status: Accepted

Solution code:
#constraint 2 <= K <= N <= 50
N,K = map(int,input().split())
locations = [tuple(map(int,input().split())) for _ in range(N)]
## sort by x coordinate
locations.sort()
## search for [i,j] for i-j>= K-1 (* N^2), remenber delta x (i+K) < N
## copy slice locations[i:j+1] and sort by y  (*(N+ NlogN) = * NlogN)
## search for slice, [k,l] where k - l - 1 == K , remenber delta y, calclate delta x * delta y (*N)
## total it should cost O(N^4 * logN), which is 625*1000 * log50 ~ 7*10^6... Python might TLEs?
# print(locations)
minimalArea = (10**18)*5
for i in range(N-K+1):
    for j in range(i+K-1,N):
        deltaX = locations[j][0] - locations[i][0]
        sliced = locations[i:j+1]
        sliced.sort(key= lambda p: p[1])
        # print(sliced)
        length = j-i+1
        if length < K:
            continue
        for k in range(length-K+1):
            deltaY = sliced[k + K - 1][1] - sliced[k][1]
            area = deltaX * deltaY
            # print(deltaX,deltaY,area)
            # if area == 0: continue
            minimalArea = min(area,minimalArea)
print(minimalArea)

Submission status: Accepted

Solution code:
n, kk = map(int, input().split())
p = [list(map(int, input().split())) for i in range(n)]
x_set = set(i[1] for i in p)
y_set = set(i[0] for i in p)
d_x = {}
d_y = {}
for i, x in enumerate(sorted(list(x_set))):
    d_x[x] = i
for i, y in enumerate(sorted(list(y_set))):
    d_y[y] = i
g_x = {}
g_y = {}
w = len(d_x)
h = len(d_y)
board = [[0]*(w+1) for i in range(h+1)]
tmp = [[0]*h for i in range(w)]
for y, x in p:
    ys = d_y[y]
    xs = d_x[x]
    g_x[xs] = x
    g_y[ys] = y
    tmp[ys][xs] += 1
for i in range(h):
    for j in range(w):
        board[i+1][j+1] = board[i+1][j] + board[i][j+1] - board[i][j] + tmp[i][j]
#for i in board:
#    print(i)
ans = float("inf")
for i in range(h-1):
    for j in range(i+1, h):
        for k in range(w-1):
            for l in range(k+1, w):
                s = board[j+1][l+1] - board[i][l+1] - board[j+1][k] + board[i][k]
                if s >= kk:
                    #print(g_y[j], g_y[i], g_x[l] , g_x[k])
                    area = (g_y[j] - g_y[i]) * (g_x[l] - g_x[k])
                    ans = min(ans, area)
print(ans)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
p = [list(map(int, input().split())) for i in range(n)]
ans = float("inf")

p.sort()
for i in range(n-k+1):
    for j in range(i+k-1, n):
        x = p[j][0] - p[i][0]
        yl = sorted(p[i:j+1],key=lambda x:x[1])
        for l in range(len(yl)-k+1):
            y = yl[l+k-1][1] - yl[l][1]
            ans = min(ans, y*x)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=[list(map(int,input().split()))for i in range(n)]
a.sort()
b=float("inf")
for i in range(n-k+1):
    for j in range(i+k-1,n):
        p=a[j][0]-a[i][0]
        c=sorted([d[1] for d in a[i:j+1]])
        for s in range(j-i-k+2):
            q=c[s+k-1]-c[s]
            b=min(b,p*q)
print(b)