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())
x = []
y = []
for i in range(n):
    a,b = map(int,input().split())
    x.append(a)
    y.append(b)
ans = 10 ** 40
x.sort()
y.sort()
for i in range(n-1):
    for j in range(i+1,n):
        for l in range(n-1):
            for h in range(l+1,n):
                lx = x[i]
                rx = x[j]
                uy = y[h]
                dy = y[l]
                cnt = 0
                for ii in range(n):
                    if lx <= x[ii] <= rx and dy <= y[ii] <= uy:
                        cnt += 1
                if cnt >= k:
                    ans = min(ans,(rx-lx)*(uy-dy))
print(ans)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
xy = sorted([list(map(int, input().split())) for _ in range(n)])
x, y = zip(*xy)
ans = float("inf")
for i in range(n-k+1):
  for j in range(i+k-1, n):
    dx = x[j] - x[i]
    dy = max(y[i:j+1]) - min(y[i:j+1])
    ans = min(ans, dx*dy)
print(ans)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
xy = sorted([list(map(int, input().split())) for _ in range(n)])
x, y = zip(*xy)
ans = float("inf")
for i in range(n-k+1):
  dx = x[i+k-1] - x[i]
  dy = max(y[i:i+k]) - min(y[i:i+k])
  ans = min(ans, dx*dy)
print(ans)

Submission status: Wrong Answer

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

ys.sort()
xs.sort()

ans = []
# y優先
idx = []
dy = float('INF')
for i in range(n-k+1):
    y1 = ys[i]
    y2 = ys[i+k-1]
    if dy > y2 - y1:
        dy = y2 - y1
        idx = [i]
    elif dy == y2 - y1:
        idx.append(i)

graph.sort(key=lambda x: x[1])
for i in idx:
    x1, x2 = min([x for x, y in graph[i:i+k]]), max([x for x, y in graph[i:i+k]])
    y1, y2 = graph[i][1], graph[i+k-1][1]
    ans.append((x2-x1)*(y2-y1))


# x優先
idx = []
dx = float('INF')
for i in range(n-k+1):
    x1 = xs[i]
    x2 = xs[i+k-1]
    if dx > x2 - x1:
        dx = x2 - x1
        idx = [i]
    elif dx == x2 - x1:
        idx.append(i)

graph.sort()
for i in idx:
    y1, y2 = min([y for x, y in graph[i:i+k]]), max([y for x, y in graph[i:i+k]])
    x1, x2 = graph[i][0], graph[i+k-1][0]
    ans.append((x2-x1)*(y2-y1))

print(min(ans))

Submission status: Wrong Answer

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

x.sort()
y.sort()

ans = (x[-1] - x[0]) * (y[-1] - y[0])

for xi in range(n):
    for xj in range(xi+1, n):
        for yi in range(n):
            for yj in range(yi+1, n):
                num = 0
                lx = x[xi]
                rx = x[xj]
                by = y[yi]
                uy = y[yj]

                for i in range(n):
                    if lx <= x[i] and x[i] <= rx and by <= y[i] and y[i] <= uy:
                        num += 1
                if num >= k:
                    ans = min(ans, (rx - lx) * (uy - by))

print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations,groupby
import sys
import bisect
import string
import math
import time
import random
def S_():
    return input()
def LS():
    return [i for i in input().split()]
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)]
        rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
#sys.setrecursionlimit(10**5)
input=lambda: sys.stdin.readline().rstrip()

def ran_input():
    import random
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

show_flg=False
show_flg=True

ans=1

n,k=LI()
a=[]

for i in range(n):
    x,y=LI()
    a.append((x,y))

a.sort()

ans=inf

for lx in range(n):
    for rx in range(lx+1,n):
        for ly in range(n):
            for ry in range(ly+1,n):
                c=0
                x1,x2,y1,y2=a[lx][0],a[rx][0],a[ly][1],a[ry][1]
                for i in range(lx,rx+1):
                    x,y=a[i]
                    if x1<=x<=x2 and y1<=y<=y2:
                        c+=1
                
#                show(c,lx,rx,ly,ry,(x1,x2,y1,y2))
                if c>=k:
                    ans=min(ans,(x2-x1)*(y2-y1))

print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations,groupby
import sys
import bisect
import string
import math
import time
import random
def S_():
    return input()
def LS():
    return [i for i in input().split()]
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)]
        rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
#sys.setrecursionlimit(10**5)
input=lambda: sys.stdin.readline().rstrip()

def ran_input():
    import random
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

show_flg=False
show_flg=True

ans=1

n,k=LI()
a=[]

for i in range(n):
    x,y=LI()
    a.append((x,y))

a.sort()

ans=inf

for lx in range(n):
    for rx in range(lx+1,n):
        for ly in range(n):
            for ry in range(ly+1,n):
                c=0
                x1,x2,y1,y2=a[lx][0],a[rx][0],a[ly][0],a[ly][1]
                for i in range(lx,rx+1):
                    x,y=a[i]
                    if x1<=x<=x2 and y1<=y<=y2:
                        c+=1
                if c>=k:
                    ans=min(ans,(x2-x1)*(y2-y1))


print(ans)

Submission status: Wrong Answer

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

answer = []
for i in range(N):
  for j in range(i + 1, N):
    x1, y1 = XY[i]
    x2, y2 = XY[j]
    x1, x2 = min(x1, x2), max(x1, x2)
    y1, y2 = min(y1, y2), max(y1, y2)
    
    cnt = 0
    for n in range(N):
      x3, y3 = XY[n]
      if x1 <= x3 <= x2 and y1 <= y3 <= y2:
        cnt += 1
    #print(cnt, x1, x2, y1, y2)
    if cnt >= K:
      answer.append((x2 - x1) * (y2 - y1))
print(answer)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

import sys
from operator import itemgetter

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
# 20億^2で10^18を超えるので19乗で
INF = 10 ** 19
MOD = 10 ** 9 + 7

N, K = MAP()
XY = []
for i in range(N):
    x, y = MAP()
    XY.append((x, y))

# xとyでそれぞれソート
XY1 = sorted(XY, key=itemgetter(0))
XY2 = sorted(XY, key=itemgetter(1))

# XY1とXY2両方で、区間Kとなるものを1つずつ確認していく
ans = INF
for i in range(N-K+1):
    seg = XY1[i:i+K]
    X, Y = zip(*seg)
    xlen = X[-1] - X[0]
    # 制約が小さいので、ソートされてない方は毎回minmax取っても全然大丈夫
    ylen = max(Y) - min(Y)
    ans = min(ans, xlen * ylen)
for i in range(N-K+1):
    seg = XY2[i:i+K]
    X, Y = zip(*seg)
    xlen = max(X) - min(X)
    ylen = Y[-1] - Y[0]
    ans = min(ans, xlen * ylen)
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, Y = [], []
for x, y in XY:
  X.append(x)
  Y.append(y)
X.sort()
Y.sort()
  
answer = 10 ** 10
for ix in range(N):
  xi = X[ix]
  for jx in range(ix + 1, N):
    xj = X[jx]
    for iy in range(N):
      yi = Y[iy]
      for jy in range(iy + 1, N):
        yj = Y[jy]
        cnt = 0
        for ii in range(N):
          if xi <= X[ii] <= xj and yi <= Y[ii] <= yj:
            cnt += 1
        if cnt == K:
          answer = min((xj - xi) * (yj - yi), answer)

print(answer)

Submission status: Wrong Answer

Solution code:
import sys

inf = float('inf')

n, k, *xy = map(int, sys.stdin.read().split())
xy = list(zip(*[iter(xy)] * 2))

def minimize(xy, key):
    xy = sorted(xy, key=lambda x: x[key])
    x = []
    y = []
    for i in range(n):
        x.append(xy[i][0])
        y.append(xy[i][1])
    if key == 1:
        x, y = y, x
    
    area = inf
    for i in range(n-k+1):
        l = i; r = i + k - 1
        dx = x[r] - x[l]
        seq_y = sorted(y[l:r+1])
        dy = seq_y[-1] - seq_y[0]
        area = min(area, dx * dy)
    return area

def main():
    return min(minimize(xy, 0), minimize(xy, 1))

if __name__ == '__main__':
    ans = main()
    print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import*
n,k,*L=map(int,open(0).read().split())
p=sorted((x,y) for x,y in zip(*[iter(L)]*2))
ans=float("inf")
for mi,Mi in combinations(range(n),2):
	if Mi-mi<k-1:
		continue
	w=p[Mi][0]-p[mi][0]
	l=[p[j][1] for j in range(mi,Mi+1)]
	ans=min(ans,w*(max(l)-min(l)))
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import*
n,k,*L=map(int,open(0).read().split())
p=[(x,y) for x,y in zip(*[iter(L)]*2)]
X=sorted(x for x,y in p)
Y=sorted(y for x,y in p)
ans=float("inf")
for i,mx in enumerate(X[-k:]):
	for Mx in X[i+k-1:]:
		for my,My in combinations(Y,2):
			if sum(mx<=x<=Mx and my<=y<=My for x,y in p)>=k:
				ans=min(ans,(Mx-mx)*(My-my))
print(ans)

Submission status: Wrong Answer

Solution code:
n,k,*l=map(int,open(0).read().split())
p=sorted((x,y) for x,y in zip(*[iter(l)]*2))
ans=float('inf')
for i in range(n-k+1):
	w=p[i+k-1][0]-p[i][0]
	y=[p[j][1] for j in range(i,i+k)]
	ans=min(ans,w*(max(y)-min(y)))
print(ans)

Submission status: Wrong Answer

Solution code:
n,k,*l=map(int,open(0).read().split())
p=sorted((x,y) for x,y in zip(*[iter(l)]*2))
ans=1<<100
for i in range(n-k+1):
	w=p[i+k-1][0]-p[i][0]
	y=[p[j][1] for j in range(i,i+k)]
	ans=min(ans,w*(max(y)-min(y)))
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
N,K=map(int,input().split())
XY=[list(map(int,input().split())) for i in range(N)]
ans=float("inf")
xlist=itertools.combinations( [xy[0] for xy in XY] ,2)
ylist=itertools.combinations( [xy[1] for xy in XY] ,2)

for xv in xlist:
  for yv in ylist:
    xmax=max(xv[0],yv[1])
    xmin=min(xv[0],xv[1])
    ymax=max(yv[0],yv[1])
    ymin=min(yv[0],yv[1])

    k=0
    for xy in XY:
      x,y=xy[0],xy[1]
      if xmin<=x and x<=xmax:
        if ymin<=y and y<=ymax:
          k+=1    
    if k>=K:
      ans=min(ans,(xmax-xmin)*(ymax-ymin))
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
N,K=map(int,input().split())
XY=[list(map(int,input().split())) for i in range(N)]
l=[i for i in range(N)]
ans=float("inf")
    
for v in itertools.combinations(l,4):
  for i in range(3):
    if i==0:
      xmax=max(XY[v[0]][0],XY[v[1]][0],XY[v[2]][0],XY[v[3]][0])
      xmin=min(XY[v[0]][0],XY[v[1]][0],XY[v[2]][0],XY[v[3]][0])
      ymax=max(XY[v[0]][1],XY[v[1]][1],XY[v[2]][1],XY[v[3]][1])
      ymin=min(XY[v[0]][1],XY[v[1]][1],XY[v[2]][1],XY[v[3]][1])
    elif i==1:
      for j in itertools.combinations(v,3):
        xmax=max(XY[j[0]][0],XY[j[1]][0],XY[j[2]][0])
        xmin=min(XY[j[0]][0],XY[j[1]][0],XY[j[2]][0])
        ymax=max(XY[j[0]][1],XY[j[1]][1],XY[j[2]][1])
        ymin=min(XY[j[0]][1],XY[j[1]][1],XY[j[2]][1])
    else:
      for j in itertools.combinations(v,2):
        xmax=max(XY[j[0]][0],XY[j[1]][0])
        xmin=min(XY[j[0]][0],XY[j[1]][0])
        ymax=max(XY[j[0]][1],XY[j[1]][1])
        ymin=min(XY[j[0]][1],XY[j[1]][1])
  
    k=0
    for xy in XY:
      x,y=xy[0],xy[1]
      if xmin<=x and x<=xmax:
        if ymin<=y and y<=ymax:
          k+=1    
    if k>=K:
      ans=min(ans,(xmax-xmin)*(ymax-ymin))
print(ans)

Submission status: Wrong Answer

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

ans = 10 ** 20
for xl in range(N):
    for xr in range(xl + 1, N):
        Ysub = sorted([y for x, y in XY[xl:xr + 1]])
        for i in range(xr - xl - K + 2):
            ans = min(ans, (XY[xr][0] - XY[xl][0]) * (max(Ysub) - min(Ysub)))

print(ans)

Submission status: Wrong Answer

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

ans = 10 ** 20

XY.sort()
for i in range(N - K + 1):
    X, Y = [x for x, y in XY[i:i + K]], [y for x, y in XY[i:i + K]]
    ans = min(ans, (max(Y) - min(Y)) * (max(X) - min(X)))

XY.sort(key=lambda x: x[1])
for i in range(N - K + 1):
    X, Y = [x for x, y in XY[i:i + K]], [y for x, y in XY[i:i + K]]
    ans = min(ans, (max(Y) - min(Y)) * (max(X) - min(X)))

print(ans)

Submission status: Wrong Answer

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

ans = 10 ** 20
for i in range(N - K + 1):
    X, Y = [x for x, y in XY[i:i + K]], [y for x, y in XY[i:i + K]]
    ans = min(ans, (max(Y) - min(Y)) * (max(X) - min(X)))

print(ans)

Submission status: Wrong Answer

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

ans = float("inf")
for L in range(K, N+1):
    xy.sort(key=lambda x: x[0])
    for i in range(N-L+1):
        tmp = xy[i:i+L]
        x = [10**9, -1*10**9]
        y = [10**9, -1*10**9]
        for j in range(K):
            y[0] = min(y[0], tmp[j][1])
            y[1] = max(y[1], tmp[j][1])
            x[0] = min(x[0], tmp[j][0])
            x[1] = max(x[1], tmp[j][0])

        ans = min(ans, (y[1]-y[0])*(x[1]-x[0]))

    xy.sort(key=lambda x: x[1])
    for i in range(N-L+1):
        tmp = xy[i:i+L]
        x = [10**9, -1*10**9]
        y = [10**9, -1*10**9]
        for j in range(K):
            y[0] = min(y[0], tmp[j][1])
            y[1] = max(y[1], tmp[j][1])
            x[0] = min(x[0], tmp[j][0])
            x[1] = max(x[1], tmp[j][0])

        ans = min(ans, (y[1]-y[0])*(x[1]-x[0]))
print(ans)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
xy = [tuple(map(int, input().split())) for i in range(N)]
xy.sort(key=lambda x: x[0])
ans = float("inf")
for L in range(K, N+1):
    for i in range(N-L+1):
        tmp = xy[i:i+L]
        x = [10**9, -1*10**9]
        y = [10**9, -1*10**9]
        for j in range(K):
            y[0] = min(y[0], tmp[j][1])
            y[1] = max(y[1], tmp[j][1])
            x[0] = min(x[0], tmp[j][0])
            x[1] = max(x[1], tmp[j][0])

        ans = min(ans, (y[1]-y[0])*(x[1]-x[0]))

    xy.sort(key=lambda x: x[1])
    for i in range(N-L+1):
        tmp = xy[i:i+L]
        x = [10**9, -1*10**9]
        y = [10**9, -1*10**9]
        for j in range(K):
            y[0] = min(y[0], tmp[j][1])
            y[1] = max(y[1], tmp[j][1])
            x[0] = min(x[0], tmp[j][0])
            x[1] = max(x[1], tmp[j][0]) 

        ans = min(ans, (y[1]-y[0])*(x[1]-x[0]))
print(ans)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
xy = [tuple(map(int, input().split())) for i in range(N)]
xy.sort(key=lambda x: x[1])
xy.sort(key=lambda x: x[0])
ans = float("inf")
for i in range(N-K+1):
    tmp = xy[i:i+K]
    x = [10**9, -1*10**9]
    y = [10**9, -1*10**9]
    for j in range(K):
        y[0] = min(y[0], tmp[j][1])
        y[1] = max(y[1], tmp[j][1])
        x[0] = min(x[0], tmp[j][0])
        x[1] = max(x[1], tmp[j][0])

    ans = min(ans, (y[1]-y[0])*(x[1]-x[0]))

xy.sort(key=lambda x: x[1])
for i in range(N-K+1):
    tmp = xy[i:i+K]
    x = [10**9, -1*10**9]
    y = [10**9, -1*10**9]
    for j in range(K):
        y[0] = min(y[0], tmp[j][1])
        y[1] = max(y[1], tmp[j][1])
        x[0] = min(x[0], tmp[j][0])
        x[1] = max(x[1], tmp[j][0])

    ans = min(ans, (y[1]-y[0])*(x[1]-x[0]))
print(ans)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
xy = [tuple(map(int, input().split())) for i in range(N)]
xy.sort(key=lambda x: x[1])
xy.sort(key=lambda x: x[0])
ans = 4*10**18
for i in range(N-K+1):
    tmp = xy[i:i+K]
    x = [10**9, -1*10**9]
    y = [10**9, -1*10**9]
    for j in range(K):
        y[0] = min(y[0], tmp[j][1])
        y[1] = max(y[1], tmp[j][1])
        x[0] = min(x[0], tmp[j][0])
        x[1] = max(x[1], tmp[j][0])

    ans = min(ans, (y[1]-y[0])*(x[1]-x[0]))

xy.sort(key=lambda x: x[1])
for i in range(N-K+1):
    tmp = xy[i:i+K]
    x = [10**9, -1*10**9]
    y = [10**9, -1*10**9]
    for j in range(K):
        y[0] = min(y[0], tmp[j][1])
        y[1] = max(y[1], tmp[j][1])
        x[0] = min(x[0], tmp[j][0])
        x[1] = max(x[1], tmp[j][0])

    ans = min(ans, (y[1]-y[0])*(x[1]-x[0]))
print(ans)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
xy = [tuple(map(int, input().split())) for i in range(N)]
xy.sort(key=lambda x: x[1])
xy.sort(key=lambda x: x[0])
ans = 4*10**18
for i in range(N-K+1):
    tmp = xy[i:i+K]
    y = [10**9, -1*10**9]
    for j in range(K):
        y[0] = min(y[0], tmp[j][1])
        y[1] = max(y[1], tmp[j][1])

    ans = min(ans, (tmp[-1][0]-tmp[0][0])*(y[1]-(y[0])))

xy.sort(key=lambda x: x[1])
for i in range(N-K+1):
    tmp = xy[i:i+K]
    x = [10**9, -1*10**9]
    for j in range(K):
        x[0] = min(x[0], tmp[j][0])
        x[1] = max(x[1], tmp[j][0])

    ans = min(ans, (tmp[-1][1]-tmp[0][1])*(x[1]-(x[0])))
print(ans)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
xy = [tuple(map(int, input().split())) for i in range(N)]
xy.sort(key=lambda x: x[1])
xy.sort(key=lambda x: x[0])
ans = 10**20
for i in range(N-K+1):
    tmp = xy[i:i+K]
    y = [10**9, -1*10**9]
    for j in range(K):
        y[0] = min(y[0], xy[i+j][1])
        y[1] = max(y[1], xy[i+j][1])

    ans = min(ans, (tmp[-1][0]-tmp[0][0])*(y[1]-(y[0])))

xy.sort(key=lambda x: x[1])
for i in range(N-K+1):
    tmp = xy[i:i+K]
    x = [10**9, -1*10**9]
    for j in range(K):
        x[0] = min(x[0], xy[i+j][0])
        x[1] = max(x[1], xy[i+j][0])

    ans = min(ans, (tmp[-1][1]-tmp[0][1])*(x[1]-(x[0])))
print(ans)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
xy = [tuple(map(int, input().split())) for i in range(N)]
xy.sort(key=lambda x: x[1])
xy.sort(key=lambda x: x[0])
ans = 4*10**18
for i in range(N-K+1):
    tmp = xy[i:i+K]
    y = [10**9, -1*10**9]
    for j in range(K):
        y[0] = min(y[0], xy[i+j][1])
        y[1] = max(y[1], xy[i+j][1])

    ans = min(ans, (tmp[-1][0]-tmp[0][0])*(y[1]-(y[0])))

xy.sort(key=lambda x: x[1])
for i in range(N-K+1):
    tmp = xy[i:i+K]
    x = [10**9, -1*10**9]
    for j in range(K):
        x[0] = min(x[0], xy[i+j][0])
        x[1] = max(x[1], xy[i+j][0])

    ans = min(ans, (tmp[-1][1]-tmp[0][1])*(x[1]-(x[0])))
print(ans)

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
xy=[tuple(map(int,input().split())) for i in range(N)]
xy.sort(key=lambda x:x[0])
ans=4*10**18
for i in range(N-K+1):
  tmp=xy[i:i+K]
  y=[10**9,-1*10**9]
  for j in range(K):
    y[0]=min(y[0],xy[i+j][1])
    y[1]=max(y[1],xy[i+j][1])
  ans=min(ans,(tmp[-1][0]-tmp[0][0])*(y[1]-(y[0])))
  
xy.sort(key=lambda x:x[1])
for i in range(N-K+1):
  tmp=xy[i:i+K]
  x=[10**9,-1*10**9]
  for j in range(K):
    x[0]=min(x[0],xy[i+j][0])
    x[1]=max(x[1],xy[i+j][0])
  ans=min(ans,(tmp[-1][1]-tmp[0][1])*(x[1]-(x[0])))
print(ans)

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
xy=[tuple(map(int,input().split())) for i in range(N)]
xy.sort(key=lambda x:x[0])
ans=4*10**18
for i in range(N-K+1):
  tmp=xy[i:i+K]
  y=[10**9,-1*10**9]
  for j in range(K):
    y[0]=min(y[0],xy[j][1])
    y[1]=max(y[1],xy[j][1])
  ans=min(ans,(tmp[-1][0]-tmp[0][0])*(y[1]-(y[0])))
  
xy.sort(key=lambda x:x[1])
for i in range(N-K+1):
  tmp=xy[i:i+K]
  x=[10**9,-1*10**9]
  for j in range(K):
    x[0]=min(x[0],xy[j][0])
    x[1]=max(x[1],xy[j][0])
  ans=min(ans,(tmp[-1][1]-tmp[0][1])*(x[1]-(x[0])))
print(ans)

Submission status: Wrong Answer

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

    ans = ((10**9)*2)**2 + 5
    xy.sort(key=lambda p: p[0])
    for i in range(N-K+1):
        x_min = xy[i][0]
        x_max = xy[i+K-1][0]
        y_min = (10**9)*2 + 5
        y_max = -((10**9)*2 + 5)
        for j in range(i, i+K):
            y_min = min(y_min, xy[j][1])
            y_max = max(y_max, xy[j][1])
        ans = min(ans, (x_max-x_min)*(y_max-y_min))
    xy.sort(key=lambda p: p[1])
    for i in range(N-K+1):
        x_min = (10**9)*2 + 5
        x_max = -((10**9)*2 + 5)
        y_min = xy[i][1]
        y_max = xy[i+K-1][1]
        for j in range(i, i+K):
            x_min = min(x_min, xy[j][0])
            x_max = max(x_max, xy[j][0])
        ans = min(ans, (x_max-x_min)*(y_max-y_min))
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

    ans = ((10**9)*2)**2 + 5
    xy.sort(key=lambda p: p[0])
    for i in range(N-K+1):
        x_min = (10**9)*2 + 5
        x_max = -((10**9)*2 + 5)
        y_min = (10**9)*2 + 5
        y_max = -((10**9)*2 + 5)
        for j in range(i, i+K):
            x_min = min(x_min, xy[j][0])
            x_max = max(x_max, xy[j][0])
            y_min = min(y_min, xy[j][1])
            y_max = max(y_max, xy[j][1])
        ans = min(ans, (x_max-x_min)*(y_max-y_min))
    xy.sort(key=lambda p: p[1])
    for i in range(N-K+1):
        x_min = (10**9)*2 + 5
        x_max = -((10**9)*2 + 5)
        y_min = (10**9)*2 + 5
        y_max = -((10**9)*2 + 5)
        for j in range(i, i+K):
            x_min = min(x_min, xy[j][0])
            x_max = max(x_max, xy[j][0])
            y_min = min(y_min, xy[j][1])
            y_max = max(y_max, xy[j][1])
        ans = min(ans, (x_max-x_min)*(y_max-y_min))
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    N, K = map(int, input().split())
    x = [0] * N
    y = [0] * N
    for i in range(N):
        x[i], y[i] = map(int, input().split())
        
    ans = float('inf')

    for i in range(N):
        for j in range(N):
            for k in range(N):
                for l in range(N):
                    if x[i] < x[j] and y[k] < y[l]:
                        right = x[i]
                        left = x[j]
                        bottom = y[k]
                        top = y[l]

                        cnt = 0

                        for i in range(N):
                            if right <= x[i] <= left and bottom <= y[i] <= top:
                                cnt += 1

                        if cnt >= K:
                            ans = min(ans, (top - bottom) * (right - left))
    print(ans)



if __name__ == "__main__":
    main()

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),2)
d=itertools.combinations(range(n),2)
ans=10**10
for i0 in range(n):
    for i1 in range(n):
        for j0 in range(n):
            for j1 in range(n):
                i=[i0,i1]
                j=[j0,j1]
                #print(i,j)
                lx=min(l[i[0]][0],l[i[1]][0])
                rx=max(l[i[0]][0],l[i[1]][0])
                dy=min(l[j[0]][1],l[j[1]][1])
                uy=max(l[j[0]][1],l[j[1]][1])
                tk=0
                for p in l:
                    if lx<=p[0]<=rx and dy<=p[1]<=uy:
                        tk+=1
                if tk>=k:
                    ans=min(ans,(uy-dy)*(rx-lx))
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),2)
ans=1e25
for i in c:
    for j in c:
        lx=min(l[i[0]][0],l[i[1]][0])
        rx=max(l[i[0]][0],l[i[1]][0])
        dy=min(l[j[0]][1],l[j[1]][1])
        uy=max(l[j[0]][1],l[j[1]][1])
        tk=0
        for p in l:
            if lx<=p[0]<=rx and dy<=p[1]<=uy:
                tk+=1
        if tk>=k:
            ans=min(ans,(uy-dy)*(rx-lx))
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),2)
ans=1e25
for i in c:
    p=l[i[0]]
    q=l[i[1]]
    uy=max(p[1],q[1])
    dy=min(p[1],q[1])
    lx=min(p[0],q[0])
    rx=max(p[0],q[0])
    tk=0
    for j in l:
        if lx<=j[0]<=rx and dy<=j[1]<=uy:
            tk+=1
    if tk>=k:
        ans=min(ans,(uy-dy)*(rx-lx))
print(ans)

Submission status: Wrong Answer

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

dp1 = [[-float('inf')] * n for _ in range(n+1)]
dp2 = [[-float('inf')] * n for _ in range(n+1)]
dp3 = [[float('inf')] * n for _ in range(n+1)]
dp4 = [[float('inf')] * n for _ in range(n+1)]

# k = 1
for i in range(n):
    dp1[1][i] = xy[i][0]
    dp2[1][i] = xy[i][1]
    dp3[1][i] = xy[i][0]
    dp4[1][i] = xy[i][1]


for i in range(2, n+1):
    for j in range(i-1, n):
        # xy[j]までを使ってi点含む最小の面積の座標
        minarea = float('inf')
        for a in range(j):
            tmp = [(min(xy[j][0], dp1[i-1][a]), min(xy[j][1], dp2[i-1][a])), (max(xy[j][0], dp3[i-1][a]), max(xy[j][1], dp4[i-1][a]))]
            area = (tmp[1][1] - tmp[0][1]) * (tmp[1][0] - tmp[0][0])
            if area < minarea:
                minarea = area
                ret = tmp

        dp1[i][j] = ret[0][0]
        dp2[i][j] = ret[0][1]
        dp3[i][j] = ret[1][0]
        dp4[i][j] = ret[1][1]
        # print(i, j, minarea)

minarea = float('inf')
for i in range(k, n+1):
    for j in range(len(dp1[i])):
        tmp = [(dp1[i][j], dp2[i][j]), (dp3[i][j], dp4[i][j])]
        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)]

dp_all = [[]]

# 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)
dp_all.append(dp)

for i in range(2, n+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
    dp_all.append(dp)
    # print(i, dp)

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

print(minarea)