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 sys
input = sys.stdin.readline
def inputs():return [int(x) for x in input().split()]
N,K = inputs()
xy = [inputs() for _ in range(N)]
xy = sorted(xy,key=lambda x: x[1])
xy = sorted(xy,key=lambda x: x[0])
#print(xy)
ans = 10**20
for i in range(N):
  for j in range(i+1,N):
    xy1 = xy[i:j+1]
    miny=min([xy1[i][1] for i in range(j-i+1)])
    maxy=max([xy1[i][1] for i in range(j-i+1)])
    if len([y for x,y in xy1 if miny<y<maxy])>=K-2:
      ans = min(ans,(xy[j][0]-xy[i][0])*(maxy-miny))
    miny=min(xy[i][1],xy[j][1])
    maxy=max(xy[i][1],xy[j][1])
    if len([y for x,y in xy1 if miny<y<maxy])>=K-2:
      ans = min(ans,(xy[j][0]-xy[i][0])*(maxy-miny))
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
n,k=map(int,input().split())
l=[]
for i in range(n):
    l.append(list(map(int,input().split())))
c=itertools.combinations(range(n),k)
ans=100000000000
for i in c:
    x=[]
    y=[]
    for j in i:
        x.append(l[j][0])
        y.append(l[j][1])
    ans=min(ans,(max(x)-min(x))*(max(y)-min(y)))
print(ans)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
l=[]
for i in range(n):
    x,y=map(int,input().split())
    l.append([x,y])
l.sort(key=lambda x:[x[0],x[1]])
def check(l):
    #print(l)
    xmin=ymin=10**20 
    xmax=ymax=-(10**20)
    for a,b in l:
        xmin=min(xmin,a)
        xmax=max(xmax,a)
        ymin=min(ymin,b)
        ymax=max(ymax,b)
    return (xmax-xmin)*(ymax-ymin)
l1=[l[i] for i in range(k)]
mini=check(l1)
for i in range(k,n):
    l1.pop(0)
    l1.append(l[i])
    mini=min(mini,check(l1))
print(mini)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
l=[]
for i in range(n):
    x,y=map(int,input().split())
    l.append([x,y])
l.sort(key=lambda x:[x[0],x[1]])
def check(l):
    xmin=ymin=10**20 
    xmax=ymax=-(10**20)
    for a,b in l:
        xmin=min(xmin,a)
        xmax=max(xmax,a)
        ymin=min(ymin,b)
        ymax=max(ymax,b)
    return (xmax-xmin)*(ymax-ymin)
l1=[l[i] for i in range(k)]
mini=check(l1)
for i in range(k,n):
    l1.pop(0)
    l1.append(l[k])
    mini=min(mini,check(l1))
print(mini)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
xy1=sorted([list(map(int,input().split())) for i in range(n)],key=lambda x:x[0])
xy2=sorted(xy1,key=lambda x:x[1])
z=[]
for i in range(n-k+1):
    h=xy1[i+k-1][0]-xy1[i][0]
    z.append(h*(max(xy1[i:i+k],key=lambda x:x[1])[1]-min(xy1[i:i+k],key=lambda x:x[1])[1]))
for i in range(n-k+1):
    w=xy2[i+k-1][1]-xy2[i][1]
    z.append(w*(max(xy2[i:i+k],key=lambda x:x[0])[0]-min(xy2[i:i+k],key=lambda x:x[0])[0]))
print(min(z))

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
xy1=sorted([list(map(int,input().split())) for i in range(n)],key=lambda x:x[0])
xy2=sorted(xy1,key=lambda x:x[1])
z=[]
for i in range(n-k+1):
    h=xy1[i+k-1][0]-xy1[i][0]
    mink=xy1[i][1]
    maxk=xy1[i][1]
    for j in range(i,i+k):
        mink=min(xy1[j][1],mink)
        maxk=max(xy1[j][1],maxk)
    z.append(h*(maxk-mink))
for i in range(n-k+1):
    w=xy2[i+k-1][1]-xy2[i][1]
    mink=xy2[i][0]
    maxk=xy2[i][0]
    for j in range(i,i+k):
        mink=min(xy2[j][0],mink)
        maxk=max(xy2[j][0],maxk)
    z.append(w*(maxk-mink))
print(min(z))

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
xy1=sorted([list(map(int,input().split())) for i in range(n)],key=lambda x:x[0])
xy2=sorted(xy1,key=lambda x:x[1])
z=[]
for i in range(n-k+1):
    h=xy1[i+k-1][0]-xy1[i][0]
    mink=xy2[i][0]
    maxk=xy2[i][0]
    for j in range(i,i+k):
        mink=min(xy1[j][1],mink)
        maxk=max(xy1[j][1],maxk)
    z.append(h*(maxk-mink))
for i in range(n-k+1):
    w=xy2[i+k-1][1]-xy2[i][1]
    mink=xy1[i][1]
    maxk=xy1[i][1]
    for j in range(i,i+k):
        mink=min(xy2[j][0],mink)
        maxk=max(xy2[j][0],maxk)
    z.append(w*(maxk-mink))
print(min(z))

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
xy1=sorted([list(map(int,input().split())) for i in range(n)],key=lambda x:x[0])
xy2=sorted(xy1,key=lambda x:x[1])
z=[]
for i in range(n-k+1):
    h=xy1[i+k-1][0]-xy1[i][0]
    mink=xy2[n-1][0]
    maxk=xy2[0][0]
    for j in range(i,i+k):
        mink=min(xy1[j][1],mink)
        maxk=max(xy1[j][1],maxk)
    z.append(h*(maxk-mink))
for i in range(n-k+1):
    w=xy2[i+k-1][1]-xy2[i][1]
    mink=xy1[n-1][1]
    maxk=xy1[0][1]
    for j in range(i,i+k):
        mink=min(xy2[j][0],mink)
        maxk=max(xy2[j][0],maxk)
    z.append(w*(maxk-mink))
print(sorted(z)[0])

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.buffer.readline
N, M = map(int, input().split())
P = []
for _ in range(N):
  P.append(list(map(int, input().split())))
P.sort(key = lambda x: (x[0], x[1]))
#print(P)
res = float("inf")
X = [p[0] for p in P]
Y = [p[1] for p in P]
for l in range(N - M + 1):
  for r in range(l + M - 1, N):
    d = min(Y[l: r + 1])
    u = max(Y[l: r + 1])
    #print(l, r, d, u)
    res = min((X[r] - X[l]) * (u - d), res)
#print(res)
P.sort(key = lambda x: (x[1], x[0]))
X = [p[0] for p in P]
Y = [p[1] for p in P]
for d in range(N - M + 1):
  for u in range(d + M - 1, N):
    l = min(X[d: u + 1])
    r = max(X[d: u + 1])
    #print(l, r, d, u)
    res = min((Y[u] - Y[d]) * (r - l), res)
    #print(res)
print(res)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.buffer.readline
N, M = map(int, input().split())
P = []
for _ in range(N):
  P.append(list(map(int, input().split())))
P.sort(key = lambda x: (x[0], x[1]))
#print(P)
res = float("inf")
X = [p[0] for p in P]
Y = [p[1] for p in P]
for l in range(N - M + 1):
  for r in range(l + M - 1, N):
    d = min(Y[l: r + 1])
    u = max(Y[l: r + 1])
    #print(l, r, d, u)
    res = min((X[r] - X[l]) * (u - d), res)
print(res)

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=1e20
for x1 in range(n):
    for x2 in range(i,n):
        tmp=[]
        for i in range(n):
            if x[x1] <= x[i] <= x[x2]: tmp.append(y[i])
        if len(tmp) < k: continue
        r=0
        for l in range(len(tmp)):
            while r-l+1<k and r<len(tmp): r += 1
            if r == len(tmp): break
            ans = min(ans, (abs(x[x1]-x[x2]) * abs(y[l] - y[r])))
print(ans)

Submission status: Wrong Answer

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

XY.sort()
x_list, y_list = [list(l) for l in zip(*XY)]

min_area = 10**24
for i in range(N-K+1):
    xs = x_list[i:i+K]
    ys = y_list[i:i+K]
    area = (xs[-1]-xs[0])*(max(ys)-min(ys))
    min_area = min(
        min_area,
        area
    )

print(min_area)

Submission status: Wrong Answer

Solution code:
print(0)

Submission status: Wrong Answer

Solution code:
import numpy as np
n,k = map(int,input().split())
ary = [list(map(int,input().split())) for _ in range(n)]
ary.sort()
num = np.array(ary,dtype=float)
ans = float("Inf")
for i in range(n-k+1):
    min_a = np.min(num[i:i+k],axis=0)
    max_a = np.max(num[i:i+k],axis=0)
    a = int(max_a[0] - min_a[0])
    b = int(max_a[1] - min_a[1])
    if ans > a * b:
        ans = a * b
ary.sort(key=lambda x:(x[1],x[0]))
num = np.array(ary,dtype=float)
for i in range(n-k+1):
    min_a = np.min(num[i:i+k],axis=0)
    max_a = np.max(num[i:i+k],axis=0)
    a = int(max_a[0] - min_a[0])
    b = int(max_a[1] - min_a[1])
    if ans > a * b:
        ans = a * b
print(ans)

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
A = [list(map(int,input().split())) for _ in range(N)]
s = 10**19
B = sorted(A,key=lambda x:x[0])
for i in range(N-K+1):
    for j in range(K,N-i+1):
        xmin = B[i][0]
        xmax = B[i+j-1][0]
        By = sorted(B[i:i+j],key=lambda x:x[1])
        ymin = By[0][1]
        ymax = By[-1][1]
        s = min(s,(xmax-xmin)*(ymax-ymin))
print(s)

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
A = [list(map(int,input().split())) for _ in range(N)]
s = 10**19
B = sorted(A,key=lambda x:x[0])
for i in range(N-K+1):
    xmin = B[i][0]
    xmax = B[i+K-1][0]
    By = sorted(B[i:i+K],key=lambda x:x[1])
    ymin = By[0][1]
    ymax = By[-1][1]
    s = min(s,(xmax-xmin)*(ymax-ymin))
C = sorted(A,key=lambda x:x[1])
for i in range(N-K+1):
    ymin = C[i][1]
    ymax = C[i+K-1][1]
    Cx = sorted(C[i:i+K],key=lambda x:x[0])
    xmin = Cx[0][0]
    xmax = Cx[-1][0]
    s = min(s,(xmax-xmin)*(ymax-ymin))
print(s)

Submission status: Wrong Answer

Solution code:
import numpy as np
n,k = map(int,input().split())
ary = [list(map(int,input().split())) for _ in range(n)]
ary.sort()
num = np.array(ary,dtype=float)
ans = float("Inf")
for i in range(n-k+1):
    min_a = np.min(num[i:i+k],axis=0)
    max_a = np.max(num[i:i+k],axis=0)
    a = int(max_a[0] - min_a[0])
    b = int(max_a[1] - min_a[1])
    if ans > a * b:
        ans = a * b
ary.sort(key=lambda x:(x[1]))
num = np.array(ary,dtype=float)
for i in range(n-k+1):
    min_a = np.min(num[i:i+k],axis=0)
    max_a = np.max(num[i:i+k],axis=0)
    a = int(max_a[0] - min_a[0])
    b = int(max_a[1] - min_a[1])
    if ans > a * b:
        ans = a * b
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
n,k = map(int,input().split())
ary = [list(map(int,input().split())) for _ in range(n)]
ary.sort()
ary = np.array(ary,dtype=float)
ans = float("Inf")
for i in range(n-k+1):
    min_a = np.min(ary[i:i+k],axis=0)
    max_a = np.max(ary[i:i+k],axis=0)
    a = int(max_a[0] - min_a[0])
    b = int(max_a[1] - min_a[1])
    if ans > a * b:
        ans = a * b
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
import itertools
n,k = map(int,input().split())
ary = np.array([list(map(int,input().split())) for _ in range(n)],dtype=float)
a = list(itertools.combinations(ary,k))
ans = float("Inf")
for i in a:
    min_a = np.min(i,axis=0)
    max_a = np.max(i,axis=0)
    ans = min(ans,(max_a[0] - min_a[0]) * (max_a[1] - min_a[1]))
print(int(ans))

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
x_list = [0]*n
y_list = [0]*n
for i in range(n):
    x_list[i], y_list[i] = map(int, input().split())

x_element = sorted(set(x_list))
y_element = sorted(set(y_list))
ans = float("inf")

for i in range(len(x_element)):
    for j in range(len(y_element)):
        for k in range(i+1, len(x_element)):
            for l in range(j+1, len(y_element)):
                num = 0
                for m in range(n):
                    if x_element[i] <= x_list[m] <= x_element[k] and y_element[j] <= y_list[m] <= y_element[l]:
                        num += 1
                if num >= k:
                    ans = min((x_element[k] - x_element[i]) * (y_element[l] - y_element[j]), ans)

print(ans)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
x_list = [0]*n
y_list = [0]*n
for i in range(n):
    x_list[i], y_list[i] = map(int, input().split())

x_element = list(set(x_list))
y_element = list(set(y_list))
ans = float("inf")

for i in range(len(x_element)):
    for j in range(len(y_element)):
        for k in range(i+1, len(x_element)):
            for l in range(j+1, len(y_element)):
                num = 0
                for m in range(n):
                    x_left = x_element[i]
                    x_right = x_element[k]
                    y_bottom = y_element[j]
                    y_upper = y_element[l]
                    if x_left <= x_list[m] <= x_right and y_bottom <= y_list[m] <= y_upper:
                        num += 1
                    if num >= k:
                        ans = min((x_right - x_left) * (y_upper - y_bottom), ans)

print(ans)

Submission status: Wrong Answer

Solution code:
from operator import itemgetter

n, k = map(int, input().split())
xy_list = [list(map(int, input().split())) for _ in range(n)]
xy_list = sorted(xy_list)
ans = 0
for i in range(n - k + 1):
    start = i
    end = i + k - 1
    xrange = xy_list[end][0] - xy_list[start][0]
    xy_list_part = sorted(xy_list[start:end+1], key=itemgetter(1))
    yrange = xy_list_part[-1][1] - xy_list_part[0][1]
    ans = max(ans, xrange * yrange)
xy_list = sorted(xy_list, key=itemgetter(1))
for i in range(n - k + 1):
    start = i
    end = i + k - 1
    yrange = xy_list[end][1] - xy_list[start][1]
    xy_list_part = sorted(xy_list[start:end+1])
    xrange = xy_list_part[-1][0] - xy_list_part[0][0]
    ans = max(ans, xrange * yrange)
print(ans)

Submission status: Wrong Answer

Solution code:
### reference
#https://atcoder.jp/contests/abc075/submissions/2242350
N,K=map(int,input().split())

points=[tuple(map(int,input().split())) for i in range(N)]
answer=10**19
sortx=sorted(points)
numberx = list(enumerate(sortx))
print(sortx)
print(numberx)

#n-k+1以降を左の頂点とすると点の数が明らかに足りない
for left,(x1,y1) in numberx[:N-K+1]:
  #left+K-1以降を右の頂点にしないと間に足りる点の数が入ってない
  for right,(x2,y2) in numberx[left+K-1:]:
    dx=x2-x1
    #left-rightの間でyについてsort
    sorty=sorted(y for x,y in sortx[left:right+1])
    #K個点を入れた状態で面積を求める
    for y3,y4 in zip(sorty,sorty[K-1:]):
      if y3<=y1 and y3<=y2 and y4>=y1 and y4>=y2:
        answer=min(answer,dx*(y4-y3))
         
print(answer)

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np
input = sys.stdin.readline

def main():
    N, K = map(int, input().split())
    xy = [list(map(int, input().split())) for i in range(N)]
    xy = np.array(sorted(xy, key=lambda x: x[0]))
    ans = int(1e20)
    for i in range(N-K+1):
        ans = min(ans, (xy[i+K-1][0] - xy[i][0]) * (max(xy[i:i+K, 1]) - min(xy[i:i+K, 1])))
    xy = np.array(sorted(xy, key=lambda x: x[1]))
    for i in range(N-K+1):
        ans = min(ans, (xy[i+K-1][1] - xy[i][1]) * (max(xy[i:i+K, 0]) - min(xy[i:i+K, 0])))
    print(int(ans))

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np
input = sys.stdin.readline

def main():
    N, K = map(int, input().split())
    xy = np.array(sorted([list(map(int, input().split())) for i in range(N)]))
    ans = int(1e20)
    for i in range(N-K+1):
        ans = min(ans, (xy[i+K-1][0] - xy[i][0]) * (max(xy[i:i+K, 1]) - min(xy[i:i+K, 1])))
    print(int(ans))

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n, k = map(int,input().split())
xs = []
ys = []
points = []
for _ in range(n):
    x, y = map(int, input().split())
    xs.append(x)
    ys.append(y)
    points.append((x, y))
xs = list(sorted(xs))
ys = list(sorted(ys))
min_ = float('inf')
for i in range(len(xs)):
    for j in range(i+1, len(xs)):
        for k in range(len(ys)):
            for l in range(k+1, len(ys)):
                cnt = 0
                for tx, ty in points:
                    if (xs[i] <= tx <= xs[j]) and (ys[k] <= ty <= ys[l]):
                        cnt += 1
                if cnt >= k:
                    yoko = xs[j] - xs[i]
                    tate = ys[l] - ys[k]
                    men = yoko*tate
                if men <= min_:
                    min_ = men
print(min_)

Submission status: Wrong Answer

Solution code:
n, k = map(int,input().split())
xs = []
ys = []
points = []
for _ in range(n):
    x, y = map(int, input().split())
    xs.append(x)
    ys.append(y)
    points.append((x, y))

                
min_ = float('inf')
for leftx in xs:
    for rightx in xs:
        if leftx >= rightx:
            continue
        for downy in ys:
            for upy in ys:
                if downy >= upy:
                    continue

                for tx, ty in points:
                    if (leftx <= tx <= rightx) and (downy <= ty <= upy):
                        yoko = rightx - leftx
                        tate = upy - downy
                        men = yoko*tate
                        if men < min_:
                            min_ = men

print(min_)

Submission status: Wrong Answer

Solution code:
n, k = map(int,input().split())
xs = []
ys = []
points = []
for _ in range(n):
    x, y = map(int, input().split())
    xs.append(x)
    ys.append(y)
    points.append((x, y))

for leftx in xs:
    for rightx in xs:
        if leftx >= rightx:
            continue
        for downy in ys:
            for upy in ys:
                if downy >= upy:
                    continue
                
                min_ = float('inf')
                for tx, ty in points:
                    if (leftx <= tx <= rightx) and (downy <= ty <= upy):
                        yoko = rightx - leftx
                        tate = upy - downy
                        men = yoko*tate
                        if men < min_:
                            min_ = men

print(min_)

Submission status: Wrong Answer

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

ans = float("inf")
for i in range(N):
    for j in range(i+1,N):
        for k in range(j+1,N):
            x1,y1 = XY[i]
            x2,y2 = XY[j]
            x3,y3 = XY[k]
            u = max(y1,y2,y3)
            d = min(y1,y2,y3)
            r = max(x1,x2,x3)
            l = min(x1,x2,x3)
            num = 0
            for m in range(N):
                x,y = XY[m]
                if l<=x<=r and d<=y<=u:
                    num += 1
            if num >= K:
                tmp = (u-d)*(r-l)
                if tmp < ans:
                    ans = tmp
        x1,y1 = XY[i]
        x2,y2 = XY[j]
        u = max(y1,y2)
        d = min(y1,y2)
        r = max(x1,x2)
        l = min(x1,x2)
        num = 0
        for m in range(N):
            x,y = XY[m]
            if l<=x<=r and d<=y<=u:
                num += 1
        if num >= K:
            tmp = (u-d)*(r-l)
            if tmp < ans:
                ans = tmp
print(ans)

Submission status: Wrong Answer

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

ans = float("inf")
for i in range(N):
    for j in range(i+1,N):
        if K >= 3:
            for k in range(j+1,N):
                x1,y1 = XY[i]
                x2,y2 = XY[j]
                x3,y3 = XY[k]
                u = max(y1,y2,y3)
                d = min(y1,y2,y3)
                r = max(x1,x2,x3)
                l = min(x1,x2,x3)
                num = 0
                for m in range(N):
                    x,y = XY[m]
                    if l<=x<=r and d<=y<=u:
                        num += 1
                if num >= K:
                    tmp = (u-d)*(r-l)
                    if tmp < ans:
                        ans = tmp
        else:
            x1,y1 = XY[i]
            x2,y2 = XY[j]
            u = max(y1,y2)
            d = min(y1,y2)
            r = max(x1,x2)
            l = min(x1,x2)
            num = 0
            for m in range(N):
                x,y = XY[m]
                if l<=x<=r and d<=y<=u:
                    num += 1
            if num >= K:
                tmp = (u-d)*(r-l)
                if tmp < ans:
                    ans = tmp
print(ans)

Submission status: Wrong Answer

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

ans = float("inf")
for i in range(N):
    for j in range(i+1,N):
        if K >= 3:
            for k in range(j+1,N):
                x1,y1 = XY[i]
                x2,y2 = XY[j]
                x3,y3 = XY[k]
                u = max(y1,y2,y3)
                d = min(y1,y2,y3)
                r = max(x1,x2,x3)
                l = min(x1,x2,x3)
                num = 0
                for m in range(N):
                    x,y = XY[m]
                    if l<=x<=r and d<=y<=u:
                        num += 1
                if num == K:
                    tmp = (u-d)*(r-l)
                    if tmp < ans:
                        ans = tmp
        else:
            x1,y1 = XY[i]
            x2,y2 = XY[j]
            u = max(y1,y2)
            d = min(y1,y2)
            r = max(x1,x2)
            l = min(x1,x2)
            num = 0
            for m in range(N):
                x,y = XY[m]
                if l<=x<=r and d<=y<=u:
                    num += 1
            if num == K:
                tmp = (u-d)*(r-l)
                if tmp < ans:
                    ans = tmp
print(ans)

Submission status: Wrong Answer

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

p_list.sort()
ans = float('inf')
for i in range(N):
    for j in range(i + K - 1, N):
        x = p_list[j][0] - p_list[i][0]
        y_list = []
        for k in range(i, j + 1):
            y_list.append((p_list[k][1]))
        y_list.sort()
        ans = min(ans, x * abs(y_list[-1] - y_list[0]))

print(ans)

Submission status: Wrong Answer

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

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

p_list.sort()

ans = float('inf')

for i in range(N - K + 1):
    for j in range(i + K - 1, N):
        x = abs(p_list[j][0] - p_list[i][0])
        y_list = []
        for k in range(j + 1):
            y_list.append((p_list[k][1]))
        y_list.sort()
        ans = min(ans, x * abs(y_list[-1] - y_list[0]))

print(ans)

Submission status: Wrong Answer

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

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

p_list.sort()

ans = float('inf')

for i in range(N - K + 1):
    for j in range(i + K - 1, N):
        x = p_list[j][0] - p_list[i][0]
        y_list = []
        for k in range(K):
            y_list.append((p_list[i + k][1]))
        y_list.sort()
        ans = min(ans, x * abs(y_list[K-1] - y_list[0]))

print(ans)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
xys = []
for i in range(N):
  x, y = map(int, input().split())
  xys.append((x, y))
xs = sorted(map(lambda xy: xy[0], xys))
ys = sorted(map(lambda xy: xy[1], xys))
rs = []
for i in range(N):
  for j in range(i+1, N):
    x1 = xs[i]
    x2 = xs[j]
    for k in range(N):
      for l in range(k+1, N):
        y1 = ys[i]
        y2 = ys[j]
        n = len([(x, y) for x, y in xys if x1 <= x <= x2 and y1 <= y <= y2])
        #xys2 = filter(lambda xy: x1 <= xy[0] <= x2 and y1 <= xy[1] <= y2, xys)
        if n >= K:
          r = (x2-x1)*(y2-y1)
          rs.append(r)
r = min(rs)
print(r)

Submission status: Wrong Answer

Solution code:
from operator import itemgetter
import sys
input = sys.stdin.readline

def main():
    N, K = map(int, input().split())
    V = [list(map(int, input().split())) for _ in range(N)]
    V_x = sorted(V, key=itemgetter(0))
    V_y = sorted(V, key=itemgetter(1))

    ans = (V_x[N-1][0] - V_x[0][0]) * (V_y[N-1][1] - V_y[0][1])
    for i in range(N-K):
        for j in range(N-K):
            s = (V_x[i+K-1][0] - V_x[i][0]) * (V_y[i+K-1][1] - V_y[i][1])
            ans = min(ans, s)
    
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
XY = [[0, 0, 0] for _ in range(N)]
for i in range(N):
  x, y = map(int, input().split())
  XY[i] = [x, y, i]
X = sorted(XY)
Y = sorted(XY, key=lambda x: x[1])
rect = (X[-1][0] - X[0][0]) * (Y[-1][1] - Y[0][1])
for l in range(N - K + 1):
  for r in range(l + K - 1, N):
    for d in range(N - K + 1):
      for u in range(d + K - 1, N - 1):
        if len([x for x in XY if X[l][0] <= x[0] <= X[r][0] and Y[d][1] <= x[1] <= Y[u][1]]) >= K:
          rect = min((X[r][0] - X[l][0]) * (Y[u][1] - Y[d][1]), rect)
print(rect)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
XY = [[0, 0, 0] for _ in range(N)]
for i in range(N):
  x, y = map(int, input().split())
  XY[i] = [x, y, i]
X = sorted(XY)
Y = sorted(XY, key=lambda x: x[1])
rect = (X[-1][0] - X[0][0]) * (Y[-1][1] - Y[0][1])
for l in range(N - K):
  for r in range(l + K - 1, N):
    for d in range(N - K):
      for u in range(d + K - 1, N - 1):
        if len([x for x in XY if X[l][0] <= x[0] <= X[r][0] and Y[d][1] <= x[1] <= Y[u][1]]) >= K:
          rect = min((X[r][0] - X[l][0]) * (Y[u][1] - Y[d][1]), rect)
print(rect)

Submission status: Wrong Answer

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

    x_sort = sorted(vertex)
    y_sort = sorted(vertex, key=lambda x: x[1])

    tmp_x = 0
    square_x = float('inf')
    while tmp_x < N-K+1:
        diff_x = abs(x_sort[tmp_x][0] - x_sort[tmp_x+K-1][0])
        y_min = float('inf')
        y_max = 0
        for i in range(tmp_x+K):
            y_min = min(y_min, x_sort[i][1])
            y_max = max(y_max, x_sort[i][1])
        square_x = min(square_x, diff_x * (y_max - y_min))
        
        tmp_x += 1

    tmp_y = 0
    square_y = float('inf')
    while tmp_y < N-K+1:
        diff_y = abs(y_sort[tmp_y][1] - y_sort[tmp_y+K-1][1])
        x_min = float('inf')
        x_max = 0
        for i in range(tmp_y+K):
            x_min = min(x_min, y_sort[i][0])
            x_max = max(x_max, y_sort[i][0])
        square_y = min(square_y, diff_y * (x_max - x_min))
        
        tmp_y += 1

    print(min(square_x,square_y))
        

main()

Submission status: Wrong Answer

Solution code:
import sys
from operator import itemgetter
from collections import deque
input = sys.stdin.readline

n, k = map(int, input().split())
p = [list(map(int, input().split())) for _ in range(n)]
p.sort(key=itemgetter(0))

d = deque()
ans = float('INF')
for i in range(n):
    if len(d) < k:
        d.append(p[i])
    else:
        # len(d) == k
        _ = d.popleft()
        d.append(p[i])

    if len(d) < k:
        continue

    x_min, y_min = d[0]
    x_max, y_max = d[0]
    for j in range(1, len(d)):
        x, y = d[j]
        x_min = min(x_min, x)
        y_min = min(y_min, y)
        x_max = max(x_max, x)
        y_max = max(y_max, y)
    ans = min(ans, (x_max - x_min) * (y_max - y_min))


p.sort(key=itemgetter(1))
d = deque()
for i in range(n):
    if len(d) < k:
        d.append(p[i])
    else:
        # len(d) == k
        _ = d.popleft()
        d.append(p[i])

    if len(d) < k:
        continue

    x_min, y_min = d[0]
    x_max, y_max = d[0]
    for j in range(1, len(d)):
        x, y = d[j]
        x_min = min(x_min, x)
        y_min = min(y_min, y)
        x_max = max(x_max, x)
        y_max = max(y_max, y)
    ans = min(ans, (x_max - x_min) * (y_max - y_min))


print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from operator import itemgetter
from collections import deque
input = sys.stdin.readline

n, k = map(int, input().split())
p = [list(map(int, input().split())) for _ in range(n)]
p.sort(key=itemgetter(0))

d = deque()
ans = float('INF')
for i in range(n):
    if len(d) < k:
        d.append(p[i])
    else:
        # len(d) == k
        _ = d.popleft()
        d.append(p[i])

    if len(d) < k:
        continue

    x_min, y_min = d[0]
    x_max, y_max = d[0]
    for j in range(1, len(d)):
        x, y = d[j]
        x_min = min(x_min, x)
        y_min = min(y_min, y)
        x_max = max(x_max, x)
        y_max = max(y_max, y)
    ans = min(ans, (x_max - x_min) * (y_max - y_min))

print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import combinations

N,K = map(int,input().split())
pos_list = [list(map(int, input().split())) for _ in range(N)]
idx_list = [i for i in range(N)]
ans = float('inf')
for cmb in list(combinations(idx_list,K)):
  xlist, ylist = [], []
  for idx in cmb:
    xlist.append(pos_list[idx][0])
    ylist.append(pos_list[idx][1])
  area = abs(max(xlist) - min(xlist))*abs(max(ylist) - min(ylist))
  if ans > area:ans = area
print(area if area != 0 else 1)

Submission status: Wrong Answer

Solution code:
from itertools import combinations

N,K = map(int,input().split())
pos_list = [list(map(int, input().split())) for _ in range(N)]
idx_list = [i for i in range(N)]
ans = float('inf')
for cmb in list(combinations(idx_list,K)):
  xlist, ylist = [], []
  for idx in cmb:
    xlist.append(pos_list[idx][0])
    ylist.append(pos_list[idx][1])
  area = (max(xlist) - min(xlist))*(max(ylist) - min(ylist))
  if ans > area:ans = area
print(area if area != 0 else 1)

Submission status: Wrong Answer

Solution code:
from itertools import combinations

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

ans = float('inf')
for cmb in list(combinations(pos_list,K)):
  pos_list = [a for a in zip(*cmb)]
  area = (max(pos_list[0]) - min(pos_list[0]))*(max(pos_list[1]) - min(pos_list[1]))
  if ans > area:ans = area
print(area if area != 0 else 1)

Submission status: Wrong Answer

Solution code:
from itertools import combinations

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

ans = float('inf')
for cmb in list(combinations(pos_list,K)):
  pos_list = [a for a in zip(*cmb)]
  area = (max(pos_list[0]) - min(pos_list[0]))*(max(pos_list[1]) - min(pos_list[1]))
  if ans > area:ans = area
print(area)

Submission status: Wrong Answer

Solution code:
def main():

    N, K = map(int, input().split())
    p = []
    for _ in range(N):
        x, y = map(int, input().split())
        p.append([x, y])
    p.sort(key = lambda x: x[0])

    min_area = float('inf')
    for i in range(N-1):
        for j in range(i+1, N):
            if j-i+1 >= K:
                x1 = p[i][0]
                x2 = p[j][0]
                ys = []
                for k in range(i, j+1):
                    ys.append(p[k][1])
                ys.sort()
                for k in range(len(ys)):
                    for l in range(k+K-1, len(ys)):
                        y1 = ys[k]
                        y2 = ys[l]
                        area = (x2-x1)*(y2-y1)
                        if area > 0:
                            min_area = min(min_area, area)
    return min_area