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:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

n, k = map(int, readline().split())
xy = []
xx = []
yy = []
for _ in range(n):
    x, y = map(int, readline().split())
    xx.append(x)
    yy.append(y)
    xy.append((x, y))
xx.sort()
yy.sort()
ans = float('inf')
for i, ix in enumerate(xx):
    for jx in xx[i + 1:]:
        for j, iy in enumerate(yy):
            for jy in yy[j + 1:]:
                cnt = 0
                for x, y in xy:
                    if ix <= x <= jx and iy <= y <= jy:
                        cnt += 1
                if cnt >= k:
                    ans = min(ans, (jx - ix) * (jy - iy))
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(key=lambda x: x[0])
XY = [xy + [x] for x, xy in enumerate(XY)]
XY.sort(key=lambda x: x[1])
XY = [xy + [y] for y, xy in enumerate(XY)]

gr = [[0] * n for _ in range(n)]
for _, _, i, j in XY:
  gr[i][j] = 1
  
rui = [[0] * (n + 1) for _ in range(n + 1)]
for i in range(n):
  for j in range(n):
    rui[i + 1][j + 1] = rui[i + 1][j] + rui[i][j + 1] - rui[i][j] + gr[i][j]
    
# XYの2点,3点,4点を総当たり
ans = 10 ** 21
for i in range(n - 1):
  for j in range(i + 1, n):
    x = [XY[m][0] for m in [i, j]]
    y = [XY[m][1] for m in [i, j]]
    ii = [XY[m][2] for m in [i, j]]
    jj = [XY[m][3] for m in [i, j]]
    innerPoints = rui[max(ii) + 1][max(jj) + 1] \
                + rui[min(ii)][min(jj)] \
                - rui[min(ii)][max(jj) + 1] \
                - rui[max(ii) + 1][min(jj)]
    if innerPoints >= k:
      area = (max(x) - min(x)) * (max(y) - min(y)) 
      if area < ans:
        ans = area

if n > 2:
  for i in range(n - 2):
    for j in range(i + 1, n - 1):
      for l in range(j + 1, n):
        x = [XY[m][0] for m in [i, j, l]]
        y = [XY[m][1] for m in [i, j, l]]
        ii = [XY[m][2] for m in [i, j, l]]
        jj = [XY[m][3] for m in [i, j, l]]
        innerPoints = rui[max(ii) + 1][max(jj) + 1] \
                    + rui[min(ii)][min(jj)] \
                    - rui[min(ii)][max(jj) + 1] \
                    - rui[max(ii) + 1][min(jj)]
        if innerPoints >= k:
          area = (max(x) - min(x)) * (max(y) - min(y)) 
          if area < ans:
            ans = area

if n > 3:
  for i in range(n - 3):
    for j in range(i + 1, n - 2):
      for l in range(j + 1, n - 1):
        for o in range(l + 1, n):
          x = [XY[m][0] for m in [i, j, o, l]]
          y = [XY[m][1] for m in [i, j, o, l]]
          ii = [XY[m][2] for m in [i, j, o, l]]
          jj = [XY[m][3] for m in [i, j, o, l]]
          innerPoints = rui[max(ii) + 1][max(jj) + 1] \
                      + rui[min(ii)][min(jj)] \
                      - rui[min(ii)][max(jj) + 1] \
                      - rui[max(ii) + 1][min(jj)]
          if innerPoints >= k:
            area = (max(x) - min(x)) * (max(y) - min(y)) 
            if area < ans:
              ans = area

print(ans)

Submission status: Accepted

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

ans = float('inf')
for i in range(N):
    for j in range(i + K - 1, N):
        xmin, xmax = points[i][0], points[j][0]
        que = []
        for k in range(N):
            if xmin <= points[k][0] <= xmax:
                que.append(points[k][1])
        if len(que) >= K:
            que.sort()
            for k in range(len(que) - K + 1):
                ans = min(ans, (max(que[k: k + K]) - min(que[k: k + K])) * (xmax - xmin))
print(ans)

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**19
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    N,K = LI()
    px = [LI() for _ in range(N)]
    px.sort()

    ans = INF
    for k in range(K,N+1):
        for i in range(N-k+1):
            w = px[i+k-1][0] - px[i][0]
            py = []
            for _,y in px[i:i+k]:
                py.append(y)
            py.sort()
            min_y = INF
            for j in range(k-K+1):
                min_y = min(min_y,py[K+j-1]-py[j])
            ans = min(ans,w * min_y)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 8)
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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


def solve():
    minarea = 1 << 62
    for t in range(N):
        _, yt = coords[t]
        for b in range(N):
            _, yb = coords[b]
            if yb < yt:
                continue
            h = yb - yt
            xs = []
            for i in range(N):
                xi, yi = coords[i]
                if yi < yt or yi > yb:
                    continue
                xs.append(xi)
            for i in range(K - 1, len(xs)):
                w = xs[i] - xs[i - K + 1]
                a = w * h
                minarea = min(minarea, a)
    return minarea


if __name__ == "__main__":
    print(solve())

Submission status: Accepted

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

def check(x1,y1,x2,y2):
    cnt=0
    for node in xy:
        x,y=node
        if x1<=x<=x2 and y1<=y<=y2:
            cnt+=1
    return cnt

xlis=[]
ylis=[]
for itm in xy:
    x,y=itm
    xlis.append(x)
    ylis.append(y)
xlis.sort()
ylis.sort()

ans=10**20
from itertools import *
for tmp1 in combinations(xlis,2):
    for tmp2 in combinations(ylis,2):
        x1,x2=tmp1
        y1,y2=tmp2
        ret = check(x1,y1,x2,y2)
        if ret==k:
            ans=min(ans,(x2-x1)*(y2-y1))

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
from collections import deque
from fractions import gcd
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def inputI(): return int(input().strip())
def inputS(): return input().strip()
def inputIL(): return list(map(int,input().split()))
def inputSL(): return list(map(str,input().split()))
def inputILs(n): return list(int(input()) for _ in range(n))
def inputSLs(n): return list(input().strip() for _ in range(n))
def inputILL(n): return [list(map(int, input().split())) for _ in range(n)]
def inputSLL(n): return [list(map(str, input().split())) for _ in range(n)]

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])
    return arr

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#############
# Main Code #
#############


N,K = inputIL()
P = inputILL(N)



xtic = list(set([xy[0] for xy in P]))
ytic = list(set([xy[1] for xy in P]))
xtic.sort()
ytic.sort()


o_list = []
for x in xtic:
  for y in ytic:
    o_list.append([x,y])
ans = INF

for p in o_list:
  x0,y0 = p
  for xmax in xtic:
    if xmax < x0:
      continue
    else:
      tempP = []
      for q in P:
        if x0 <= q[0] <= xmax and y0 <= q[1]:
          tempP.append(q)
      if len(tempP) < K:
        continue
      tempP = sorted(tempP, key=lambda x:x[1])
      ans = min(ans,(xmax-x0)*(tempP[K-1][1]-y0))
      
      
      
      

      
print(ans)

Submission status: Accepted

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

x = sorted(v for v, _ in X)
y = sorted(v for _, v in X)
ans = 10 ** 20
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):
                x1 = x[i]
                x2 = x[j]
                y1 = y[k]
                y2 = y[l]
                num = 0
                for n in range(N):
                    if x1 <= X[n][0] <= x2 and y1 <= X[n][1] <= y2:
                        num += 1
                if num >= K:
                    ans = min(ans, (x2 - x1) * (y2 - y1))

print(ans)

Submission status: Accepted

Solution code:
from copy import deepcopy
N, K = map(int, input().split())
X, Y = [], []
for _ in range(N):
    x, y = map(int, input().split())
    X.append(x)
    Y.append(y)
PX, PY = deepcopy(X), deepcopy(Y)
X.sort()
Y.sort()

ans = (X[-1] - X[0]) * (Y[-1] - Y[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):
                num = 0
                lx, rx = X[xi], X[xj]
                by, uy = Y[yi], Y[yj]

                for i in range(N):
                    if lx <= PX[i] and PX[i] <= rx and by <= PY[i] and PY[i] <= uy:
                        num += 1

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

Submission status: Accepted

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

xlist,ylist,xylist=[],[],[]
xyset=set()
xydic={}
yxdic={}
for i in range(N):
  x,y=map(int,input().split())
  xlist.append(x)
  ylist.append(y)
  xylist.append((x,y))
  xyset.add((x,y))
  xydic[x]=y
  yxdic[y]=x

xy_prod_list=[]
for x in xlist:
  for y in ylist:
    xy_prod_list.append((x,y))
xy_prod_list.sort()
#print(xy_prod_list)    

num_ld_dic={}
for xx,yy in xy_prod_list:
  num_ld=0
  for x,y in xylist:
    if x<=xx and y<=yy:
      num_ld+=1
  num_ld_dic[(xx,yy)]=num_ld
#print(num_ld_dic)

answer=float("inf")
for i in range(len(xy_prod_list)):
  x1,y1=xy_prod_list[i]
  for j in range(len(xy_prod_list)):
    x2,y2=xy_prod_list[j]
    if x1>=x2 or y1>=y2:
      continue
    
    area=(x2-x1)*(y2-y1)
    if area>answer:
      continue
      
    num_point=num_ld_dic[(x2,y2)]-num_ld_dic[(x1,y2)]-num_ld_dic[(x2,y1)]+num_ld_dic[(x1,y1)]
    if (x1,y1) in xyset:  
      num_point+=1
    else:
      xx=yxdic[y1]
      if x1<=xx<=x2:
        num_point+=1
      yy=xydic[x1]
      if y1<=yy<=y2:
        num_point+=1
      
    if num_point>=K:
      #print((x1,y1),(x2,y2),num_point)
      answer=min(answer,area)
    
print(answer)

Submission status: Accepted

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

n, k = [int(x) for x in input().split()]
xy = []
for _ in range(n):
    xy.append([int(x) for x in input().split()])
ans = float('inf')
xy.sort()
for i in range(n):
    left = xy[i][0]
    y = [xy[i][1]]
    for j in range(i + 1, n):
        right = xy[j][0]
        y.append(xy[j][1])
        y.sort()
        if j - i + 1 < k:
            continue
        for p in range(len(y)):
            bottom = y[p]
            for q in range(len(y)):
                if q - p + 1 < k:
                    continue
                top = y[q]
                ans = min(ans, (right - left)*(top - bottom))
print(ans)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
li=sorted([list(map(int,input().split())) for i in range(n)],key=lambda x:(x[1],x[0]))
ans=float("INF")
#print(li)
for i in range(n):
    for j in range(i+1,n):
        ux,lx=max(li[i][0],li[j][0]),min(li[i][0],li[j][0])
        l,r=0,0
        cnt=int(lx<=li[r][0]<=ux)
#        print("!",ux,lx,"!",end="")
        while True:
#            print("cnt:",cnt,end="")
            while r<n-1 and cnt<k:
                r+=1
                cnt+=int(lx<=li[r][0]<=ux)
            if cnt<k or not(0<=r<=n-1) or not(0<=l<=n-1) or r<=l :break
            if ans>(ux-lx)*(li[r][1]-li[l][1]):
                ans=(ux-lx)*(li[r][1]-li[l][1])
#                print(i,j,l,r,cnt,ans)
            cnt-=int(lx<=li[l][0]<=ux)
            l+=1
print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations

n,k = map(int,input().split())
xy = [list(map(int,input().split())) + [i] for i in range(n)]
x_order = sorted(xy)
y_order = sorted(xy,key = lambda x:x[1])

pos = [[None]*2 for _ in range(n)]

for i,(x,y,j) in enumerate(x_order):
    pos[j][0] = i
for i,(x,y,j) in enumerate(y_order):
    pos[j][1] = i

count = [[0] * (n+1) for _ in range(n+1)]

for x,y in pos:
    count[y+1][x+1] += 1

for i in range(n+1):
    for j in range(1,n+1):
        count[i][j] += count[i][j-1]

for i in range(n+1):
    for j in range(1,n+1):
        count[j][i] += count[j-1][i]

ans = float('inf')
for x1,x2 in combinations(range(1,n+1),2):
    for y1,y2 in combinations(range(1,n+1),2):
        if count[y2][x2] - count[y2][x1-1] - count[y1-1][x2] + count[y1-1][x1-1] >=k:
            S = (x_order[x2-1][0] - x_order[x1-1][0]) * (y_order[y2-1][1] - y_order[y1-1][1])
            ans = min(ans, S)
print(ans)

Submission status: Accepted

Solution code:
import itertools

def main():
  n,k = map(int, input().split())
  xy = [tuple(map(int, input().split())) for i in range(n)]
  INF = 10 ** 20
  ans = INF
  for i in itertools.combinations(xy,2):
    max_x,min_x = -INF,INF
    for x,Y in i:
      max_x = max(max_x,x)
      min_x = min(min_x,x)
    for j in itertools.combinations(xy,2):
      max_y,min_y = -INF,INF
      for X,y in j:
        max_y = max(max_y,y)
        min_y = min(min_y,y)
      inrec = 0
      for xi,yi in xy:
        if  (min_x <= xi <= max_x) and (min_y <= yi <= max_y):
          inrec += 1
      if (inrec >= k):
        ans = min(ans,(max_x-min_x)*(max_y-min_y))
  print(ans)
  
if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()
sys.setrecursionlimit(10**6)

n,k = na()
xy = []

for i in range(n):
    x,y = na()
    xy.append((x,y))

xy.sort()
ans = 10000000000000000000000000000

for i in range(n):
    for j in range(i+1, n):
        x = xy[j][0] - xy[i][0]
        yy = sorted(xy[i:j+1], key=lambda x:x[1])
        for u in range(len(yy)-k+1):
            y = yy[u+k-1][1] - yy[u][1]
            ans = min(ans, y*x)
            
print(ans)

Submission status: Accepted

Solution code:
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())

Xs = sorted(X)
Ys = sorted(Y)
XY = sorted(list(zip(X,Y)))
ans = 1e100
for i in range(n-k+1):
    for j in range(i+k-1,n):
        w = Xs[j] - Xs[i]
        XYs = sorted(XY[i:j+1],key = lambda x:x[1])
        h = 1e100
        for l in range(len(XYs) - k + 1):
            h = min(h, XYs[l + k - 1][1] - XYs[l][1])
        ans = min(ans , h*w)
print(ans)

Submission status: Accepted

Solution code:
# solution

import io
import math
import scipy.sparse
import numpy

nim, mike = map(int, input().split())
array = [list(map(int, input().split())) for i in range(nim)]

answer = 10**100
sortx = sorted(array, key = lambda x: x[0])
for a, pt1 in enumerate(sortx[:nim-mike+1]):
    for b, pt2 in enumerate(sortx[a+mike-1:]):
        #print(a,b)
        sorty = sorted(sortx[a:a+mike+b], key = lambda x: x[1])
        sorty_len = len(sorty)
        for c, pt3 in enumerate(sorty[:sorty_len-mike+1]):
            #print(len(sorty), c, k)
            pt4 = sorty[c+mike-1]
            #print(pt1, pt2, pt3, pt4)
            if pt3[1] <= pt1[1] and pt3[1] <= pt2[1] and pt4[1] >= pt1[1] and pt4[1] >= pt2[1]:
                answer = min(answer, (pt2[0] - pt1[0]) * (pt4[1] - pt3[1]))
print(answer)

Submission status: Accepted

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

MAX = 10**9
MIN = -1 * MAX
def check(x_r, x_l, y_t, y_b):
    tl = [MIN, MAX]
    br = [MAX, MIN]
    if x_r == x_l or y_t == y_b:
        return False, -1

    tl[0] = max(tl[0], xy[x_l][0])
    tl[1] = min(tl[1], xy[y_t][1])
    br[0] = min(br[0], xy[x_r][0])
    br[1] = max(br[1], xy[y_b][1])

    # count k
    cnt = 0
    for i in range(n):
        if tl[0] <= xy[i][0] <= br[0] and br[1] <= xy[i][1] <= tl[1]:
            cnt += 1
    if cnt < k:
        return False, -1
    area = (br[0] - tl[0]) * (tl[1] - br[1])
    return True, area

INF = 10**20
ans = INF
for a in range(n):
    for b in range(n):
        if a == b:
            continue
        if xy[a][0] < xy[b][0]:
            continue
        for c in range(n):
            for d in range(n):
                if c == d:
                    continue
                if xy[c][1] < xy[d][1]:
                    continue
                f, area = check(a, b, c, d)
                if f:
                    ans = min(ans, area)
print(ans)

Submission status: Accepted

Solution code:
n,K=map(int,input().split())
S=[[0 for i in range(n+1)] for j in range(n+1)]
p=[list(map(int,input().split())) for i in range(n)]
p.sort(key=lambda x:x[1])
for i in range(n):
    p[i].append(i)
p.sort()
y=[0]*n
for i in range(n):
    y[i]=p[i][2]
for i in range(n):
    S[i+1][y[i]+1]=1
X=[p[i][0] for i in range(n)]
Y=[p[i][1] for i in range(n)]
X.sort();Y.sort()
for i in range(1,n+1):
    for j in range(1,n+1):
        S[i][j]=S[i][j]+S[i][j-1]+S[i-1][j]-S[i-1][j-1]
ans=10**20
for i in range(n):
    for j in range(n):
        for k in range(i+1,n+1):
            for l in range(j+1,n+1):
                if S[k][l]-S[k][j]-S[i][l]+S[i][j]>=K:
                    #print(S[k][l]-S[k][j]-S[i][l]+S[i][j])
                    if ans > (X[k-1]-X[i])*(Y[l-1]-Y[j]):
                        ans = (X[k-1]-X[i])*(Y[l-1]-Y[j])
                #print(ans)
print(ans)

Submission status: Accepted

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

ans = float('inf')
sx = sorted(x)
sy = sorted(y)
for xi in range(N):
    for xj in range(xi+1,N):
        for yi in range(N):
            for yj in range(yi+1,N):
                lx = sx[xi]
                rx = sx[xj]
                by = sy[yi]
                uy = sy[yj]
                cnt = 0
                for i in range(N):
                    if lx <= x[i] <= rx and by <= y[i] <= uy:
                        cnt += 1
                if cnt >= K:
                    area = (rx-lx)*(uy-by)
                    ans = min(ans,area)
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import *
import heapq
import math
import bisect
import copy
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

n,k=map(int,input().split())
xy=[list(map(int,input().split())) for i in range(n)]
ru=[[0]*(n+1) for i in range(n+1)]
lst=sorted(xy)
lst2=sorted(xy,key=lambda x: x[1])

for i in range(n):
    for j in range(n):
        flag=0
        for l in range(n):
            if xy[l]==[lst[i][0],lst2[j][1]]:
                flag=1
        if flag:
            ru[i+1][j+1]=1
        ru[i+1][j+1]+=ru[i+1][j]+ru[i][j+1]-ru[i][j]
# print(ru)
xdic=defaultdict(int)
ydic=defaultdict(int)
for i in range(n):
    xdic[lst[i][0]]=i+1
    ydic[lst2[i][1]]=i+1
# print(xdic)
# print(ydic)
lst=[0]*n
lst2=[0]*n
for i in range(n):
    x,y=xy[i]
    lst[i],lst2[i]=x,y
lst,lst2=list(permutations(lst,2)),list(permutations(lst2,2))
ans=float('inf')
for i in range(len(lst)):
    xl,xr=min(lst[i]),max(lst[i])
    for j in range(len(lst2)):
        yl,yr=min(lst2[j]),max(lst2[j])
        # print(ru[xdic[xr]][ydic[yr]]-ru[xdic[xr]][ydic[yl]-1]-ru[xdic[xl]-1][ydic[yr]]+ru[xdic[xl]-1][ydic[yl]-1])
        if ru[xdic[xr]][ydic[yr]]-ru[xdic[xr]][ydic[yl]-1]-ru[xdic[xl]-1][ydic[yr]]+ru[xdic[xl]-1][ydic[yl]-1] >=k:
            ans=min(ans,(xr-xl)*(yr-yl))
print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

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())

xc = list(combinations(x,2))
yc = list(combinations(y,2))
ans = 4*10**18

for yy in yc:
    u = max(yy)
    d = min(yy)
    for xx in xc:
        r = max(xx)
        l = min(xx)
        count = 0
        for i in range(n):
            if l <= x[i] <=r and d <= y[i] <=u: count += 1
        if count >= k:
            ans = min(ans, (u-d)*(r-l))

print(ans)

Submission status: Accepted

Solution code:

import itertools as it

from functools import *
import sys
sys.setrecursionlimit(100000)
input = sys.stdin.readline


def acinput():
    return list(map(int, input().split(" ")))


def II():
    return int(input())



N, K = acinput()


ary = [acinput() for i in range(N)]
x = list(map(lambda x: x[0], sorted(ary, key=lambda s: s[0])))
y = list(map(lambda x: x[1], sorted(ary, key=lambda x: x[1])))


#print(list(it.combinations(y,2)))
#print(list(x))

res = 10**20
for sy in it.combinations(y, 2):
    #print(sy)
    for sx in it.combinations(x, 2):
        #print(sx)
        #print(sy, sx)
        count = 0
        for sa in ary:
            
            if sy[0] <= sa[1] and sa[1] <= sy[1]:
                if sx[0] <= sa[0] and sa[0] <= sx[1]:
                    count += 1

        #print(count)
        if count >= K:
            #dx = np.diff(sx)[0]
            #dy = np.diff(sy)[0]
            dx=sx[1]-sx[0]
            dy=sy[1]-sy[0]
            #print(dx,dy)
            res = min(res, dx*dy)
            #print(res)

print(res)

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby
    #from itertools import product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

    n,k = map(int, input().split())
    xy = [list(map(int, input().split())) for _ in range(n)]
    x = sorted(xy, key=lambda a: a[0])
    y = sorted(xy, key=lambda a: a[1])

    res = 10**20
    for l in range(n):
        for r in range(l+1, n):
            for b in range(n):
                for t in range(b+1, n):
                    cnt = 0
                    for vx, vy in x[l:r+1]:
                        if y[b][1] <= vy <= y[t][1]:
                            cnt += 1
                        if cnt >= k:
                            res = min(res, (x[r][0]-x[l][0])*(y[t][1]-y[b][1]))
                            break
    print(res)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import itertools

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

X = sorted([x for x, _ in P])
Y = sorted([y for _, y in P])
dict_x = {v: k + 1 for k, v in enumerate(X)}
dict_y = {v: k + 1 for k, v in enumerate(Y)}

table = [[0] * (N + 1) for _ in range(N + 1)]
for x, y in P:
    table[dict_y[y]][dict_x[x]] = 1

for x in range(N + 1):
    for y in range(N):
        table[y + 1][x] += table[y][x]
for y in range(N + 1):
    for x in range(N):
        table[y][x + 1] += table[y][x]

ans = float('inf')
for x1, x2 in itertools.combinations(range(N), 2):
    for y1, y2 in itertools.combinations(range(N), 2):
        if table[y2 + 1][x2 + 1] - table[y2 + 1][x1] - table[y1][x2 + 1] + table[y1][x1] >= K:
            ans = min(ans, (X[x2] - X[x1]) * (Y[y2] - Y[y1]))
print(ans)

Submission status: Accepted

Solution code:
n,k= map(int,input().split())
grid=[]
gridx=set()
gridy=set()
for i in range(n):
    x,y= map(int,input().split())
    grid.append((x,y))
    gridx.add(x)
    gridy.add(y)
gridxl = sorted(gridx)
xlen = len(gridxl)
gridyl = sorted(gridy)
ylen = len(gridyl)
atable = [[0 for _ in range(ylen+1)] for _ in range(xlen+1)]
for i in range(n):
    (px,py) = grid[i]
    xid = gridxl.index(px)
    yid = gridyl.index(py)
    atable[yid+1][xid+1]=1
for i in range(1,ylen+1):
    for j in range(1,xlen+1):atable[i][j]+=atable[i][j-1]
for j in range(1,xlen+1):
    for i in range(1,ylen+1):atable[i][j]+=atable[i-1][j]
gmin = 99999999999999999999
for x1 in range(1,xlen):
    for x2 in range(x1,xlen+1):
        for y1 in range(1,ylen):
            for y2 in range(y1,ylen+1):
                a = atable[y2][x2]
                b = atable[y1-1][x2]
                c = atable[y2][x1-1]
                d = atable[y1-1][x1-1]
                rui = a - b - c + d
                if rui>=k:
                    r = (gridxl[x2-1]-gridxl[x1-1])*(gridyl[y2-1]-gridyl[y1-1])
                    if gmin>r:
                        gmin = min(gmin,r)                  
print(gmin)

Submission status: Accepted

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

xy=sorted(xy, key=lambda x:x[0])
#print(xy)

lst=[]
for left in range(0, N-K+1):
    for right in range(left+K-1,N):
        #print(left, right)
        W = xy[right][0] - xy[left][0]
        #print(W)
        temp=sorted(xy[left:right+1], key=lambda x:x[1])
        #print(temp)
        #含まれる点の個数はright-left+1個
        for bottom in range(0, right-left+1 - K+1):
            #print('W', W, 'bottom',bottom)
            H = temp[bottom+K-1][1] - temp[bottom][1]
            #print('H', H)
            lst.append(H * W)
#print('lst',lst)
print(min(lst))

Submission status: Accepted

Solution code:
#075_D
n, k = map(int, input().split())
xy = [tuple(map(int, input().split())) for _ in range(n)]
ans = 10 ** 50
xy.sort()
for l in range(0, n):
    for r in range(l+k-1, n):
        y = [xy[i][1] for i in range(l, r+1)]
        y.sort()
        h = 10 ** 50
        for i in range(len(y)-k+1):
            h = min(h, y[i+k-1] - y[i])
        ans = min(ans, h * (xy[r][0] - xy[l][0]))
print(ans)

Submission status: Accepted

Solution code:

n,k=map(int,input().split())
x=[0]*n
y=[0]*n
a=[]
for i in range(n):
  x[i],y[i]=map(int,input().split())
  a.append((x[i],y[i]))
ans=4*(10**18)
x.sort()
y.sort()
for i in range(n-1):
  for j in range(i+1,n):
    for l in range(n-1):
      for m in range(l+1,n):
        L=x[i]
        R=x[j]
        D=y[l]
        U=y[m]
        if L==R or U==D:
          continue
        cnt=0
        for s in a:
          if L<=s[0]<=R and D<=s[1]<=U:
            cnt+=1
        if cnt>=k:
          ans=min(ans,(R-L)*(U-D))
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
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()
xary = []; yary = []
a = []
for i in range(n):
    x,y = inpl()
    xary.append(x)
    yary.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)

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.append(x)
        yary.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()