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: Time Limit Exceeded

Solution code:
import itertools

n , k = map(int, input().split())
points = [list(map(int, input().split())) for i in range(n)]
sorted_x_list = sorted([point[0] for point in points])
sorted_y_list = sorted([point[1] for point in points])

area = float("inf")
for i, x_left in enumerate(sorted_x_list):
    for j, y_lower in enumerate(sorted_y_list):
        for x_right in sorted_x_list[i+1:]:
            for y_upper in sorted_y_list[j+1:]:
                count = 0
                for point in points:
                    if (x_left <= point[0] <= x_right
                        and y_lower <= point[1] <= y_upper):
                        count += 1
                if count >= k:
                    area = min(area, (x_right-x_left)*(y_upper-y_lower))
print(area)

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
x,y,xy=[],[],[]
for _ in range(n):
  a,b=map(int,input().split())
  x.append(a)
  y.append(b)
  xy.append((a,b))
x.sort()
y.sort()
ans=float('inf')
for i in range(n-1):
  x1=x[i]
  for j in range(i+1,n):
    x2=x[j]
    for l in range(n-1):
      y1=y[l]
      for m in range(l+1,n):
        y2=y[m]
        cnt=0
        for o in range(n):
          x3,y3=xy[o]
          if x1<=x3<=x2 and y1<=y3<=y2:
            cnt+=1
        if cnt>=k:
          ans=min(ans,(x2-x1)*(y2-y1))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
N, K, *L = map(int, open(0).read().split())
L = [(x,y) for x,y in zip(*[iter(L)]*2)]
ans = float('inf')
for m in combinations(L,2):
  for n in combinations(L,2):
    mx = min(m,key=lambda x:x[0])[0]
    Mx = max(m,key=lambda x:x[0])[0]
    my = min(n,key=lambda x:x[1])[1]
    My = max(n,key=lambda x:x[1])[1]
    cnt = 0
    for x,y in L:
      if mx<=x<=Mx and my<=y<=My:
        cnt += 1
    if cnt>=K:
      ans = min(ans, (Mx-mx)*(My-my))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

N, K = map(int, input().split())
xy = [list(map(int, input().split())) for _ in range(N)]
INF = 10 ** 19

acc = defaultdict(int)

x = [-INF]
y = [-INF]

for ex, ey in xy:
	acc[(ex, ey)] = 1
	x.append(ex)
	y.append(ey)

x.sort()
y.sort()

for i in range(N):
	for j in range(N + 1):
		acc[(x[i+1], y[j])] += acc[(x[i], y[j])]

for j in range(N):
	for i in range(N + 1):
		acc[(x[i], y[j+1])] += acc[(x[i], y[j])]

ans = INF
for i in range(1, N + 1):
	for j in range(i + 1, N + 1):
		for k in range(1, N + 1):
			for l in range(k + 1, N + 1):
				cnt = acc[(x[j], y[l])] - acc[(x[j], y[k-1])] - acc[(x[i-1], y[l])] + acc[(x[i-1], y[k-1])]
				if cnt >= K:
					sq = (x[j] - x[i]) * (y[l] - y[k])
					ans = min(ans, sq)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

N, K = map(int, input().split())
xy = [list(map(int, input().split())) for _ in range(N)]
INF = 10 ** 19

acc = defaultdict(int)

for x, y in xy:
	acc[(x, y)] = 1

x = [-INF] + [e for e, _ in xy]
y = [-INF] + [e for _, e in xy]
x.sort()
y.sort()

for i in range(N):
	for j in range(N + 1):
		acc[(x[i+1], y[j])] += acc[(x[i], y[j])]

for j in range(N):
	for i in range(N + 1):
		acc[(x[i], y[j+1])] += acc[(x[i], y[j])]

ans = INF
for i in range(1, N + 1):
	for j in range(i + 1, N + 1):
		for k in range(1, N + 1):
			for l in range(k + 1, N + 1):
				cnt = acc[(x[j], y[l])] - acc[(x[j], y[k-1])] - acc[(x[i-1], y[l])] + acc[(x[i-1], y[k-1])]
				if cnt >= K:
					sq = (x[j] - x[i]) * (y[l] - y[k])
					ans = min(ans, sq)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,K=[int(s) for s in input().split()]
points=[[int(s) for s in input().split()] for _ in range(N)]
X=sorted([points[i][0] for i in range(N)])
Y=sorted([points[i][1] for i in range(N)])
ans=set()
for a in range(N):
  for b in range(a+1,N):
    for c in range(N):
      for d in range(c+1,N):
        count=0
        for [x,y] in points:
          if (X[a]<=x and x<=X[b] and Y[c]<=y and y<=Y[d]):
            count+=1
        if count>=K:
          ans.add((X[b]-X[a])*(Y[d]-Y[c]))
print(min(ans))

Submission status: Time Limit Exceeded

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

ans = float("inf")
for p1, p2 in combinations(xy, 2):
    x1 = p1[0]
    x2 = p2[0]
    if x2 < x1:
        x1, x2 = x2, x1
        #x2 > x1
    for p3, p4 in combinations(xy, 2):
        y1 = p3[1]
        y2 = p4[1]
        if y2 < y1:
            y1, y2 = y2, y1
        # y2 >= y1
        count = 0
        for x, y in xy:
            if x >= x1 and x <= x2 and y >= y1 and y <= y2:
                count += 1

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


print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int,input().split())
XY = []
for i in range(N):
    XY.append(list(map(int,input().split())))
ans = 10**100
for i in range(N):
    for j in range(i+1):
        for k in range(N):
            for l in range(k+1):
                p1x = XY[i][0]
                p2x = XY[j][0]
                p1y = XY[k][1]
                p2y = XY[l][1]
                p1x,p2x = sorted([p1x,p2x])
                p1y,p2y = sorted([p1y,p2y])
                c = 0
                for e in XY:
                    ex,ey = e
                    if ex <= p2x and ex >= p1x and ey <= p2y and ey >= p1y:
                        c += 1
                if c >= K:
                    value = (p2x-p1x)*(p2y-p1y)
                    ans = min(value,ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left,bisect_right

N,K = map(int,input().split())
XY = []
for i in range(N):
    XY.append(list(map(int,input().split())))
ans = 10**100
for i in range(N):
    for j in range(N):
        for k in range(N):
            for l in range(N):
                p1x = XY[i][0]
                p2x = XY[j][0]
                p1y = XY[k][1]
                p2y = XY[l][1]
                p1x,p2x = sorted([p1x,p2x])
                p1y,p2y = sorted([p1y,p2y])
                c = 0
                for e in XY:
                    ex,ey = e
                    if ex <= p2x and ex >= p1x and ey <= p2y and ey >= p1y:
                        c += 1
                if c >= K:
                    value = (p2x-p1x)*(p2y-p1y)
                    ans = min(value,ans)
print(ans)

Submission status: Time Limit Exceeded

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(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 cnt == k:
                            ans = min(ans, (x2 - x1) * (y2 - y1))
                            break




print(ans)

Submission status: Time Limit Exceeded

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(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 cnt == k:
                            ans = min(ans, (x2 - x1) * (y2 - y1))
                            continue




print(ans)

Submission status: Time Limit Exceeded

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 cnt == k:
                            ans = min(ans, (x2 - x1) * (y2 - y1))
                            continue


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 cnt == k:
                        ans = min(ans, (x2 - x1) * (y2 - y1))
                        continue

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 cnt == k:
                    ans = min(ans, (x2 - x1) * (y2 - y1))
                    continue



print(ans)

Submission status: Time Limit Exceeded

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: Time Limit Exceeded

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

ans = 10**20
for i1 in x:
    for i2 in x:
        for i3 in y:
            for i4 in y:
                l = 0
                for j in range(n):
                    if i1 <= x[j] <= i2 and i3 <= y[j] <= i4:
                        l += 1
                if l == k:
                    ans = min(ans, abs((i1 - i2) * (i3 - i4)))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

def area(px,py):
  return (px[1]-px[0])*(py[1]-py[0])

def isInRect(x, px, py):
  return x[0]<=px[1] and x[0]>=px[0] and x[1]<=py[1] and x[1]>=py[0]

def searchMinArea(p, N, K):
  validAreas = []
  for pw in range(N-1):
    for pe in range(pw+1, N):
      for ps in range(N-1):
        for pn in range(ps+1, N):
          ppx = [p[pw][0], p[pe][0]]
          ppy = [p[ps][1], p[pn][1]]
          px = [min(ppx), max(ppx)]
          py = [min(ppy), max(ppy)]
          pInRect = [pid for pid in range(N) if isInRect(p[pid], px, py)]
          if len(pInRect)>=K:
            validAreas.append(area(px, py))
  return min(validAreas)


if __name__ == "__main__":
  # admit stdin
  nk = input().split()
  N = int(nk[0])
  K = int(nk[1])

  p = []
  for i in range(N):
    xy = list(map(lambda x: int(x), input().split()))
    p.append(xy)
  
  print(searchMinArea(p, N, K))

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
xy=[list(map(int,input().split())) for i in range(n)]
x,y=[[xy[i][0],i] for i in range(n)],[[xy[i][1],i] for i in range(n)]
x.sort()
y.sort()
inf=10**18*4
ans=inf
def upper_k(x_sub1,x_sub2,y_sub1,y_sub2):
    global n,k,xy
    z=0
    for i in range(n):
        if x_sub1<=xy[i][0]<=x_sub2 and y_sub1<=xy[i][1]<=y_sub2:
            z+=1
        if z>=k:return True
    return False

for i1 in range(n):
    i1_sub=n-i1
    x_sub1=x[i1][0]
    for l1 in range(i1_sub,1,-1):
        x_sub2=x[i1+l1-1][0]
        x_subsub=x_sub2-x_sub1
        for i2 in range(n):
            ans_sub=inf
            i2_sub=n-i2
            y_sub1=y[i2][0]
            l,r=2,i2_sub
            if r<l:break
            while l+1<r:
                t=(l+r)//2
                y_sub2=y[i2+t-1][0]
                if upper_k(x_sub1,x_sub2,y_sub1,y_sub2):
                    r=t
                else:
                    l=t
            y_sub2=y[i2+r-1][0]
            if upper_k(x_sub1,x_sub2,y_sub1,y_sub2):
                ans=min(x_subsub*(y_sub2-y_sub1),ans)
            if l!=r:
                y_sub2=y[i2+l-1][0]
                if upper_k(x_sub1,x_sub2,y_sub1,y_sub2):
                    ans=min(x_subsub*(y_sub2-y_sub1),ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    n,k=map(int,input().split())
    xy=[list(map(int,input().split())) for i in range(n)]
    x,y=[[xy[i][0],i] for i in range(n)],[[xy[i][1],i] for i in range(n)]
    x.sort()
    y.sort()
    ans=10**18*4
    for i1 in range(n):
        i1_sub=n-i1
        x_sub1=x[i1][0]
        for l1 in range(i1_sub,1,-1):
            x_sub2=x[i1+l1-1][0]
            for i2 in range(n):
                i2_sub=n-i2
                y_sub1=y[i2][0]
                x_subsub=x_sub2-x_sub1
                for l2 in range(i2_sub,1,-1):
                    y_sub2=y[i2+l2-1][0]
                    z=0
                    for i in range(n):
                        if x_sub1<=xy[i][0]<=x_sub2 and y_sub1<=xy[i][1]<=y_sub2:
                            z+=1
                        if z>=k:
                            ans=min(x_subsub*(y_sub2-y_sub1),ans)
                            break
                    else:
                        break
    print(ans)
main()

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
xy=[list(map(int,input().split())) for i in range(n)]
x,y=[[xy[i][0],i] for i in range(n)],[[xy[i][1],i] for i in range(n)]
x.sort()
y.sort()
ans=10**18*4
for i1 in range(n):
    i1_sub=n-i1
    x_sub1=x[i1][0]
    for l1 in range(i1_sub,1,-1):
        x_sub2=x[i1+l1-1][0]
        for i2 in range(n):
            i2_sub=n-i2
            y_sub1=y[i2][0]
            x_subsub=x_sub2-x_sub1
            for l2 in range(i2_sub,1,-1):
                y_sub2=y[i2+l2-1][0]
                z=0
                for i in range(n):
                    if x_sub1<=xy[i][0]<=x_sub2 and y_sub1<=xy[i][1]<=y_sub2:
                        z+=1
                    if z>=k:
                        ans=min(x_subsub*(y_sub2-y_sub1),ans)
                        break
                else:
                    break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
xy=[list(map(int,input().split())) for i in range(n)]
x,y=[[xy[i][0],i] for i in range(n)],[[xy[i][1],i] for i in range(n)]
x.sort()
y.sort()
inf=10**18*4
ans=inf
def upper_k(x_sub1,x_sub2,y_sub1,y_sub2):
    global n,k,xy
    z=[0]*n
    for i in range(n):
        if x_sub1<=xy[i][0]<=x_sub2 and y_sub1<=xy[i][1]<=y_sub2:
            z[i]=1
    return sum(z)>=k

for i1 in range(n):
    i1_sub=n-i1
    x_sub1=x[i1][0]
    for l1 in range(i1_sub,1,-1):
        x_sub2=x[i1+l1-1][0]
        x_subsub=x_sub2-x_sub1
        for i2 in range(n):
            ans_sub=inf
            i2_sub=n-i2
            y_sub1=y[i2][0]
            l,r=2,i2_sub
            if r<l:
                break
            while l+1<r:
                t=(l+r)//2
                y_sub2=y[i2+t-1][0]
                if upper_k(x_sub1,x_sub2,y_sub1,y_sub2):
                    r=t
                else:
                    l=t
            y_sub2=y[i2+r-1][0]
            if upper_k(x_sub1,x_sub2,y_sub1,y_sub2):
                ans=min(x_subsub*(y_sub2-y_sub1),ans)
            if l!=r:
                y_sub2=y[i2+l-1][0]
                if upper_k(x_sub1,x_sub2,y_sub1,y_sub2):
                    ans=min(x_subsub*(y_sub2-y_sub1),ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
xy=[list(map(int,input().split())) for i in range(n)]
x,y=[[xy[i][0],i] for i in range(n)],[[xy[i][1],i] for i in range(n)]
x.sort()
y.sort()
inf=10**18*4
ans=inf
def upper_k(x_sub1,x_sub2,y_sub1,y_sub2):
    global n,k,xy
    z=[0]*n
    k_sub=0
    for i in range(n):
        if x_sub1<=xy[i][0]<=x_sub2 and y_sub1<=xy[i][1]<=y_sub2:
            z[i]=1
            k_sub+=1
            if k_sub>=k:return True
    return False

for i1 in range(n):
    i1_sub=n-i1
    x_sub1=x[i1][0]
    for l1 in range(i1_sub,1,-1):
        x_sub2=x[i1+l1-1][0]
        for i2 in range(n):
            ans_sub=inf
            i2_sub=n-i2
            y_sub1=y[i2][0]
            l,r=2,i2_sub
            if r<l:
                break
            while l+1<r:
                t=(l+r)//2
                y_sub2=y[i2+t-1][0]
                if upper_k(x_sub1,x_sub2,y_sub1,y_sub2):
                    r=t
                else:
                    l=t
            y_sub2=y[i2+r-1][0]
            if upper_k(x_sub1,x_sub2,y_sub1,y_sub2):
                ans=min((x_sub2-x_sub1)*(y_sub2-y_sub1),ans)
            if l!=r:
                y_sub2=y[i2+l-1][0]
                if upper_k(x_sub1,x_sub2,y_sub1,y_sub2):
                    ans=min((x_sub2-x_sub1)*(y_sub2-y_sub1),ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
xy=[list(map(int,input().split())) for i in range(n)]
x,y=[[xy[i][0],i] for i in range(n)],[[xy[i][1],i] for i in range(n)]
x.sort()
y.sort()
ans=10**18*4
for i1 in range(n):
    i1_sub=n-i1
    x_sub1=x[i1][0]
    for l1 in range(i1_sub,1,-1):
        x_sub2=x[i1+l1-1][0]
        for i2 in range(n):
            i2_sub=n-i2
            y_sub1=y[i2][0]
            for l2 in range(i2_sub,1,-1):
                y_sub2=y[i2+l2-1][0]
                z=[0]*n
                for i in range(n):
                    z[i]=(x_sub1<=xy[i][0]<=x_sub2 and y_sub1<=xy[i][1]<=y_sub2)
                if sum(z)>=k:
                    ans=min((x_sub2-x_sub1)*(y_sub2-y_sub1),ans)
                else:
                    break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
xy=[list(map(int,input().split())) for i in range(n)]
x,y=[[xy[i][0],i] for i in range(n)],[[xy[i][1],i] for i in range(n)]
x.sort()
y.sort()
ans=10**18*4
def upper_k(x_sub1,x_sub2,y_sub1,y_sub2):
    global n,k,xy
    z=[0]*n
    for i in range(n):
        if x_sub1<=xy[i][0]<=x_sub2 and y_sub1<=xy[i][1]<=y_sub2:
            z[i]=1
    return sum(z)>=k

for i1 in range(n):
    i1_sub=n-i1
    x_sub1=x[i1][0]
    for l1 in range(i1_sub,1,-1):
        x_sub2=x[i1+l1-1][0]
        for i2 in range(n):
            i2_sub=n-i2
            y_sub1=y[i2][0]
            l,r=2,i2_sub
            if r<l:
                break
            while l+1<r:
                t=(l+r)//2
                y_sub2=y[i2+t-1][0]
                if upper_k(x_sub1,x_sub2,y_sub1,y_sub2):
                    r=t
                else:
                    l=t
            y_sub2=y[i2+r-1][0]
            if upper_k(x_sub1,x_sub2,y_sub1,y_sub2):
                ans=min((x_sub2-x_sub1)*(y_sub2-y_sub1),ans)
            if l!=r:
                y_sub2=y[i2+l-1][0]
                if upper_k(x_sub1,x_sub2,y_sub1,y_sub2):
                    ans=min((x_sub2-x_sub1)*(y_sub2-y_sub1),ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
xy=[list(map(int,input().split())) for i in range(n)]
x,y=[[xy[i][0],i] for i in range(n)],[[xy[i][1],i] for i in range(n)]
x.sort()
y.sort()
ans=10**18*4
def upper_k(x_sub1,x_sub2,y_sub1,y_sub2):
    global n,k,xy
    z=[0]*n
    for i in range(n):
        if x_sub1<=xy[i][0]<=x_sub2 and y_sub1<=xy[i][1]<=y_sub2:
            z[i]=1
    return sum(z)>=k

for i1 in range(n):
    i1_sub=n-i1
    x_sub1=x[i1][0]
    for l1 in range(i1_sub,1,-1):
        x_sub2=x[i1+l1-1][0]
        for i2 in range(n):
            i2_sub=n-i2
            y_sub1=y[i2][0]
            l,r=2,i2_sub
            if r<l:
                break
            while l+1<r:
                t=(l+r)//2
                y_sub2=y[i2+t-1][0]
                if upper_k(x_sub1,x_sub2,y_sub1,y_sub2):
                    r=t
                else:
                    l=t
                #print(str(l)+" "+str(r))
            #print(i2+l-1)
            y_sub2=y[i2+l-1][0]
            if upper_k(x_sub1,x_sub2,y_sub1,y_sub2):
                ans=min((x_sub2-x_sub1)*(y_sub2-y_sub1),ans)
            y_sub2=y[i2+r-1][0]
            if upper_k(x_sub1,x_sub2,y_sub1,y_sub2):
                ans=min((x_sub2-x_sub1)*(y_sub2-y_sub1),ans)
print(ans)

Submission status: Time Limit Exceeded

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)

ABC075D(n,k,xy)

Submission status: Time Limit Exceeded

Solution code:
def main():
    n,k=map(int,input().split())
    xy=[list(map(int,input().split())) for i in range(n)]
    x,y=[[xy[i][0],i] for i in range(n)],[[xy[i][1],i] for i in range(n)]
    x.sort()
    y.sort()
    ans=10**18*4
    for i1 in range(n):
        i1_sub=n-i1
        x_sub1=x[i1][0]
        for l1 in range(i1_sub,1,-1):
            x_sub2=x[i1+l1-1][0]
            for i2 in range(n):
                i2_sub=n-i2
                y_sub1=y[i2][0]
                for l2 in range(i2_sub,1,-1):
                    y_sub2=y[i2+l2-1][0]
                    z=[0]*n
                    for i in range(n):
                        if x_sub1<=xy[i][0]<=x_sub2 and y_sub1<=xy[i][1]<=y_sub2:
                            z[i]=1
                    if sum(z)>=k:
                        ans=min((x_sub2-x_sub1)*(y_sub2-y_sub1),ans)
                    else:
                        break
    print(ans)
main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n,k=map(int,input().split())
xy=[list(map(int,input().split())) for i in range(n)]
xy=np.reshape(np.array(xy),(n,2))
x,y=[[xy[i][0],i] for i in range(n)],[[xy[i][1],i] for i in range(n)]
x.sort()
y.sort()
ans=10**18*4
for i1 in range(n):
    i1_sub=n-i1
    x_sub1=x[i1][0]
    for l1 in range(i1_sub,1,-1):
        x_sub2=x[i1+l1-1][0]
        for i2 in range(n):
            i2_sub=n-i2
            y_sub1=y[i2][0]
            for l2 in range(i2_sub,1,-1):
                y_sub2=y[i2+l2-1][0]
                z=[0]*n
                for i in range(n):
                    if x_sub1<=xy[i][0]<=x_sub2 and y_sub1<=xy[i][1]<=y_sub2:
                        z[i]=1
                if sum(z)>=k:
                    ans=min((x_sub2-x_sub1)*(y_sub2-y_sub1),ans)
                else:
                    break
print(ans)

Submission status: Time Limit Exceeded

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))
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)

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
xy=[list(map(int,input().split())) for i in range(n)]
x,y=[[xy[i][0],i] for i in range(n)],[[xy[i][1],i] for i in range(n)]
x.sort()
y.sort()
ans=10**18*4
r=[i for i in range(n)]
for i1 in r:
    i1_sub=n-i1
    x_sub1=x[i1][0]
    for l1 in range(i1_sub,1,-1):
        x_sub2=x[i1+l1-1][0]
        for i2 in r:
            i2_sub=n-i2
            y_sub1=y[i2][0]
            for l2 in range(i2_sub,1,-1):
                y_sub2=y[i2+l2-1][0]
                z=[0]*n
                for i in r:
                    if x_sub1<=xy[i][0]<=x_sub2 and y_sub1<=xy[i][1]<=y_sub2:
                        z[i]=1
                if sum(z)>=k:
                    ans=min((x_sub2-x_sub1)*(y_sub2-y_sub1),ans)
                else:
                    break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
xy=[list(map(int,input().split())) for i in range(n)]
x,y=[[xy[i][0],i] for i in range(n)],[[xy[i][1],i] for i in range(n)]
x.sort()
y.sort()
ans=10**18*4
for i1 in range(n):
    i1_sub=n-i1
    x_sub1=x[i1][0]
    for l1 in range(i1_sub,1,-1):
        x_sub2=x[i1+l1-1][0]
        for i2 in range(n):
            i2_sub=n-i2
            y_sub1=y[i2][0]
            for l2 in range(i2_sub,1,-1):
                y_sub2=y[i2+l2-1][0]
                z=[0]*n
                for i in range(n):
                    if x_sub1<=xy[i][0]<=x_sub2 and y_sub1<=xy[i][1]<=y_sub2:
                        z[i]=1
                if sum(z)>=k:
                    ans=min((x_sub2-x_sub1)*(y_sub2-y_sub1),ans)
                else:
                    break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
xy=[list(map(int,input().split())) for i in range(n)]
x,y=[[xy[i][0],i] for i in range(n)],[[xy[i][1],i] for i in range(n)]
x.sort()
y.sort()
inf=10**18*4
ans=inf
for i1 in range(n):
    i1_sub=n-i1
    x_sub1=x[i1][0]
    for l1 in range(i1_sub,1,-1):
        x_sub2=x[i1+l1-1][0]
        for i2 in range(n):
            i2_sub=n-i2
            y_sub1=y[i2][0]
            ans_sub=inf
            for l2 in range(i2_sub,1,-1):
                y_sub2=y[i2+l2-1][0]
                z=[0]*n
                for i in range(n):
                    if x_sub1<=xy[i][0]<=x_sub2 and y_sub1<=xy[i][1]<=y_sub2:
                        z[i]=1
                if sum(z)>=k:
                    ans_sub=(x_sub2-x_sub1)*(y_sub2-y_sub1)
                else:
                    break
            ans=min(ans,ans_sub)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
xy=[list(map(int,input().split())) for i in range(n)]
x,y=[[xy[i][0],i] for i in range(n)],[[xy[i][1],i] for i in range(n)]
x.sort()
y.sort()
ans=(10**18)*5
for i1 in range(n):
    i1_sub=n-i1
    for l1 in range(i1_sub,1,-1):
        for i2 in range(n):
            i2_sub=n-i2
            for l2 in range(i2_sub,1,-1):
                x_sub1=x[i1][0]
                x_sub2=x[i1+l1-1][0]
                y_sub1=y[i2][0]
                y_sub2=y[i2+l2-1][0]
                z=[0]*n
                for i in range(n):
                    if x_sub1<=xy[i][0]<=x_sub2 and y_sub1<=xy[i][1]<=y_sub2:
                        z[i]=1
                if sum(z)>=k:
                    s=(x_sub2-x_sub1)*(y_sub2-y_sub1)
                    if s<ans:
                        ans=s
                else:
                    break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
xy=[list(map(int,input().split())) for i in range(n)]
x,y=[[xy[i][0],i] for i in range(n)],[[xy[i][1],i] for i in range(n)]
x.sort()
y.sort()
ans=(10**18)*5
r=range(n)
for i1 in r:
    i1_sub=n-i1
    for l1 in range(i1_sub,1,-1):
        for i2 in r:
            i2_sub=n-i2
            for l2 in range(i2_sub,1,-1):
                x_sub1=x[i1][0]
                x_sub2=x[i1+l1-1][0]
                y_sub1=y[i2][0]
                y_sub2=y[i2+l2-1][0]
                z=[0]*n
                for i in r:
                    if x_sub1<=xy[i][0]<=x_sub2 and y_sub1<=xy[i][1]<=y_sub2:
                        z[i]=1
                if sum(z)>=k:
                    ans=min((x_sub2-x_sub1)*(y_sub2-y_sub1),ans)
                else:
                    break
print(ans)