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: Wrong Answer

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

ans = INF

for p in P:
  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))
      
      
      
      
P = [[-xy[0],xy[1]] for xy in P]

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


for p in P:
  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))
      
P = [[xy[0],-xy[1]] for xy in P]

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


for p in P:
  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))
      
P = [[-xy[0],xy[1]] for xy in P]

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


for p in P:
  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: Wrong Answer

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

ans = INF

for p in P:
  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))
      
      
      
      
P = [[-xy[0],xy[1]] for xy in P]

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


for p in P:
  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: Wrong Answer

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

ans = INF

for p in P:
  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))
      
      
      
      
P = [[-xy[0],xy[1]] for xy in P]

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

ans = INF

for p in P:
  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: Wrong Answer

Solution code:
N, K = map(int, input().split())
X, Y = [], []
for _ in range(N):
    x, y = map(int, input().split())
    X.append(x)
    Y.append(y)
X.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 <= X[i] and X[i] <= rx and by <= Y[i] and Y[i] <= uy:
                        num += 1

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

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
XY = []
for _ in range(N):
    x, y = map(int, input().split())
    XY.append((x, y))
XY.sort(key=lambda x: x[0])
ans = float('inf')
for i in range(N-1):
    for j in range(i + 1, N):
        t = XY[i:j+1]
        if len(t) < K:
            continue
        X = [x[0] for x in t]
        Y = [x[1] for x in t]
        # print(X)
        # print(Y)
        area = (max(X) - min(X)) * (max(Y) - min(Y))
        ans = min(ans, area)
print(ans)

Submission status: Wrong Answer

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

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

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)    

answer=float("inf")
for i in range(len(xy_prod_list)):
  x1,y1=xy_prod_list[i]
  for j in range(i+1,len(xy_prod_list)):
    x2,y2=xy_prod_list[j]
    area=abs(x2-x1)*abs(y2-y1)
    if area==0 or area>answer:
      continue

    x1,y1,x2,y2=min(x1,x2),min(y1,y2),max(x1,x2),max(y1,y2)  
    num_inbox=0
    for x,y in xylist:
      if x1<=x<=x2 and y1<=y<=y2:
        num_inbox+=1
        if num_inbox==K:
          break
    
    if num_inbox>=K:
      answer=min(answer,area)
    
print(answer)

Submission status: Wrong Answer

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")
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=0
        while True:
            while r<n and cnt<k:
                cnt+=int(lx<=li[r][0]<=ux)
                if cnt!=k:r+=1
            if cnt<k or not(k-1<=r<=n-1) or not(0<=l<=n-k+1) or r<l:break
            
            ans=min(ans,(ux-lx)*(li[r][1]-li[l][1]))
            cnt-=int(lx<=li[l][0]<=ux)
            l+=1
print(ans)

Submission status: Wrong Answer

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")
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=0
        while True:
            while r<n and cnt<k:
                cnt+=int(lx<=li[r][0]<=ux)
                if cnt!=k:r+=1
            if cnt<k or not(k-1<=r<=n-1) or not(0<=l<=n-k+1) or r<l:break
            
            ans=min(ans,(ux-lx)*(li[r][1]-li[l][1]))
            cnt-=int(lx<=li[l][0]<=ux)
            l-=1
print(ans)

Submission status: Wrong Answer

Solution code:
from operator import itemgetter

n,k = map(int, input().split())
xy = sorted([list(map(int, input().split())) for i in range(n)])
ans = 10 ** 20
for i in range(n-k+1):
  X = xy[i+k-1][0]-xy[i][0]
  ymax = -(10 ** 10)
  ymin = 10 ** 10
  for x,y in xy[i:i+k]:
    ymax = max(ymax,y)
    ymin = min(ymin,y)
  Y = ymax-ymin
  ans = min(ans,X*Y)
xy = sorted(xy,key=itemgetter(1))
for i in range(n-k+1):
  Y = xy[i+k-1][1]-xy[i][1]
  xmax = -(10 ** 10)
  xmin = 10 ** 10
  for x,y in xy[i:i+k]:
    xmax = max(xmax,x)
    xmin = min(xmin,x)
  X = xmax-xmin
  ans = min(ans,X*Y)
print(ans)

Submission status: Wrong Answer

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 = 1000000000000

for i in range(n-k+1):
    for j in range(i+k-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: Wrong Answer

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 = 1000000000000

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: Wrong Answer

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

*point, = map(lambda p: [int(p[0]),int(p[1])], [input().split() for _ in range(N)])
point.sort()
x = list(zip(*point[:K]))[0]
y = list(zip(*point[:K]))[1]

area = abs(x[K-1]-x[0]) * abs(max(y)-min(y))
print(area)

Submission status: Wrong Answer

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

*point, = map(lambda p: [int(p[0]),int(p[1])], [input().split() for _ in range(N)])
point.sort()
x = list(zip(*point[0:K]))[0]
y = list(zip(*point[0:K]))[1]

area = abs(x[K-1]-x[0]) * abs(max(y)-min(y))
print(area)

Submission status: Wrong Answer

Solution code:
N,K = map(int, input().split())
*point, = map(lambda p: [int(p[0]),int(p[1])], [input().split() for _ in range(N)])
point.sort()

area = abs(point[K-1][0]-point[0][0]) * abs(max(list(zip(*point[0:K]))[1])-min(list(zip(*point[0:K]))[1]))
print(area)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)


############ ---- Input Functions ---- ############
def in_int():
    return (int(input()))


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


def in_str():
    s = input()
    return (list(s[:len(s) - 1]))


def in_ints():
    return (map(int, input().split()))


n, k = in_ints()


l = []
for nn in range(n):
    x, y = in_ints()
    l.append((x,y))


ans = sys.maxsize

for i in range(n):
    for j in range(n):
        x, y = min(l[i][0], l[j][0]), min(l[i][1], l[j][1])
        xx, yy = max(l[i][0], l[j][0]), max(l[i][1], l[j][1])
        count  = 0
        for kk in range(n):
            xxx, yyy = l[kk]

            if x <= xxx and xxx<= xx and y <= yyy and yyy <= yy:
                count +=1

        if count >= k :
            ans  = min((yy-y)*(xx-x), ans)


print(ans)

Submission status: Wrong Answer

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')
x.sort()
y.sort()
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 = x[xi]
                rx = x[xj]
                by = y[yi]
                uy = y[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: Wrong Answer

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 = (max(x)-min(x))*(max(y)-min(y))
x.sort()
y.sort()
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 = x[xi]
                rx = x[xj]
                by = y[yi]
                uy = y[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: Wrong Answer

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)]
xy.sort()
lst=[0]*n
lst2=[0]*n
for i in range(n):
    lst[i]=xy[i][0]
    lst2[i]=xy[i][1]
# print(lst)
# print(lst2)
per=list(combinations(lst2,2))
# print(per)
ans=float('inf')
for i in range(n-k+1):
    xl,xr=lst[i],lst[i+k-1]
    for j in range(len(per)):
        yl,yr=min(per[j]),max(per[j])
        cnt=0
        for l in range(n):
            x,y=xy[l]
            if xl<=x<=xr and yl<=y<=yr:
                cnt+=1
        if cnt>=k:
            # print((xl,yl),(xr,yr))
            ans=min(ans,(xr-xl)*(yr-yl))

xy.sort(key=lambda x: x[1])
lst=[0]*n
lst2=[0]*n
for i in range(n):
    lst[i]=xy[i][1]
    lst2[i]=xy[i][0]
# print(lst)
# print(lst2)
per=list(combinations(lst2,2))
# print(per)
# ans=float('inf')
for i in range(n-k+1):
    yl,yr=lst[i],lst[i+k-1]
    for j in range(len(per)):
        xl,xr=min(per[j]),max(per[j])
        cnt=0
        for l in range(n):
            x,y=xy[l]
            if xl<=x<=xr and yl<=y<=yr:
                cnt+=1
        if cnt>=k:
            # print((xl,yl),(xr,yr))
            ans=min(ans,(xr-xl)*(yr-yl))
print(ans)

Submission status: Wrong Answer

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)]
def func(xy):
    lst=[0]*n
    lst2=[0]*n
    for i in range(n):
        lst[i]=xy[i][0]
        lst2[i]=xy[i][1]
    # print(lst)
    # print(lst2)
    per=list(combinations(lst2,2))
    # print(per)
    ans=float('inf')
    for i in range(n-k+1):
        xl,xr=lst[i],lst[i+k-1]
        for j in range(len(per)):
            yl,yr=min(per[j]),max(per[j])
            cnt=0
            for l in range(n):
                x,y=xy[l]
                if xl<=x<=xr and yl<=y<=yr:
                    cnt+=1
            if cnt>=k:
                # print((xl,yl),(xr,yr))
                ans=min(ans,(xr-xl)*(yr-yl))
    return ans

xy.sort()
tmp=func(xy)
for i in range(n):
    xy[i]=[xy[i][1],xy[i][0]]
xy.sort()
tmp2=func(xy)
print(min(tmp,tmp2))

Submission status: Wrong Answer

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)]
xy.sort()
def func():
    lst=[0]*n
    lst2=[0]*n
    for i in range(n):
        lst[i]=xy[i][0]
        lst2[i]=xy[i][1]
    # print(lst)
    # print(lst2)
    per=list(combinations(lst2,2))
    # print(per)
    ans=float('inf')
    for i in range(n-k+1):
        xl,xr=lst[i],lst[i+k-1]
        for j in range(len(per)):
            yl,yr=min(per[j]),max(per[j])
            cnt=0
            for l in range(n):
                x,y=xy[l]
                if xl<=x<=xr and yl<=y<=yr:
                    cnt+=1
            if cnt>=k:
                # print((xl,yl),(xr,yr))
                ans=min(ans,(xr-xl)*(yr-yl))
    return ans

tmp=func()
for i in range(n):
    xy[i]=[xy[i][1],xy[i][0]]
xy.sort()
tmp2=func()
print(min(tmp,tmp2))

Submission status: Wrong Answer

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)]
xy.sort()
def func():
    lst=[0]*n
    lst2=[0]*n
    for i in range(n):
        lst[i]=xy[i][0]
        lst2[i]=xy[i][1]
    # print(lst)
    # print(lst2)
    per=list(combinations(lst2,2))
    # print(per)
    ans=float('inf')
    for i in range(n-k+1):
        xl,xr=lst[i],lst[i+k-1]
        for j in range(len(per)):
            yl,yr=min(per[j]),max(per[j])
            cnt=0
            for l in range(n):
                x,y=xy[l]
                if xl<=x<=xr and yl<=y<=yr:
                    cnt+=1
            if cnt>=k:
                # print((xl,yl),(xr,yr))
                ans=min(ans,(xr-xl)*(yr-yl))
    return ans

tmp=func()
for i in range(n):
    xy[i]=[xy[i][1],xy[i][0]]
tmp2=func()
print(min(tmp,tmp2))

Submission status: Wrong Answer

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)]
xy.sort()
lst=[0]*n
lst2=[0]*n
for i in range(n):
    lst[i]=xy[i][0]
xy.sort(key=lambda x: x[1])
for i in range(n):
    lst2[i]=xy[i][1]
# print(lst)
# print(lst2)

ans=float('inf')
for i in range(n-k+1):
    xl,xr=lst[i],lst[i+k-1]
    for j in range(n-k+1):
        yl,yr=lst2[j],lst2[j+k-1]
        cnt=0
        for l in range(n):
            x,y=xy[l]
            if xl<=x<=xr and yl<=y<=yr:
                cnt+=1
        if cnt>=k:
            # print((xl,yl),(xr,yr))
            ans=min(ans,(xr-xl)*(yr-yl))

print(ans)

Submission status: Wrong Answer

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)]
xy.sort()
lst=[0]*n
lst2=[0]*n
for i in range(n):
    lst[i]=xy[i][0]
xy.sort(key=lambda x: x[1])
for i in range(n):
    lst2[i]=xy[i][1]
# print(lst)
# print(lst2)

ans=float('inf')
for i in range(n-k+1):
    xl,xr=lst[i],lst[i+k-1]
    for j in range(n-k+1):
        yl,yr=lst2[i],lst2[i+k-1]
        cnt=0
        for l in range(n):
            x,y=xy[l]
            if xl<=x<=xr and yl<=y<=yr:
                cnt+=1
        if cnt>=k:
            # print((xl,yl),(xr,yr))
            ans=min(ans,(xr-xl)*(yr-yl))

print(ans)

Submission status: Wrong Answer

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)]
xy.sort()
lst=[0]*n
lst2=[0]*n
for i in range(n):
    lst[i]=xy[i][0]
    lst2[i]=xy[i][1]
# print(lst)
# print(lst2)
per=list(combinations(lst2,2))
# print(per)
ans=float('inf')
for i in range(n-k+1):
    xl,xr=lst[i],lst[i+k-1]
    for j in range(len(per)):
        yl,yr=min(per[j]),max(per[j])
        cnt=0
        for l in range(n):
            x,y=xy[l]
            if xl<=x<=xr and yl<=y<=yr:
                cnt+=1
        if cnt>=k:
            # print((xl,yl),(xr,yr))
            ans=min(ans,(xr-xl)*(yr-yl))
if ans==0:
    lst[n]=0
print(ans)

Submission status: Wrong Answer

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)]
xy.sort()
lst=[0]*n
lst2=[0]*n
for i in range(n):
    lst[i]=xy[i][0]
    lst2[i]=xy[i][1]
print(lst)
print(lst2)
per=list(combinations(lst2,2))
print(per)
ans=float('inf')
for i in range(n-k+1):
    xl,xr=lst[i],lst[i+k-1]
    for j in range(len(per)):
        yl,yr=min(per[j]),max(per[j])
        cnt=0
        for l in range(n):
            x,y=xy[l]
            if xl<=x<=xr and yl<=y<=yr:
                cnt+=1
        if cnt>=k:
            print((xl,yl),(xr,yr))
            ans=min(ans,(xr-xl)*(yr-yl))
if ans==0:
    lst[n]=0
print(ans)

Submission status: Wrong Answer

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)]
xy.sort()
lst=[0]*n
lst2=[0]*n
for i in range(n):
    lst[i]=xy[i][0]
    lst2[i]=xy[i][1]
# print(lst)
# print(lst2)
per=list(combinations(lst2,2))
# print(per)
ans=float('inf')
for i in range(n-k+1):
    xl,xr=lst[i],lst[i+k-1]
    for j in range(len(per)):
        yl,yr=min(per[j]),max(per[j])
        cnt=0
        for l in range(n):
            x,y=xy[l]
            if xl<=x<=xr and yl<=y<=yr:
                cnt+=1
        if cnt>=k:
            ans=min(ans,(xr-xl)*(yr-yl))
if ans==float('inf'):
    print(lst[n+1])
print(ans)