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: Runtime Error

Solution code:
import numpy as sp
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)

Submission status: Runtime Error

Solution code:
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)

Submission status: Runtime Error

Solution code:
n,k=map(int,input().split())
x,y=[[0,0] for i in range(n)],[[0,0] for i in range(n)]
xy=[list(map(int,input().split())) for i in range(n)]
for i in range(n):
    x_sub,y_sub=xy[i]
    x[i][0]=x_sub
    x[i][1]=i
    y[i][0]=y_sub
    y[i][1]=i
x.sort()
y.sort()
w=[(i1,l1) for i1 in range(n) for l1 in range(n-i1,1,-1)]
v=[(i2,l2) for i2 in range(n) for l2 in range(n-i2,1,-1)]
#print(w)
#print(v)
ans=(10**18)*5
for w_sub in w:
    for v_sub in v:
        if l1*l2<k:
            continue
        i1,l1=w_sub
        i2,l2=v_sub
        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:
            ans=min((x_sub2-x_sub1)*(y_sub2-y_sub1),ans)
print(ans)

Submission status: Runtime Error

Solution code:
n,k=map(int,input().split())
x,y=[[0,0] for i in range(n)],[[0,0] for i in range(n)]
xy=[list(map(int,input().split())) for i in range(n)]
for i in range(n):
    x_sub,y_sub=xy[i]
    x[i][0]=x_sub
    x[i][1]=i
    y[i][0]=y_sub
    y[i][1]=i
x.sort(key=lambda z:z[0])
y.sort(key=lambda z:z[0])
ans=[]
for i1 in range(n):
    for l1 in range(n-i1,1,-1):
        for i2 in range(n):
            for l2 in range(n-i2,1,-1):
                if l1*l2<k:
                    break
                z=[0]*n
                for i in range(i1,i1+l1):
                    l=x[i][1]
                    z[l]=1
                for i in range(i2,i2+l2):
                    l=y[i][1]
                    z[l]=1
                if sum(z)>=k:
                    x_sub1,y_sub1=10**9+1,10**9+1
                    x_sub2,y_sub2=-10**9-1,-10**9-1
                    for i in range(n):
                        if z[i]==1:
                            x_sub1=min(xy[i][0],x_sub1)
                            x_sub2=max(xy[i][0],x_sub2)
                            y_sub1=min(xy[i][1],y_sub1)
                            y_sub2=max(xy[i][1],y_sub2)
                    ans.append(x_sub2-x_sub1)*(y_sub2-y_sub1))
                else:
                    break
print(max(ans))

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Mlst=set()
for s in range(N-1):
    for g in range(s,N):
        for z in range(g,N):
            x1,y1=XY[s]
            x2,y2=XY[g]
            x3,y3=XY[z]
            x1,x2=min(x1,x2,x3),max(x1,x2,x3)
            y1,y2=min(y1,y2,y3),max(y1,y2,y3)
            if sum([x1<=X<=x2 and y1<=Y<=y2 for X,Y in XY])>=K:
                Mlst.add((y2-y1)*(x2-x1))
print(min(Mlst))

Submission status: Runtime Error

Solution code:
lists=[]
for i in range(n):
    x,y=map(int,input().split())
    lists.append((x,y))
anslist=[]
for i in range(n):
    for j in range(i+1,n):
        for k in range(n):
            for l in range(k+1,n):       
                a=lists[i][0]
                b=lists[j][0]
                c=lists[k][1]
                d=lists[l][1]
                counter=0
                for s in range(n):
                    p,q=lists[s][0],lists[s][1]
                    if min(a,b)<=p<=max(a,b) and min(d,c)<=q<=max(c,d):
                        counter+=1
                    if counter>=K:
                        anslist.append(abs(a-b)*abs(c-d))
print(min(anslist))

Submission status: Runtime Error

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

Submission status: Runtime Error

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

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

Submission status: Runtime Error

Solution code:
import itertools
n,k=map(int,input().split())
l=[]
for i in range(n):
    l.append(list(map(int,input().split())))
c=itertools.combinations(range(n),2)
ans=1e25
for i in c:
    for j in c:
        lx=min(l[i[0]][0],l[i[1]][0])
        rx=max(l[i[0]][0],l[i[1]][0])
        dy=min(l[j[0]][1],l[j[1]][1])
        uy=max(l[j[0]][1],l[j[1]][1])
        for p in l:
            if lx<=p[0]<=rx and dy<=p[1]<=uy:
                tk+=1
        if tk>=k:
            ans=min(ans,(uy-dy)*(rx-lx))
print(ans)

Submission status: Runtime Error

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

for i in range(n-k):
    x=[xy[i][0] for i in range(n-i)]
    y=[xy[i][1] for i in range(n-i)]
    xl = min(x)
    xr = max(x)
    yl = min(y)
    yr = max(y)

    xr2 = sorted(x)[-2]
    xl2 = sorted(x)[1]
    yr2 = sorted(y)[-2]
    yl2 = sorted(y)[1]

    res1 = (xl2-xl)*(yr-yl)
    res2 = (xr-xr2)*(yr-yl)
    res3 = (yl2-yl)*(xr-xl)
    res4 = (yr-yr2)*(xr-xl)
    if max(res1,res2,res3,res4) ==res1:
        xy.pop(x.index(xl))
    elif max(res1,res2,res3,res4) ==res2:
        xy.pop(x.index(xr))
    elif max(res1,res2,res3,res4) ==res3:
        xy.pop(x.index(yl))
    elif max(res1,res2,res3,res4) ==res4:
        xy.pop(x.index(yr))

x=[xy[i][0] for i in range(k)]
y=[xy[i][1] for i in range(k)]
xl = min(x)
xr = max(x)
yl = min(y)
yr = max(y)
print((xr-xl)*(yr-yl))

Submission status: Runtime Error

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

for i in range(n-k):
    x=[xy[i][0] for i in range(n-i)]
    y=[xy[i][1] for i in range(n-i)]
    xl = min(x)
    xr = max(x)
    yl = min(y)
    yr = max(y)

    xr2 = sorted(x)[-2]
    xl2 = sorted(x)[0]
    yr2 = sorted(y)[-2]
    yl2 = sorted(y)[0]

    res1 = (xl2-xl)*(yr-yl)
    res2 = (xr-xr2)*(yr-yl)
    res3 = (yl2-yl)*(xr-xl)
    res4 = (yr-yr2)*(xr-xl)
    if max(res1,res2,res3,res4) ==res1:
        xy.pop(x.index(xl))
    elif max(res1,res2,res3,res4) ==res2:
        xy.pop(x.index(xr))
    elif max(res1,res2,res3,res4) ==res3:
        xy.pop(x.index(yl))
    elif max(res1,res2,res3,res4) ==res4:
        xy.pop(x.index(yr))

x=[xy[i][0] for i in range(k)]
y=[xy[i][1] for i in range(k)]
xl = min(x)
xr = max(x)
yl = min(y)
yr = max(y)
print((xr-xl)*(yr-yl))

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
def inputs():return [int(x) for x in input().split()]
N,K = inputs()
xy = [inputs() for _ in range(N)]
#xy = sorted(xy,key=lambda x: x[1])
xy = sorted(xy,key=lambda x: x[0])
#print(xy)
ans = 10**20
for i in range(N-K+1):
  for j in range(i+K-1,N):
    #print(i,j)
    xy1 = xy[i:j+1]
    #print(xy1)
    xy1 = sorted(xy1,key=lambda x: x[1])
    mi = min(xy1[i+K-1]-xy1[i] for i in range(len(xy1)-K+1))
    ans = min(ans,(xy[j][0]-xy[i][0])*mi)
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
n,k = map(int,input().split())
ary = [list(map(int,input().split())) for _ in range(n)]
ary.sort()

ans = float("Inf")
for i in range(n-k+1):
    for j in range(k,n-i+1):
        xmin = ary[i][0]
        xmax = ary[i+j-1][0]
        ary_y = sorted(ary[i:i+j], key=lambda x: (x[1]))
        for l in range(len(ary_y)-k+1):
            ymin = ary_y[l][1]
            ymax = ary_y[l+k-1][1]
            ans = min(ans,(xmax - xmin) * (ymax - ymin))
print(ans)

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
x_list = [0]*n
y_list = [0]*n
for i in range(n):
    x_list[i], y_list[i] = map(int, input().split())

x_element = set(x_list)
y_element = set(y_list)
ans = float("inf")

for i in range(len(x_element)):
    for j in range(len(y_element)):
        for k in range(i+1, len(x_element)):
            for l in range(j+1, len(y_element)):
                num = 0
                for m in range(n):
                    x_left = x_element[i]
                    x_right = x_element[k]
                    y_bottom = y_element[j]
                    y_upper = y_element[l]
                    if x_left <= x_list[m] <= x_right and y_bottom <= y_list[m] <= y_upper:
                        num += 1
                    if num >= k:
                        ans = min((x_right - x_left) * (y_upper - y_bottom), ans)

print(ans)

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
x_list = [0]*n
y_list = [0]*n
for i in range(n):
    x_list[i], y_list[i] = map(int, input().split())

x_element = set(x_list)
y_element = set(y_list)
ans = float("inf")

for i in range(len(x_element)):
    for j in range(len(y_element)):
        for k in range(i+1, len(x_element)):
            for l in range(j+1, len(y_element)):
                num = 0
                for m in range(n):
                    x_left = x_element[i]
                    x_right = x_element[k]
                    y_bottom = y_element[j]
                    y_upper = y_element[l]
                    if x_left <= x[m] <= x_right and y_bottom <= y[m] <= y_upper:
                        num += 1
                    if num >= k:
                        ans = min((x_right - x_left) * (y_upper - y_bottom), ans)

print(ans)

Submission status: Runtime Error

Solution code:
n,k=map(int,input().split())
P=[list(map(int,input().split())) for _ in range(n)]
X=sorted(list(map(lambda x:x[0],P)))
Y=sorted(list(map(lambda x:x[1],P)))
s=(X[0]-X[-1])*(Y[0]-Y[-1])
ans=0
for r in range(1,n):
  for l in range(r):
    if c<k:
      break
    for u in range(1,n):
      for b in range(u):
        c=0
        for p in P:
          if X[l]<=p[0]<=X[r] and Y[b]<=p[1]<=Y[u]:
            c+=1
        if c>=k:
          s=min(s,(X[r]-X[l])*(Y[u]-Y[b]))
        else:break
print(s)

Submission status: Runtime Error

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

    def count(x_min, x_max, y_min, y_max, i, j):
        OK = 0
        # NG = 0
        a = j - i + 1 - K
        for m in XY[i:j + 1]:
            if y_min <= m[1] <= y_max:
                OK += 1
        if OK >= K:
            return True
        return False

    ans = 10 ** 20
    for i, val in enumerate(A[:N - 1]):
        a = val[0]
        for j in range(i + K - 1, N):
            b = XY[j][0]
            e = b - a
            for k in range(N):
                c = XY[k][1]
                for l in range(N):
                    d = XY[l][1]
                    if c < d:
                        if count(a, b, c, d, i, j):
                            # print ('A')
                            ans = min(ans, e * (d - c))
    print (ans)
    return

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
N,K = map(int,input().split())
XY = list(list(map(int,input().split()))for i in range(N))
XY.sort()
ans = float('inf')
for i in range(N-K+1):
    miny = XY[i][1]
    maxy = miny
    y = []
    for j in range(i,i+K):
        y.append(XY[j][1])
    y.sort()
    ans = min((XY[j][0] - XY[i][0])*(y[-1]-y[0]),ans)
    for j in range(i+K,N):
        y.append(XY[j][1])  
        y.sort()
        for k in range(j-K+1):
            ans = min((XY[j][0] - XY[i][0])*(y[k+K-1]-y[k]),ans)
print(ans)

Submission status: Runtime Error

Solution code:
def main():
    N,K = map(int,input().split())
    XY = [list(map(int,input().split())) for _ in [0]*N]
    iX = [0]*N
    iY = [0]*N
    for i,xy in enumerate(XY):
        x,y = xy
        iX[i] = x
        iY[i] = y
    iX.sort()
    iY.sort()
    X = {x:i for i,x in enumerate(iX)}
    Y = {y:i for i,y in enumerate(iY)}

    c = [[0]*(N+1) for i in [0]*(N+1)]
    for x,y in XY:
        c[Y[y]+1][X[x]+1] = 1

    for i in range(N):
        ci1 = c[i+1
        for j in range(N):
            ci1[j+1] += ci1[j]
    for i in range(N):
        ci1 = c[i+1]
        ci = c[i]
        for j,cij in enumerate(ci[1:],1):
            ci1[j] += cij

    ans = 10**20
    for u in range(N):
        for d in range(u+K-1,N):
            l = 0
            r = K-1
            dY = iY[d]-iY[u]
            cd = c[d+1]
            cu = c[u]
            while r<N:
                if cd[r+1]+cu[l]-cu[r+1]-cd[l] >=K:
                    ans = min(ans, (iX[r] - iX[l])*dY)
                    l+=1
                else:r+=1

    print(ans)
main()

Submission status: Runtime Error

Solution code:
N,K = map(int,input().split())
x = []
y = []
l = []
for i in range(N):
    xx,yy = map(int,input().split())
    x.append(xx)
    y.append(yy)
    l.append((xx,yy))

x = sorted(x)
y = sorted(y)

import itertools
ans = float("inf")

for xx in itertools.combinations(x,2):
    for i in range(N):
        if x[i] == xx[0]:
            xai = i
        if x[i] == xx[1]:
            xbi = i

    for yy in itertools.combinations(y,2):
        for i in range(N):
            if y[i] == yy[0]:
                yai = i
            if y[i] == yy[1]:
                ybi = i

        if x[ai] > x[bi] and y[ai] > y[bi]:
            continue

        num = 0
        for i in range(N):
            if l[i][0] >= x[xai] and l[i][0] <= x[xbi] and l[i][1] >= y[yai] and l[i][1] <= y[ybi]:
                num += 1

        if K > num:
            continue

        ans = min(ans , abs(xx[0] - xx[1])*abs(yy[0] - yy[1]))
print(ans)

Submission status: Runtime Error

Solution code:
ab = lambda a,b:abs(a-b)
area = lambda a,b:ab(a[1],b[1])*ab(a[0],b[0])

N, K = map(int, input().split())
A = []
x_lst = []
y_lst = []
for i in range(N):
    a,b = map(int, input().split())
    A.append([a,b])
    x_lst.append(a)
    y_lst.append(b)
if N == 2:
    print(area(a,b))
    exit()

x_lst.sort()
y_lst.sort()
mn = float('INF')
for x in range(N-1):
    for x_ in range(x,N):
        for y in range(N-1):
            for y_ in range(y,N):
                cnt = 0
                for a,b in A:
                    if x_lst[x] <= a <= x_lst[x_] and y_lst[y] <= b <= y_lst[y_]:
                        cnt += 1
                if cnt >= K:
                    mn = min(mn, area([x_lst[x],y_lst[y]], [x_lst[x_], y_lst[y_]]))
print(mn)

Submission status: Runtime Error

Solution code:
from heapq import heappop, heappush
ab = lambda a,b:abs(a-b)
area = lambda a,b:ab(a[1],b[1])*ab(a[0],b[0])
dist = lambda a,b:(ab(a[1],b[1])**2+ab(a[0],b[0])**2)>>1

N, K = map(int, input().split())
A = []
graph = []
inf = float('INF')
mn_x, mn_y, mx_x, mx_y = inf, inf, 0, 0
for i in range(N):
    a,b = map(int, input().split())
    A.append([a,b])
    graph.append([inf for i in range(N)])
    mn_x, mn_y, mx_x, mx_y = min(mn_x, a), min(mn_y, b), max(mx_x, a), max(mx_y, b)

if N == 2:
    print(area(a,b))
    exit()
center = [(mx_x - mn_x) // 2, (mx_y - mn_y) // 2]
mn_dist = inf
for i in range(N):
    for j in range(N):
        if i == j:
            continue
        graph[i][j] = graph[j][i] = dist(A[i], A[j]) + dist(A[j], center)
        if mn_dist > graph[i][j]:
            mn_dist = graph[i][j]
            mn_dict = {i:1,j:1}
            mn_lst = [i,j]

x_lst = [A[mn_lst[0]][0], A[mn_lst[1]][0]]
y_lst = [A[mn_lst[0]][1], A[mn_lst[1]][1]]
cands = []
tmp = min([[graph[mn_lst[0]][i], i] for i in range(N) if i not in mn_dict])
heappush(cands, tmp)
tmp = min([[graph[mn_lst[1]][i], i] for i in range(N) if i not in mn_dict])
heappush(cands, tmp)
    
for i in range(K-2):
    _, idx = heappop(cands)
    mn_dict[idx] = 1
    mn_lst.append(idx)
    x_lst.append(A[idx][0])
    y_lst.append(A[idx][1])
    # print(idx, mn_lst, graph[3][3])
    tmp_lst = [[graph[idx][i], i] for i in range(N) if i not in mn_dict]
    if tmp_lst != []:
        tmp = min(tmp_lst)
        heappush(cands, tmp)

a = [min(x_lst), min(y_lst)]
b = [max(x_lst), max(y_lst)]
print(area(a,b))
# for i in range(N):
#     print(graph[i])
# print(a,b, cands)

Submission status: Runtime Error

Solution code:
from heapq import heappop, heappush
ab = lambda a,b:abs(a-b)
area = lambda a,b:ab(a[1],b[1])*ab(a[0],b[0])
dist = lambda a,b:(ab(a[1],b[1])**2+ab(a[0],b[0])**2)

N, K = map(int, input().split())
A = []
graph = []
inf = float('INF')
mn_x, mn_y, mx_x, mx_y = inf, inf, 0, 0
for i in range(N):
    a,b = map(int, input().split())
    A.append([a,b])
    graph.append([inf for i in range(N)])
    mn_x, mn_y, mx_x, mx_y = min(mn_x, a), min(mn_y, b), max(mx_x, a), max(mx_y, b)

if N == 2:
    print(area(a,b))
    exit()
center = [(mx_x - mn_x) / 2, (mx_y - mn_y) / 2]
mn_dist = inf
for i in range(N):
    for j in range(N):
        if i == j:
            continue
        graph[i][j] = graph[j][i] = dist(A[i], A[j]) + dist(A[j], center)
        if mn_dist > graph[i][j]:
            mn_dist = graph[i][j]
            mn_dict = {i:1,j:1}
            mn_lst = [i,j]

x_lst = [A[mn_lst[0]][0], A[mn_lst[1]][0]]
y_lst = [A[mn_lst[0]][1], A[mn_lst[1]][1]]
cands = []
tmp = min([[graph[mn_lst[0]][i], i] for i in range(N) if i not in mn_dict])
heappush(cands, tmp)
tmp = min([[graph[mn_lst[1]][i], i] for i in range(N) if i not in mn_dict])
heappush(cands, tmp)
    
for i in range(K-2):
    _, idx = heappop(cands)
    mn_dict[idx] = 1
    mn_lst.append(idx)
    x_lst.append(A[idx][0])
    y_lst.append(A[idx][1])
    # print(idx, mn_lst, graph[3][3])
    tmp_lst = [[graph[idx][i], i] for i in range(N) if i not in mn_dict]
    if tmp_lst != []:
        tmp = min(tmp_lst)
        heappush(cands, tmp)

a = [min(x_lst), min(y_lst)]
b = [max(x_lst), max(y_lst)]
print(area(a,b))
# for i in range(N):
#     print(graph[i])
# print(a,b, cands)

Submission status: Runtime Error

Solution code:
from heapq import heappop, heappush
ab = lambda a,b:abs(a-b)
area = lambda a,b:ab(a[1],b[1])*ab(a[0],b[0])
dist = lambda a,b:(ab(a[1],b[1])**2+ab(a[0],b[0])**2)>>1

N, K = map(int, input().split())
A = []
graph = []
inf = float('INF')
for i in range(N):
    a,b = map(int, input().split())
    A.append([a,b])
    graph.append([inf for i in range(N)])
if N == 2:
    print(area(a,b))
    exit()
    
mn_dist = inf
for i in range(N):
    for j in range(N):
        if i == j:
            continue
        graph[i][j] = graph[j][i] = dist(A[i], A[j])
        if mn_dist > graph[i][j]:
            mn_dist = graph[i][j]
            mn_dict = {i:1,j:1}
            mn_lst = [i,j]

x_lst = [A[mn_lst[0]][0], A[mn_lst[1]][0]]
y_lst = [A[mn_lst[0]][1], A[mn_lst[1]][1]]
cands = []
tmp = min([[graph[mn_lst[0]][i], i] for i in range(N) if i not in mn_dict])
heappush(cands, tmp)
tmp = min([[graph[mn_lst[1]][i], i] for i in range(N) if i not in mn_dict])
heappush(cands, tmp)
    
for i in range(K-2):
    _, idx = heappop(cands)
    mn_dict[idx] = 1
    mn_lst.append(idx)
    x_lst.append(A[idx][0])
    y_lst.append(A[idx][1])
    tmp_lst = [[graph[mn_lst[idx]][i], i] for i in range(N) if i not in mn_dict]
    if tmp_lst != []:
        tmp = min(tmp_lst)
        heappush(cands, tmp)

a = [min(x_lst), min(y_lst)]
b = [max(x_lst), max(y_lst)]
print(area(a,b))

Submission status: Runtime Error

Solution code:
from heapq import heappop, heappush
ab = lambda a,b:abs(a-b)
area = lambda a,b:ab(a[1],b[1])*ab(a[0],b[0])
dist = lambda a,b:(ab(a[1],b[1])**2+ab(a[0],b[0])**2)>>1

N, K = map(int, input().split())
A = []
graph = []
inf = float('INF')
for i in range(N):
    a,b = map(int, input().split())
    A.append([a,b])
    graph.append([inf for i in range(N)])
if N == 2:
    print(area(a,b))
    exit()
    
mn_dist = inf
for i in range(N):
    for j in range(N):
        if i == j:
            continue
        graph[i][j] = graph[j][i] = dist(A[i], A[j])
        if mn_dist > graph[i][j]:
            mn_dist = graph[i][j]
            mn_dict = {i:1,j:1}
            mn_lst = [i,j]

x_lst = [A[mn_lst[0]][0], A[mn_lst[1]][0]]
y_lst = [A[mn_lst[0]][1], A[mn_lst[1]][1]]
cands = []
tmp = min([[graph[mn_lst[0]][i], i] for i in range(N) if i not in mn_dict])
heappush(cands, tmp)
tmp = min([[graph[mn_lst[1]][i], i] for i in range(N) if i not in mn_dict])
heappush(cands, tmp)
    
for i in range(K-2):
    _, idx = heappop(cands)
    mn_dict[idx] = 1
    mn_lst.append(idx)
    x_lst.append(A[idx][0])
    y_lst.append(A[idx][1])
    tmp_lst = [[graph[mn_lst[idx]][i], i] for i in range(N) if i not in mn_dict]
    if tmp_lst != []:
        tmp = min(tmp_lst)
        heappush(cands, tmp)

a = [min(x_lst), min(y_lst)]
b = [max(x_lst), max(y_lst)]
print(area(a,b), mn_lst)

Submission status: Runtime Error

Solution code:
from heapq import heappop, heappush
ab = lambda a,b:abs(a-b)
area = lambda a,b:ab(a[1],b[1])*ab(a[0],b[0])
dist = lambda a,b:(ab(a[1],b[1])**2+ab(a[0],b[0])**2)>>1

N, K = map(int, input().split())
A = []
graph = []
inf = float('INF')
for i in range(N):
    a,b = map(int, input().split())
    A.append([a,b])
    graph.append([inf for i in range(N)])
if N == 2:
    print(area(a,b))
    exit()
    
mn_dist = inf
for i in range(N):
    for j in range(N):
        if i == j:
            continue
        graph[i][j] = graph[j][i] = dist(A[i], A[j])
        if mn_dist > graph[i][j]:
            mn_dist = graph[i][j]
            mn_dict = {i:1,j:1}
            mn_lst = [i,j]
print(mn_dict, mn_dist)

x_lst = [A[mn_lst[0]][0], A[mn_lst[1]][0]]
y_lst = [A[mn_lst[0]][1], A[mn_lst[1]][1]]
cands = []
tmp = min([[graph[mn_lst[0]][i], i] for i in range(N) if i not in mn_dict])
heappush(cands, tmp)
tmp = min([[graph[mn_lst[1]][i], i] for i in range(N) if i not in mn_dict])
heappush(cands, tmp)
print(cands)
    
for i in range(K-2):
    _, idx = heappop(cands)
    mn_dict[idx] = 1
    mn_lst.append(idx)
    x_lst.append(A[idx][0])
    y_lst.append(A[idx][1])
    tmp_lst = [[graph[mn_lst[idx]][i], i] for i in range(N) if i not in mn_dict]
    if tmp_lst != []:
        tmp = min(tmp_lst)
        heappush(cands, tmp)

a = [min(x_lst), min(y_lst)]
b = [max(x_lst), max(y_lst)]
print(area(a,b), mn_lst)

Submission status: Runtime Error

Solution code:
from heapq import heappop, heappush
N, K = map(int, input().split())
A = []
graph = []
inf = float('INF')
for i in range(N):
    a,b = map(int, input().split())
    A.append([a,b])
    graph.append([inf for i in range(N)])

ab = lambda a,b:abs(a-b)
area = lambda a,b:ab(a[1],b[1])*ab(a[0],b[0])
dist = lambda a,b:(ab(a[1],b[1])**2+ab(a[0],b[0])**2)>>1
mn_dist = inf
for i in range(N):
    for j in range(N):
        if i == j:
            continue
        graph[i][j] = graph[j][i] = dist(A[i], A[j])
        if mn_dist > graph[i][j]:
            mn_dist = graph[i][j]
            mn_dict = {i:1,j:1}
            mn_lst = [i,j]

x_lst = [A[mn_lst[0]][0], A[mn_lst[1]][0]]
y_lst = [A[mn_lst[0]][1], A[mn_lst[1]][1]]
cands = []
tmp = min([[graph[mn_lst[0]][i], i] for i in range(N) if i not in mn_dict])
heappush(cands, tmp)
tmp = min([[graph[mn_lst[1]][i], i] for i in range(N) if i not in mn_dict])
heappush(cands, tmp)
    
for i in range(K-2):
    _, idx = heappop(cands)
    mn_dict[idx] = 1
    mn_lst.append(idx)
    x_lst.append(A[idx][0])
    y_lst.append(A[idx][1])
    tmp_lst = [[graph[mn_lst[idx]][i], i] for i in range(N) if i not in mn_dict]
    if tmp_lst != []:
        tmp = min(tmp_lst)
        heappush(cands, tmp)

a = [min(x_lst), min(y_lst)]
b = [max(x_lst), max(y_lst)]
print(area(a,b))

Submission status: Runtime Error

Solution code:
import bisect
def count_generate(h,w,a):
    count = [[0]*w for j in range(h)]
    count[0][0] = a[0][0]
    for i in range(1,w):
        count[0][i] = count[0][i-1]+a[0][i]
    for i in range(1,h):
        cnt_w = 0
        for j in range(w):
            cnt_w += a[i][j]
            count[i][j] = count[i-1][j]+cnt_w
    return count

def da_calc(p,q,x,y, da):
    if p > x or q > y:
        return 0
    if p == 0 and q == 0:
        return da[x][y]
    if p == 0:
        return da[x][y]-da[x][q-1]
    if q == 0:
        return da[x][y]-da[p-1][y]
    return da[x][y]-da[p-1][y]-da[x][q-1]+da[p-1][q-1]

N, K = map(int, input().split())
a = []
b = []
for i in range(n):
    ai, bi = map(int, input().split())
    a.append(ai)
    b.append(bi)
    
a_sorted = sorted(set(a))
b_sorted = sorted(set(b))
h = len(a_sorted)
w = len(b_sorted)

Map = [[0]*w for _ in range(h)]

for i in range(N):
    ai = bisect.bisect_left(a_sorted, a[i])
    bi = bisect.bisect_left(b_sorted, b[i])
    Map[ai][bi]+=1

count = count_generate(h, w, Map)
ans = float('inf')
for i in range(h):
    for j in range(i+1, h):
        for k in range(w):
            for l in range(k+1, w):
                #print(i, j, k, l, da_calc(i, k, j, l, count))
                if da_calc(i, k, j, l, count)>=K:
                    #print(i, j, k, l)
                    ans = min(ans, (a_sorted[j]-a_sorted[i])
                              *(b_sorted[l]-b_sorted[k]))
print(ans)

Submission status: Runtime Error

Solution code:
from itertools import combinations as cc
l = []
n,k = map(int, input().split())
xs,ys = set(),set()
t = 10**24
for _ in range(n):
  x,y = map(int, input().split())
  xs.add(x)
  ys.add(y)
  l.append((x,y))
xs = sorted(list(xs))
ys = sorted(list(ys))
for xl,xr in cc(xs,2):
  foe yl,yr in cc(ys,2):
    cnt = 0
    for x,y in l:
      if xl<=x<=xr and yl<=y<=yr:
        cnt += 1
      if cnt >= k:
        s = (xr-xl)*(yr-yl)
        if t > s:
          t = s
print(t)

Submission status: Runtime Error

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

XY = [tuple(map(int,input().split())) for i in range(N)]

dots = XY[:]

import sys
INT_MAX = sys.maxsize


def sub_f(x):
    right_x, left_x = x[0], x[1]
    ans = INT_MAX
    for ((_, under_y), (_, top_y)) in itertools.combinations(dots, 2):
        if under_y > top_y:
            under_y, top_y = top_y, under_y
        counter = 0
        for d_x, d_y in dots:
            if  (left_x <= d_x) and (d_x <= right_x) and (under_y <= d_y) and (d_y <= top_y):
                counter += 1

        if counter >= K:
            area = (top_y-under_y) * (right_x-left_x)
            ans = min(ans, area)
    return ans

import itertools
multiprocessing_inputs = []
for ((left_x, _), (right_x, _)) in itertools.combinations(dots, 2):
    if left_x > right_x:
        left_x, right_x = right_x, left_x
    
    multiprocessing_inputs.append((right_x, left_x))
    #ans_list.append(sub_f(right_x, left_x))


from multiprocessing import Pool
with Pool(5) as p:
    ans_list = p.map(sub_f, multiprocessing_inputs)

ans = min(ans_list)
print(ans)