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 cnt(xl, xr, yb, yt):
    c = 0
    for i in range(n):
        if xl <= xy[i][0] <= xr and yb <= xy[i][1] <= yt:
            c += 1
    return c


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

x = []
y = []
xy = []
for i in range(n):
    u, v = map(int, input().split())
    x.append(u)
    y.append(v)
    xy.append([u,v])
    
x.sort()
y.sort()

ans = (x[-1]-x[0])*(y[-1]-y[0])
for l in range(n-1):
    for r in range(l+1, n):
        xl, xr = x[l], x[r]
        for b in range(n-1):
            for t in range(b+1, n):
                yb, yt = y[b], y[t]
                s = (xr-xl)*(yt-yb)
                if s < ans:
                    ck = cnt(xl, xr, yb, yt)
                    # print(xl, xr, yb, yt, ck)
                    if ck >= k:
                        ans = s
print(ans)

Submission status: Accepted

Solution code:
def da_generate(h,w,a):
    da = [[0]*w for j in range(h)]
    da[0][0] = a[0][0]
    for i in range(1,w):
        da[0][i] = da[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]
            da[i][j] = da[i-1][j]+cnt_w
    return da

def da_calc(da,p,q,x,y):
    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())
mototen = []
atuten = []
zax = []
zay = []
for i in range(n):
    x , y = map(int,input().split())
    mototen.append((x,y))
    zax.append(x)
    zay.append(y)
zax.sort()
zay.sort()

a = [[0 for i in range(len(zay))] for j in range(len(zax))]

for x , y in mototen:
    atx = zax.index(x)
    aty = zay.index(y)
    a[atx][aty] += 1
b = da_generate(len(zax),len(zay),a)
ans = float("inf")
for p in range(len(zax)-1):
    for q in range(len(zay)-1):
        for x in range(p+1,len(zax)):
            for y in range(q+1,len(zax)):
                kar = da_calc(b,p,q,x,y)
                if kar >= k:
                    men = (zax[x]-zax[p])*(zay[y]-zay[q])
                    ans = min(ans,men)
print(ans)

Submission status: Accepted

Solution code:
from copy import deepcopy
import sys
def main():
    input = sys.stdin.readline
    n, k = map(int, input().split())
    x, y = [], []
    for i in range(n):
        x_, y_ = map(int, input().split())
        x.append(x_)
        y.append(y_)
    X, Y = deepcopy(x), deepcopy(y)
    x.sort()
    y.sort()
    ans = (x[-1] - x[0]) * (y[-1] - y[0])
    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
                    x1, x2, y1, y2 = x[i], x[j], y[K], y[l]
                    for m in range(n):
                        if x1 <= X[m] <= x2 and y1 <= Y[m] <= y2:
                            cnt += 1
                    if cnt >= k:
                        ans = min(ans, (x2 - x1) * (y2 - y1))
    print(ans)
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
import math
import collections
import bisect
import itertools

# import numpy as np

sys.setrecursionlimit(10 ** 7)
INF = 10 ** 20
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline().rstrip())
ns = lambda: map(int, sys.stdin.readline().rstrip().split())
na = lambda: list(map(int, sys.stdin.readline().rstrip().split()))
na1 = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().rstrip().split()))


# ===CODE===

def main():
    n, k = ns()
    pos = []
    for _ in range(n):
        x, y = ns()
        pos.append((x, y))

    ans = INF
    for tmp in itertools.combinations_with_replacement(pos, 4):
        xl = max(tmp, key=lambda t: t[0])[0]
        xs = min(tmp, key=lambda t: t[0])[0]
        yl = max(tmp, key=lambda t: t[1])[1]
        ys = min(tmp, key=lambda t: t[1])[1]

        cnt = 0
        for xi, yi in pos:
            if xs <= xi <= xl and ys <= yi <= yl:
                cnt += 1
        if cnt >= k:
            ans = min(ans, (xl - xs) * (yl - ys))

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import combinations


N, K, *XY = map(int, open(0).read().split())
X = sorted(XY[::2])
Y = sorted(XY[1::2])

ans = 10 ** 20
for x1, x2 in combinations(X, 2):
    for y1 in Y[:-1]:
        y2s = sorted(y for x, y in zip(*[iter(XY)] * 2) if x1 <= x <= x2 and y1 <= y)
        if len(y2s) < K:
            continue
        ans = min(ans, (x2 - x1) * (y2s[K - 1] - y1))
print(ans)

Submission status: Accepted

Solution code:
# 55:33
import numpy as np

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

X = XY[::2]
comp_X = {}
decomp_X = {}
for i, x in enumerate(sorted(set(X))):
    comp_X[x] = i
    decomp_X[i] = x

Y = XY[1::2]
comp_Y = {}
decomp_Y = {}
for i, y in enumerate(sorted(set(Y))):
    comp_Y[y] = i
    decomp_Y[i] = y

I = len(comp_X)
J = len(comp_Y)
comp_XY = [(comp_X[x], comp_Y[y]) for x, y in zip(X, Y)]
acc = np.zeros((I + 1, J + 1), np.int32)
for c_x, c_y in comp_XY:
    acc[c_x + 1][c_y + 1] += 1
acc = np.add.accumulate(acc, axis=0)
acc = np.add.accumulate(acc, axis=1)

ans = float("inf")
for i in range(1, I + 1):
    for j in range(1, J + 1):
        cur = acc[i:, j:] + acc[:-i, :-j] - acc[:-i, j:] - acc[i:, :-j]
        for k, row in enumerate(cur):
            for l, val in enumerate(row):
                if val >= K:
                    ans = min(
                        ans,
                        (decomp_X[k + i - 1] - decomp_X[k])
                        * (decomp_Y[l + j - 1] - decomp_Y[l]),
                    )
print(ans)

Submission status: Accepted

Solution code:
import numpy as np

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

X = XY[::2]
comp_X = {}
decomp_X = {}
for i, x in enumerate(sorted(set(X))):
    comp_X[x] = i
    decomp_X[i] = x

Y = XY[1::2]
comp_Y = {}
decomp_Y = {}
for i, y in enumerate(sorted(set(Y))):
    comp_Y[y] = i
    decomp_Y[i] = y

I = len(comp_X)
J = len(comp_Y)
comp_XY = [(comp_X[x], comp_Y[y]) for x, y in zip(X, Y)]
acc = np.zeros((I + 1, J + 1), np.int32)
for c_x, c_y in comp_XY:
    acc[c_x + 1][c_y + 1] += 1
acc = np.add.accumulate(acc, axis=0)
acc = np.add.accumulate(acc, axis=1)

ans = float("inf")
for i in range(1, I + 1):
    for j in range(1, J + 1):
        cur = acc[i:, j:] + acc[:-i, :-j] - acc[:-i, j:] - acc[i:, :-j]
        for k, row in enumerate(cur):
            for l, val in enumerate(row):
                if val >= K:
                    ans = min(
                        ans,
                        (decomp_X[k + i - 1] - decomp_X[k])
                        * (decomp_Y[l + j - 1] - decomp_Y[l]),
                    )
print(ans)

Submission status: Accepted

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

ans = 10**20+1
for a in range(n):
    for b in range(a+1,n):
        axy = xyl[a]
        bxy = xyl[b]
        ax,ay = axy
        bx,by = bxy
        l = min(ax,bx)
        r = max(ax,bx)
        t = max(ay,by)
        bo = min(ay,by)
        v = 0
        for x,y in xyl:
            if l <= x <= r and bo <= y <= t:
                v += 1
        if v >= k:
            area = (r-l)*(t-bo)
            ans = min(ans, area)

        for c in range(b+1,n):
            cxy = xyl[c]
            cx,cy = cxy
            l = min(ax,bx,cx)
            r = max(ax,bx,cx)
            t = max(ay,by,cy)
            bo = min(ay,by,cy)
            v = 0
            for x,y in xyl:
                if l <= x <= r and bo <= y <= t:
                    v += 1
            if v >= k:
                area = (r-l)*(t-bo)
                ans = min(ans, area)

            for d in range(c+1,n):
                dxy = xyl[d]
                dx,dy = dxy
                left = min(ax,bx,cx,dx)
                right = max(ax,bx,cx,dx)
                top = max(ay,by,cy,dy)
                bottom = min(ay,by,cy,dy)
                cnt = 0
                for x,y in xyl:
                    if left <= x <= right and bottom <= y <= top:
                        cnt += 1
                if cnt >= k:
                    area = (right-left)*(top-bottom)
                    ans = min(ans, area)


print(ans)

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
XY = [tuple(map(int,input().split())) for i in range(N)]
xs = []
ys = []
for x,y in XY:
    xs.append(x)
    ys.append(y)
xs.sort()
ys.sort()

ans = float('inf')
for l in range(N-1):
    for r in range(l+1,N):
        w = xs[r] - xs[l]
        for d in range(N-1):
            for u in range(d+1,N):
                h = ys[u] - ys[d]
                if ans <= w*h: continue
                c = 0
                for x,y in XY:
                    if xs[l] <= x <= xs[r] and ys[d] <= y <= ys[u]:
                        c += 1
                        if c >= K:
                            ans = w*h
                            break
print(ans)

Submission status: Accepted

Solution code:
from itertools import groupby, accumulate, product, permutations, combinations
def compress(arr):
    *XS, = set(arr)
    XS.sort()
    return {e: i+1 for i, e in enumerate(XS)},{i+1: e for i, e in enumerate(XS)}

def solve():
  ans = float('inf')
  N, K = map(int, input().split())
  X,Y = [0]*N,[0]*N
  for i in range(N):
    X[i],Y[i] = map(int, input().split())
  x_c,x_r = compress(X)
  y_c,y_r = compress(Y)
  n_x = len(x_c)
  n_y = len(y_c)
  num = [[0]*(N+1) for _ in range(N+1)]
  for i in range(N):
    X[i] = x_c[X[i]]
    Y[i] = y_c[Y[i]]
    num[X[i]][Y[i]] += 1
  cum2 = [[0]*(N+1) for _ in range(N+1)]
  for i in range(1,N+1):
    for j in range(1,N+1):
      cum2[i][j] = cum2[i-1][j]+cum2[i][j-1]-cum2[i-1][j-1]+num[i][j]
  for x1,x2 in combinations(range(1,n_x+1),2):
    x_l = x_r[x2]-x_r[x1]
    for y1,y2 in combinations(range(1,n_y+1),2):
      k = cum2[x2][y2]+cum2[x1-1][y1-1]-cum2[x1-1][y2]-cum2[x2][y1-1]
      if k>=K:
        y_l = y_r[y2]-y_r[y1]
        ans = min(ans,x_l*y_l)
  return ans
print(solve())

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
x=[]
y=[]
xy=[]
for _ in range(n):
  xx,yy=map(int,input().split())
  xy.append((xx,yy))
  x.append(xx)
  y.append(yy)
xx=sorted(x)
yy=sorted(y)
ans=10**20
for sxi in range(n-1):
  for syi in range(n-1):
    for tyi in range(1,n):
      sx,sy,ty=xx[sxi],yy[syi],yy[tyi]
      ax=sorted([xxx for xxx,yyy in xy if sx<=xxx and sy<=yyy<=ty])
      if len(ax)<k:continue
      tx=ax[k-1]
      ans=min(ans,(tx-sx)*(ty-sy))
print(ans)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
f = [list(map(int, input().split())) for _ in range(n)]
f.sort()
ans = 1145141919810893364364
for i in range(n - k + 1):
    for j in range(i + k - 1, n):
        a = [f[l][1] for l in range(i, j + 1)]
        a.sort()
        for l in range(j - i - k + 2):
            ans = min(ans, (f[j][0] - f[i][0]) * (a[l + k - 1] - a[l]))
print(ans)

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


def main():

    N, K = in_nn()

    X = []
    Y = []
    for i in range(N):
        x, y = in_nn()
        X.append(x)
        Y.append(y)

    sort_x = sorted(set(X))
    sort_y = sorted(set(Y))

    nx = len(sort_x)
    ny = len(sort_y)

    total_sum = [[0 for _ in range(nx + 1)] for _ in range(ny + 1)]

    for i in range(N):
        x, y = X[i], Y[i]
        ix = sort_x.index(x)
        iy = sort_y.index(y)
        total_sum[iy + 1][ix + 1] += 1

    for y in range(ny + 1):
        for x in range(nx):
            total_sum[y][x + 1] += total_sum[y][x]

    for x in range(nx + 1):
        for y in range(ny):
            total_sum[y + 1][x] += total_sum[y][x]

    def calc_area(u, d, l, r):
        return total_sum[d][r] - total_sum[u][r] - total_sum[d][l] + total_sum[u][l]

    ans = 10**19
    for y1 in range(ny + 1):
        for y2 in range(y1 + 2, ny + 1):
            for x1 in range(nx + 1):
                for x2 in range(x1 + 2, nx + 1):
                    if calc_area(y1, y2, x1, x2) >= K:
                        area = (sort_x[x2 - 1] - sort_x[x1]) * (sort_y[y2 - 1] - sort_y[y1])
                        ans = min(ans, area)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
def main():
    N,K=mi()
    G = []

    X=[]
    Y=[]
    for i in range(N):
        x,y = mi()
        G.append((x,y))
        X.append(x)
        Y.append(y)

    def count(downx,upx,downy,upy):
        _count = 0
        for i in range(N):
            x,y = G[i]
            if downx<=x<=upx and downy<=y<=upy:
                _count += 1
        
        return _count

    ans = INF
    for downx in X:
        for upx in X:
            if upx <= downx: continue
            for downy in Y:
                for upy in Y:
                    if upy <= downy: continue

                    if count(downx,upx,downy,upy) >= K:
                        ans = min(ans,abs(upx-downx) * abs(upy-downy))
                        



    print(ans)

            



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N, K, *XY = [int(_) for _ in open(0).read().split()]
XY = sorted(zip(XY[::2], XY[1::2]))
ans = float('inf')
for i in range(N):
    for j in range(i + K - 1, N):
        xlen = XY[j][0] - XY[i][0]
        Y = sorted(y for x, y in XY[i:j + 1])
        ylen = min(y2 - y1 for y1, y2 in zip(Y, Y[K - 1:]))
        ans = min(ans, xlen * ylen)
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
from numba import njit
N, K, *XY = [int(_) for _ in open(0).read().split()]
XY = np.array(XY, dtype=np.int64).reshape((N, 2)).T
X = np.sort(XY[0])
Y = np.sort(XY[1])

@njit
def solve(XY, X, Y):
    v = 4 * 10**18 + 1
    ans = np.array([0, 0, 0, 0], dtype=np.int64)
    for i1 in range(N - 1):
        x1=X[i1]
        for i2 in range(i1 + 1, N):
            x2=X[i2]
            for j1 in range(N - 1):
                y1=Y[j1]
                for j2 in range(j1 + 1, N):
                    y2 = Y[j2]
                    if np.sum((x1 <= XY[0]) * (XY[0] <= x2) * (y1 <= XY[1]) * (XY[1] <= y2)) < K:
                        continue
                    v2 = (x2 - x1) * (y2 - y1)
                    v = min(v, v2)
    return v

ans = solve(XY, X, Y)
print(ans)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
xy = [tuple(map(int, input().split())) for _ in range(N)]
xy.sort(key=lambda t: t[0])
ans = 10**20

for i in range(N):
    for j in range(i+K-1, N):
        xlen = xy[j][0]-xy[i][0]
        ys = []
        
        for k in range(i, j+1):
            ys.append(xy[k][1])
            
        ys.sort()
        ylen = 10**20
        
        for k in range(len(ys)-K+1):
            ylen = min(ylen, ys[k+K-1]-ys[k])
        
        ans = min(ans, xlen*ylen)
    
print(ans)

Submission status: Accepted

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

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()

def main():
	n,k=MI()
	li=[LI() for _ in range(n)]
	#print(li)

	ans=10**20

	X=[]
	Y=[]

	for x,y in li:
		X.append(x)
		Y.append(y)
	X.sort()
	Y.sort()
	#print(X,Y)

	for i in range(n):
		for ii in range(i+1,n):
			for j in range(n):
				for jj in range(j+1,n):
					cnt=0
					for x,y in li:
						if X[i]<=x<=X[ii] and Y[j]<=y<=Y[jj]:
							cnt+=1
					#print(i,ii,j,jj,X[i],X[ii],Y[j],Y[jj],cnt,ans)
					if cnt>=k:
						ans=min(ans,(X[ii]-X[i])*(Y[jj]-Y[j]))

	print(ans)












if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
import itertools

n,k = map(int,input().split())
x = []
y = []
xy = []
for i in range(n):
  x0,y0 = map(int,input().split())
  x.append(x0)
  y.append(y0)
  xy.append((x0,y0))
x.sort()
y.sort()
xs = {}
ys = {}
for i in range(n):
  xs[x[i]] = i
  ys[y[i]] = i
m = [[0 for _ in range(n+1)] for _ in range(n+1)]
for x0,y0 in xy:
  m[ys[y0]+1][xs[x0]+1] += 1
for i in range(n):
  for j in range(n):
    m[i+1][j+1] += m[i][j+1]+m[i+1][j]-m[i][j]

ans = float('INF')
for x1,x2 in itertools.combinations(range(n),2):
  for y1,y2 in itertools.combinations(range(n),2):
    if k <= m[y2+1][x2+1]-m[y2+1][x1]-m[y1][x2+1]+m[y1][x1]:
      #print(x1,x2,y1,y2)
      ans = min((x[x2]-x[x1])*(y[y2]-y[y1]),ans)
print(ans)
#print(m)

Submission status: Accepted

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

def main():
  n, k = map(int, input().split())
  point = [[int(x) for x in input().split()] for _ in range(n)]
  
  ans = pow(10, 18)*4
  for a in range(n):
    for b in range(a+1):
      for c in range(b+1):
        for d in range(c+1):
          x, y = [point[a][0], point[b][0], point[c][0], point[d][0]], [point[a][1], point[b][1], point[c][1], point[d][1]]
          x1, x2, y1, y2 = min(x), max(x), min(y), max(y)
          count = 0
          for e in range(n):
            if x1 <= point[e][0] <= x2 and y1 <= point[e][1] <= y2:
              count += 1
          if count < k:
            continue
          sub = (x2-x1)*(y2-y1)
          if ans > sub:
            ans = sub
  
  print(ans)
  
  
if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
from collections import defaultdict
def main():
  n,k=map(int,input().split())
  xy=[list(map(int,input().split())) for _ in range(n)]
  x=[p[0] for p in xy]
  y=[p[1] for p in xy]
  x.sort()
  y.sort()
  
  s1=[[0]*n for _ in range(n)]
  s2=[[0]*n for _ in range(n)]
  s3=[[0]*n for _ in range(n)]
  s4=[[0]*n for _ in range(n)]
  for i in range(n):
    for j in range(n):
        for p in xy:
            if p[0]<=x[i] and p[1]<=y[j]:
              s1[i][j]+=1
              s2[i][j]+=(p[0]<x[i])
              s3[i][j]+=(p[1]<y[j])
              s4[i][j]+=(p[0]<x[i])*(p[1]<y[j])
  ans=float('inf')
  for s in range(n):
    for t in range(s+1,n):
      for u in range(n):
        for v in range(u+1,n):
          if s1[t][v]-s3[t][u]-s2[s][v]+s4[s][u]>=k:
            ans=min(ans,(x[t]-x[s])*(y[v]-y[u]))
  print(ans)

if __name__=='__main__':
  main()

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_left
from itertools import accumulate

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, K, *XY = map(int, read().split())

    X = set()
    Y = set()
    for i, (x, y) in enumerate(zip(*[iter(XY)] * 2)):
        X.add(x - 1)
        Y.add(y - 1)

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

    P, Q = len(X), len(Y)

    G = [[0] * Q for _ in range(P)]
    for x, y in zip(*[iter(XY)] * 2):
        G[bisect_left(X, x - 1)][bisect_left(Y, y - 1)] = 1

    csum = [[0] * (Q + 1) for _ in range(P + 1)]
    for i in range(P):
        for j in range(Q):
            csum[i + 1][j + 1] = csum[i + 1][j] + csum[i][j + 1] - csum[i][j] + G[i][j]

    ans = -1
    for x1 in range(P):
        for x2 in range(x1, P + 1):
            for y1 in range(Q):
                for y2 in range(y1, Q + 1):
                    if csum[x2][y2] - csum[x1][y2] - csum[x2][y1] + csum[x1][y1] >= K:
                        if ans > (X[x2 - 1] - X[x1]) * (Y[y2 - 1] - Y[y1]) or ans == -1:
                            ans = (X[x2 - 1] - X[x1]) * (Y[y2 - 1] - Y[y1])

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
def MI(): return map(int,sys.stdin.readline().rstrip().split())

N,K = MI()
xy = [tuple(MI()) for i in range(N)]

xy.sort()

from operator import itemgetter

ans = 10**19
for i in range(N-1):
    for j in range(i+1,N):
        a = xy[j][0]-xy[i][0]
        A = xy[i:j+1]
        if len(A) >= K:
            A = sorted(A, key=itemgetter(1))
            b = 10**18
            for k in range(len(A)-K+1):
                b = min(b,A[k+K-1][1]-A[k][1])
            ans = min(ans,a*b)

print(ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, k = map(int, input().split())
    X, Y = [], []
    XY = []
    for _ in range(n):
        x, y = map(int, input().split())
        X.append(x)
        Y.append(y)
        XY.append([x, y])
    X.sort()
    Y.sort()

    res = f_inf
    for x1 in range(n):
        left = X[x1]
        for x2 in range(x1 + 1, n):
            right = X[x2]
            for y1 in range(n):
                bottom = Y[y1]
                for y2 in range(y1 + 1, n):
                    up = Y[y2]
                    cnt = 0
                    for x, y in XY:
                        if left <= x <= right and bottom <= y <= up:
                            cnt += 1
                        if cnt >= k:
                            area = (right - left) * (up - bottom)
                            res = min(res, area)
                            break
    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

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

dp=[[[] for _ in range(n)] for _ in range(n)]
for i in range(n):
    for j in range(i+1,n):
        for k in range(i,j+1):
            dp[i][j].append(xy[k][1])
        
        dp[i][j].sort()

ans=10**19

for x in range(K,n+1):
    for i in range(n-x+1):
        left=xy[i][0]
        right=xy[i+x-1][0]

        for j in range(len(dp[i][i+x-1])-K+1):
            down=dp[i][i+x-1][j]
            up=dp[i][i+x-1][j+K-1]

            ans=min(ans,(right-left)*(up-down))

print(ans)

Submission status: Accepted

Solution code:
import sys
from itertools import accumulate
def input(): return sys.stdin.readline().strip()

def main():
    N, K = map(int, input().split())
    points = []
    X = set()
    Y = set()
    for _ in range(N):
        x, y = map(int, input().split())
        points.append((x, y))
        X.add(x)
        Y.add(y)
    X = list(X)
    Y = list(Y)
    X.sort()
    Y.sort()

    mapX = {} # mapX[x] = (点のx座標が小さい方から何番目か)
    mapY = {} # mapY[y] = (点のy座標が小さい方から何番目か)
    for i, x in enumerate(X): mapX[x] = i + 1
    for i, y in enumerate(Y): mapY[y] = i + 1

    # 圧縮後の座標平面に対してグリッドを張るので、そのサイズを求めておく
    h, w = len(mapX), len(mapY)
    grid = [[0] * (w + 1) for _ in range(h + 1)]
    for x, y in points:
        grid[mapY[y]][mapX[x]] = 1
    sum_grid = [list(accumulate(grid[y])) for y in range(h + 1)]
    for y in range(1, h + 1):
        for x in range(1, w + 1):
            sum_grid[y][x] += sum_grid[y - 1][x]

    ans = 10**20
    for sx in range(1, w + 1):
        for sy in range(1, h + 1):
            for ex in range(sx, w + 1):
                for ey in range(sy, h + 1):
                    cnt = sum_grid[ey][ex] - sum_grid[ey][sx-1] - sum_grid[sy-1][ex] + sum_grid[sy-1][sx-1]
                    if cnt < K: continue
                    area = (X[ex - 1] - X[sx - 1]) * (Y[ey - 1] - Y[sy - 1])
                    ans = min(ans, area)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

x_index=set([])
y_index=set([])

for (x,y) in xy:
    x_index.add(x)
    y_index.add(y)
    
####座標圧縮

x_index=list(x_index)
y_index=list(y_index)

x_index.sort()
y_index.sort()
ans=0
for xl in range(len(x_index)-1):
    for xr in range(xl+1,len(x_index)):
        for yl in range(len(y_index)-1):
            for yr in range(yl+1,len(y_index)):
                cnt=0
                for (x,y) in xy:
                    if x_index[xl]<=x and x<=x_index[xr] and y_index[yl]<=y and y<=y_index[yr]:
                        cnt+=1
                if cnt==k:
                    tmp=(x_index[xr]-x_index[xl])*(y_index[yr]-y_index[yl])
                    if ans==0:
                        ans=tmp
                    else:
                        ans=min(ans,tmp)
print(ans)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
n,g = map(int,readline().split())
XY = []
for i in range(n):
    XY.append(list(map(int,readline().split())))
ans = 10**32

if g == 2:
    for i in range(n):
        for j in range(i+1,n):
            hidarisita = (min(XY[i][0],XY[j][0]),min(XY[i][1],XY[j][1]))
            migiue = (max(XY[i][0],XY[j][0]),max(XY[i][1],XY[j][1]))
            ans = min(ans,abs((migiue[0]-hidarisita[0])*(migiue[1]-hidarisita[1])))

elif g == 3:
    for i in range(n):
        for j in range(i+1,n):
            for k in range(j+1,n):
                hidarisita = (min(XY[i][0],XY[j][0],XY[k][0]),
                min(XY[i][1],XY[j][1],XY[k][1]))
                migiue = (max(XY[i][0],XY[j][0],XY[k][0]),
                max(XY[i][1],XY[j][1],XY[k][1]))
                ans = min(ans,abs((migiue[0]-hidarisita[0])*(migiue[1]-hidarisita[1])))
else:

    for i in range(n):
        for j in range(i+1,n):
            for k in range(j+1,n):
                for l in range(k+1,n):
                    hidarisita = (min(XY[i][0],XY[j][0],XY[k][0],XY[l][0]),
                    min(XY[i][1],XY[j][1],XY[k][1],XY[l][1]))
                    migiue = (max(XY[i][0],XY[j][0],XY[k][0],XY[l][0]),
                    max(XY[i][1],XY[j][1],XY[k][1],XY[l][1]))

                    res = 0
                    for m in range(n):
                        if hidarisita[0] <= XY[m][0] <= migiue[0] and \
                            hidarisita[1] <= XY[m][1] <= migiue[1]:
                            res += 1

                    if res >= g:
                        ans = min(ans,abs((migiue[0]-hidarisita[0])*(migiue[1]-hidarisita[1])))

print(ans)

Submission status: Accepted

Solution code:
N,K,*xy = map(int, open(0).read().split())
_x_ = sorted(xy[::2])
ans = 4 * 10 ** 18
for _x in _x_:
  for x_ in _x_[1:]:
    w = x_ - _x
    c = 0
    _h_ = []
    for x, y in zip(xy[::2], xy[1::2]):
      if _x <= x <= x_:
        c += 1
        _h_.append(y)
      if c >= K:
        _h_.sort()
        h = min(_h_[i + K - 1] - _h_[i] for i in range(c - K + 1))
        ans = min(ans, h * w)

print(ans)

Submission status: Accepted

Solution code:
import sys

N, K = map(int, sys.stdin.readline().split())
points = []
for _ in range(N):
    x, y = map(int, sys.stdin.readline().split())
    points.append((x, y))

area = float("inf")
x_sorted = sorted(points)
y_sorted = sorted(points, key = lambda x: x[1])
for i1 in range(N-1):
    for i2 in range(i1+1, N):
        for j1 in range(N-1):
            for j2 in range(j1+1, N):
                x_min = x_sorted[i1][0]
                x_max = x_sorted[i2][0]
                y_min = y_sorted[j1][1]
                y_max = y_sorted[j2][1]
                num = 0
                for i in range(N):
                    if x_min <= points[i][0] <= x_max and y_min <= points[i][1] <= y_max:
                        num += 1
                tmp_area = (x_max - x_min) * (y_max - y_min)
                if num >= K and tmp_area < area:
                    area = tmp_area
                
print(area)

Submission status: Accepted

Solution code:
import itertools
N, K = map(int, input().split())
xy = []
x, y = [], []
for i in range(N):
    a, b = map(int, input().split())
    xy.append([a, b])
    x.append(a)
    y.append(b)

ans = float('inf')
for sx, ex in itertools.combinations(x, 2):
    for sy, ey in itertools.combinations(y, 2):
        if ex < sx:
            sx, ex = ex, sx
        if ey < sy:
            sy, ey = ey, sy
        s = (ex-sx)*(ey-sy)
        if s == 0:
            continue

        c = 0
        for k in range(N):
            a, b = xy[k]
            if sx <= a and a <= ex and sy <= b and b <= ey:
                c += 1
        if c >= K and s < ans:
            ans = s

print(ans)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
x = [None] * N
y = [None] * N

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

ans = 10**20
sx = sorted(x)
sy = 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):# 下
                count = 0
                # 点が長方形に含まれるか確認
                for m in range(N):
                    if sx[i] <= x[m] <= sx[j] and sy[k] <= y[m] <= sy[l]:
                        count += 1
                if count >= K:
                    ans = min(ans, (sx[j]-sx[i]) * (sy[l]-sy[k]))
print(ans)

Submission status: Accepted

Solution code:
def check(x1,x2,y1,y2):
  p1=x1
  p2=x2
  q1=y1
  q2=y2
  if x1<=x2:
    x1=p1
    x2=p2
  else:
    x1=p2
    x2=p1
  if y1<=y2:
    y1=q1
    y2=q2
  else:
    y1=q2
    y2=q1
  count=0
  for ttx,tty in xy:
    if x1<=ttx<=x2 and y1<=tty<=y2:
      count+=1
  if count>=k:
    res=True
  else:
    res=False
  return res

n,k=map(int,input().split())
x,y=[],[]
xy=[]
for i in range(n):
  a,b=map(int,input().split())
  x.append(a)
  y.append(b)
  xy.append((a,b))
from itertools import combinations
ans=10**20
for xx in combinations(x,2):
  for yy in combinations(y,2):
    if check(xx[0],xx[1],yy[0],yy[1]):
      tmp=abs(xx[0]-xx[1])*abs(yy[0]-yy[1])
      ans=min(ans,tmp)
print(ans)