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:
N, K = map(int, input().split())

XY = []
for _ in range(N):
    x, y = map(int, input().split())
    XY.append((x, y))
    
    
import numpy as np
dots = np.asarray(XY[:])

import sys
INT_MAX = sys.maxsize

ans = INT_MAX

import itertools
for ((left_x, _), (right_x, _)) in itertools.combinations(dots, 2):
    if left_x > right_x:
        left_x, right_x = right_x, left_x
    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)
            if ans > area:
                ans = area
            
print(ans)

Submission status: Runtime Error

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

XY = []
for _ in range(N):
    x, y = map(int, input().spålit())
    XY.append((x, y))
    

dots = XY[:]

import sys
INT_MAX = sys.maxsize

ans = INT_MAX

import itertools
for left_d, right_d in itertools.permutations(dots, 2):
    if left_d[0] < right_d[0]:
        left_x = left_d[0]
        right_x = right_d[0]
    else:
        left_x = right_d[0]
        right_x =  left_d[0]
    
    for under_d, top_d in itertools.permutations(dots, 2):
        c += 1
        if under_d[1] < top_d[1]:
            under_y = under_d[1]
            top_y = top_d[1]
        else:
            under_y = top_d[1]
            top_y = under_d[1]
            
        counter = 0
        for d in dots:
            if  (left_x <= d[0]) and (d[0] <= right_x) and (under_y <= d[1]) and (d[1] <= top_y):
                counter += 1
            if counter >= K:
                break
                
        if counter >= K:
            area = (top_y-under_y) * (right_x-left_x)
            ans = min(ans, area)
            
print(ans)

Submission status: Runtime Error

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

XY = []
for _ in range(N):
    x, y = map(int, input().split())
    XY.append((x, y))
    

dots = XY[:]

import sys
INT_MAX = sys.maxsize

ans = INT_MAX

import itertools
for left_d, right_d in itertools.permutations(dots, 2):
    if left_d[0] < right_d[0]:
        left_x = left_d[0]
        right_x = right_d[0]
    else:
        left_x = right_d[0]
        right_x =  left_d[0]
    
    for under_d, top_d in itertools.permutations(dots, 2):
        c += 1
        if under_d[1] < top_d[1]:
            under_y = under_d[1]
            top_y = top_d[1]
        else:
            under_y = top_d[1]
            top_y = under_d[1]
            
        counter = 0
        for d in dots:
            if  (left_x <= d[0]) and (d[0] <= right_x) and (under_y <= d[1]) and (d[1] <= top_y):
                counter += 1
                if counter >= K:
                    break
                
        if counter >= K:
            area = (top_y-under_y) * (right_x-left_x)
            ans = min(ans, area)
            
print(ans)

Submission status: Runtime Error

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

XY = []
for _ in range(N):
    x, y = map(int, input().split())
    XY.append((x, y))
    

dots = XY[:]

import sys
INT_MAX = sys.maxsize

x_dots = [(x, y) for x, y in dots]
x_dots = sorted(x_dots)
y_dots = [(x, y) for x, y in dots]
y_dots = sorted(y_dots, key=lambda x: x[1])

ans = INT_MAX
for l in range(N):
    for r in range(l+1, N+1):
        for u in range(N):
            for t in range(u+1, N+1):
                xy_dots =  set(x_dots[l:r]) & set(y_dots[u:t])
                if len(xy_dots) >= K:
                    #print("---")
                    #print(l, r, x_dots[l:r])
                    #print(u, t, y_dots[u:t])
                    l = x_dots[l:r][0][0]
                    r = x_dots[l:r][-1][0]
                    u = y_dots[u:t][0][1]
                    t = y_dots[u:t][-1][1]
                    #print((r-l)*(t-u))
                    ans = min(ans, (r-l)*(t-u))
print(ans)


#y_dots = sorted(y_dots, key=lambda x: x[1])
#ans = INT_MAX

Submission status: Runtime Error

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

XY = []
for _ in range(N):
    x, y = map(int, input().split())
    XY.append((x, y))
    

dots = XY[:]

import sys
INT_MAX = sys.maxsize

x_dots = [(x, y) for x, y in dots]
x_dots = sorted(x_dots)
y_dots = [(x, y) for x, y in dots]
y_dots = sorted(x_dots, key=lambda x: x[1])

ans = INT_MAX
for l in range(N):
    for r in range(l+1, N+1):
        for u in range(N):
            for t in range(u+1, N+1):
                xy_dots =  set(x_dots[l:r]) & set(y_dots[u:t])
                if len(xy_dots) >= K:
                    #print("---")
                    #print(l, r, x_dots[l:r])
                    #print(u, t, y_dots[u:t])
                    l = x_dots[l:r][0][0]
                    r = x_dots[l:r][-1][0]
                    u = y_dots[u:t][0][1]
                    t = y_dots[u:t][-1][1]
                    #print((r-l)*(t-u))
                    ans = min(ans, (r-l)*(t-u))
print(ans)


#y_dots = sorted(y_dots, key=lambda x: x[1])
#ans = INT_MAX

Submission status: Runtime Error

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

XY = []
for _ in range(N):
    x, y = map(int, input().split())
    XY.append((x, y))

if name == 'main':
    dots = XY[:]

    import sys
    INT_MAX = sys.maxsize

    x_dots = [(x, y) for x, y in dots]
    x_dots = sorted(x_dots)
    y_dots = [(x, y) for x, y in dots]
    y_dots = sorted(y_dots, key=lambda x: x[1])

    ans = INT_MAX
    for i in range(N):
        for j in range(i+1, N):
            sub_x_dots = set(x_dots[i:j+1])
            xl = x_dots[i:j+1][0][0]
            xr = x_dots[i:j+1][-1][0]
            for k in range(N):
                for l in range(k+1, N):
                    sub_y_dots = set(y_dots[k:l+1])
                    #print("----")
                    #print(x_dots[i:j+1])
                    #print(y_dots[k:l+1])
                    intersection = sub_x_dots & sub_y_dots
                    if len(intersection) >= K:
                        yl = y_dots[k:l+1][0][1]
                        yr = y_dots[k:l+1][-1][1]
                        area = (xl-xr) * (yl-yr)

                        ans = min(ans, area)
    print(ans)

Submission status: Runtime Error

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

XY = []
for _ in range(N):
    x, y = map(int, input().split())
    XY.append((x, y))
    
if name == 'main':
    dots = XY[:]

    import sys
    INT_MAX = sys.maxsize

    x_dots = [(x, y) for x, y in dots]
    x_dots = sorted(x_dots)
    y_dots = [(x, y) for x, y in dots]
    y_dots = sorted(y_dots, key=lambda x: x[1])

    ans = INT_MAX
    for i in range(N):
        for j in range(i+1, N):
            sub_x_dots = set(x_dots[i:j+1])
            xl = x_dots[i:j+1][0][0]
            xr = x_dots[i:j+1][-1][0]
            for k in range(N):
                for l in range(k+1, N):
                    sub_y_dots = set(y_dots[k:l+1])
                    #print("----")
                    #print(x_dots[i:j+1])
                    #print(y_dots[k:l+1])
                    intersection = sub_x_dots & sub_y_dots
                    if len(intersection) >= K:
                        yl = y_dots[k:l+1][0][1]
                        yr = y_dots[k:l+1][-1][1]
                        area = (xl-xr) * (yl-yr)

                        ans = min(ans, area)
    print(ans)

Submission status: Runtime Error

Solution code:
def main():
	N, K = map(int,input().split())
	points = [0]*N
	max_x, max_y, min_x, min_y = -10**9, -10**9, 10**9, 10**9
	for i in range(N):
		points[i] = list(map(int, input().split()))
		max_x = max(max_x, points[i][0])
		min_x = min(min_x, points[i][0])
		max_y = max(max_y, points[i][1])
		min_y = min(min_y, points[i][1])

	points.sort(key=lambda x:x[0])
	ans = (max_x-min_x)*(max_y-min_y)
	for lr in range(1, N-K+1):
		for l in range(lr):
			this_points = list(points[l:N-lr+l])
			w = this_points[-1][0]-this_points[0][0]
			if w <= 0:
				continue
			this_points.sort(key=lambda x:x[1])
			for t in range(N-K-lr+1):
				h = this_points[t+N-K-lr-1][1] - this_points[t][1]
				if h <= 0:
					continue
				ans = min(ans, w*h)
	print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from itertools import product
n, k = map(int, input().split())
p = [list(map(int, input().split())) for i in range(n)]
ans = float("inf")

p.sort()
for i in range(n-k+1):
    for j in range(i+k-1, n):
        x = p[j][0] - p[i][0]
        yl = sorted(p[i:j+1],key=lambda x:x[1])
        for l in range(len(yl)-k+1):
            y = yl[l+k-1] - yl[k]
            ans = min(ans, y*x)
print(ans)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(1000000)
def input():
    return sys.stdin.readline()[:-1]

'''
n=int(input())
for i in range(n):
    a[i]=int(input())
    a[i],b[i]=map(int,input().split())
a=[int(x) for x in input().split()]
n,m=map(int,input.split())
from operator import itemgetter
a = [(1, "c", 1), (1, "b", 3), (2, "a", 0), (1, "a", 2)]
print(sorted(a))  # 0 番目の要素でソート、先頭の要素が同じなら 1 番目以降の要素も見る
print(sorted(a, key=itemgetter(0)))  # 0 番目の要素だけでソート
print(sorted(a, key=itemgetter(0, 2)))  # 0 番目と 2 番目の要素でソート
print(sorted(a, key=lambda x: x[0] * x[2]))  # 0 番目の要素 * 2 番目の要素でソート
print(sorted(a, reverse=True))  # 降順にソート
a.sort()  # 破壊的にソート、sorted() よりも高速
try: # エラーキャッチ list index out of range
    for i in range():
        k=b[i]
except IndexError as e:
    print(i)
'''

test_data1 = '''\
4 4
1 4
3 3
6 2
8 1
'''

test_data2 = '''\
4 2
0 0
1 1
2 2
3 3
'''

test_data3 = '''\
4 3
-1000000000 -1000000000
1000000000 1000000000
-999999999 999999999
999999999 -999999999
'''
td_num=3

def GetTestData(index):
    if index==1:
        return test_data1
    if index==2:
        return test_data2
    if index==3:
        return test_data3

if False:
    with open("../test.txt", mode='w') as f:
        f.write(GetTestData(td_num))
    with open("../test.txt") as f:
        # Start Input code ---------------------------------------
        
        n,k=map(int,f.readline().split())
        x=[0]*n
        y=[0]*n
        for i in range(n):
            x[i],y[i]=map(int,f.readline().split())
            
        # End Input code ---------------------------------------
else:
    for i in range(1):
        # Start Input code ---------------------------------------
        n,k=map(int,input().split())
        x=[0]*n
        y=[0]*n
        for i in range(n):
            x[i],y[i]=map(int,input().split())
        # End Input code ---------------------------------------
#print('n,k,x,y=',n,k,x,y)
ans=10**20
for x1 in range(n):
    for x2 in range(x1,n+1):
        for y1 in range(n):
            for y2 in range(y1,n+1):                
                cnt=0
                for i in range(n):
                    if min(x[x1],x[x2])<=x[i] and x[i]<=max(x[x1],x[x2]) and min(y[y1],y[y2])<=y[i] and y[i]<=max(y[y1],y[y2]):
                        cnt+=1
                        
                if cnt>=k:
                    ans=min(ans,abs(x[x2]-x[x1])*abs(y[y2]-y[y1]))
                    #print(x1,x2,y1,y2,ans)
print(ans)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(1000000)
#def input():
#    return sys.stdin.readline()[:-1]

'''
n=int(input())
for i in range(n):
    a[i]=int(input())
    a[i],b[i]=map(int,input().split())
a=[int(x) for x in input().split()]
n,m=map(int,input.split())
from operator import itemgetter
a = [(1, "c", 1), (1, "b", 3), (2, "a", 0), (1, "a", 2)]
print(sorted(a))  # 0 番目の要素でソート、先頭の要素が同じなら 1 番目以降の要素も見る
print(sorted(a, key=itemgetter(0)))  # 0 番目の要素だけでソート
print(sorted(a, key=itemgetter(0, 2)))  # 0 番目と 2 番目の要素でソート
print(sorted(a, key=lambda x: x[0] * x[2]))  # 0 番目の要素 * 2 番目の要素でソート
print(sorted(a, reverse=True))  # 降順にソート
a.sort()  # 破壊的にソート、sorted() よりも高速
try: # エラーキャッチ list index out of range
    for i in range():
        k=b[i]
except IndexError as e:
    print(i)
'''

test_data1 = '''\
4 4
1 4
3 3
6 2
8 1
'''

test_data2 = '''\
2 3 0
4 5 6
7 8 9
-1 2 -5
'''

test_data3 = '''\

'''
td_num=1

def GetTestData(index):
    if index==1:
        return test_data1
    if index==2:
        return test_data2
    if index==3:
        return test_data3

if True:
    with open("../test.txt", mode='w') as f:
        f.write(GetTestData(td_num))
    with open("../test.txt") as f:
        # Start Input code ---------------------------------------
        
        n,k=map(int,f.readline().split())
        x=[0]*n
        y=[0]*n
        for i in range(n):
            x[i],y[i]=map(int,f.readline().split())
            
        # End Input code ---------------------------------------
else:
    for i in range(1):
        # Start Input code ---------------------------------------
        n,k=map(int,input().split())
        x=[0]*n
        y=[0]*n
        for i in range(n):
            x[i],y[i]=map(int,input().split())
        # End Input code ---------------------------------------
#print('n,k,x,y=',n,k,x,y)
ans=10**10
for x1 in range(n):
    for x2 in range(n):
        for y1 in range(n):
            for y2 in range(n):                
                cnt=0
                for i in range(n):
                    if min(x[x1],x[x2])<=x[i] and x[i]<=max(x[x1],x[x2]) and min(y[y1],y[y2])<=y[i] and y[i]<=max(y[y1],y[y2]):
                        cnt+=1
                        
                if cnt>=k:
                    ans=min(ans,abs(x[x2]-x[x1])*abs(y[y2]-y[y1]))
                    #print(x1,x2,y1,y2,ans)
print(ans)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(1000000)
#def input():
#    return sys.stdin.readline()[:-1]

'''
n=int(input())
for i in range(n):
    a[i]=int(input())
    a[i],b[i]=map(int,input().split())
a=[int(x) for x in input().split()]
n,m=map(int,input.split())
from operator import itemgetter
a = [(1, "c", 1), (1, "b", 3), (2, "a", 0), (1, "a", 2)]
print(sorted(a))  # 0 番目の要素でソート、先頭の要素が同じなら 1 番目以降の要素も見る
print(sorted(a, key=itemgetter(0)))  # 0 番目の要素だけでソート
print(sorted(a, key=itemgetter(0, 2)))  # 0 番目と 2 番目の要素でソート
print(sorted(a, key=lambda x: x[0] * x[2]))  # 0 番目の要素 * 2 番目の要素でソート
print(sorted(a, reverse=True))  # 降順にソート
a.sort()  # 破壊的にソート、sorted() よりも高速
try: # エラーキャッチ list index out of range
    for i in range():
        k=b[i]
except IndexError as e:
    print(i)
'''

test_data1 = '''\
4 4
1 4
3 3
6 2
8 1
'''

test_data2 = '''\
2 3 0
4 5 6
7 8 9
-1 2 -5
'''

test_data3 = '''\

'''
td_num=1

def GetTestData(index):
    if index==1:
        return test_data1
    if index==2:
        return test_data2
    if index==3:
        return test_data3

if True:
    with open("../test.txt", mode='w') as f:
        f.write(GetTestData(td_num))
    with open("../test.txt") as f:
        # Start Input code ---------------------------------------
        
        n,k=map(int,f.readline().split())
        x=[0]*n
        y=[0]*n
        for i in range(n):
            x[i],y[i]=map(int,f.readline().split())
            
        # End Input code ---------------------------------------
else:
    for i in range(1):
        # Start Input code ---------------------------------------
        n=int(input())
        n,m=map(int,input().split())
        for i in range(n):
            x,y=map(int,input().split())
            a[i]=int(input())
            a[i],b[i]=map(int,input().split())
            a=[int(x) for x in input().split()]
        # End Input code ---------------------------------------
#print('n,k,x,y=',n,k,x,y)
ans=10**10
for x1 in range(n):
    for x2 in range(n):
        for y1 in range(n):
            for y2 in range(n):                
                cnt=0
                for i in range(n):
                    if min(x[x1],x[x2])<=x[i] and x[i]<=max(x[x1],x[x2]) and min(y[y1],y[y2])<=y[i] and y[i]<=max(y[y1],y[y2]):
                        cnt+=1
                        
                if cnt>=k:
                    ans=min(ans,abs(x[x2]-x[x1])*abs(y[y2]-y[y1]))
                    #print(x1,x2,y1,y2,ans)
print(ans)

Submission status: Runtime Error

Solution code:
import copy
N,M=map(int,input().split())

A = [[int(i)-1 for i in input().split()] for i in range(M)]
#print(A)
def dfs(x):
  if visited[x]:
    return
  visited[x]=True
  for i in range(N):
    if edgemat[x][i]:
      dfs(i)
answer=0

for i in range(M):
  visited=[False]*N
  Acopy=copy.deepcopy(A)
  del Acopy[i]
  edgemat=[[0] *N for j in range(N)]
  for m,n in Acopy:
    edgemat[m][n]=1
    edgemat[n][m]=1
  dfs(0)
  if any(visited[y] == False for y in range(N)):
    answer+=1
print(answer)

Submission status: Runtime Error

Solution code:
# d
N,K = map(int, input().split())
xy = []
for _ in range(N):
    xy.append( tuple(map(int, input().split())) )
xs,ys = map(list, zip(*xy))
xs.sort()
ys.sort()
ans = float('inf')
for l in range(N):
    for r in range(l+1,N):
        for b in range(N):
            for t in range(t+1,N):
                xl,xr = xs[l],xs[r]
                yb,yt = ys[b],ys[t]
                cnt = 0
                for xi,yi in xy:
                    if xl<=xi<=xr and yb<=yi<=yt: 
                        cnt += 1
                if cnt>=K:
                    ans = min(ans, (xr-xl)*(yt-yb))
print(ans)

Submission status: Runtime Error

Solution code:
N,K = map(int, input().split())
xy = []
for _ in range(N):
    xy.append( tuple(map(int, input().split())) )
xy.sort(key=lambda x:x[0])
ans = float('inf')
for i in range(N-K+1):
    use_x,use_y = xy[i:i+K]
    area = abs(max(use_x)-min(use_x)) * abs(max(use_y)-min(use_y))
    ans = min(ans, area)
print(ans)

Submission status: Runtime Error

Solution code:
N,K=map(int,input().split())
z=[tuple(map(int,input().split()))for _ in range(N)]
x=[i for i,_ in z]
y=[j for _,j in z]
x.sort()
y.sort()
a=10**20
for i in range(N):
    for j in range(i+1,N):
        for k in range(N):
            for l in range(k+1,N):
                l,r,d,u=x[i],x[j],y[k],y[l]
                if sum([1for v,w in z if l<=v<=r and d<=w<=u else 0])>=K:
                    a=min(a,(r-l)*(u-d))
print(a)

Submission status: Runtime Error

Solution code:
n,k_num = map(int,input().split())
info =[list(map(int,input().split())) for i in range(n)]
li_x = []
li_y = []

for i in range(n):
 # if info[i][0] not in li_x:
    li_x.append(info[i][0])
 # if info[i][1] not in li_y:
    li_y.append(info[i][1])

li_x = sorted(li_x)
li_y = sorted(li_y)

bunpu = [[0]*n for i in range(n)]
for i in range(n):
  for j in range(n):
    if info[i][0]==li_x[j]:
      zahyo_x=j
      break
  for k in range(n):
    if info[i][0]==li_y[k]:
      zahyo_y=k
      break
  bunpu[zahyo_x][zahyo_y]=1

ruiseki = [[0]*n for i in range(n)]


#for i in range(0,n):
#  for j in range(0,n):
#    ruiseki[i][j] = bunpu[i][j]
#横方向(j)の累積
#for i in range(n):
#  for j in range(1,n):
#    ruiseki[i][j] = ruiseki[i][j-1] + ruiseki[i][j]
#縦方向(i)の累積
#for j in range(n):
#  for i in range(1,n):
#    ruiseki[i][j] = ruiseki[i-1][j] + ruiseki[i][j]

#print(bunpu)
#print(ruiseki)

ans = float("inf")

#for i in range(len(li_x)):
#  for j in range(i,len(li_x)):
#    for k in range(len(li_y)):
#      for l in range(j,len(li_y)):
#        count = ruiseki[j][l]
#        if 0<=k-1:
#          count -= ruiseki[j][k-1]
#        if 0<=i-1:
#          count -= ruiseki[i-1][l]
#        if 0<=k-1 and 0<=i-1:
#          count += ruiseki[i-1][k-1]      
#        if count ==k_num:
#          ans = min(ans,(li_x[j]-li_x[i])*(li_y[l]-li_y[k]))
print(1)

Submission status: Runtime Error

Solution code:
n,k_num = map(int,input().split())
info =[list(map(int,input().split())) for i in range(n)]
li_x = []
li_y = []

for i in range(n):
 # if info[i][0] not in li_x:
    li_x.append(info[i][0])
 # if info[i][1] not in li_y:
    li_y.append(info[i][1])

li_x = sorted(li_x)
li_y = sorted(li_y)

bunpu = [[0]*n for i in range(n)]
for i in range(n):
  for j in range(n):
    if info[i][0]==li_x[j]:
      zahyo_x=j
      break
  for k in range(n):
    if info[i][0]==li_y[k]:
      zahyo_y=k
      break
  bunpu[zahyo_x][zahyo_y]=1

ruiseki = [[0]*n for i in range(n)]


for i in range(0,n):
  for j in range(0,n):
    ruiseki[i][j] = bunpu[i][j]
#横方向(j)の累積
for i in range(n):
  for j in range(1,n):
    ruiseki[i][j] = ruiseki[i][j-1] + ruiseki[i][j]
#縦方向(i)の累積
for j in range(n):
  for i in range(1,n):
    ruiseki[i][j] = ruiseki[i-1][j] + ruiseki[i][j]

#print(bunpu)
#print(ruiseki)

ans = float("inf")

#for i in range(len(li_x)):
#  for j in range(i,len(li_x)):
#    for k in range(len(li_y)):
#      for l in range(j,len(li_y)):
#        count = ruiseki[j][l]
#        if 0<=k-1:
#          count -= ruiseki[j][k-1]
#        if 0<=i-1:
#          count -= ruiseki[i-1][l]
#        if 0<=k-1 and 0<=i-1:
#          count += ruiseki[i-1][k-1]      
#        if count ==k_num:
#          ans = min(ans,(li_x[j]-li_x[i])*(li_y[l]-li_y[k]))
print(1)

Submission status: Runtime Error

Solution code:
n,k_num = map(int,input().split())
info =[list(map(int,input().split())) for i in range(n)]
li_x = []
li_y = []

for i in range(n):
 # if info[i][0] not in li_x:
    li_x.append(info[i][0])
 # if info[i][1] not in li_y:
    li_y.append(info[i][1])

li_x = sorted(li_x)
li_y = sorted(li_y)

bunpu = [[0]*n for i in range(n)]
for i in range(n):
  for j in range(n):
    if info[i][0]==li_x[j]:
      zahyo_x=j
      break
  for k in range(n):
    if info[i][0]==li_y[k]:
      zahyo_y=k
      break
  bunpu[zahyo_x][zahyo_y]=1

ruiseki = [[0]*n for i in range(n)]


for i in range(0,n):
  for j in range(0,n):
    ruiseki[i][j] = bunpu[i][j]
#横方向(j)の累積
for i in range(n):
  for j in range(1,n):
    ruiseki[i][j] = ruiseki[i][j-1] + ruiseki[i][j]
#縦方向(i)の累積
for j in range(n):
  for i in range(1,n):
    ruiseki[i][j] = ruiseki[i-1][j] + ruiseki[i][j]

#print(bunpu)
#print(ruiseki)

ans = float("inf")

for i in range(len(li_x)):
  for j in range(i,len(li_x)):
    for k in range(len(li_y)):
      for l in range(j,len(li_y)):
        count = ruiseki[j][l]
        if 0<=k-1:
          count -= ruiseki[j][k-1]
        if 0<=i-1:
          count -= ruiseki[i-1][l]
        if 0<=k-1 and 0<=i-1:
          count += ruiseki[i-1][k-1]      
        if count ==k_num:
          ans = min(ans,(li_x[j]-li_x[i])*(li_y[l]-li_y[k]))
print(ans)

Submission status: Runtime Error

Solution code:
import math

def func(n, k, pos):
    out = math.inf
    for i in range(n):
        # pos[i]を含む長方形を考える
        box = [pos[i] for _ in range(4)]
        used = [False for _ in range(n)]
        used[i] = True
        minS = math.inf
        for _k in range(k-1):
            minS = math.inf
            using = -1
            for j in range(n):
                if not used[j]:
                    s = (max(box[1][0], pos[j][0]) - min(box[0][0], pos[j][0])) \
                         * (max(box[1][1], pos[j][1]) - min(box[2][1], pos[j][1]))
                    if s < minS:
                        minS = s
                        using = j
            used[using] = True
            right = max(box[1][0], pos[using][0])
            left = min(box[0][0], pos[using][0])
            upper = max(box[1][1], pos[using][1])
            botom = min(box[2][1], pos[using][1])
            box = [[left, upper], [right, upper], [right, botom], [left, botom]]
            # print("i:{} _k:{} minS:{} box:{}".format(i, _k, minS, box))
        # if minS != math.inf:
            # print(minS)
        out = min(out, minS)
    return out
n, k = [int(i) for i in input().split()]
pos = [[0, 0] for _ in range(n)]
for i in range(n):
    pos[i] = [int(i) for i in input().split()]
print(func(n, k, pos))
"""
print("21 vs " + str(func(4, 4, [[1, 4], [3, 3], [6, 2], [8, 1]])))
print("1 vs " + str(func(4, 2, [[0, 0], [1, 1], [2, 2], [3, 3]])))
print("3999999996000000001 vs " + str(func(4, 3, [[-1000000000, -1000000000], [1000000000, 1000000000], [-999999999, 999999999], [999999999, -999999999]])))
# print("print(\"\"+str(func({}, {}, {})))".format(n, k, pos))
"""

Submission status: Runtime Error

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

    ans = float('inf')
    for u in range(N):
        for r in range(N):
            for d in range(N):
                for l in range(N):
                    x1, x2 = min(Points[l][0], Points[r][0]), max(Points[l][0], Points[r][0])
                    y1, y2 = min(Points[d][1], Points[u][1]), max(Points[d][1], Points[u][1])
                    tmp = 0
                    for x, y in Points:
                        if (x1 <= x <= x2) and (y1 <= y <= y2):
                            tmp += 1
                    if tmp >= K:
                        ans = min(ans,  (x2 - x1) * (y2 - y1))

    print(ans)


main()

Submission status: Runtime Error

Solution code:
n,t=map(int, input().split())
x=[]
y=[]
m=[]
for i in range(n):
    a,b=map(int, input().split())
    x.append(a)
    y.append(b)
    m.append([a,b])
x.sort()
y.sort()
for i in range(n-1):
    for j in range(i,n):
        if i>=j:continue
        for k in range(n-1):
            for l in range(k,n):
                if k>=l:continue
                count=0
                for a,b in m:
                    if x[i]<=a<=x[j] and y[k]<=b<=y[l]:
                        count+=1
                if count>=t:
                    ans=min(ans,(x[j]-x[i])*(y[l]-y[k]))
print(ans)

Submission status: Runtime Error

Solution code:
N, K = map(int, input().split())
x = []
for i in range(N):
    x.append(list(map(int, input().split())))
ans = []
for i in range(N):
    for j in range(i+1, N):
        count = 0
        x1 = min(x[i][0], x[j][0])
        x2 = max(x[i][0], x[j][0])
        y1 = min(x[i][1], x[j][1])
        y2 = max(x[i][1], x[j][1])

        for k in range(N):
            if x1 <= x[k][0] and x[k][0] <= x2 and y1 <= x[k][1] and x[k][1] <= y2:
                count += 1
        if count >= K:
            ans.append((x2 - x1) * (y2 - y1))
print(min(ans))

Submission status: Runtime Error

Solution code:
N, K = map(int, input().split())
x = []
for i in range(N):
    x.append(list(map(int, input().split())))
ans = []
for i in range(N):
    for j in range(i+1, N):
        count = 0
        x1 = min(x[i][0], x[j][0])
        x2 = max(x[i][0], x[j][0])
        y1 = min(x[i][1], x[j][1])
        y2 = max(x[i][1], x[j][1])
        print([x1, x2, y1, y2])

        for k in range(N):
            if x1 <= x[k][0] and x[k][0] <= x2 and y1 <= x[k][1] and x[k][1] <= y2:
                count += 1
        if count >= K:
            ans.append((x2 - x1) * (y2 - y1))
print(min(ans))

Submission status: Runtime Error

Solution code:
N, K = map(int, input().split())
x = []
for i in range(N):
    x.append(list(map(int, input().split())))
ans = []
for i in range(N):
    for j in range(i+1, N):
        count = 0
        x1 = min(x[i][0], x[j][0])
        x2 = max(x[i][0], x[j][0])
        y1 = min(x[i][1], x[j][1])
        y2 = max(x[i][1], x[j][1])
        print([x1, x2, y1, y2])

        for k in range(N):
            if x1 <= x[k][0] and x[k][0] <= x2 and y1 <= x[k][1] and x[k][1] <= y2:
                count += 1
        print(count)
        if count >= K:
            ans.append((x2 - x1) * (y2 - y1))
print(min(ans))

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
pos = [list(map(int, input().split())) for i in range(n)]
pos.sort(key=lambda x: x[0])

ans = float('inf')
for a in range(n-k+1):
    for i in range(a+1):
        res = pos[i:n-a+i+1]
        for j in range(n-k-a+1):
            res.sort(key=lambda x: x[1])
            res = res[j:n-a-(n-k-a-j)+1]
            ymin = res[0][1]
            ymax = res[-1][1]
            res.sort(key=lambda x: x[0])
            xmin = res[0][0]
            xmax = res[-1][0]
            ans = min(ans, (xmax-xmin)*(ymax-ymin))

print(ans)

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
#define GET_MACRO(_1,_2,_3,_4,_5,_6,_7,_8,NAME,...) NAME
#define pr(...) cerr<< GET_MACRO(__VA_ARGS__,pr8,pr7,pr6,pr5,pr4,pr3,pr2,pr1)(__VA_ARGS__) <<endl
#define pr1(a) (#a)<<"="<<(a)<<" "
#define pr2(a,b) pr1(a)<<pr1(b)
#define pr3(a,b,c) pr1(a)<<pr2(b,c)
#define pr4(a,b,c,d) pr1(a)<<pr3(b,c,d)
#define pr5(a,b,c,d,e) pr1(a)<<pr4(b,c,d,e)
#define pr6(a,b,c,d,e,f) pr1(a)<<pr5(b,c,d,e,f)
#define pr7(a,b,c,d,e,f,g) pr1(a)<<pr6(b,c,d,e,f,g)
#define pr8(a,b,c,d,e,f,g,h) pr1(a)<<pr7(b,c,d,e,f,g,h)
using namespace std;
using Int = long long;
using _int = int;
using ll = long long;
using Double = long double;
const Int INF = (1LL<<62)+1e9; // ~ 3.6 * 1e16
const Int mod = (1e9)+7;
const Double EPS = 1e-8;
const Double PI = 6.0 * asin((Double)0.5);
using P = pair<Int,Int>;
using T = tuple<Int,Int,Int>;
template<class T> T Max(T &a,T b){return a=max(a,b);}
template<class T> T Min(T &a,T b){return a=min(a,b);}
ostream& operator<<(ostream& o,pair<auto,auto> p){return o<<"("<<p.first<<","<<p.second<<")";}
ostream& operator<<(ostream& o,tuple<auto,auto,auto> t){
  return o<<"("<<get<0>(t)<<","<<get<1>(t)<<","<<get<2>(t)<<")";}
istream& operator>>(istream& i,pair<auto,auto> &p){return i>>p.first>>p.second;}
ostream& operator<<(ostream& o,vector<auto> &a){Int i=0;for(auto t:a)o<<(i++?" ":"")<<t;return o;}
istream& operator>>(istream& i,vector<auto> &a){for(auto &t:a)i>>t;return i;}
void prArr(auto a,string s=" "){Int i=0;for(auto t:a)cout<<(i++?s:"")<<t;cout<<endl;}


bool in(Int x,Int y, Int X,Int Y,Int a,Int b){
  return x <= a && a <= X && y <= b && b <= Y;  
}

signed main(){
  srand((unsigned)time(NULL));
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(12);

  Int n, K;
  cin>>n>>K;
  vector<P> A(n);
  cin>>A;

  Int ans = INF;
  for(Int i=0;i<n;i++)
    for(Int j=0;j<n;j++)
      for(Int k=0;k<n;k++)
	for(Int l=0;l<n;l++){
	  Int x = A[i].first;
	  Int y = A[j].second;
	  Int X = A[k].first;
	  Int Y = A[l].second;
	  Int area = (X - x) * (Y - y);
	  if(x >= X || y >= Y) continue;
	  
	  Int cnt = 0;
	  for(Int m=0;m<n;m++)
	    cnt += in(x, y, X, Y, A[m].first, A[m].second);
	  if(cnt >= K) Min(ans, area);
	}
  cout<<ans<<endl;
  
  return 0;
}