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: Accepted

Solution code:
import sys
def LI(): return [int(x) for x in sys.stdin.readline().split()]

N,K = LI()
p = []
for i in range(N):
    a,b = LI()
    p.append((a,b,i))
sx = sorted(p)
ans = 10**50
for x,y,i in sx:
    for x2,y2,i2 in sx:
        if x2 <= x:
            continue
        points = sx.index((x2,y2,i2)) - sx.index((x,y,i)) + 1
        if points < K:
            continue
        sy = sorted(sx[sx.index((x,y,i)):sx.index((x2,y2,i2))+1],key=lambda sx: sx[1])
        for j in range(len(sy)-K+1):
            if sy[j][1] <= y and y2 <= sy[j+K-1][1]:
                ans = min(ans, (x2 - x) * (sy[j+K-1][1]-sy[j][1])) 
print(ans)

Submission status: Accepted

Solution code:
import math,heapq,collections,sys,numpy
sys.setrecursionlimit(10**7)

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()

N,K = LI()
p = []
for i in range(N):
    a,b = LI()
    p.append((a,b,i))
sx = sorted(p)
ans = 10**50
for x,y,i in sx:
    for x2,y2,i2 in sx:
        if x2 <= x:
            continue
        points = sx.index((x2,y2,i2)) - sx.index((x,y,i)) + 1
        if points >= K:
            sy2 = sorted(sx[sx.index((x,y,i)):sx.index((x2,y2,i2))+1],key=lambda sx: sx[1])
            for j in range(len(sy2)-K+1):
                if sy2[j][1] <= y and sy2[j+K-1][1] >= y2:          
                    ans = min(ans, (x2 - x) * (sy2[j+K-1][1]-sy2[j][1])) 
print(ans)

Submission status: Accepted

Solution code:
def i1():
 return int(input())
def i2():
 return [int(i) for i in input().split()]
[n,k]=i2()
x=[]
y=[]
zz=[]
for i in range(n):
 z=i2()
 x.append([z[0],i])
 y.append([z[1],i])
 zz.append(z)
x.sort()
y.sort()
xx=[i[1] for i in x]
yy=[i[1] for i in y]
a=float("inf")
for i in range(n):
 for j in range(i,n):
  for kk in range(n):
   for l in range(kk,n):
     if len(set(xx[i:j+1])&set(yy[kk:l+1]))==k:
         a=min(a,(zz[xx[j]][0]-zz[xx[i]][0])*(zz[yy[l]][1]-zz[yy[kk]][1]))
print(a)

Submission status: Accepted

Solution code:
def D_Axis_Parallel_Rectangle(N, K, P):
    x = [0 for _ in range(N)]  # 点のx座標
    y = [0 for _ in range(N)]  # y座標
    x_array = [0 for _ in range(N)]
    y_array = [0 for _ in range(N)]
    for i in range(N):
        x[i] = P[i][0]
        y[i] = P[i][1]
        x_array[i] = x[i]
        y_array[i] = y[i]

    x_array = sorted(x_array)
    y_array = sorted(y_array)

    # すべての点を内部に含む、最大の面積を持つ矩形が初期値
    ans = (x_array[N - 1] - x_array[0]) * (y_array[N - 1] - y_array[0])

    # 全探索
    for xi in range(0, N, 1):
        for xj in range(xi + 1, N, 1):
            for yi in range(0, N, 1):
                for yj in range(yi + 1, N, 1):
                    num = 0
                    left = x_array[xi]
                    right = x_array[xj]
                    bottom = y_array[yi]
                    upper = y_array[yj]

                    for i in range(N):
                        if(left <= x[i] and x[i] <= right and bottom <= y[i] and y[i] <= upper):
                            num += 1
                    if num >= K:
                        ans = min(ans, (right - left) * (upper - bottom))
    return ans

N,K = [int(i) for i in input().split()]
P = [[int(i) for i in input().split()] for j in range(N)]
print(D_Axis_Parallel_Rectangle(N, K, P))

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
sx, sy = [], []
for i in range(n):
    x, y = map(int, input().split())
    sx.append((x, i))
    sy.append((y, i))
sx.sort()
sy.sort()
px = [[0] for _ in range(n)]
for cx, (x, i) in enumerate(sx):
    px[i] = cx

acm = [[0] * (n + 1) for _ in range(n + 1)]
for cy, (y, i) in enumerate(sy):
    for cx in range(n):
        acm[cx][cy] = acm[cx - 1][cy] + acm[cx][cy - 1] - acm[cx - 1][cy - 1] + int(px[i] == cx)

ans = 5e18
for lcx in range(n - k + 1):
    for lcy in range(n - k + 1):
        acm_l = acm[lcx - 1][lcy - 1]
        for ucx in range(lcx + k - 1, n):
            for ucy in range(lcy + k - 1, n):
                if acm[ucx][ucy] - acm[ucx][lcy - 1] - acm[lcx - 1][ucy] + acm_l >= k:
                    ans = min(ans, (sx[ucx][0] - sx[lcx][0]) * (sy[ucy][0] - sy[lcy][0]))
                    break
print(ans)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
sx, sy = [], []
for i in range(n):
    x, y = map(int, input().split())
    sx.append((x, i))
    sy.append((y, i))
sx.sort()
sy.sort()
px = [[0] for _ in range(n)]
for cx, (x, i) in enumerate(sx):
    px[i] = cx

acm = [[0] * (n + 1) for _ in range(n + 1)]
for cy, (y, i) in enumerate(sy):
    for cx in range(n):
        acm[cx][cy] = acm[cx - 1][cy] + acm[cx][cy - 1] - acm[cx - 1][cy - 1] + int(px[i] == cx)

ans = 5e18
for lcx in range(n - k + 1):
    for ucx in range(lcx + k - 1, n):
        for lcy in range(n - k + 1):
            for ucy in range(lcy + k - 1, n):
                # print(li, ui, lj, uj)
                # print(acm[ui][uj], acm[ui][lj - 1], acm[li - 1][uj], acm[li - 1][lj - 1])
                if acm[ucx][ucy] - acm[ucx][lcy - 1] - acm[lcx - 1][ucy] + acm[lcx - 1][lcy - 1] >= k:
                    ans = min(ans, (sx[ucx][0] - sx[lcx][0]) * (sy[ucy][0] - sy[lcy][0]))
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict, Counter
from itertools import combinations
INF = float("inf")


def main():
    N, K = map(int, input().split())
    points = []
    for i in range(N):
        x, y = map(int, input().split())
        points.append((y, x))

    ans = INF
    for i in range(N):
        for j in range(N):
            for k in range(N):
                for l in range(N):
                    y1, y2, x1, x2 = points[i][0], points[j][0], points[k][1], points[l][1]
                    area = abs(y1 - y2) * abs(x1 - x2)
                    if y1 <= y2 and x1 <= x2 and area < ans:
                        n = 0
                        for p in points:
                            n += y1 <= p[0] <= y2 and x1 <= p[1] <= x2
                        if n >= K:
                            ans = min(ans, area)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, K = map(int, raw_input().split())
ps = []
for i in xrange(N):
  ps.append(map(int, raw_input().split()))

xsorted = zip(*sorted(ps, key=lambda p: p[0]))[0]
ysorted = zip(*sorted(ps, key=lambda p: p[1]))[1]

ans = float('inf')
for i in xrange(N):
  bottom = ysorted[i]
  for j in xrange(i+K-1, N):
    top = ysorted[j]
    for k in xrange(N):
      if k+K-1 >= N:
        break
      right = xsorted[k]
      # 2 bun tansaku
      f, t = k+K-1, N
      sol = None
      while True:
        mid = (f+t)//2
        left = xsorted[mid]
        c = 0
        for p in ps:
          if right <= p[0] <= left and bottom <= p[1] <= top:
            c += 1
            if c >= K: break
        else:
          if f+1 >= t:
            break
          f = mid
          continue
        sol = mid
        if f+1 >= t:
          break
        t = mid
      if sol:
        area = (xsorted[sol] - right) * (top - bottom)
        if area < ans:
          ans = area

print ans

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
points1 = []
points2 = []
for i in range(N):
	x,y = tuple((map(int,input().split())))
	points1.append((x,y))
	points2.append(y)
points1.sort()
points2.sort()

xDict = {}
index = 0
for x,y in points1:
	if index in xDict:
		if xDict[index] != x:
			index += 1
			xDict[index] = x
	else:
		xDict[index] = x

yDict = {}
index = 0
for y in points2:
	if index in yDict:
		if yDict[index] != y:
			index += 1 
			yDict[index] = y
	else:
		yDict[index] = y

nPoints = [[0 for j in range(len(yDict))] for i in range(len(xDict))]

for kx,vx in xDict.items():
	for ky,vy in yDict.items():
		exists = 1 if (vx,vy) in points1 else 0
		if kx == 0 and ky == 0:
			nPoints[kx][ky] += exists
		elif kx == 0 and ky > 0:
			nPoints[kx][ky] += nPoints[kx][ky-1] + exists
		elif kx > 0 and ky == 0:
			nPoints[kx][ky] += nPoints[kx-1][ky] + exists
		else:
			nPoints[kx][ky] += nPoints[kx-1][ky] + nPoints[kx][ky-1] - nPoints[kx-1][ky-1] + exists

ans = -1
for x1 in range(len(xDict)):
	for x2 in range(x1+1,-1,-1):
		for y1 in range(len(yDict)):
			for y2 in range(y1+1,-1,-1):
				point = nPoints[x1][y1]
				if x2 > 0:
					point -= nPoints[x2-1][y1]
				if y2 > 0:
					point -= nPoints[x1][y2-1]
				if x2 > 0 and y2 > 0:
					point += nPoints[x2-1][y2-1]
				if point >= K:
					area = (xDict[x1]-xDict[x2]) * (yDict[y1]-yDict[y2])
					if ans < 0:
						ans = area
					else:
						ans = min(ans, area)
					break
print(ans)

Submission status: Accepted

Solution code:
# D
import numpy as np

N, K = map(int, input().split())
x_list = []
y_list = []

for _ in range(N):
    x, y = map(int, input().split())
    x_list.append(x)
    y_list.append(y)

x_list_np = np.array(x_list)
x_args = np.argsort(x_list_np)
x_sorted = np.sort(x_list_np)

res = (max(x_list) - min(x_list)) * (max(y_list) - min(y_list))

for i1 in range(N):
    for i2 in range(i1+K-1, N):
        x_ = x_sorted[i2] - x_sorted[i1]
        y_pick = np.sort(np.array(y_list)[x_args[i1:(i2+1)]])
        y_ = min([y_pick[i+K-1] - y_pick[i] for i in range(i2-i1-K+2)])
        res = min(res, x_*y_)
print(res)

Submission status: Accepted

Solution code:
from collections import defaultdict, Counter
from itertools import combinations
INF = float("inf")


memo1 = {}
memo2 = {}

def ok(y1, y2, x1, x2, yd, yd2, xd, xd2, K):
    if (y1, y2) in memo1:
        y = memo1[(y1, y2)]
    else:
        a = yd2[y1]
        b = yd[y2]
        y = b.difference(a)
        memo1[(y1, y2)] = y

    if (x1, x2) in memo2:
        x = memo2[(x1, x2)]
    else:
        c = xd2[x1]
        d = xd[x2]
        x = d.difference(c)
        memo2[(x1, x2)] = x

    # print(a, b, c, d)
    # print(y, x)

    n = len(y & x)

    return n >= K


def main():
    import time
    N, K = map(int, raw_input().split())
    ys, xs = [], []
    for i in range(N):
        x, y = map(int, raw_input().split())
        ys.append((y, i))
        xs.append((x, i))

    ys.sort()
    yd = defaultdict(set)
    yd2 = defaultdict(set)
    old = set()
    for y, i in ys:
        yd2[y] = old.copy()
        old.add(i)
        yd[y] = old.copy()

    xs.sort()
    xd = defaultdict(set)
    xd2 = defaultdict(set)
    old = set()
    for x, i in xs:
        xd2[x] = old.copy()
        old.add(i)
        xd[x] = old.copy()

    ans = INF

    # print(yd)
    # print(xd)
    #
    # print(ok(1, 4, 1, 8, yd, yd2, xd, xd2, K))
    for i, j in combinations(range(N), 2):
        for k, l in combinations(range(N), 2):
            a, b, c, d = ys[i], ys[j], xs[k], xs[l]
            y1 = min(a[0], b[0])
            y2 = max(a[0], b[0])

            x1 = min(c[0], d[0])
            x2 = max(c[0], d[0])

            kkk = abs(x1 - x2) * abs(y1 - y2)
            if kkk < ans:
                # print(i, j)
                # print(x1, x2, abs(x1 - x2))
                # print(y1, y2, abs(y1 - y2))
                # print(ok(y1, y2, x1, x2, yd, yd2, xd, xd2, K))
                if ok(y1, y2, x1, x2, yd, yd2, xd, xd2, K):
                    ans = kkk

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

x,y = [],[]
xx,yy = [],[]

for _ in range(n):
    X,Y = map(int,input().split())

    x.append(X)
    xx.append(X)
    y.append(Y)
    yy.append(Y)

xx.sort()
yy.sort()

ans = 10**20
for i in range(n):
    for j in range(i):
        lx,rx = xx[j],xx[i]

        num = [0 for _ in range(n+1)]
        for k in range(n):
            if lx <= x[k] <= rx:
                num[yy.index(y[k])+1] += 1

        for k in range(n):
            num[k+1] += num[k]

        for k in range(n):
            for l in range(k):
                ly,ry = yy[l],yy[k]

                if num[k+1] - num[l] >= K:
                    ans = min(ans, (rx-lx)*(ry-ly))

print(ans)

Submission status: Accepted

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

xs = []
ys = []
pts = []
for _ in range(n):
    (x, y) = map(int, input().split(" "))
    xs += [x]
    ys += [y]
    pts += [(x, y)]

xs.sort()
ys.sort()

res = float("inf")
for a in xs:
    for b in xs:
        ci = 0
        di = 1
        while di < len(ys):
            num = 0
            c = ys[ci]
            d = ys[di]
            
            for x in pts:
                if a <= x[0] <= b and c <= x[1] <= d:
                    num += 1
        
            if num >= k:
                res = min(res, abs(b-a)*abs(d-c))
                if ci < di:
                    ci += 1
                else:
                    di += 1
            else:
                di += 1

print(res)

Submission status: Accepted

Solution code:
# coding: utf-8
# Here your code !
n,k=[int(x) for x in input().split()]
x=[0]*n
y=[0]*n
for i in range(n):
   x[i],y[i]=[int(x) for x in input().split()]
from itertools import product
ans=float("inf")
for xmax,xmin,ymax,ymin in product(x,x,y,y):
    if xmax<=xmin or ymax<=ymin or (xmax-xmin)*(ymax-ymin)>=ans:
        continue
    if len([0 for xi,yi in zip(x,y) if xmin<=xi<=xmax and ymin<=yi<=ymax])>=k:
        ans=(xmax-xmin)*(ymax-ymin)
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env pypy3

import itertools


def det_rect_area(n, k, points):
    area = float("inf")
    # 点の直積から2点選んで，それを長方形の対角とする
    xs = (p[0] for p in points)
    ys = (p[1] for p in points)
    all_points = itertools.product(xs, ys)
    for (x1, y1), (x2, y2) in itertools.combinations(all_points, 2):
        min_x, max_x = min(x1, x2), max(x1, x2)
        min_y, max_y = min(y1, y2), max(y1, y2)
        # その中にk個以上の点が入るか？
        num_inc_rects = 0
        for x, y in points:
            if min_x <= x <= max_x and min_y <= y <= max_y:
                num_inc_rects += 1
        if num_inc_rects >= k:
            area = min(area, (max_x - min_x) * (max_y - min_y))
    return area


def main():
    n, k = (int(x) for x in input().split())
    points = [tuple(int(x) for x in input().split()) for _ in range(n)]
    print(det_rect_area(n, k, points))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
p=[]
for i in range(n):
    x,y=map(int,input().split())
    p.append([x,y])
ret=10**25
for a in range(n):
    for b in range(a):
        r=max(p[a][0],p[b][0])
        l=min(p[a][0],p[b][0])
        for c in range(n):
            for d in range(c):
                u=min(p[c][1],p[d][1])
                t=max(p[c][1],p[d][1])
                cnt=0
                for i in range(n):
                    if l<=p[i][0]<=r and u<=p[i][1]<=t:
                        cnt+=1
                if cnt>=k:
                    ret=min(ret,(r-l)*(t-u))
print(ret)

Submission status: Accepted

Solution code:
line=input().split()
n=int(line[0])
k=int(line[1])

points=[]
hojds=[]
bredds=[]
for i in range(n):
    line=input().split()
    x=int(line[0])
    y=int(line[1])
    points.append([x,y])
    bredds.append(x)
    hojds.append(y)
hojds.sort()
bredds.sort()
points.sort(key=lambda x:x[0])

area=10**18*4
for h1 in hojds:
    for h2 in hojds:
        if h1>=h2:
            continue
        for b1 in bredds:
            num=0
            for p in points:
                if p[0]>=b1 and p[1]>=h1 and p[1]<=h2:
                    num+=1
                    if num==k:
                        b2=p[0]
                        newarea=(b2-b1)*(h2-h1)
                        area=min(area,newarea)
                        break
            
print(area)

Submission status: Accepted

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

ans = int(4e18)
for i0 in range(len(x) - 1):
    x0 = x[i0]
    for i1 in range(i0 + 1, len(x)):
        x1 = x[i1]
        for j0 in range(len(y) - 1):
            y0 = y[j0]
            for j1 in range(j0 + 1, len(y)):
                y1 = y[j1]
                s = (x1 - x0) * (y1 - y0)
                cnt = 0
                for xy in xys:
                    if x0 <= xy[0] <= x1 and y0 <= xy[1] <= y1:
                        cnt += 1
                if k <= cnt:
                    ans = min(ans, s)
print(ans)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
X = set(); Y = set()
P = set()
for i in range(n):
    x, y = map(int, input().split())
    X.add(x); Y.add(y)
    P.add((x, y))

X = sorted(X); w = len(X)
Y = sorted(Y); h = len(Y)
MX = {x: i for i, x in enumerate(X)}
MY = {y: i for i, y in enumerate(Y)}
Q = {(MX[x], MY[y]) for x, y in P}
S = [[0]*(w+1) for i in range(h+1)]
for i in range(h):
    tmp = 0
    for j in range(w):
        if (j, i) in Q:
            tmp += 1
        S[i+1][j+1] = S[i][j+1] + tmp

ans = 10**100
for y1 in range(h):
    for x1 in range(w):
        for y2 in range(h):
            for x2 in range(w):
                count = S[y2+1][x2+1] - S[y2+1][x1] - S[y1][x2+1] + S[y1][x1]
                if count >= k:
                    ans = min(ans, (X[x2]-X[x1])*(Y[y2]-Y[y1]))
print(ans)

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline()

n, kk = na()
ps = [na() for _ in range(n)]

ans = 99999999999999999999999
for i in range(n):
    for j in range(n):
        for k in range(n):
            for l in range(n):
                if ps[i][0] <= ps[k][0] and ps[j][1] <= ps[l][1] and (ps[k][0]-ps[i][0])*(ps[l][1]-ps[j][1]) < ans:
                    hit = len([_ for _ in ps if ps[i][0] <= _[0] <= ps[k][0] and ps[j][1] <= _[1] <= ps[l][1]])
                    if hit >= kk:
                        ans = (ps[k][0]-ps[i][0])*(ps[l][1]-ps[j][1])
print(ans)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
n,k=map(int,input().split())
xy=[list(map(int,input().split())) for _ in range(n)]
xwl=dict((c[0],i) for i,c in enumerate(xy))
ywl=dict((c[1],i) for i,c in enumerate(xy))
x=list(xwl.keys())
y=list(ywl.keys())
x.sort()
y.sort()

xdict=dict()
ydict=dict()
xdict[x[0]]=[1<<xwl[x[0]],0]
ydict[y[0]]=[1<<ywl[y[0]],0]
size=lambda x:sum(x>>i&1 for i in range(n))
minus=lambda x,y:(x|y)^y
for i in range(1,n):
  xdict[x[i]]=[xdict[x[i-1]][0]|(1<<xwl[x[i]]), xdict[x[i-1]][1]|(1<<xwl[x[i-1]])]
  ydict[y[i]]=[ydict[y[i-1]][0]|(1<<ywl[y[i]]), ydict[y[i-1]][1]|(1<<ywl[y[i-1]])]

cand=[min(ans,(x[t]-x[s])*(y[v]-y[u])) for s in range(n) for t in range(n) \
 for u in range(n) for v in range(n) \
 if size(minus(xdict[x[t]][0],xdict[x[s]][1])&\
                minus(ydict[y[v]][0],ydict[y[u]][1]))>=k and s<t and u<v]

print(min(cand))

Submission status: Runtime Error

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

ans = 10**20

for i in range(n):
    for j in range(i+1,n):
        if K == 2:
            ans = min(ans,abs(xy[i][0]-xy[j][0])*abs(xy[i][1]-xy[j][1]))
        for k in range(j+1,n):
            if K == 2:
                print(xy[n][2])
                break
            max_x = max(xy[i][0],xy[j][0],xy[k][0])
            min_x = min(xy[i][0],xy[j][0],xy[k][0])
            max_y = max(xy[i][1],xy[j][1],xy[k][1])
            min_y = min(xy[i][1],xy[j][1],xy[k][1])
            if K == 3:
                #max_x = max(xy[i][0],xy[j][0],xy[k][0])
                #min_x = min(xy[i][0],xy[j][0],xy[k][0])
                #max_y = max(xy[i][1],xy[j][1],xy[k][1])
                #min_y = min(xy[i][1],xy[j][1],xy[k][1])
                ans = min(ans,abs(max_x-min_x)*abs(max_y-min_y))
            for l in range(k+1,n):
                if K == 2 or K == 3:
                    print(xy[n][2])
                    break
                cnt = 0
                max_x = max(max_x,xy[l][0])
                min_x = min(min_x,xy[l][0])
                max_y = max(max_y,xy[l][1])
                min_y = min(min_y,xy[l][1])
                for m in range(n):
                    if xy[m][0] >= min_x and xy[m][0] <= max_x\
                       and xy[m][1] >= min_y and xy[m][1] <= max_y:
                           cnt += 1
                if cnt >= K:
                    #print(cnt,K)
                    ans = min(ans,(max_x-min_x)*(max_y-min_y))
                
print(ans)

Submission status: Runtime Error

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

XY.sort(key=lambda x: x[0])

ans = float("INF")
for i in range(N):
    for j in range(i+K-1, N):
        W = XY[j][0] - XY[i][0]
        Y = [XY[x][1] for x in range(i, j+1)]
        Y.sort()
        for k in range(len(Y)):
            for l in range(i+K-1, N):
                H = Y[l] - Y[k]
                ans = min(ans, W*H)

print(ans)

Submission status: Runtime Error

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

XY.sort(key=lambda x: x[0])

ans = float("INF")
for i in range(N):
    for j in range(i+K-1, N):
        W = XY[j][0] - XY[i][0]
        Y = [XY[x][1] for x in range(i, j+1)]
        Y.sort()
        for l, k in zip(Y, Y[K-1:]):
                H = Y[k] - Y[l]
                ans = min(ans, W*H)

print(ans)

Submission status: Runtime Error

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

XY.sort(key=lambda x: x[0])

ans = float("INF")
for i in range(N):
    for j in range(i+K-1, N):
        W = XY[j][0] - XY[i][0]
        Y = [XY[x][1] for x in range(i, j+1)]
        Y.sort()
        for k in range(len(Y)):
            for l in range(k+K-1, N):
                H = Y[l] - Y[k]
                ans = min(ans, W*H)

print(ans)

Submission status: Runtime Error

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

XY.sort(key lambda x: x[0])

ans = float("INF")
for i in range(N-K):
    for j in range(i + K - 1, N):
        W = XY[j][0] - XY[i][0]
        Y = [XY[x][1] for x in range(i, j+1)]
        Y.sort()
        for k in range(len(Y)-K):
            for l in range(k + K - 1, N):
                H = Y[l] - Y[k]
                ans = min(ans, W*H)

print(ans)

Submission status: Runtime Error

Solution code:
import heapq
from collections import defaultdict, deque
from math import ceil, factorial, gcd
from itertools import accumulate
import sys
import bisect

sys.setrecursionlimit(10 ** 7)
INF = float("inf")
MOD = 10 ** 9 + 7

si = lambda: input().strip()
ii = lambda: int(input())
mii = lambda: map(int, input().split())
lmii = lambda: list(map(int, input().split()))
lmsi = lambda: list(map(str, input().split()))
smii = lambda: sorted(map(int, input().split()))

# ----------

N, K = mii()

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

ans = INF

for left in range(N):
    for right in range(N):
        for top in range(N):
            for bottom in range(N):
                if X[right]-X[left] <= 0:
                    continue
                if Y[top]-Y[bottom] <= 0:
                    continue
                cnt = 0
                for i in range(N):
                    if X[left] <= X[i] <= X[right] and Y[bottom] <= Y[i] <= Y[top]:
                        cnt += 1
                if cnt >= K:
                    ans = min(ans, (X[right]-X[left])*(Y[top]-Y[bottom]))

print(ans)

Submission status: Runtime Error

Solution code:
n,K = map(int,input().split())
X, Y = [], []
dots = []
for _ in range(n):
    x,y = map(int,input().split())
    dots.append((x,y))
    X.append(x)
    Y.append(y)
X.sort()
Y.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(k+1, l):
                x1,x2 = X[i], X[j]
                y1,y2 = Y[k], Y[l]
                cnt = 0
                for dot in dots:
                    if x1<=dot[0]<=x2 and y1<=dot[1]<=y2:
                        cnt += 1
                if cnt >= K:
                    ans = min(ans, (x2-x1)*(y2-y1))
print(ans)

Submission status: Runtime Error

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

ans = float("inf")
for i in range(n):
    for j in range(i+1, n):
        for h in range(j+1, n):
            for g in range(h+1, n):
                x1 = min(xyl[i][0], xyl[j][0], xyl[h][0], xyl[g][0])
                x2 = max(xyl[i][0], xyl[j][0], xyl[h][0], xyl[g][0])
                y1 = min(xyl[i][1], xyl[j][1], xyl[h][1], xyl[g][1])
                y2 = max(xyl[i][1], xyl[j][1], xyl[h][1], xyl[g][1])
                cnt = 0
                for p in range(n):
                    if x1 <= xyl[p][0] <= x2 and  y1 <= xyl[p][1] <= y2:
                        cnt += 1
                if k <= cnt:
                    ans = min(ans, (x2-x1)*(y2-y1))

for i in range(n):
    for j in range(i+1, n):
        for h in range(j+1, n):
            x1 = min(xyl[i][0], xyl[j][0], xyl[h][0])
            x2 = max(xyl[i][0], xyl[j][0], xyl[h][0])
            y1 = min(xyl[i][1], xyl[j][1], xyl[h][1])
            y2 = max(xyl[i][1], xyl[j][1], xyl[h][1])
                cnt = 0
                for p in range(n):
                    if x1 <= xyl[p][0] <= x2 and  y1 <= xyl[p][1] <= y2:
                        cnt += 1
                if k <= cnt:
                    ans = min(ans, (x2-x1)*(y2-y1))

for i in range(n):
    for j in range(i+1, n):
        x1 = min(xyl[i][0], xyl[j][0])
        x2 = max(xyl[i][0], xyl[j][0])
        y1 = min(xyl[i][1], xyl[j][1])
        y2 = max(xyl[i][1], xyl[j][1])
            cnt = 0
            for p in range(n):
                if x1 <= xyl[p][0] <= x2 and  y1 <= xyl[p][1] <= y2:
                    cnt += 1
            if k <= cnt:
                ans = min(ans, (x2-x1)*(y2-y1))



print(ans)

Submission status: Runtime Error

Solution code:
import sys
import itertools

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, K = lr()
XY = [lr() for _ in range(N)]
answer = float('inf')
# 端の4点、まずはx軸の2点を選ぶ
for i, j in itertools.permutations(list(range(N)), repeat=2):
    xleft = XY[i][0]
    xright = XY[j][0]
    if xright < xleft: xleft, xright = xright, xleft
    candidate = [(x, y) for x, y in XY if xleft <= x <= xright]
    if len(candidate) < K:
        continue
    candidate.sort(key=lambda z: z[1])
    for s in range(len(candidate) - K + 1):
        yup = candidate[s+K-1][1]
        ylow = candidate[s][1]
    area = (xright - xleft) * (yup - ylow)
    if area < answer:
        answer = area

print(answer)
# 31

Submission status: Runtime Error

Solution code:
import numpy as sp
n,k=map(int,input().split())
xy=[list(map(int,input().split())) for i in range(n)]
xy = sp.reshape(sp.array(xy), (n, 2))
def ABC075D(n, k, xy):
    x = xy[:, 0]
    y = xy[:, 1]
    Min = sp.inf
    for x1 in range(n-1):
        for x2 in range(x1+1, n):
            minx = min(x[x1], x[x2])
            maxx = max(x[x1], x[x2])
            for y1 in range(n-1):
                for y2 in range(y1+1, n):
                    count = 0
                    for i in range(n):
                        if minx <= x[i] <= maxx and min(y[y1], y[y2]) <= y[i] <= max(y[y1], y[y2]):
                            count += 1
                    if count == k:
                        Min = min(Min, abs((x[x1]-x[x2])*(y[y1]-y[y2])))
    print(Min)
n,k=map(int,input().split())
xy=[list(map(int,input().split())) for i in range(n)]
ABC075D(n,k,xy)

Submission status: Runtime Error

Solution code:
import numpy as sp
n,k=map(int,input().split())
xy=[list(map(int,input().split())) for i in range(n)]

def ABC075D(n, k, xy):
    xy = sp.reshape(sp.array(xy), (n, 2))
    x = xy[:, 0]
    y = xy[:, 1]
    Min = sp.inf
    for x1 in range(n-1):
        for x2 in range(x1+1, n):
            minx = min(x[x1], x[x2])
            maxx = max(x[x1], x[x2])
            for y1 in range(n-1):
                for y2 in range(y1+1, n):
                    count = 0
                    for i in range(n):
                        if minx <= x[i] <= maxx and min(y[y1], y[y2]) <= y[i] <= max(y[y1], y[y2]):
                            count += 1
                    if count == k:
                        Min = min(Min, abs((x[x1]-x[x2])*(y[y1]-y[y2])))
    print(Min)
n,k=map(int,input().split())
xy=[list(map(int,input().split())) for i in range(n)]
ABC075D(n,k,xy)

Submission status: Runtime Error

Solution code:
import numpy as sp
def ABC075D(n, k, xy):
    xy = sp.reshape(sp.array(list(map(int, xy.split()))), (n, 2))
    x = xy[:, 0]
    y = xy[:, 1]
    Min = sp.inf
    for x1 in range(n-1):
        for x2 in range(x1+1, n):
            minx = min(x[x1], x[x2])
            maxx = max(x[x1], x[x2])
            for y1 in range(n-1):
                for y2 in range(y1+1, n):
                    count = 0
                    for i in range(n):
                        if minx <= x[i] <= maxx and min(y[y1], y[y2]) <= y[i] <= max(y[y1], y[y2]):
                            count += 1
                    if count == k:
                        Min = min(Min, abs((x[x1]-x[x2])*(y[y1]-y[y2])))
    print(Min)
n,k=map(int,input().split())
xy=[list(map(int,input().split())) for i in range(n)]
ABC075D(n,k,xy)

Submission status: Runtime Error

Solution code:
def ABC075D(n, k, xy):
    xy = sp.reshape(sp.array(list(map(int, xy.split()))), (n, 2))
    x = xy[:, 0]
    y = xy[:, 1]
    Min = sp.inf
    for x1 in range(n-1):
        for x2 in range(x1+1, n):
            minx = min(x[x1], x[x2])
            maxx = max(x[x1], x[x2])
            for y1 in range(n-1):
                for y2 in range(y1+1, n):
                    count = 0
                    for i in range(n):
                        if minx <= x[i] <= maxx and min(y[y1], y[y2]) <= y[i] <= max(y[y1], y[y2]):
                            count += 1
                    if count == k:
                        Min = min(Min, abs((x[x1]-x[x2])*(y[y1]-y[y2])))
    print(Min)
n,k=map(int,input().split())
xy=[list(map(int,input().split())) for i in range(n)]
ABC075D(n,k,xy)