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())
S = []
T = []
A = []
for i in range(N):
    x, y = map(int, input().split())
    S.append(x)
    T.append(y)
    A.append([x, y])

S.sort()
T.sort()
ans = float("inf")
for i in range(N):
    for j in range(i+1, N):
        for k in range(N):
            for l in range(i+1, N):
                c = 0
                for x, y in A:
                    if S[i] <= x <= S[j]:
                        if T[k] <= y <= T[l]:
                            c += 1
                if c >= K:
                    ans = min(ans, (S[j] - S[i])*(T[l] - T[k]))
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import combinations

N, K = [int(i) for i in input().split()]
XYS = [[int(i) for i in input().split()] for _ in range(N)]

INF = float('inf')
mina = INF
for XY in combinations(XYS, K):
  minx, miny, maxx, maxy = INF, INF, 0, 0
  for x, y in XY:
    minx = min(minx, x)
    miny = min(miny, y)
    maxx = max(maxx, x)
    maxy = max(maxy, y)
  mina = min(mina, (maxx - minx) * (maxy - miny))

print(mina)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
XY = [tuple(map(int, input().split())) for _ in range(n)]
# それぞれのxyについて、距離と相手を記録
xy_dists = [[] for _ in range(n)]
for i, (x0, y0) in enumerate(XY[:n-1]):
    for j in range(i+1, n):
        x1, y1 = XY[j]
        d = abs(x0-x1) + abs(y0-y1)
        xy_dists[i].append((d, x1, y1))
        xy_dists[j].append((d, x0, y0))

ans = 10**19
for i in range(n):
    xi, yi = XY[i]
    # 距離が小さい方からk-1個
    dxy = sorted(xy_dists[i], key=lambda xx: xx[0])[:k-1]
    dxy.append((0, xi, yi))
    maxx = max(dxy, key=lambda x: x[1])[1]
    minx = min(dxy, key=lambda x: x[1])[1]
    maxy = max(dxy, key=lambda x: x[2])[2]
    miny = min(dxy, key=lambda x: x[2])[2]
    ans = min(ans, (maxx-minx)*(maxy-miny))
print(ans)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
XY = [ tuple(map(int, input().split())) for _ in range(n)]
XXY = sorted(XY, key=lambda x: x[0])
YXY = sorted(XY, key=lambda x: x[1])
def f(n, k, XY):
    ans = 10**19+1
    for i in range(n-k+1):
        XYK = XY[i: i+k]
        maxx = max(XYK, key=lambda x: x[0])[0]
        minx = min(XYK, key=lambda x: x[0])[0]
        maxy = max(XYK, key=lambda x: x[1])[1]
        miny = min(XYK, key=lambda x: x[1])[1]
        ans = min(ans, (maxx - minx)*(maxy - miny))
    return ans
print(min(f(n, k, XXY), f(n, k, YXY)))

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
XY = [ tuple(map(int, input().split())) for _ in range(n)]
XY = sorted(XY, key=lambda x: x[0])
ans = 10**19+1
for i in range(n-k+1):
    XYK = XY[i: i+k]
    maxx = max(XYK, key=lambda x: x[0])[0]
    minx = min(XYK, key=lambda x: x[0])[0]
    maxy = max(XYK, key=lambda x: x[1])[1]
    miny = min(XYK, key=lambda x: x[1])[1]
    ans = min(ans, (maxx - minx)*(maxy - miny))

print(ans)

Submission status: Wrong Answer

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce, lru_cache
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def TUPLE(): return tuple(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = 10**6#float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
#from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

N, K = MAP()
xy = [LIST() for _ in range(N)]

ans = INF

xy.sort()
for l in range(N-K+1):  #長方形の最も左の点
	for r in range(l+K, N+1):  #長方形の最も右の点
		y = sorted(xy[l:r], key = lambda x: x[1]) #lからrの中でyのとりうる値をソート
		for i in range(r-l-K+1):
			sq = (xy[r-1][0] - xy[l][0])*(y[i+K-1][1] - y[i][1])
			ans = min(ans, sq)
print(ans)

Submission status: Wrong Answer

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

P = [[int(_) for _ in input().split()] for n in range(N)]

ans = 10 ** 20
for i in range(N):
    for j in range(i+1, N):
        if K > 2:
            for k in range(j+1, N):
                X = [P[i][0], P[j][0], P[k][0]]
                Y = [P[i][1], P[j][1], P[k][1]]
                x1, y1 = min(X), min(Y)
                x2, y2 = max(X), max(Y)
                c = 0
                for v in range(N):
                    x, y = P[v]
                    if x1 <= x <= x2 and y1 <= y <= y2:
                        c += 1
                if c >= K:
                    ans = min(ans, (x2-x1) * (y2-y1))
        else:
            X = [P[i][0], P[j][0]]
            Y = [P[i][1], P[j][1]]
            x1, y1 = min(X), min(Y)
            x2, y2 = max(X), max(Y)
            c = 0
            for v in range(N):
                x, y = P[v]
                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:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def TUPLE(): return tuple(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

N, K = MAP()
xy = [LIST() for _ in range(N)]

ans = INF
for (ax, ay), (bx, by) in combinations(xy, 2):
	cnt = 0
	for cx, cy in xy:
		if cx == ax or cx == bx:
			continue
		elif min(ax, bx) <= cx <= max(ax, bx) and min(ay, by) <= cy <= max(ay, by):
			cnt += 1
	if K <= cnt+2:
		ans = min(abs(ax-bx)*abs(ay-by), ans)

for (ax, ay), (bx, by), (cx, cy) in combinations(xy, 3):
	edge_left = min(ax, bx, cx)
	edge_right = max(ax, bx, cx)
	edge_top = max(ay, by, cy)
	edge_bottom = min(ay, by, cy)
	cnt = 0
	for dx, dy in xy:
		if dx == ax or dx == bx or dx == cx:
			continue
		elif edge_left <= dx <= edge_right and edge_bottom <= dy <= edge_top:
			cnt += 1
	if K <= cnt+3:
		ans = min((edge_right-edge_left)*(edge_top-edge_bottom), ans)

print(ans)

Submission status: Wrong Answer

Solution code:
#atcoder -take a rest-(easy)

def main():
    N,K = map(int,input().split())
    que = []
    que_x =  []
    que_y = []
    for i in range(N):
        x,y = map(int,input().split())
        que_x.append(x)
        que_y.append(y)
        que.append((x,y))
    que_x.sort()
    que_y.sort()
    ans = 10**100
    for i in range(N):
        for j in range(i+1,N):
            for _i in range(N):
                for _j in range(_i+1,N):
                    h,w = que_x[j]-que_x[i],que_y[_j] -que_x[_i]
                    cnt = 0
                    for x,y in que:
                        if que_x[i]<=x<=que_x[j] and que_y[_i]<=y<=que_y[_j]:
                            cnt += 1
                    if cnt >=K:
                        ans = min(ans,h*w)
    print(ans)
    return




if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
#atcoder -take a rest-(easy)

def main():
    N,K = map(int,input().split())
    que = []
    que_x =  []
    que_y = []
    for i in range(N):
        x,y = map(int,input().split())
        que_x.append(x)
        que_y.append(y)
        que.append((x,y))
    que_x.sort()
    que_y.sort()
    ans = 10**20
    for i in range(N):
        for j in range(i,N):
            for _i in range(N):
                for _j in range(_i,N):
                    h,w = que_x[j]-que_x[i],que_y[_j] -que_x[_i]
                    cnt = 0
                    for x,y in que:
                        if que_x[i]<=x<=que_x[j] and que_y[_i]<=y<=que_y[_j]:
                            cnt += 1
                    if cnt >=K:
                        ans = min(ans,h*w)
    print(ans)
    return




if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
#atcoder -take a rest-(easy)

def main():
    N,K = map(int,input().split())
    que = []
    que_x =  []
    que_y = []
    for i in range(N):
        x,y = map(int,input().split())
        que_x.append(x)
        que_y.append(y)
        que.append((x,y))
    que_x.sort()
    que_y.sort()
    ans = 10**20
    for i in range(N):
        for j in range(i+1,N):
            for _i in range(N):
                for _j in range(_i+1,N):
                    h,w = que_x[j]-que_x[i],que_y[_j] -que_x[_i]
                    cnt = 0
                    for x,y in que:
                        if que_x[i]<=x<=que_x[j] and que_y[_i]<=y<=que_y[_j]:
                            cnt += 1
                    if cnt >=K:
                        ans = min(ans,h*w)
    print(ans)
    return




if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

dot=[]
xxx=[]
yyy=[]

ans=float('inf')

for i in range(n):
  x,y=map(int,input().split())
  dot.append([x,y])
  xxx.append(x)
  yyy.append(y)

for sx,sy in dot:
  for gx in xxx:
    for gy in yyy:
      if sx==gx or sy==gy:
        continue
      cnt=0
      for lst in dot:
        if sx<=lst[0]<=gx or gx<=lst[0]<=sx:
          if sy<=lst[1]<=gy or gy<=lst[1]<=sy:
            cnt+=1
      
      if cnt>=k:
        ans=min(ans,abs(sx-gx)*abs(sy-gy))


print(ans)

Submission status: Wrong Answer

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

dot=[]
xxx=[]
yyy=[]

ans=float('inf')

for i in range(n):
  x,y=map(int,input().split())
  dot.append([x,y])
  xxx.append(x)
  yyy.append(y)

for sx,sy in dot:
  for gx in xxx:
    for gy in yyy:
      if sx==gx or sy==gy:
        continue
      cnt=0
      for lst in dot:
        if (sx<=lst[0]<=gx or gx<=lst[0]<=sx) and (sy<=lst[1]<=gy or gy<=lst[1]<=sy):
          cnt+=1
      
      if cnt>=k:
        ans=min(ans,abs(sx-gx)*abs(sy-gy))


print(ans)

Submission status: Wrong Answer

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

dot=[]
xxx=[]
yyy=[]

ans=float('inf')

for i in range(n):
  x,y=map(int,input().split())
  dot.append([x,y])
  xxx.append(x)
  yyy.append(y)

for sx,sy in dot:
  for gx in xxx:
    for gy in yyy:
      cnt=0
      for lst in dot:
        if (sx<=lst[0]<=gx or gx<=lst[0]<=sx) and (sy<=lst[1]<=gy or gy<=lst[1]<=sy):
          cnt+=1
      
      if cnt>=k:
        ans=min(ans,abs(sx-gx)*abs(sy-gy))


print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub, itemgetter, attrgetter


import sys
# sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()

def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, M, XY):
    XY.sort(key=itemgetter(1))
    XY.sort()
    # print(XY)

    ans = INF
    for i, (x, y) in enumerate(XY):
        yl = [y]
        for j in range(i+1, N):
            x2, y2 = XY[j]
            yl.append(y2)
            if len(yl) >= M:
                yl.sort()
                ans = min(ans, (x2-x)*(yl[-1]-yl[0]))
                for k in range(M-len(yl)+1):
                    ans = min(ans, (x2-x)*(yl[k+M-1]-yl[k]))
    return ans


def main():
    N, M = read_int_n()
    XY = [read_int_n() for _ in range(N)]
    print(slv(N, M, XY))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub, itemgetter, attrgetter


import sys
# sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()

def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, M, XY):
    XY.sort(key=itemgetter(1))
    XY.sort()
    # print(XY)

    ans = INF
    for i, (x, y) in enumerate(XY):
        yl = [y]
        for j in range(i+1, N):
            x2, y2 = XY[j]
            yl.append(y2)
            if len(yl) >= M:
                yl.sort()
                ans = min(ans, (x2-x)*(yl[-1]-yl[0]))
                for k in range(M-len(yl)):
                    ans = min(ans, (x2-x)*(yl[k+M-1]-yl[k]))
    return ans


def main():
    N, M = read_int_n()
    XY = [read_int_n() for _ in range(N)]
    print(slv(N, M, XY))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub, itemgetter, attrgetter


import sys
# sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()

def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, M, XY):
    XY.sort(key=itemgetter(1))
    XY.sort()
    # print(XY)

    ans = INF
    for i, (x, y) in enumerate(XY):
        yl = [y]
        for j in range(i+1, N):
            x2, y2 = XY[j]
            yl.append(y2)
            yl.sort()
            if len(yl) >= M:
                ans = min(ans, (x2-x)*(yl[-1]-yl[0]))
                for k in range(M-len(yl)):
                    ans = min(ans, (x2-x)*(yl[k+M]-yl[k]))
    return ans


def main():
    N, M = read_int_n()
    XY = [read_int_n() for _ in range(N)]
    print(slv(N, M, XY))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n,k = map(int, input().split())
xs = []
ys = []
ps = []
for i in range(n):
    x,y = map(int, input().split())
    xs.append(x)
    ys.append(y)
    ps.append((x,y))
# 座圧
xs = sorted(list(set(xs)))
ys = sorted(list(set(ys)))
xdic = {x:i for i, x in enumerate(xs)}
ydic = {y:i for i, y in enumerate(ys)}
xrdic = {i:x for i, x in enumerate(xs)}
yrdic = {i:y for i, y in enumerate(ys)}
nx = len(xs)
ny = len(ys)


fs = [[0] * (1+ny) for i in range(nx+1)]
for x,y in ps:
    ix = xdic[x]
    iy = ydic[y]
    fs[ix][iy] += 1

acc = [[0] * (1+ny) for i in range(nx+1)]
for i in range(nx):
    for j in range(ny):
        acc[i+1][j+1] = acc[i+1][j] + acc[i][j+1] - acc[i][j] + fs[i][j]

def calc(sx,sy,tx,ty):
    ix1 = xrdic[sx]
    ix2 = xrdic[tx]
    iy1 = yrdic[sy]
    iy2 = yrdic[ty]
    return (ix2-ix1) * (iy2-iy1)

# print(xs,xdic,".",ys,ydic)
ans = 10**20
for sx in range(nx):
    for sy in range(ny):
        for tx in range(sx+1, nx+1):
            for ty in range(sy+1, ny+1):
                cnt = acc[tx][ty] - acc[sx][ty] - acc[tx][sy] + acc[sy][sx]
                # print(cnt)
                if cnt >= k:
                    S = calc(sx,sy,tx-1,ty-1)
                    # print(S," ",sx,sy," ",tx-1,ty-1)
                    ans = min(ans, S)
print(ans)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
x=[0]*n
y=[0]*n
for i in range(n):
  x[i],y[i]=map(int,input().split())
ans=10**19
for i in range(n):
  for j in range(i+1,n):
    for k in range(j+1,n):
      for l in range(k+1,n):
        xl=min(x[i],x[j],x[k],x[l])
        xr=max(x[i],x[j],x[k],x[l])
        yl=min(y[i],y[j],y[k],y[l])
        yh=max(y[i],y[j],y[k],y[l])
        cnt=0
        for c in range(n):
          cnt+=xl<=x[c]<=xr and yl<=y[c]<=yh
        if cnt>=m:ans=min(ans,(xr-xl)*(yh-yl))
print(ans)

Submission status: Wrong Answer

Solution code:
N, K = (int(x) for x in input().split())
Plot = [tuple(int(x) for x in input().split()) for _ in range(N)]
X = [p[0] for p in Plot]
Y = [p[1] for p in Plot]
#全2点間で長方形の辺を作り、その内内部点がK個のものだけ面積を比較する。
#2点p,qが頂点にある長方形は確かに最小の長方形を成す
#2点が頂点でない場合、内部点の個数が変わらないように適当な2点p,qを取って頂点とすることでより小さい長方形を形成できる
ans = 10e20
for x1 in X:
    X.remove(x1)
    for x2 in X:
        if x1 < x2:
            minx, maxx = x1, x2
        else:
            minx, maxx = x2, x1
        for y1 in Y:
            Y.remove(y1)
            for y2 in Y:
                if y1 < y2:
                    miny, maxy = y1, y2
                else:
                    miny, maxy = y2, y1
                S = (maxx-minx)*(maxy-miny)
                cnt = 0
                for r in Plot:
                    if minx <= r[0] <= maxx and miny <= r[1] <= maxy:
                        cnt += 1
                if cnt == K and S != 0:
                    ans = min(ans, S)
print(ans)

Submission status: Wrong Answer

Solution code:
def cnt(xl, xr, yb, yt):
    c = 0
    for i in range(n):
        if xl <= x[i] <= xr and yb <= y[i] <= yt:
            c += 1
    return c



n, k = map(int, input().split())

x = []
y = []
xy = []
for i in range(n):
    u, v = map(int, input().split())
    x.append(u)
    y.append(v)
    xy.append([u,v])
    
x.sort()
y.sort()

ans = (x[-1]-x[0])*(y[-1]-y[0])
for l in range(n-1):
    for r in range(l+1, n):
        xl, xr = x[l], x[r]
        for b in range(n-1):
            for t in range(b+1, n):
                yb, yt = y[b], y[t]
                ck = cnt(xl, xr, yb, yt)
                if ck >= k:
                    ans = min(ans, (xr-xl)*(yt-yb))
print(ans)

Submission status: Wrong Answer

Solution code:
def cnt(xl, xr, yb, yt):
    c = 0
    for i in range(n):
        if xl <= x[i] <= xr and yb <= y[i] <= yt:
            c += 1
    return c



n, k = map(int, input().split())

x = []
y = []
xy = []
for i in range(n):
    u, v = map(int, input().split())
    x.append(u)
    y.append(v)
    xy.append([u,v])
    
x.sort()
y.sort()

ans = (x[-1]-x[0])*(y[-1]-y[0])
for l in range(n):
    for r in range(l+1, n):
        xl, xr = x[l], x[r]
        for b in range(n):
            for t in range(b+1, n):
                yb, yt = y[b], y[t]
                ck = cnt(xl, xr, yb, yt)
                if ck >= k:
                    ans = min(ans, (xr-xl)*(yt-yb))
print(ans)

Submission status: Wrong Answer

Solution code:
def cnt(xl, xr, yb, yt):
    c = 0
    for i in range(n):
        if xl <= x[i] <= xr and yb <= y[i] <= yt:
            c += 1
    return c



n, k = map(int, input().split())

x = []
y = []
xy = []
for i in range(n):
    u, v = map(int, input().split())
    x.append(u)
    y.append(v)
    xy.append([u,v])
    
x.sort()
y.sort()

ans = 10**20
for l in range(n):
    for r in range(l+1, n):
        xl, xr = x[l], x[r]
        for b in range(n):
            for t in range(b+1, n):
                yb, yt = y[b], y[t]
                ck = cnt(xl, xr, yb, yt)
                if ck >= k:
                    ans = min(ans, (xr-xl)*(yt-yb))
print(ans)

Submission status: Wrong Answer

Solution code:
def cnt(xl, xr, yb, yt):
    c = 0
    for i in range(n):
        if xl <= x[i] <= xr and yb <= y[i] <= yt:
            c += 1
    return c



n, k = map(int, input().split())

x = []
y = []
xy = []
for i in range(n):
    u, v = map(int, input().split())
    x.append(u)
    y.append(v)
    xy.append([u,v])
    
x.sort()
y.sort()

ans = 10**30
for l in range(n):
    for r in range(l+1, n):
        xl, xr = x[l], x[r]
        for b in range(n):
            for t in range(b+1, n):
                yb, yt = y[b], y[t]
                ck = cnt(xl, xr, yb, yt)
                if ck >= k:
                    ans = min(ans, (xr-xl)*(yt-yb))
print(ans)

Submission status: Wrong Answer

Solution code:
def cnt(xl, xr, yb, yt):
    c = 0
    for i in range(n):
        if xl <= x[i] <= xr and yb <= y[i] <= yt:
            c += 1
    return c



n, k = map(int, input().split())

x = []
y = []
xy = []
for i in range(n):
    u, v = map(int, input().split())
    x.append(u)
    y.append(v)
    xy.append([u,v])
    
x.sort()
y.sort()

ans = 10**20
for l in range(n):
    for r in range(l+1, n):
        xl, xr = x[l], x[r]
        for b in range(n):
            for t in range(b+1, n):
                yb, yt = y[b], y[t]
                ck = cnt(xl, xr, yb, yt)
                if ck >= k:
                    ans = min(ans, (xr-xl)*(yt-yb))
print(ans)

Submission status: Wrong Answer

Solution code:
from copy import deepcopy
import sys
def main():
    input = sys.stdin.readline
    n, k = map(int, input().split())
    x, y = [], []
    for i in range(n):
        x_, y_ = map(int, input().split())
        x.append(x_)
        y.append(y_)
    X, Y = deepcopy(x), deepcopy(y)
    x.sort()
    y.sort()
    print(x, y)
    ans = (x[-1] - x[0]) * (y[-1] - y[0])
    for i in range(n):
        for j in range(i + 1, n):
            for K in range(n):
                for l in range(K + 1, n):
                    cnt = 0
                    x1, x2, y1, y2 = x[i], x[j], y[K], y[l]
                    for m in range(n):
                        if x1 <= X[m] <= x2 and y1 <= Y[m] <= y2:
                            cnt += 1
                    if cnt >= k:
                        ans = min(ans, (x2 - x1) * (y2 - y1))
    print(ans)
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from itertools import combinations


N, K, *XY = map(int, open(0).read().split())
X = sorted(XY[::2])
Y = sorted(XY[1::2])

ans = 10 ** 20
for x1, x2 in combinations(X, 2):
    for y1 in Y[:-1]:
        y2s = sorted(y for x, y in zip(*[iter(XY)] * 2) if x1 <= x <= x2 and y1 <= y)
        if len(y2s) < K:
            continue
        ans = min(ans, (x2 - x1) * (y2s[-1] - y1))
print(ans)

Submission status: Wrong Answer

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

ans = 10**18+1
for a in range(n):
    for b in range(a+1,n):
        axy = xyl[a]
        bxy = xyl[b]
        ax,ay = axy
        bx,by = bxy
        l = min(ax,bx)
        r = max(ax,bx)
        t = max(ay,by)
        bo = min(ay,by)
        v = 0
        for x,y in xyl:
            if l <= x <= r and bo <= y <= t:
                v += 1
        if v >= k:
            area = (r-l)*(t-bo)
            ans = min(ans, area)

        for c in range(b+1,n):
            cxy = xyl[c]
            cx,cy = cxy
            l = min(ax,bx,cx)
            r = max(ax,bx,cx)
            t = max(ay,by,cy)
            bo = min(ay,by,cy)
            v = 0
            for x,y in xyl:
                if l <= x <= r and bo <= y <= t:
                    v += 1
            if v >= k:
                area = (r-l)*(t-bo)
                ans = min(ans, area)

            for d in range(c+1,n):
                dxy = xyl[d]
                dx,dy = dxy
                left = min(ax,bx,cx,dx)
                right = max(ax,bx,cx,dx)
                top = max(ay,by,cy,dy)
                bottom = min(ay,by,cy,dy)
                cnt = 0
                for x,y in xyl:
                    if left <= x <= right and bottom <= y <= top:
                        cnt += 1
                if cnt >= k:
                    area = (right-left)*(top-bottom)
                    ans = min(ans, area)


print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
N, K = map(int, input().split())
xy = [list(map(int, input().split())) for _ in range(N)]
xy = sorted(xy)
idxs = [i for i in range(N)]
y = [y for _, y in xy]
ans = float('inf')
for a, b in itertools.combinations(idxs, 2):
  if b-a+1 >= K:
    yy = y[a:b+1]
    for i in range(b-a+1-K+1):
      yyy = yy[i:K+i]
      miny = min(yyy)
      maxy = max(yyy)
      ans = min(ans, (maxy-miny)*(xy[b][0]-xy[a][0]))

print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
N, K = map(int, input().split())
xy = [list(map(int, input().split())) for _ in range(N)]
xy = sorted(xy)
idxs = [i for i in range(N)]
y = [y for _, y in xy]
ans = float('inf')
for a, b in itertools.combinations(idxs, 2):
  if b-a+1 >= K:
    yy = y[a:b+1]
    miny = min(yy)
    maxy = max(yy)
    ans = min(ans, (maxy-miny)*(xy[b][0]-xy[a][0]))

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
def main():
    N,K=mi()
    G = []

    X=[]
    Y=[]
    for i in range(N):
        x,y = mi()
        G.append((x,y))
        X.append(x)
        Y.append(y)

    def count(downx,upx,downy,upy):
        _count = 0
        for i in range(N):
            x,y = G[i]
            if downx<=x<=upx and downy<=y<=upy:
                _count += 1
        
        return _count

    ans = 0
    for downx in X:
        for upx in X:
            if upx == downx: continue
            for downy in Y:
                for upy in Y:
                    if upy == downy: continue

                    if count(downx,upx,downy,upy) >= K:
                        ans = abs(upx-downx) * abs(upy-downy)
                        



    print(ans)

            



if __name__ == "__main__":
    main()