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:
n, k = map(int, input().split())
xy = [list(map(int, input().split())) for _ in range(n)]



# k = 1
dp = []
for i in range(n):
    ret = [(xy[i][0], xy[i][1]), (xy[i][0], xy[i][1])]
    dp.append(ret)
# print(dp)

for i in range(2, k+1):
    dp_new = []
    for j in range(i-1):
        dp_new.append([(float('inf'), float('inf')), (float('inf'), float('inf'))])
    for j in range(i-1, n):
        # xy[j]までを使ってi点含む最小の面積の座標
        minarea = float('inf')

        for a in range(j):
            tmp = [(min(xy[j][0], dp[a][0][0]), min(xy[j][1], dp[a][0][1])), (max(xy[j][0], dp[a][1][0]), max(xy[j][1], dp[a][1][1]))]
            area = (tmp[1][1] - tmp[0][1]) * (tmp[1][0] - tmp[0][0])
            if area < minarea:
                minarea = area
                ret = tmp
        dp_new.append(ret)

    dp = dp_new
    # print(i, dp)

minarea = float('inf')
for i in range(len(dp)):
    tmp = dp[i]
    area = (tmp[1][1] - tmp[0][1]) * (tmp[1][0] - tmp[0][0])
    minarea = min(minarea, area)

print(minarea)

Submission status: Wrong Answer

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



# k = 1
dp = []
for i in range(n):
    ret = [(xy[i][0], xy[i][1]), (xy[i][0], xy[i][1])]
    dp.append(ret)
# print(dp)

for i in range(2, k+1):
    dp_new = []
    for j in range(i-1):
        dp_new.append([(float('inf'), float('inf')), (float('inf'), float('inf'))])
    for j in range(i-1, n):
        # xy[j]までを使ってi点含む最小の面積の座標
        minarea = float('inf')

        for a in range(j):
            tmp = [(min(xy[j][0], dp[a][0][0]), min(xy[j][1], dp[a][0][1])), (max(xy[j][0], dp[a][1][0]), max(xy[j][1], dp[a][1][1]))]
            area = (tmp[1][1] - tmp[0][1]) * (tmp[1][0] - tmp[0][0])
            if area < minarea:
                minarea = area
                ret = tmp
        dp_new.append(ret)

    dp = dp_new
    # print(i, dp)

print((dp[-1][1][1] - dp[-1][0][1]) * (dp[-1][1][0] - dp[-1][0][0]))

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def main():
    n,k=MI()
    xy=[]
    xx=[]
    yy=[]
    for _ in range(n):
        x,y=MI()
        xy.append([x,y])
        xx.append(x)
        yy.append(y)
    xx.sort()
    yy.sort()
    ans=10**16
    for ri in range(n):
        r=xx[ri]
        for li in range(ri):
            l=xx[li]
            for ti in range(n):
                t=yy[ti]
                for bi in range(ti):
                    b=yy[bi]
                    cnt=0
                    for x,y in xy:
                        if l<=x<=r and b<=y<=t:
                            cnt+=1
                    if cnt>=k:
                        s=(r-l)*(t-b)
                        if s<ans:ans=s
    print(s)

main()

Submission status: Wrong Answer

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

ans = 10**20
for i in range(N-1):
    for j in range(i+1, N):
        x0 = min(p[i][0], p[j][0])
        x1 = max(p[i][0], p[j][0])
        y0 = min(p[i][1], p[j][1])
        y1 = max(p[i][1], p[j][1])

        c = 0
        for m in range(N):
            if x0 <= p[m][0] <= x1 and y0 <= p[m][1] <= y1:
                c += 1

        if c >= K:
            ans = min(ans, (x1-x0)*(y1-y0))

print(ans)

Submission status: Wrong Answer

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

P.sort()

ans = 10**20
for i in range(N-K+1):
    X = P[i+K-1][0]
    x = P[i][0]
    Y = []
    for j in range(i, K+i):
        Y.append(P[j][1])
    Y.sort()
    ans = min(ans, (X-x)*(Y[-1]-Y[0]))
    for j in range(K+i, N):
        Y.append(P[j][1])
        Y.sort()
        for k in range(len(Y)-K+1):
            ans = min(ans, (X-x)*(Y[k+K-1]-Y[k]))
            
print(ans)

Submission status: Wrong Answer

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

P.sort()

ans = 10**20
for i in range(N-K+1):
    x = P[i][0]
    Y = []
    for j in range(i, K+i):
        Y.append(P[j][1])
    Y.sort()
    ans = min(ans, (P[i+K-1][0]-x)*(Y[-1]-Y[0]))
    for j in range(K+i, N):
        if Y[0] < P[j][1] < Y[-1]:
            if min(P[j][1], Y[1])-Y[0] > Y[-1]-max(P[j][1], Y[-2]):
                if ans > (P[j][0]-x)*(Y[-1]-min(P[j][1], Y[1])):
                    ans = (P[j][0]-x)*(Y[-1]-min(P[j][1], Y[1]))
                    Y.pop(0)
                    Y.append(P[j][1])
                    Y.sort()
            else:
                if ans > (P[j][0]-x)*(max(P[j][1], Y[-2])-Y[0]):
                    ans = (P[j][0]-x)*(max(P[j][1], Y[-2])-Y[0])
                    Y.pop(-1)
                    Y.append(P[j][1])
                    Y.sort()
        elif P[j][1] > Y[-1]:
            if ans > (P[j][0]-x)*(P[j][1]-Y[1]):
                ans = (P[j][0]-x)*(P[j][1]-Y[1])
                Y.pop(0)
                Y.append(P[j][1])
        elif P[j][1] < Y[0]:
            if ans > (P[j][0]-x)*(Y[-2]-P[j][1]):
                ans = (P[j][0]-x)*(Y[-2]-P[j][1])
                Y.pop(-1)
                Y.append(P[j][1])
                Y.sort()
            
print(ans)

Submission status: Wrong Answer

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

P.sort()

ans = 10**20
for i in range(N-K+1):
    x = P[i][0]
    Y = []
    for j in range(i, K+i):
        Y.append(P[j][1])
    Y.sort()
    ans = min(ans, (P[i+K-1][0]-x)*(Y[-1]-Y[0]))
    for j in range(K+i, N):
        if Y[0] < P[j][1] < Y[-1]:
            if P[j][1]-Y[0] > Y[-1]-P[j][1]:
                if ans > (P[j][0]-x)*(Y[-1]-min(P[j][1], Y[1])):
                    ans = (P[j][0]-x)*(Y[-1]-min(P[j][1], Y[1]))
                    Y.pop(0)
                    Y.append(P[j][1])
                    Y.sort()
            else:
                if ans > (P[j][0]-x)*(max(P[j][1], Y[-2])-Y[0]):
                    ans = (P[j][0]-x)*(max(P[j][1], Y[-2])-Y[0])
                    Y.pop(-1)
                    Y.append(P[j][1])
                    Y.sort()
        elif P[j][1] > Y[-1]:
            if ans > (P[j][0]-x)*(P[j][1]-Y[1]):
                ans = (P[j][0]-x)*(P[j][1]-Y[1])
                Y.pop(0)
                Y.append(P[j][1])
        elif P[j][1] < Y[0]:
            if ans > (P[j][0]-x)*(Y[-2]-P[j][1]):
                ans = (P[j][0]-x)*(Y[-2]-P[j][1])
                Y.pop(-1)
                Y.append(P[j][1])
                Y.sort()
            
print(ans)

Submission status: Wrong Answer

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

P.sort()

ans = 10**20
for i in range(N-K+1):
    x = P[i][0]
    Y = []
    for j in range(i, K+i):
        Y.append(P[j][1])
    Y.sort()
    ans = min(ans, (P[i+K-1][0]-x)*(Y[-1]-Y[0]))
    for j in range(K+i, N):
        if Y[0] < P[j][1] < Y[-1]:
            if ans > (P[j][0]-x)*(Y[-1]-min(P[j][1], Y[1])):
                ans = (P[j][0]-x)*(Y[-1]-min(P[j][1], Y[1]))
                Y.pop(0)
                Y.append(P[j][1])
                Y.sort()
            if ans > (P[j][0]-x)*(max(P[j][1], Y[-2])-Y[0]):
                ans = (P[j][0]-x)*(max(P[j][1], Y[-2])-Y[0])
                Y.pop(-1)
                Y.append(P[j][1])
                Y.sort()
        elif P[j][1] > Y[-1]:
            if ans > (P[j][0]-x)*(Y[-1]-min(P[j][1], Y[1])):
                ans = (P[j][0]-x)*(Y[-1]-min(P[j][1], Y[1]))
                Y.pop(0)
                Y.append(P[j][1])
                Y.sort()
        elif P[j][1] < Y[0]:
            if ans > (P[j][0]-x)*(max(P[j][1], Y[-2])-Y[0]):
                ans = (P[j][0]-x)*(max(P[j][1], Y[-2])-Y[0])
                Y.pop(-1)
                Y.append(P[j][1])
                Y.sort()
            
print(ans)

Submission status: Wrong Answer

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

P.sort()

ans = 10**20
for i in range(N-K+1):
    x = P[i][0]
    Y = []
    for j in range(i, K+i):
        Y.append(P[j][1])
    Y.sort()
    ans = min(ans, (P[i+K-1][0]-x)*(Y[-1]-Y[0]))
    for j in range(K+i, N):
        if Y[0] < P[j][1]:
            if ans > (P[j][0]-x)*(max(P[j][1], Y[-1])-min(P[j][1], Y[1])):
                ans = (P[j][0]-x)*(max(P[j][1], Y[-1])-min(P[j][1], Y[1]))
                Y.pop(0)
                Y.append(P[j][1])
                Y.sort()
        elif P[j][1] < Y[-1]:
            if ans > (P[j][0]-x)*(max(P[j][1], Y[-2])-min(P[j][1], Y[0])):
                ans = (P[j][0]-x)*(max(P[j][1], Y[-2])-min(P[j][1], Y[0]))
                Y.pop(-1)
                Y.append(P[j][1])
                Y.sort()
            
print(ans)

Submission status: Wrong Answer

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

P.sort()

ans = 10**20
for i in range(N-K+1):
    x = P[i][0]
    Y = []
    for j in range(i, K+i):
        Y.append(P[j][1])
    Y.sort()
    ans = min(ans, (P[i+K-1][0]-x)*(Y[-1]-Y[0]))
    for j in range(K+i, N):
        if Y[0] < P[j][1] < Y[-1]:
            if ans > (P[j][0]-x)*(Y[-1]-min(P[j][1], Y[1])):
                ans = (P[j][0]-x)*(Y[-1]-min(P[j][1], Y[1]))
                Y.pop(0)
                Y.append(P[j][1])
                Y.sort()
            if ans > (P[j][0]-x)*(max(P[j][1], Y[-2])-Y[0]):
                ans = (P[j][0]-x)*(max(P[j][1], Y[-2])-Y[0])
                Y.pop(-1)
                Y.append(P[j][1])
                Y.sort()
            
print(ans)

Submission status: Wrong Answer

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

P.sort()

ans = 10**20
for i in range(N-K+1):
    x = P[i][0]
    Y = []
    for j in range(i, K+i):
        Y.append(P[j][1])
    Y.sort()
    ans = min(ans, (P[i+K-1][0]-x)*(Y[-1]-Y[0]))
    for j in range(K+i, N):
        if Y[0] < P[j][1] < Y[-1]:
            if Y[-1]-P[j][1] < P[j][1]-Y[0]:
                if ans > (P[j][0]-x)*(Y[-1]-min(P[j][1], Y[1])):
                    ans = (P[j][0]-x)*(Y[-1]-min(P[j][1], Y[1]))
                    Y.pop(0)
                    Y.append(P[j][1])
                    Y.sort()
            else:
                if ans > (P[j][0]-x)*(max(P[j][1], Y[-2])-Y[0]):
                    ans = (P[j][0]-x)*(max(P[j][1], Y[-2])-Y[0])
                    Y.pop(-1)
                    Y.append(P[j][1])
                    Y.sort()
            
print(ans)

Submission status: Wrong Answer

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

P.sort()

ans = 10**20
for i in range(N-K+1):
    x = P[i][0]
    Y = []
    for j in range(i, K+i):
        Y.append(P[j][1])
    Y.sort()
    ans = min(ans, (P[i+K-1][0]-x)*(Y[-1]-Y[0]))
    for j in range(K+i, N):
        if ans > (P[j][0]-x)*(max(Y[-2], P[j][1])-Y[0]):
            ans = (P[j][0]-x)*(max(Y[-2], P[j][1])-Y[0])
            Y.pop(-1)
            Y.append(P[j][1])
            Y.sort()
            
print(ans)

Submission status: Wrong Answer

Solution code:
from operator import itemgetter

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

P.sort(key=itemgetter(1))
P.sort()

ans = 10**20
for i in range(N-K+1):
    X = []
    Y = []
    for j in range(i, K+i):
        X.append(P[j][0])
        Y.append(P[j][1])
    Y.sort()
    ans = min(ans, (X[-1]-X[0])*(Y[-1]-Y[0]))
    for j in range(K+i+1, N):
        if ans > (P[j][0]-X[0])*(max(Y[-2], P[j][1])-Y[0]):
            ans = (P[j][0]-X[0])*(max(Y[-2], P[j][1])-Y[0])
            X.append(P[j][0])
            Y.pop(-1)
            Y.append(P[j][1])
            Y.sort()
            
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


X = []
Y = []
n, k = LI()
for _ in range(n):
    x, y = LI()
    X += [x]
    Y += [y]


X.sort()
Y.sort()

ans = INF
for li in range(n):
    l = X[li]
    for ri in range(li, n):
        r = X[ri]
        for di in range(n):
            d = Y[di]
            for ui in range(di, n):
                u = Y[ui]
                ret = 0
                for i in range(n):
                    if l <= X[i] <= r and d <= Y[i] <= u:
                        ret += 1
                if ret >= k:
                    ans = min(ans, (r - l) * (u - d))


print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


X = []
Y = []
n, k = LI()
for _ in range(n):
    x, y = LI()
    X += [x]
    Y += [y]


X.sort()
Y.sort()

ans = INF
for li in range(n):
    l = X[li]
    for ri in range(li + 1, n):
        r = X[ri]
        for di in range(n):
            d = Y[di]
            for ui in range(di + 1, n):
                u = Y[ui]
                ret = 0
                for i in range(n):
                    if l <= X[i] <= r and d <= Y[i] <= u:
                        ret += 1
                if ret >= k:
                    ans = min(ans, (r - l) * (u - d))


print(ans)

Submission status: Wrong Answer

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

for i in range(n-k):
    x=[xy[i][0] for i in range(n-i)]
    y=[xy[i][1] for i in range(n-i)]
    xl = min(x)
    xr = max(x)
    yl = min(y)
    yr = max(y)

    xr2 = sorted(x)[-2]
    xl2 = sorted(x)[1]
    yr2 = sorted(y)[-2]
    yl2 = sorted(y)[1]

    res1 = (xl2-xl)*(yr-yl)
    res2 = (xr-xr2)*(yr-yl)
    res3 = (yl2-yl)*(xr-xl)
    res4 = (yr-yr2)*(xr-xl)
    if max(res1,res2,res3,res4) ==res1:
        xy.pop(x.index(xl))
    elif max(res1,res2,res3,res4) ==res2:
        xy.pop(x.index(xr))
    elif max(res1,res2,res3,res4) ==res3:
        xy.pop(y.index(yl))
    elif max(res1,res2,res3,res4) ==res4:
        xy.pop(y.index(yr))

x=[xy[i][0] for i in range(k)]
y=[xy[i][1] for i in range(k)]
xl = min(x)
xr = max(x)
yl = min(y)
yr = max(y)
print((xr-xl)*(yr-yl))

Submission status: Wrong Answer

Solution code:
import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
mod = 10**9 + 7
inf = float('inf')
ans = int(0)

N, K = LI()
x = [0]*N; y = [0]*N
for i in range(N):
    x[i], y[i] = LI()

X = x; Y = y
X.sort(); Y.sort()

Xcandi = [0]*2; Ycandi = [0]*2
ylower = 0; yupper = N-1; ycur = (ylower+yupper)//2
ansC = []
for i in range(N-1):
    Xcandi[0] = X[i]
    for j in range(i+1,N):
        Xcandi[1] = X[j]
        for k in range(N-1):
            ylower = k+1; yupper = N - 1; ycur = (ylower + yupper) // 2
            Ycandi[0] = Y[k]
            while(True):
                cur = int(0)
                Ycandi[1] = Y[ycur]
                for l in range(N):
                    if Xcandi[0] <= x[l] <= Xcandi[1] and Ycandi[0] <= y[l] <= Ycandi[1]:
                        cur += 1
                if yupper - ylower >= 2:
                    if cur < K:
                        ylower = ycur
                        ycur = (ycur + yupper) // 2
                    else:
                        yupper = ycur
                        ycur = (ycur + ylower) // 2
                else:
                    cur = int(0)
                    Ycandi[1] = Y[yupper]
                    for l in range(N):
                        if Xcandi[0] <= x[l] <= Xcandi[1] and Ycandi[0] <= y[l] <= Ycandi[1]:
                            cur += 1
                    if cur < K:
                        break
                    else:
                        cur = int(0)
                        Ycandi[1] = Y[ylower]
                        for l in range(N):
                            if Xcandi[0] <= x[l] <= Xcandi[1] and Ycandi[0] <= y[l] <= Ycandi[1]:
                                cur += 1
                        if cur < K:
                            Ycandi[1] = Y[ylower+1]
                    cur = (Xcandi[1] - Xcandi[0])*(Ycandi[1] - Ycandi[0])
                    ansC.append(cur)
                    break


#print(ansC)
print(min(ansC))

Submission status: Wrong Answer

Solution code:
import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
mod = 10**9 + 7
inf = float('inf')
ans = int(0)

N, K = LI()
x = [0]*N; y = [0]*N
for i in range(N):
    x[i], y[i] = LI()

X = x; Y = y
X.sort(); Y.sort()

Xcandi = [0]*2; Ycandi = [0]*2
ylower = 0; yupper = N-1; ycur = (ylower+yupper)//2
ansC = []
for i in range(N):
    Xcandi[0] = X[i]
    for j in range(i+1,N):
        Xcandi[1] = X[j]
        for k in range(N):
            Ycandi[0] = Y[k]
            while(True):
                cur = int(0)
                Ycandi[1] = Y[ycur]
                for l in range(N):
                    if Xcandi[0] <= x[l] <= Xcandi[1] and Ycandi[0] <= y[l] <= Ycandi[1]:
                        cur += 1
                if yupper - ylower >= 2:
                    if cur < K:
                        ylower = ycur
                        ycur = (ycur + yupper) // 2
                    else:
                        yupper = ycur
                        ycur = (ycur + ylower) // 2
                else:
                    if cur<K:
                        cur = int(0)
                        Ycandi[1] = Y[yupper]
                        for l in range(N):
                            if Xcandi[0] <= x[l] <= Xcandi[1] and Ycandi[0] <= y[l] <= Ycandi[1]:
                                cur += 1
                        if cur<K:
                            break
                    else:
                        Ycandi[1] = Y[ycur]
                    cur = (Xcandi[1] - Xcandi[0])*(Ycandi[1] - Ycandi[0])
                    ansC.append(cur)
                    break


#print(ansC)
print(min(ansC))

Submission status: Wrong Answer

Solution code:
import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
mod = 10**9 + 7
inf = float('inf')
ans = int(0)

N, K = LI()
x = [0]*N; y = [0]*N
for i in range(N):
    x[i], y[i] = LI()

X = x; Y = y
X.sort(); Y.sort()

Xcandi = [0]*2; Ycandi = [0]*2
ylower = 0; yupper = N-1; ycur = (ylower+yupper)//2
ansC = []
for i in range(N):
    Xcandi[0] = X[i]
    for j in range(i+1,N):
        Xcandi[1] = X[j]
        for k in range(N):
            Ycandi[0] = Y[k]
            while(True):
                cur = int(0)
                Ycandi[1] = Y[ycur]
                for l in range(N):
                    if Xcandi[0] <= x[l] <= Xcandi[1] and Ycandi[0] <= y[l] <= Ycandi[1]:
                        cur += 1
                if yupper - ylower >= 2:
                    if cur < K:
                        ylower = ycur
                        ycur = (ycur + yupper) // 2
                    else:
                        yupper = ycur
                        ycur = (ycur + ylower) // 2
                else:
                    if cur<K:
                        cur = int(0)
                        Ycandi[1] = Y[ycur +1]
                        for l in range(N):
                            if Xcandi[0] <= x[l] <= Xcandi[1] and Ycandi[0] <= y[l] <= Ycandi[1]:
                                cur += 1
                        if cur<K:
                            break
                    else:
                        Ycandi[1] = Y[ycur]
                    cur = (Xcandi[1] - Xcandi[0])*(Ycandi[1] - Ycandi[0])
                    ansC.append(cur)
                    break


#print(ansC)
print(min(ansC))

Submission status: Wrong Answer

Solution code:
import heapq

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

Y = [[j for j in i] for i in X]
Z = [[j for j in i] for i in X]

X.sort()
Y.sort(key=lambda x:x[1])

ans = float("inf")
for i in range(n):
    x0 = X[i][0]
    for j in range(n):
        y0 = Y[j][1]
        Q = []
        x1_ind = 0
        for p in range(n):
            if len(Q) == k:
                break
            else:
                if X[p][0] >= x0 and X[p][1] >= y0:
                    heapq.heappush(Q, [-X[p][1], X[p][0], X[p][1]])
                    x1_ind = p
        if len(Q) == k:
            x1 = X[x1_ind][0]
            pop = heapq.heappop(Q)
            y1 = -pop[0]
            heapq.heappush(Q, pop)
            ans = min(ans, (x1-x0) * (y1-y0))
            st = x1_ind
            for p in range(st+1, n):
                if X[p][0] >= x0 and X[p][1] >= y0:
                    heapq.heappush(Q, [-X[p][1], X[p][0], X[p][1]])
                    x1 = X[p][0]
                    pop = heapq.heappop(Q)
                    y1 = -pop[0]
                    ans = min(ans, (x1-x0) * (y1-y0))
print(ans)

Submission status: Wrong Answer

Solution code:
import heapq

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

Y = [[j for j in i] for i in X]
Z = [[j for j in i] for i in X]

X.sort()
Y.sort(key=lambda x:x[1])

ans = float("inf")
for i in range(n):
    x0 = X[i][0]
    for j in range(n):
        y0 = Y[i][1]
        Q = []
        x1_ind = 0
        for p in range(n):
            if len(Q) == k:
                break
            else:
                if X[p][0] >= x0 and X[p][1] >= y0:
                    heapq.heappush(Q, [-X[p][1], X[p][0], X[p][1]])
                    x1_ind = p
        if len(Q) == k:
            x1 = X[x1_ind][0]
            pop = heapq.heappop(Q)
            y1 = -pop[0]
            heapq.heappush(Q, pop)
            ans = min(ans, (x1-x0) * (y1-y0))
            st = x1_ind
            for p in range(st+1, n):
                if X[p][0] >= x0 and X[p][1] >= y0:
                    heapq.heappush(Q, [-X[p][1], X[p][0], X[p][1]])
                    x1 = X[p][0]
                    pop = heapq.heappop(Q)
                    y1 = -pop[0]
                    ans = min(ans, (x1-x0) * (y1-y0))
print(ans)

Submission status: Wrong Answer

Solution code:
import heapq

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

Y = [[j for j in i] for i in X]
Z = [[j for j in i] for i in X]

X.sort()
Y.sort(key=lambda x:x[1])

ans = float("inf")
for i in range(n):
    x0 = X[i][0]
    for j in range(n):
        y0 = Y[i][1]
        Q = []
        x1_ind = 0
        for p in range(n):
            if len(Q) == k:
                break
            else:
                if X[p][0] >= x0 and X[p][1] >= y0:
                    heapq.heappush(Q, [-X[p][1], X[p][0], X[p][1]])
                    x1_ind = p
        if len(Q) == k:
            x1 = X[x1_ind][0]
            pop = heapq.heappop(Q)
            y1 = -pop[0]
            heapq.heappush(Q, pop)
            ans = min(ans, (x1-x0) * (y1-y0))
            st = x1_ind
            for p in range(st+1, n):
                heapq.heappush(Q, [-X[p][1], X[p][0], X[p][1]])
                x1 = X[p][0]
                pop = heapq.heappop(Q)
                y1 = -pop[0]
                ans = min(ans, (x1-x0) * (y1-y0))
print(ans)

Submission status: Wrong Answer

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

N=50
K=25
xy=[[i,i] for i in range(50)]


X=sorted([i[0] for i in xy])
Y=sorted([i[1] for i in xy])

ans=[]
for i in range(N-1):
  lx=X[i]
  for j in range(i+1,N):
    rx=X[j]
    for k in range(N-1):
      dy=Y[k]
      for l in range(k+1,N):
        uy=Y[l]
        cnt=0
        for x,y in xy:
          if lx<=x and x<=rx and dy<=y and y<=uy:
            cnt+=1
        if cnt>=K:
          ans.append((rx-lx)*(uy-dy))
          
          
print(min(ans))

Submission status: Wrong Answer

Solution code:
import sys
INF = 1e20
n, k = [int(i) for i in sys.stdin.readline().split()]
ls = []
for i in range(n):
    x, y = [int(i) for i in sys.stdin.readline().split()]
    ls.append((x, y))
ls.sort(key=lambda x:x[0])
x_ls, y_ls = zip(*ls)
best = INF
for left_ind in range(n - k + 1):
    left = x_ls[left_ind]
    for right_ind in range(left_ind + k - 1, n):
        right = x_ls[right_ind]
        up = max(y_ls[left_ind:right_ind + 1])
        down = min(y_ls[left_ind:right_ind + 1])
        best = min(best, (up - down) * (right - left))
print(best)

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-K+1):
  for j in range(i+K-1,N):
    #print(i,j)
    xy1 = xy[i:j+1]
    #print(xy1)
    xy1 = sorted(xy1,key=lambda x: x[1])
    ans = min(ans,(xy[j][0]-xy[i][0])*(xy1[K-1][1]-xy1[0][1]))
print(ans)

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-K):
  for j in range(i+K-1,N):
    #print(i,j)
    xy1 = xy[i:j+1]
    #print(xy1)
    xy1 = sorted(xy1,key=lambda x: x[1])
    ans = min(ans,(xy[j][0]-xy[i][0])*(xy1[K-1][1]-xy1[0][1]))
print(ans)

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]
    miny1=min([xy1[i][1] for i in range(len(xy1))])
    maxy1=max([xy1[i][1] for i in range(len(xy1))])
    miny=min(xy[i][1],xy[j][1])
    maxy=max(xy[i][1],xy[j][1])
    mi = [[maxy1,miny1],[maxy1,miny],[maxy,miny1],[maxy,miny]]
    for ma,miy in mi:
      if len([y for x,y in xy1 if miy<y<ma])>=K-2 and j+1-i>=K:
        ans = min(ans,(xy[j][0]-xy[i][0])*(ma-miy))
print(ans)

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]
    miny1=min([xy1[i][1] for i in range(j-i+1)])
    maxy1=max([xy1[i][1] for i in range(j-i+1)])
    miny=min(xy[i][1],xy[j][1])
    maxy=max(xy[i][1],xy[j][1])
    mi = [[maxy1,miny1],[maxy1,miny],[maxy,miny1],[maxy,miny]]
    for ma,miy in mi:
      if len([y for x,y in xy1 if miy<y<ma])>=K-2 and j+1-i>=K:
        ans = min(ans,(xy[j][0]-xy[i][0])*(ma-miy))
print(ans)

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 and j+1-i>=K:
      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 and j+1-i>=K:
      ans = min(ans,(xy[j][0]-xy[i][0])*(maxy-miny))
print(ans)

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 and j+1-i>=K:
      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 and j+1-i>=K-2:
      ans = min(ans,(xy[j][0]-xy[i][0])*(maxy-miny))
print(ans)