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:
import itertools
import sys

import numpy as np

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

N, K = list(map(int, input().split()))
XY = np.array([list(map(int, input().split())) for _ in range(N)])
X = XY[:, 0]
Y = XY[:, 1]
X.sort()
Y.sort()

ans = INF
for xi, xj in itertools.combinations(range(N), r=2):
    yi = 0
    yj = 1
    while yj < N:
        L, r = min(X[xi], X[xj]), max(X[xi], X[xj])
        b, u = min(Y[yi], Y[yj]), max(Y[yi], Y[yj])
        count = np.sum((L <= X) & (X <= r) & (b <= Y) & (Y <= u))
        if count >= K:
            ans = min(ans, (r - L) * (u - b))
            yi += 1
        else:
            yj += 1
        if yi == yj:
            yj += 1
print(ans)

Submission status: Wrong Answer

Solution code:
from copy import deepcopy
N,K=map(int,input().split())
xy=[]
X=[]
Y=[]
for i in range(N):
    x,y=map(int,input().split())
    X.append(x)
    Y.append(y)
    xy.append([x,y])
a=max(X)-min(X)
b=max(Y)-min(Y)
ans=a*b
for i in range(N-K):
    for j in range(len(X)):
        X_=deepcopy(X)
        Y_=deepcopy(Y)
        X_.pop(j)
        Y_.pop(j)
        a=max(X_)-min(X_)
        b=max(Y_)-min(Y_)
        if ans>=a*b:
            J=j
            ans=a*b
    X.pop(J)
    Y.pop(J)
print(ans)

Submission status: Wrong Answer

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

P = [list(map(int,input().split())) for i in range(N)]

A = sorted(P, key=lambda x: x[0])
AY = [A[i][1] for i in range(N)]
B = sorted(P, key=lambda x: x[1])
BX = [A[i][0] for i in range(N)]

ans = float("inf")

for i in range(N-K+1) :
    ha = A[i+K-1][0] - A[i][0]
    wa = max(AY[i:i+K]) - min(AY[i:i+K])
    
    hb = max(BX[i:i+K]) - min(BX[i:i+K])
    wb = B[i+K-1][1] - B[i][1]
    
    ans = min(ans, ha*wa, hb*wb)

print(ans)

Submission status: Wrong Answer

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

P = [list(map(int,input().split())) for i in range(N)]

A = sorted(P, key=lambda x: x[0])
B = sorted(P, key=lambda x: x[1])

ans = float("inf")

for i in range(N-K+1) :
    ha = A[i+K-1][0] - A[i][0]
    wa = abs(A[i+K-1][1] - A[i][1])
    
    hb = abs(B[i+K-1][0] - B[i][0])
    wb = B[i+K-1][1] - B[i][1]
    
    ans = min(ans, ha*wa, hb*wb)

print(ans)

Submission status: Wrong Answer

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

P = [list(map(int,input().split())) for i in range(N)]

P = sorted(P, key=lambda x: x[0])

Y = [P[i][1] for i in range(N)]

ans = float("inf")

for i in range(N-K+1) :
    h = P[i+K-1][0] - P[i][0]
    w = max(Y[i:i+K]) - min(Y[i:i+K])
    
    ans = min(ans, h*w)

P = sorted(P, key=lambda x: x[1])

X = [P[i][0] for i in range(N)]

for i in range(N-K+1) :
    w = P[i+K-1][1] - P[i][1]
    h = max(X[i:i+K]) - min(X[i:i+K])
    
    ans = min(ans, h*w)

print(ans)

Submission status: Wrong Answer

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

P = [list(map(int,input().split())) for i in range(N)]

P = sorted(P, key=lambda x: x[0])

Y = [P[i][1] for i in range(N)]

ans = float("inf")

for i in range(N-K+1) :
    h = P[i+K-1][0] - P[i][0]
    w = max(Y[i:i+K]) - min(Y[i:i+K])
    
    ans = min(ans, h*w)

print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
import itertools
n,k=map(int,input().split())
X,Y,XY=[0]*n,[0]*n,[0]*n
X.sort()
Y.sort()
for i in range(n):
  x,y=map(int,input().split())
  X[i],Y[i],XY[i]=x,y,[x,y]
def count(x1,x2,y1,y2):
  ct=0
  for x,y in XY:
    if x1<=x<=x2 and y1<=y<=y2:
      ct+=1
  return ct
ans=float("inf")
for x1,x2 in itertools.combinations(X,2):
  for y1,y2 in itertools.combinations(Y,2):
    if count(x1,x2,y1,y2)==k:
      ans=min(ans,abs((x1-x2)*(y1-y2)))
print(ans)

Submission status: Wrong Answer

Solution code:
from operator import itemgetter

n,k = map(int, input().split())
z = [list(map(int, input().split())) for i in range(n)]

ymax = max(z,key=itemgetter(1))[1]
ymin = min(z,key=itemgetter(1))[1]
xmax = max(z,key=itemgetter(0))[0]
xmin = min(z,key=itemgetter(0))[0]
ans = (ymax-ymin)*(xmax-xmin)

while n!=k:
    a = []
    for i in range(n):
        zz = z[:i]+z[i+1:]
        ymax = max(zz, key=itemgetter(1))[1]
        ymin = min(zz, key=itemgetter(1))[1]
        xmax = max(zz, key=itemgetter(0))[0]
        xmin = min(zz, key=itemgetter(0))[0]
        a.append((ymax-ymin)*(xmax-xmin))
    n-=1
    ans = min(a)
    z.pop(a.index(ans))

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

dots = XY[:]

import sys
INT_MAX = sys.maxsize

#x_dots = [(x, y) for x, y in dots]
#x_dots = sorted(x_dots)
#y_dots = [(x, y) for x, y in dots]
#y_dots = sorted(y_dots, key=lambda x: x[1])

ans = INT_MAX

for left_i, (left_p_x, _) in enumerate(dots):
    for right_i, (right_p_x, _) in enumerate(dots[left_i:]):
        if left_p_x > right_p_x:
            left_p_x, right_p_x = right_p_x, left_p_x
        for under_i, (_, under_p_y) in enumerate(dots):
            for top_i, (_, top_p_y) in enumerate(dots[under_i:]):
                if under_p_y > top_p_y:
                    under_p_y, top_p_y = top_p_y, under_p_y
                
                counter = 0
                for x, y in dots:
                    if left_p_x <= x and x <= right_p_x and under_p_y <= y and y <= top_p_y:
                        counter += 1
                
                if counter >= K:
                    area = (top_p_y-under_p_y) * (right_p_x-left_p_x)
                    ans = min(ans, area)


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

dots = XY[:]

import sys
INT_MAX = sys.maxsize

#x_dots = [(x, y) for x, y in dots]
#x_dots = sorted(x_dots)
#y_dots = [(x, y) for x, y in dots]
#y_dots = sorted(y_dots, key=lambda x: x[1])

ans = INT_MAX

for left_i, (left_p_x, _) in enumerate(dots):
    for right_i, (right_p_x, _) in enumerate(dots[left_i:]):
        for under_i, (_, under_p_y) in enumerate(dots):
            for top_i, (_, top_p_y) in enumerate(dots[under_i:]):
                counter = 0
                for x, y in dots:
                    if left_p_x <= x and x <= right_p_x and under_p_y <= y and y <= top_p_y:
                        counter += 1
                
                if counter >= K:
                    area = (top_p_y-under_p_y) * (right_p_x-left_p_x)
                    ans = min(ans, area)


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

dots = XY[:]

import sys
INT_MAX = sys.maxsize

x_dots = [(x, y) for x, y in dots]
x_dots = sorted(x_dots)
y_dots = [(x, y) for x, y in dots]
y_dots = sorted(y_dots, key=lambda x: x[1])

ans = INT_MAX

for left_i, left_p in enumerate(x_dots):
    for right_i, right_p in enumerate(x_dots[left_i:]):
        for under_i, under_p in enumerate(y_dots):
            for top_i, top_p in enumerate(y_dots[under_i:]):
                counter = 0
                for x, y in x_dots[left_i:right_i+1]:
                    if under_p[1] <= y and y <= top_p[1]:
                        counter += 1
                
                if counter >= K:
                    area = (top_p[1]-under_p[1]) * (right_p[0]-left_p[0])
                    ans = min(ans, area)


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

dots = XY[:]

import sys
INT_MAX = sys.maxsize

x_dots = [(x, y) for x, y in dots]
x_dots = sorted(x_dots)
y_dots = [(x, y) for x, y in dots]
y_dots = sorted(y_dots, key=lambda x: x[1])

ans = INT_MAX

for left_i, left_p in enumerate(x_dots):
    for right_i, right_p in enumerate(x_dots[left_i:]):
        for under_i, under_p in enumerate(y_dots):
            for top_i, top_p in enumerate(y_dots[under_i:]):
                counter = 0
                for x, y in x_dots[left_i:right_i+1]:
                    if under_p[1] <= y and y <= top_p[1]:
                        counter += 1
                
                if counter >= K:
                    area = (top_p[1]-under_p[1]) * (right_p[0]-left_p[1])
                    ans = min(ans, area)


print(ans)

Submission status: Wrong Answer

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

z.sort()

ans = float('inf')

i = 0

while i+k<=n:
    ymax = 0
    ymin = float('inf')
    for j in range(i,i+k):
        ymax = max(ymax,z[j][1])
        ymin = min(ymin,z[j][1])
    ans = min(ans,(z[i+k-1][0]-z[i][0])*(ymax-ymin))
    i+=1

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))
    
dots = XY[:]

import sys
INT_MAX = sys.maxsize

import itertools
ans = INT_MAX
for sub_dots in itertools.combinations(dots, K):
    #print(sub_dots)
    sub_x = [x for x,y in sub_dots]
    sub_y = [x for x,y in sub_dots]
    min_x = min(sub_x)
    min_y = min(sub_y)
    max_x = max(sub_x)
    max_y = max(sub_y)
    area = (max_x-min_x) * (max_y-min_y)
    ans = min(ans, area)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
#from collections import deque
#import bisect
#import heapq

N,K=[int(val) for val in input().split()]
#print(N,K)
#deque_x=deque()
#deque_y=deque()
list_x=list()
list_y=list()

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

#print(list_x,list_y)
#print(list_x[0:0+K])
minx=list_x[0+K-1]-list_x[0]
miny=list_y[0+K-1]-list_y[0]

for i in range(1,N-K+1):
  tmp=list_x[i+K-1]-list_x[i]
  minx=min(tmp,minx)
  tmpy=list_y[i+K-1]-list_y[i]
  miny=min(tmp,miny)
  
print(minx*miny)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
#from collections import deque
#import bisect
#import heapq

N,K=[int(val) for val in input().split()]
#print(N,K)
#deque_x=deque()
#deque_y=deque()
list_x=list()
list_y=list()

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

print(list_x,list_y)
#print(list_x[0:0+K])
minx=list_x[0+K-1]-list_x[0]
miny=list_y[0+K-1]-list_y[0]

for i in range(1,N-K+1):
  tmp=list_x[i+K-1]-list_x[i]
  minx=min(tmp,minx)
  tmpy=list_y[i+K-1]-list_y[i]
  miny=min(tmp,miny)
  
print(minx*miny)

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
xy = [list(map(int,input().split())) for _ in range(n)]
squares = []
for i in range(len(xy)):
    x1 = xy[i][0]
    for j in range(len(xy)):
        x2 = xy[j][0]
        for k in range(len(xy)):
            y1 = xy[k][1]
            for l in range(len(xy)):
                y2 = xy[l][1]
                square = (min(x1,x2),max(x1,x2),min(y1,y2),max(y1,y2))
                squares.append(square)
ans = float('inf')
for x1,x2,y1,y2 in squares:
    points = 0
    for x,y in xy:
        if x1<=x<=x2 and y1<=y<=y2:
            points+=1
    if points==k:
        ans = min(ans,(x2-x1)*(y2-y1))
print(ans)

Submission status: Wrong Answer

Solution code:
from functools import reduce
import math

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

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

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

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

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

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

Submission status: Wrong Answer

Solution code:
from functools import reduce
import math

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

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

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

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

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

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

Submission status: Wrong Answer

Solution code:
from numpy import*
a,b=map(int,input().split())
c=array([list(map(int,input().split()))+[i]for i in range(a)]).astype(float64)
x=median([s for s,t,r in c])
y=median([t for s,t,r in c])
c[:,0]-=x
c[:,1]-=y
d=sorted(c,key=lambda x:min(abs(x[0]),abs(x[1])))

maax=-float("inf")
miix=float("inf")
maay=-float("inf")
miiy=float("inf")
for i in range(b):
    s,t,r=c[int(d[i][2])]
    maax=max(maax,s)
    miix=min(miix,s)
    maay=max(maay,t)
    miiy=min(miiy,t)
    
print(int((maax-miix)*(maay-miiy)))

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())

xy = sorted([tuple(map(int, input().split())) for _ in range(n)])
ans = None
for i in range(n-k+1):
  if ans == None:
    ans = (xy[i+k-1][0] - xy[i][0]) * (max([y for _, y in xy[i:i+k]]) - min([y for _, y in xy[i:i+k]]))
  else:
    tmp_ans = (xy[i+k-1][0] - xy[i][0]) * (max([y for _, y in xy[i:i+k]]) - min([y for _, y in xy[i:i+k]]))
    if tmp_ans < ans:
      ans = tmp_ans

xy = sorted(xy, key=lambda x: x[1])
for i in range(n-k+1):
  tmp_ans = (xy[i+k-1][1] - xy[i][1]) * (max([x for x, _ in xy[i:i+k]]) - min([x for x, _ in xy[i:i+k]]))
  if tmp_ans < ans:
    ans = tmp_ans
print(ans)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())

xy = sorted([tuple(map(int, input().split())) for _ in range(n)])
ans = None
for i in range(n-k+1):
  if ans == None:
    ans = (xy[i+k-1][0] - xy[i][0]) * (max([y for _, y in xy[i:i+k]]) - min([y for _, y in xy[i:i+k]]))
  else:
    tmp_ans = (xy[i+k-1][0] - xy[i][0]) * (max([y for _, y in xy[i:i+k]]) - min([y for _, y in xy[i:i+k]]))
    if tmp_ans < ans:
      ans = tmp_ans
print(ans)

Submission status: Wrong Answer

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

INF = float('inf')
dp = [[[INF,-INF,INF,-INF] for i in range(K+1)] for j in range(N+1)]

def space(arr):
    if arr[0] == arr[1] and arr[2] == arr[3]:
        return INF
    else:
        return ( arr[0] - arr[1])*( arr[2] - arr[3])

for i in range(1,N+1):
    dp[i][1] = [src[i-1][0],src[i-1][0],src[i-1][1],src[i-1][1]]

for i in range(1,N):
    for j in range(1,K+1):
        dp[i + 1][j] = dp[i][j].copy() if space(dp[i][j]) < space(dp[i + 1][j]) else dp[i + 1][j]
        if j != K:
            tmp = [min(dp[i][j][0], src[i][0]), max(dp[i][j][1], src[i][0]), min(dp[i][j][2], src[i][1]), max(dp[i][j][3], src[i][1])]
            dp[i + 1][j + 1] = tmp.copy() if space(tmp) < space(dp[i + 1][j + 1]) else dp[i + 1][j + 1]

print(space(dp[N][K]))

Submission status: Wrong Answer

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

INF = float('inf')
dp = [[[INF,-INF,INF,-INF] for i in range(K+1)] for j in range(N+1)]

def space(arr):
    if arr[0] == arr[1] and arr[2] == arr[3]:
        return INF
    else:
        return ( arr[0] - arr[1])*( arr[2] - arr[3])

for i in range(1,N+1):
    dp[i][1] = [src[i-1][0],src[i-1][0],src[i-1][1],src[i-1][1]]

for i in range(1,N):
    for j in range(1,K):
        dp[i + 1][j] = dp[i][j].copy() if space(dp[i][j]) < space(dp[i + 1][j]) else dp[i + 1][j]
        if j != K:
            tmp = [min(dp[i][j][0], src[i][0]), max(dp[i][j][1], src[i][0]), min(dp[i][j][2], src[i][1]), max(dp[i][j][3], src[i][1])]
            dp[i + 1][j + 1] = tmp.copy() if space(tmp) < space(dp[i + 1][j + 1]) else dp[i + 1][j + 1]

print(space(dp[N][K]))

Submission status: Wrong Answer

Solution code:
import sys, os

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

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


    pts = []
    for i in range(n):
        x, y = f()
        pts.append((x,y))
    
    minarea = int(1e19)
    for i in range(n):
        for j in range(n):
            if i==j:
                continue
            minx = min(pts[i][0], pts[j][0])
            maxx = max(pts[i][0], pts[j][0])
            miny = min(pts[i][1], pts[j][1])
            maxy = max(pts[i][1], pts[j][1])
            cnt = 0
            for s in range(n):
                if pts[s][0] in range(minx, maxx+1) and pts[s][1] in range(miny, maxy+1):
                    cnt += 1

            if cnt>=k:
                minarea = min(minarea, (maxx - minx)*(maxy - miny))
        
    print(minarea)



solve()

Submission status: Wrong Answer

Solution code:
import sys, os

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

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


    pts = []
    for i in range(n):
        x, y = f()
        pts.append((x,y))
    
    minarea = int(1e19)
    for i in range(n):
        for j in range(n):
            if i==j:
                continue
            minx = min(pts[i][0], pts[j][0])
            maxx = max(pts[i][0], pts[j][0])
            miny = min(pts[i][1], pts[j][1])
            maxy = max(pts[i][1], pts[j][1])
            cnt = 0
            for s in range(n):
                if pts[s][0] in range(minx, maxx+1) and pts[s][1] in range(miny, maxy+1):
                    cnt += 1
            print(cnt, (maxx - minx)*(maxy - miny))
            if cnt>=k:
                minarea = min(minarea, (maxx - minx)*(maxy - miny))
        
    print(minarea)



solve()

Submission status: Wrong Answer

Solution code:
import sys, os

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

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

    pts = []
    for i in range(n):
        x, y = f()
        pts.append((x,y))
    

    minarea = int(1e9)
    for i in range(n):
        for j in range(n):
            if i==j:
                continue
            minx = min(pts[i][0], pts[j][0])
            maxx = max(pts[i][0], pts[j][0])
            miny = min(pts[i][1], pts[j][1])
            maxy = max(pts[i][1], pts[j][1])
            cnt = 0
            for s in range(n):
                if pts[s][0] in range(minx, maxx+1) and pts[s][1] in range(miny, maxy+1):
                    cnt += 1

            if cnt>=k:
                minarea = min(minarea, (maxx - minx)*(maxy - miny))
        
    print(minarea)



solve()

Submission status: Wrong Answer

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

	points.sort(key=lambda x:x[0])
	ans = (max_x-min_x)*(max_y-min_y)
	for lr in range(1, N-K+1):
		for l in range(lr):
			this_points = list(points[l:N-lr+l])
			w = this_points[-1][0]-this_points[0][0]
			if w == 0:
				continue
			this_points.sort(key=lambda x:x[1])
			for t in range(N-K-lr+1):
				if N-t-lr-1 <= t:
					break
				h = this_points[N-t-lr-1][1] - this_points[t][1]
				ans = min(ans, w*h)
	print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys

inf = float('inf')

def calc_s(x: "List[int]", y: "List[int]"):
    return (max(x) - min(x)) * (max(y) - min(y))


def solve(N: int, K: int, x: "List[int]", y: "List[int]"):
    for i in range(N-K):
        s_min = inf
        todel = None
        for j in range(N-i):
            s_temp = calc_s(x[:j] + x[j+1:], y[:j] + y[j+1:])
            if s_temp < s_min:
                s_min = s_temp
                todel = j
        del x[todel]
        del y[todel]

    print(calc_s(x, y))
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    x = [int()] * (N)  # type: "List[int]" 
    y = [int()] * (N)  # type: "List[int]" 
    for i in range(N):
        x[i] = int(next(tokens))
        y[i] = int(next(tokens))
    solve(N, K, x, y)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys

inf = float('inf')

def solve(N: int, K: int, x: "List[int]", y: "List[int]"):
    V = [(x[i], y[i]) for i in range(N)]
    V.sort()
    X = [v[0] for v in V]
    Y = [v[1] for v in V]
    res = inf
    for i in range(N-K+1):
        delta_x = X[i+K-1] - X[i]
        delta_y = max(Y[i:i+K]) - min(Y[i:i+K])
        s = delta_x * delta_y
        if s < res:
            res = s

    print(res)
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    x = [int()] * (N)  # type: "List[int]" 
    y = [int()] * (N)  # type: "List[int]" 
    for i in range(N):
        x[i] = int(next(tokens))
        y[i] = int(next(tokens))
    solve(N, K, x, y)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

ans = 10 ** 19
for a in range(N):
    for b in range(a+1, N):
        for c in range(N):
            for d in range(c+1, N):
                x0 = data[a][0]
                x1 = data[b][0]
                y0 = data[c][1]
                y1 = data[d][1]

                count = 0
                for i, j in data:
                    if x0 <= i <= x1 and y0 <= j <= y1:
                        count += 1
                if count >= K:
                    ans = min(ans, (x1 - x0)*(y1 - y0))

print(ans)

Submission status: Wrong Answer

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

x.sort()
y.sort()
ans = abs(x[0]-x[-1])*abs(y[0]-y[-1])
for i in range(N):
    xi = x[i]
    for j in range(N):
        yi = y[j]
        for k in range(i, N):
            xj = x[k]
            for m in range(j, N):
                yj = y[m]
                cnt = 0
                for n in range(N):
                    if xi <= x[n] <= xj and yi <= y[n] <= yj:
                        cnt += 1
                if cnt >= K:
                    ans = min(ans, abs(xi-xj)*abs(yi-yj))
print(ans)

Submission status: Wrong Answer

Solution code:
inf = float('inf')

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

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

for i in range(N):
    for j in range(i+1,N):
        for k in range(N):
            for l in range(k+1,N):
                left = X[i]; right = X[j]
                bottom = Y[k]; top = Y[l]
                res = 0
                S = (right-left)*(top-left)
                for px, py in XY:
                    if left <= px <= right and bottom <= py <= top:
                        res += 1
                if res >= K and ans > S:
                    ans = S

print(ans)

Submission status: Wrong Answer

Solution code:
inf = float('inf')

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

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

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

print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
inf = float('inf')

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

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

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

print(ans)