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:
def rect(x1,y1,x2,y2,inside_count,P):
    inf=1<<62
    while True:
        inside=0
        min_area=inf
        min_p=(inf,inf)
        for p in P:
            x=p[0]
            y=p[1]
            if x1<=x<=x2 and y1<=y<=y2:
                inside+=1
            else:
                area=(max(x,x2)-min(x,x1))*(max(y,y2)-min(y,y1))
                if min_area > area:
                    min_area = area
                    min_p = p
        if inside>=inside_count:
            return (x2-x1)*(y2-y1)
        x=min_p[0]
        y=min_p[1]
        x1=min(x,x1)
        x2=max(x,x2)
        y1=min(y,y1)
        y2=max(y,y2)

def solve():
    N,K=map(int,input().split())
    P=[]
    for i in range(N):
        x,y=map(int,input().split())
        P.append((x,y))
    inf=1<<62
    ans=inf
    for i in range(N):
        x,y=P[i]
        ans=min(ans,rect(x,y,x,y,K,P))
    return ans

print(solve())

Submission status: Wrong Answer

Solution code:
import sys
from itertools import combinations

def main():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    X = []
    Y = []
    A = []
    for _ in range(N):
        x, y = map(int, input().split())
        A.append((x, y))
        X.append(x)
        Y.append(y)

    X = [(i, x) for i, x in enumerate(sorted(X))]
    Y = [(i, y) for i, y in enumerate(sorted(Y))]

    ans = float('inf')
    for x in combinations(X, 2):
        i1, i2 = x[0][0], x[1][0]
        x1, x2 = x[0][1], x[1][1]
        if i2 - i1 < K-1:
            continue
        for y in combinations(Y, 2):
            j1, j2 = y[0][0], y[1][0]
            y1, y2 = y[0][1], y[1][1]
            if j2 - j1 < K-1:
                continue

            area = (x2 - x1) * (y2 - y1)
            ans = min(ans, area)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

o=[0,0]

l=[(-1*((o[0]-x[0])**2 + (o[1]-x[1])**2),(o[0]-x[0])**2 + (o[1]-x[1])**2) for x in p]
import heapq

a=[]
sum=10**100
for i in range(N):
    a=[(l[i][0],l[i][1],i)]
    heapq.heapify(a)
    for j in range(N):
        if(j==i):
            continue
        heapq.heappush(a,(-1*abs(l[j][1]-l[i][1]),abs(l[j][1]-l[i][1]),j))

        if(len(a)>K):
            heapq.heappop(a)
    lx=10**10
    ly=10**10
    rx=-10**10
    ry=-10**10

    for i in a:
        lx=min(lx,p[i[2]][0])
        ly=min(lx,p[i[2]][1])
        rx=max(rx,p[i[2]][0])
        ry=max(ry,p[i[2]][1])
    if(rx==lx):
        rx+=1
    if(ry==ly):
        ry+=1
    sum=min((rx-lx)*(ry-ly),sum)


print(sum)

Submission status: Wrong Answer

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

o=[0,0]

l=[(-1*(o[0]-x[0])**2 + (o[1]-x[1])**2,(o[0]-x[0])**2 + (o[1]-x[1])**2) for x in p]
import heapq

a=[]
sum=10**100
for i in range(N):
    a=[(l[i][0],l[i][1],i)]
    heapq.heapify(a)
    for j in range(N):
        if(j==i):
            continue
        heapq.heappush(a,(abs(l[j][0]-l[i][0]),abs(l[j][1]-l[i][1]),j))

        if(len(a)>K):
            heapq.heappop(a)
    lx=10**10
    ly=10**10
    rx=-10**10
    ry=-10**10

    for i in a:
        lx=min(lx,p[i[2]][0])
        ly=min(lx,p[i[2]][1])
        rx=max(rx,p[i[2]][0])
        ry=max(ry,p[i[2]][1])
    if(rx==lx):
        rx+=1
    if(ry==ly):
        ry+=1
    sum=min((rx-lx)*(ry-ly),sum)


print(sum)

Submission status: Wrong Answer

Solution code:
import sys
from itertools import combinations

def main():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    X = []
    Y = []
    A = []
    for _ in range(N):
        x, y = map(int, input().split())
        A.append((x, y))
        X.append(x)
        Y.append(y)

    X = sorted(X)
    Y = sorted(Y)
    ans = float('inf')
    for i in range(N - K + 1):
        x1, x2 = X[i], X[i+K-1]
        y1, y2 = Y[i], Y[i+K-1]

        yc = []
        xc = []
        for a in A:
            if x1 <= a[0] <= x2:
                yc.append(a[1])
            if y1 <= a[1] <= y2:
                xc.append(a[0])

        xc = sorted(xc)
        yc = sorted(yc)

        area1 = (x2 - x1) * (yc[-1] - yc[0])
        area2 = (xc[-1] - xc[0]) * (y2 - y1)
        ans = min(ans, area1, area2)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
from itertools import combinations

def main():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    X = []
    Y = []
    A = []
    for _ in range(N):
        x, y = map(int, input().split())
        A.append((x, y))
        X.append(x)
        Y.append(y)

    X = sorted(X)
    Y = sorted(Y)
    ans = float('inf')
    for i in range(N - K + 1):
        for j in range(N - K + 1):
            x1, x2 = X[i], X[i+K-1]
            y1, y2 = Y[j], Y[j+K-1]
            c = 0
            for a in A:
                if x1 <= a[0] <= x2 and y1 <= a[0] <= y2:
                    c += 1

            if c >= K:
                area = (x2 - x1) * (y2 - y1)
                ans = min(ans, area)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def axis_parallel_rectangle(N: int, K: int, xy: list)->int:
    # 1. 座標圧縮
    XY = sorted(xy)

    min_area = float('inf')
    for xli in range(N-K+1):
        xri = xli + K - 1
        ymin, ymax = float('inf'), -float('inf')
        for _, y in XY[xli:xri+1]:
            ymin = min(ymin, y)
            ymax = max(ymax, y)

        xmin, xmax = XY[xli][0], XY[xri][0]
        min_area = min(min_area, (xmax-xmin)*(ymax-ymin))

    return min_area


if __name__ == "__main__":
    N = 0
    N, K = map(int, input().split())
    xy = [tuple(map(int, input().split())) for _ in range(N)]
    ans = axis_parallel_rectangle(N, K, xy)
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1000000)
#def input():
#    return sys.stdin.readline()[:-1]

'''
n=int(input())
for i in range(n):
    a[i]=int(input())
    a[i],b[i]=map(int,input().split())
a=[int(x) for x in input().split()]
n,m=map(int,input.split())
from operator import itemgetter
a = [(1, "c", 1), (1, "b", 3), (2, "a", 0), (1, "a", 2)]
print(sorted(a))  # 0 番目の要素でソート、先頭の要素が同じなら 1 番目以降の要素も見る
print(sorted(a, key=itemgetter(0)))  # 0 番目の要素だけでソート
print(sorted(a, key=itemgetter(0, 2)))  # 0 番目と 2 番目の要素でソート
print(sorted(a, key=lambda x: x[0] * x[2]))  # 0 番目の要素 * 2 番目の要素でソート
print(sorted(a, reverse=True))  # 降順にソート
a.sort()  # 破壊的にソート、sorted() よりも高速
try: # エラーキャッチ list index out of range
    for i in range():
        k=b[i]
except IndexError as e:
    print(i)
'''

test_data1 = '''\
4 4
1 4
3 3
6 2
8 1
'''

test_data2 = '''\
2 3 0
4 5 6
7 8 9
-1 2 -5
'''

test_data3 = '''\

'''
td_num=1

def GetTestData(index):
    if index==1:
        return test_data1
    if index==2:
        return test_data2
    if index==3:
        return test_data3

if False:
    with open("../test.txt", mode='w') as f:
        f.write(GetTestData(td_num))
    with open("../test.txt") as f:
        # Start Input code ---------------------------------------
        
        n,k=map(int,f.readline().split())
        x=[0]*n
        y=[0]*n
        for i in range(n):
            x[i],y[i]=map(int,f.readline().split())
            
        # End Input code ---------------------------------------
else:
    for i in range(1):
        # Start Input 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())
        # End Input code ---------------------------------------
#print('n,k,x,y=',n,k,x,y)
ans=10**10
for x1 in range(n):
    for x2 in range(n):
        for y1 in range(n):
            for y2 in range(n):                
                cnt=0
                for i in range(n):
                    if min(x[x1],x[x2])<=x[i] and x[i]<=max(x[x1],x[x2]) and min(y[y1],y[y2])<=y[i] and y[i]<=max(y[y1],y[y2]):
                        cnt+=1
                        
                if cnt>=k:
                    ans=min(ans,abs(x[x2]-x[x1])*abs(y[y2]-y[y1]))
                    #print(x1,x2,y1,y2,ans)
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import combinations

def solve(N, K, XYs):
    ans = 10 ** 19 + 1
    XYs.sort(key=lambda x: x[0])
    for i, j in zip(range(N), range(K - 1, N)):
        xs = sorted([x for x, y in XYs[i:j + 1]])
        max_x = xs[-1]
        min_x = xs[0]
        ys = sorted([y for x, y in XYs[i:j + 1]])
        max_y = ys[-1]
        min_y = ys[0]
        ans = min(ans, abs(max_x - min_x) * abs(max_y - min_y))

    XYs.sort(key=lambda x: x[1])
    for i, j in zip(range(N), range(K - 1, N)):
        ys = sorted([y for x, y in XYs[i:j + 1]])
        max_y = ys[-1]
        min_y = ys[0]
        xs = sorted([x for x, y in XYs[i:j + 1]])
        max_x = xs[-1]
        min_x = xs[0]
        ans = min(ans, abs(max_x - min_x) * abs(max_y - min_y))

    return ans


if __name__ == "__main__":
    N, K = tuple(map(int, input().split(" ")))
    XYs = [tuple(map(int, input().split(" "))) for _ in range(N)]
    print(solve(N, K, XYs))

Submission status: Wrong Answer

Solution code:
def solve(N, K, XYs):
    ans = 10 ** 19 + 1
    XYs.sort(key=lambda x: x[0])
    for i, j in zip(range(N), range(K - 1, N)):
        max_x = XYs[j][0]
        min_x = XYs[i][0]
        ys = sorted([y for x, y in XYs[i:j + 1]])
        max_y = ys[-1]
        min_y = ys[0]
        ans = min(ans, abs(max_x - min_x) * abs(max_y - min_y))

    XYs.sort(key=lambda x: x[1])
    for i, j in zip(range(N), range(K - 1, N)):
        max_y = XYs[j][1]
        min_y = XYs[i][1]
        xs = sorted([x for x, y in XYs[i:j + 1]])
        max_x = xs[-1]
        min_x = xs[0]
        ans = min(ans, abs(max_x - min_x) * abs(max_y - min_y))

    return ans

if __name__ == "__main__":
    N, K = tuple(map(int, input().split(" ")))
    XYs = [tuple(map(int, input().split(" "))) for _ in range(N)]
    print(solve(N, K, XYs))

Submission status: Wrong Answer

Solution code:
def solve(N, K, XYs):
    ans = 10 ** 19 + 1
    XYs.sort(key=lambda x: x[0])
    for i, j in zip(range(N), range(K - 1, N)):
        print(XYs[i:j + 1])
        max_x = XYs[j][0]
        min_x = XYs[i][0]
        ys = sorted([y for x, y in XYs[i:j + 1]])
        max_y = ys[-1]
        min_y = ys[0]
        ans = min(ans, abs(max_x - min_x) * abs(max_y - min_y))

    XYs.sort(key=lambda x: x[1])
    for i, j in zip(range(N), range(K - 1, N)):
        print(XYs[i:j + 1])
        max_y = XYs[j][1]
        min_y = XYs[i][1]
        xs = sorted([x for x, y in XYs[i:j + 1]])
        max_x = xs[-1]
        min_x = xs[0]
        ans = min(ans, abs(max_x - min_x) * abs(max_y - min_y))

    return ans


if __name__ == "__main__":
    N, K = tuple(map(int, input().split(" ")))
    XYs = [tuple(map(int, input().split(" "))) for _ in range(N)]
    print(solve(N, K, XYs))

Submission status: Wrong Answer

Solution code:
def solve(N, K, XYs):
    ans = 10 ** 19 + 1
    XYs.sort(key=lambda x: x[0])
    for i, j in zip(range(N), range(K - 1, N)):
        max_x = XYs[j][0]
        min_x = XYs[i][0]
        ys = sorted([y for x, y in XYs[i:j + 1]])
        max_y = ys[-1]
        min_y = ys[0]
        ans = min(ans, (max_x - min_x) * (max_y - min_y))

    XYs.sort(key=lambda x: x[1])
    for i, j in zip(range(N), range(K - 1, N)):
        max_y = XYs[j][1]
        min_y = XYs[i][1]
        xs = sorted([x for x, y in XYs[i:j + 1]])
        max_x = xs[-1]
        min_x = xs[0]
        ans = min(ans, (max_x - min_x) * (max_y - min_y))

    return ans


if __name__ == "__main__":
    N, K = tuple(map(int, input().split(" ")))
    XYs = [tuple(map(int, input().split(" "))) for _ in range(N)]
    print(solve(N, K, XYs))

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
zahyou = []
for i in range(N):
  zahyou.append(list(map(int,input().split())))
ans = float('inf')
for h in range(N-1):
  for i in range(N-1):
    for j in range(i+1,N):
      kado1x = min(zahyou[i][0],zahyou[j][0])
      kado1y = min(zahyou[i][1],zahyou[j][1])
      kado2x = max(zahyou[i][0],zahyou[j][0])
      kado2y = max(zahyou[i][1],zahyou[j][1])
      L = [[kado1x,kado1y],[kado1x,kado2y],[kado2x,kado1y],[kado2x,kado2y]]
      for k in range(4):
        cnt = 0
        for l in range(N):
          if min(L[k][0],zahyou[h][0]) <= zahyou[l][0] <= max(L[k][0],zahyou[h][0]) and min(L[k][1],zahyou[h][1]) <= zahyou[l][1] <= max(L[k][1],zahyou[h][1]):
            cnt += 1
        if cnt >= K:
          if ans >= abs(L[k][0]-zahyou[h][0])*abs(L[k][1]-zahyou[h][1]) > 0:
            ans = abs(L[k][0]-zahyou[h][0])*abs(L[k][1]-zahyou[h][1])
print(ans)

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A
def A():
    return

#B
def B():
    return

#C
def C():
    def bfs(a,b):
        bfs_map = [1 for i in range(n)]
        bfs_map[0] = 0
        q = deque()
        q.append(0)
        s = 1
        while q:
            x = q.pop()
            for y in v[x]:
                if [x,y] != [a,b] and [x,y] != [b,a]:
                    if bfs_map[y]:
                        bfs_map[y] = 0
                        q.append(y)
                        s += 1
        return s
    n,m = LI()
    v = [deque() for i in range(n)]
    l = deque()
    for i in range(m):
        a,b = LI()
        a -= 1
        b -= 1
        v[a].append(b)
        v[b].append(a)
        l.append([a,b])
    ans = 0
    for a,b in l:
        s = bfs(a,b)
        if s < n:
            ans += 1
    print(ans)
#D
def D():
    n,k = LI()
    v = [None for i in range(n)]
    for i in range(n):
        v[i] = LI()
        v[i] = [[None,None]]+[v[i]]
    v.sort(key = lambda x:x[1][1])
    for i in range(n):
        v[i][0][1] = i
    v.sort(key = lambda x:x[1][0])
    for i in range(n):
        v[i][0][0] = i
    po = [[None for i in range(n)] for j in range(n)]
    h = [None for i in range(n)]
    w = [None for i in range(n)]
    for i in range(n):
        po[v[i][0][0]][v[i][0][1]] = v[i][1]
        h[v[i][0][0]] = v[i][1][0]
        w[v[i][0][1]] = v[i][1][1]
    re = [[[[0 for x in range(n)] for y in range(n)] for t in range(n)] for s in range(n)]
    ans = float("inf")
    for s in range(n):
        for t in range(n):
            for y in range(s,n):
                for x in range(t,n):
                    if x == s:
                        re[s][t][y][x] = re[s][t][y-1][x]
                    else:
                        re[s][t][y][x] = max(0,re[s][t][y][x-1]+re[s][t][y-1][x]-re[s][t][y-1][x-1])
                    if po[y][x] != None:
                        re[s][t][y][x] += 1
                    if re[s][t][y][x] >= k:
                        ans = min(ans,(h[y]-h[s])*(w[x]-w[t]))
    print(ans)
#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == "__main__":
    D()

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A
def A():
    return

#B
def B():
    return

#C
def C():
    def bfs(a,b):
        bfs_map = [1 for i in range(n)]
        bfs_map[0] = 0
        q = deque()
        q.append(0)
        s = 1
        while q:
            x = q.pop()
            for y in v[x]:
                if [x,y] != [a,b] and [x,y] != [b,a]:
                    if bfs_map[y]:
                        bfs_map[y] = 0
                        q.append(y)
                        s += 1
        return s
    n,m = LI()
    v = [deque() for i in range(n)]
    l = deque()
    for i in range(m):
        a,b = LI()
        a -= 1
        b -= 1
        v[a].append(b)
        v[b].append(a)
        l.append([a,b])
    ans = 0
    for a,b in l:
        s = bfs(a,b)
        if s < n:
            ans += 1
    print(ans)
#D
def D():
    n,k = LI()
    v = [None for i in range(n)]
    for i in range(n):
        v[i] = LI()
        v[i] = [[None,None]]+[v[i]]
    v.sort(key = lambda x:x[1][1])
    for i in range(n):
        v[i][0][1] = i
    v.sort(key = lambda x:x[1][0])
    for i in range(n):
        v[i][0][0] = i
    po = [[None for i in range(n)] for j in range(n)]
    h = [None for i in range(n)]
    w = [None for i in range(n)]
    for i in range(n):
        po[v[i][0][0]][v[i][0][1]] = v[i][1]
        h[v[i][0][0]] = v[i][1][0]
        w[v[i][0][1]] = v[i][1][1]
    re = [[[[0 for x in range(n)] for y in range(n)] for t in range(n)] for s in range(n)]
    ans = float("inf")
    for s in range(n):
        for t in range(n):
            for y in range(s,n):
                for x in range(t,n):
                    re[s][t][y][x] = max(0,re[s][t][y][x-1]+re[s][t][y-1][x]-re[s][t][y-1][x-1])
                    if po[y][x] != None:
                        re[s][t][y][x] += 1
                    if re[s][t][y][x] >= k:
                        ans = min(ans,(h[y]-h[s])*(w[x]-w[t]))
    print(ans)
#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == "__main__":
    D()

Submission status: Wrong Answer

Solution code:
import numpy as np

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


ans = np.inf

#m = 10**9 + 3

#F = [[0 for i in range(m*2)] for j in range(m*2)]

#for i in range(n) :
#    F[X[i][0]+m][X[i][1]+m] = 1

#for i in range(len(F)-1) :
#    F[0][i+1] += F[0][i]
#    F[i+1][0] += F[i][0]
#for i in range(len(F)-1) :
#    for j in range(len(F)-1) :
#        F[i+1][j+1] += F[i][j+1] + F[i+1][j] - F[i][j]

#X.sort()
#print(F)
for i in range(n) :
    for j in range(i, n) :
        x0 = X[i][0]
        x1 = X[j][0]
        for p in range(n) :
            for q in range(p, n) :
                y0 = min(X[p][1], X[q][1])
                y1 = max(X[p][1], X[q][1])

                co = 0
                for r in range(n) :
                    if x0<=X[r][0]<=x1 and y0<=X[r][1]<=y1 :
                        co += 1
                       

#                t = F[x1][y1] - F[x0-1][y1] - F[x1][y0-1] + F[x0-1][y0-1]
                if co >= k :
                    ans = min(ans, (y1-y0)*(x1-x0))
print(ans)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
xy = []
for _ in range(n):
  xy.append(tuple(map(int, input().split())))
xy = list(sorted(xy, key=lambda x: x[0]))
mins = None

for i in range(0, n-k+1):
  _xy = xy[i:i+k]
  if mins is None:
    mins = (_xy[-1][0] - _xy[0][0]) * (max(k[1] for k in _xy) - min(k[1] for k in _xy))
  elif mins > (_xy[-1][0] - _xy[0][0]) * (max(k[1] for k in _xy) - min(k[1] for k in _xy)):
    mins = (_xy[-1][0] - _xy[0][0]) * (max(k[1] for k in _xy) - min(k[1] for k in _xy))

xy = list(sorted(xy, key=lambda x: x[1]))
for i in range(0, n-k+1):
  _xy = xy[i:i+k]
  if mins > (_xy[-1][1] - _xy[0][1]) * (max(k[0] for k in _xy) - min(k[0] for k in _xy)):
    mins = (_xy[-1][1] - _xy[0][1]) * (max(k[0] for k in _xy) - min(k[0] for k in _xy))

print(mins)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
xy = []
for _ in range(n):
  xy.append(tuple(map(int, input().split())))
xy = list(sorted(xy, key=lambda x: x[0]))

mins = None

for i in range(0, n-k+1):
  _xy = xy[i:i+k]
  if mins is None:
    mins = (_xy[-1][0] - _xy[0][0]) * (max(k[1] for k in _xy) - min(k[1] for k in _xy))
  elif mins > (_xy[-1][0] - _xy[0][0]) * (max(k[1] for k in _xy) - min(k[1] for k in _xy)):
    mins = (_xy[-1][0] - _xy[0][0]) * (max(k[1] for k in _xy) - min(k[1] for k in _xy))

print(mins)

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

min_area = 10**100
for start in lst:
    for end in lst:
        count = 0
        for check in lst:
            if start[0] <= check[0] <= end[0] or start[0] >= check[0] >= end[0]:
                if start[1] <= check[1] <= end[1] or start[1] >= check[1] >= end[1]:
                    count += 1
        #print(count)
        if count >= k:
            area = abs(end[0] - start[0]) * abs(end[1] - start[1])
            if area < min_area:
                min_area = area
print(min_area)

Submission status: Wrong Answer

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

xlst = []
ylst = []

for x,y in XY:
    x += 10**9 + 1
    y += 10**9 + 1
    xlst.append(x)
    ylst.append(y)

xset = sorted(list(set(xlst)))
yset = sorted(list(set(ylst)))

# print(xset, yset)

S = [ [0]*(N+1) for _ in range(N+1)]

for x,y in zip(xset,yset):
    x = xset.index(x)+1
    # for y in yset:
    # print(xset, x)
    y = yset.index(y)+1
    S[y][x] = 1

for y in range(N+1):
    for x in range(1, N+1):
        S[y][x] += S[y][x-1]
for x in range(N+1):
    for y in range(1,N+1):
        S[y][x] += S[y-1][x]

# for i in S:
#     print(i)

# exit(0)

ans = float("inf")
for i in range(N):
    for j in range(N):
        for k in range(N):
            for ll in range(N):

                left     = xlst[i]
                right    = xlst[j]
                top      = ylst[k]
                bottom   = ylst[ll]

                if right <= left: continue
                if top <= bottom: continue

                left = xset.index(left)+1
                right = xset.index(right)+1
                top = yset.index(top)+1
                bottom=yset.index(bottom)+1


                cnt = 0
                cnt += S[top][right]
                # print(cnt)
                cnt += S[bottom-1][left-1]
                # print(cnt)
                cnt -= S[bottom-1][right]
                # print(cnt)
                cnt -= S[top][left-1]
                # print(cnt)
                if cnt >= K:
                    left = xset[left    -1 ]
                    right = xset[right  -1 ]
                    top = yset[top      -1 ]
                    bottom = yset[bottom-1 ]
                    rect_area = (right-left)*(top-bottom)
                    ans = min(ans, rect_area)
                
print(ans)

Submission status: Wrong Answer

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

xlst = []
ylst = []

for x,y in XY:
    x += 10**9 + 1
    y += 10**9 + 1
    xlst.append(x)
    ylst.append(y)

xset = sorted(list(set(xlst)))
yset = sorted(list(set(ylst)))

# print(xset, yset)

S = [ [0]*(N+1) for _ in range(N+1)]

for x,y in zip(xset,yset):
    x = xset.index(x)+1
    # for y in yset:
    # print(xset, x)
    y = yset.index(y)+1
    S[y][x] = 1

for y in range(N+1):
    for x in range(1, N+1):
        S[y][x] += S[y][x-1]
for x in range(N+1):
    for y in range(1,N+1):
        S[y][x] += S[y-1][x]

# for i in S:
#     print(i)

# exit(0)

ans = float("inf")
for i in range(N):
    for j in range(N):
        for k in range(N):
            for ll in range(N):

                left     = xlst[i]
                right    = xlst[j]
                top      = ylst[k]
                bottom   = ylst[ll]
                # if right >= left: continue
                # if top <= bottom: continue
                left = xset.index(left)+1
                right = xset.index(right)+1
                top = yset.index(top)+1
                bottom=yset.index(bottom)+1


                cnt = 0
                cnt += S[top][right]
                # print(cnt)
                cnt += S[bottom-1][left-1]
                # print(cnt)
                cnt -= S[bottom-1][right]
                # print(cnt)
                cnt -= S[top][left-1]
                # print(cnt)
                if cnt >= K:
                    left = xset[left    -1 ]
                    right = xset[right  -1 ]
                    top = yset[top      -1 ]
                    bottom = yset[bottom-1 ]
                    rect_area = (right-left)*(top-bottom)
                    ans = min(ans, rect_area)
                
print(ans)

Submission status: Wrong Answer

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

xlst = []
ylst = []

for x,y in XY:
    x += 10**9 + 1
    y += 10**9 + 1
    xlst.append(x)
    ylst.append(y)

xset = sorted(list(set(xlst)))
yset = sorted(list(set(ylst)))

# print(xset, yset)

S = [ [0]*(N+1) for _ in range(N+1)]

for x,y in zip(xset,yset):
    x = xset.index(x)+1
    # for y in yset:
    # print(xset, x)
    y = yset.index(y)+1
    S[y][x] = 1

for y in range(N+1):
    for x in range(1, N+1):
        S[y][x] += S[y][x-1]
for x in range(N+1):
    for y in range(1,N+1):
        S[y][x] += S[y-1][x]

for i in S:
    print(i)

# exit(0)

ans = float("inf")
for i in range(N):
    for j in range(N):
        for k in range(N):
            for ll in range(N):

                left     = xlst[i]
                right    = xlst[j]
                top      = ylst[k]
                bottom   = ylst[ll]
                # if right >= left: continue
                # if top <= bottom: continue
                left = xset.index(left)+1
                right = xset.index(right)+1
                top = yset.index(top)+1
                bottom=yset.index(bottom)+1


                cnt = 0
                cnt += S[top][right]
                # print(cnt)
                cnt += S[bottom-1][left-1]
                # print(cnt)
                cnt -= S[bottom-1][right]
                # print(cnt)
                cnt -= S[top][left-1]
                # print(cnt)
                if cnt >= K:
                    left = xset[left    -1 ]
                    right = xset[right  -1 ]
                    top = yset[top      -1 ]
                    bottom = yset[bottom-1 ]
                    rect_area = (right-left)*(top-bottom)
                    ans = min(ans, rect_area)
                
print(ans)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
x_lst = sorted([list(map(int, input().split())) for _ in range(N)], key = lambda z: z[0])
y_lst = sorted(x_lst, key = lambda z: z[1])
ans = 10**20
for i in range(N - K + 1):
    b = x_lst[K + i - 1][0] - x_lst[i][0]
    h = max(x_lst[i:K+i], key = lambda z: z[1])[1] - min(x_lst[i:K+i], key = lambda z: z[1])[1]
    ans = min(ans, b * h)
for i in range(N - K + 1):
    h = y_lst[K + i - 1][1] - y_lst[i][1]
    b = max(y_lst[i:K+i], key = lambda z: z[0])[0] - min(y_lst[i:K+i], key = lambda z: z[0])[0]
    ans = min(ans, b * h)
print(ans)

Submission status: Wrong Answer

Solution code:
# d
N,K = map(int, input().split())
xs,ys = [],[]
for _ in range(N):
    x,y = map(int, input().split())
    xs.append(x)
    ys.append(y)
xs.sort()
ys.sort()
ans = float('inf')
for l in range(N):
    for r in range(l+1,N):
        for b in range(N):
            for t in range(b+1,N):
                xl,xr = xs[l],xs[r]
                yb,yt = ys[b],ys[t]
                cnt = 0
                for xi,yi in zip(xs,ys):
                    if xl<=xi<=xr and yb<=yi<=yt: 
                        cnt += 1
                if cnt>=K:
                    ans = min(ans, (xr-xl)*(yt-yb))
print(ans)

Submission status: Wrong Answer

Solution code:
# d
N,K = map(int, input().split())
xy = []
for _ in range(N):
    xy.append( tuple(map(int, input().split())) )
xy.sort(key=lambda x:x[0])
ans = float('inf')
for j in range(K, N+1):
    for i in range(N-j+1):
        use = xy[i:i+j]
        use_x,use_y = list(zip(*use))
        area = abs(max(use_x)-min(use_x)) * abs(max(use_y)-min(use_y))
        ans = min(ans, area)
print(ans)

Submission status: Wrong Answer

Solution code:
# d
N,K = map(int, input().split())
xy = []
for _ in range(N):
    xy.append( tuple(map(int, input().split())) )
xy.sort(key=lambda x:x[0])
ans = float('inf')
for j in range(K, N+1):
    for i in range(N-j+1):
        use = xy[i:i+K]
        use_x,use_y = list(zip(*use))
        area = abs(max(use_x)-min(use_x)) * abs(max(use_y)-min(use_y))
        ans = min(ans, area)
print(ans)