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

import itertools
ans = INT_MAX
for sub_dots in itertools.combinations(dots, K):
    #print(sub_dots)
    sub_x = [x for x,y in sub_dots]
    sub_y = [y for x,y in sub_dots]
    min_x = min(sub_x)
    min_y = min(sub_y)
    max_x = max(sub_x)
    max_y = max(sub_y)
    area = (max_x-min_x) * (max_y-min_y)
    ans = min(ans, area)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split())
xy = [list(map(int,input().split())) for _ in range(n)]
ans = float('inf')
for i in range(len(xy)):
    for j in range(i+1,len(xy)):
        x1 = min(xy[i][0],xy[j][0])
        x2 = max(xy[i][0],xy[j][0])
        for m in range(len(xy)):
            for l in range(m+1,len(xy)):
                y1 = min(xy[m][1],xy[l][1])
                y2 = max(xy[m][1],xy[l][1])
                points = 0
                for c in range(len(xy)):
                    x,y = xy[c]
                    if x1<=x<=x2 and y1<=y<=y2:
                        points+=1
                if points>=k:
                    ans = min(ans,(x2-x1)*(y2-y1))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split())
xy = [list(map(int,input().split())) for _ in range(n)]
from collections import deque
squares = deque()
for i in range(len(xy)):
    x1 = xy[i][0]
    for j in range(i+1,len(xy)):
        x2 = xy[j][0]
        for m in range(len(xy)):
            y1 = xy[m][1]
            for l in range(m+1,len(xy)):
                y2 = xy[l][1]
                square = (min(x1,x2),max(x1,x2),min(y1,y2),max(y1,y2))
                squares.appendleft(square)
ans = float('inf')
pairs = (-10**9,10**9,-10**9,10**9)
while squares:
    x1,x2,y1,y2 = squares.popleft()
    if x1==x2 or y1==y2:
        continue
    if x2-x1>=pairs[1]-pairs[0] and y2-y1>= pairs[3]-pairs[2]:
        continue
    points = 0
    for x,y in xy:
        if x1<=x<=x2 and y1<=y<=y2:
            points+=1
    if points==k:
        ans = min(ans,(x2-x1)*(y2-y1))
        pairs = (x1,x2,y1,y2)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split())
xy = [list(map(int,input().split())) for _ in range(n)]
from collections import deque
squares = deque()
for i in range(len(xy)):
    x1 = xy[i][0]
    for j in range(i+1,len(xy)):
        x2 = xy[j][0]
        for m in range(len(xy)):
            y1 = xy[m][1]
            for l in range(m+1,len(xy)):
                y2 = xy[l][1]
                square = (min(x1,x2),max(x1,x2),min(y1,y2),max(y1,y2))
                squares.appendleft(square)
ans = float('inf')
while squares:
    x1,x2,y1,y2 = squares.popleft()
    if x1==x2 or y1==y2:
        continue
    points = 0
    for x,y in xy:
        if x1<=x<=x2 and y1<=y<=y2:
            points+=1
    if points==k:
        ans = min(ans,(x2-x1)*(y2-y1))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split())
xy = [list(map(int,input().split())) for _ in range(n)]
squares = []
for i in range(len(xy)):
    x1 = xy[i][0]
    for j in range(i+1,len(xy)):
        x2 = xy[j][0]
        for m in range(len(xy)):
            y1 = xy[m][1]
            for l in range(m+1,len(xy)):
                y2 = xy[l][1]
                square = (min(x1,x2),max(x1,x2),min(y1,y2),max(y1,y2))
                squares.append(square)
ans = float('inf')
for x1,x2,y1,y2 in squares:
    if x1==x2 or y1==y2:
        continue
    points = 0
    for x,y in xy:
        if x1<=x<=x2 and y1<=y<=y2:
            points+=1
    if points==k:
        ans = min(ans,(x2-x1)*(y2-y1))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce
import math

def main():
    # 文字列の2進数を数値にする
    # '101' → '5'
    # 文字列の頭に'0b'をつけてint()にわたす
    # binary = int('0b'+'101',0)

    # 2進数で立っているbitを数える
    # 101(0x5) → 2
    # cnt_bit = bin(5).count('1')
    
    # N! を求める
    # f = math.factorial(N)

    # N の逆元
    # N_inv = pow(N,MOD-2,MOD)

    # nCr
    # Nの階乗 * rの階乗の逆元 * n-rの階乗の逆元
    
    # 切り捨て
    # 4 // 3
    # 切り上げ
    #-(-4 // 3)
    
    # 初期値用:十分大きい数(100億)
    INF = float("inf")

    # 大きな素数
    MOD = 10**9+7
    
    # 1文字のみを読み込み
    # 入力:2
    # a = input().rstrip()
    # 変数:a='2'
    
    # スペース区切りで標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a, b, c, d = (int(_) for _ in input().split())  
    # 変数:a=2 b=4 c=5 d =7
    
    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a = list(int(_) for _ in input().split())
    # 変数:a = [2, 4, 5, 7]    

    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2457
    # a = list(int(_) for _ in input())
    # 変数:a = [2, 4, 5, 7]    
    N, K = (int(_) for _ in input().split())
    p = []
    for i in range(N):
        x,y = (int(_) for _ in input().split())
        p.append((x,y))
        
    ans = INF
    for i in range(N):
        for j in range(N):
            for h in range(N):
                for g in range(N):
                    x_start = min(p[i][0],p[j][0],p[h][0],p[g][0])
                    y_start = min(p[i][1],p[j][1],p[h][1],p[g][1])
                    x_end = max(p[i][0],p[j][0],p[h][0],p[g][0])
                    y_end = max(p[i][1],p[j][1],p[h][1],p[g][1])
                    area = (x_end - x_start) * (y_end - y_start)
                    cnt = 0
                    for k in range(N):
                        if p[k][0] >= x_start and p[k][1] >= y_start and p[k][0] <= x_end and p[k][1] <= y_end:
                            cnt += 1
                            if cnt == K:
                                ans = min(ans,area)
                                break
    print(ans)
    
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations

n, k = map(int, input().split())
xlist, ylist, xy = [], [], []
for _ in range(n):
  x, y = map(int, input().split())
  xlist.append(x)
  ylist.append(y)
  xy.append((x, y))

xlist.sort()
ylist.sort()
ans = (xlist[-1] - xlist[0]) * (ylist[-1] - ylist[0])
for x1, x2 in combinations(xlist, r=2):
  for y1, y2 in combinations(ylist, r=2):
    tmpk = 0
    for i in range(n):
      if x1 <= xy[i][0] <= x2 and y1 <= xy[i][1] <= y2:
        tmpk += 1

      if tmpk >= k:
        tmp_ans = (x2 - x1) * (y2 - y1)
        if ans > tmp_ans:
          ans = tmp_ans

print(ans)

Submission status: Time Limit Exceeded

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

xlist.sort()
ylist.sort()
ans = (xlist[-1] - xlist[0]) * (ylist[-1] - ylist[0])
for i, x1 in enumerate(xlist):
  for x2 in xlist[i+1:]:
    for j, y1 in enumerate(ylist):
      for y2 in ylist[j+1:]:
        tmpk = 0
        for i in range(n):
          if x1 <= xy[i][0] <= x2 and y1 <= xy[i][1] <= y2:
            tmpk += 1

          if tmpk >= k:
            tmp_ans = (x2 - x1) * (y2 - y1)
            if ans > tmp_ans:
              ans = tmp_ans

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, K = map(int,input().split())
xarr = []
yarr = []
src = []
for _ in range(n):
    x, y = map(int,input().split())
    src.append([x,y])
    xarr.append(x)
    yarr.append(y)

xarr.sort()
yarr.sort()
ans = float('inf')
for i in range(n):
    for j in range(i + 1, n):
        for k in range(n):
            for l in range(k + 1, n):
                cnt = 0
                for m in range(n):
                    if src[m][0] >= xarr[i] and src[m][0] <= xarr[j] and src[m][1] >= yarr[k] and src[m][1] <= yarr[l]:
                        cnt += 1
                if cnt >= K:
                    ans = min((xarr[i]-xarr[j])*(yarr[k]-yarr[l]), ans)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools

N,K = map(int, input().split())

X = []
Y = []

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

# 全部数えても間に合う

min_area = 5*10**18

for x1,x2 in itertools.combinations(X,2):
  for y1,y2 in itertools.combinations(Y,2):
    if x1 > x2:
      x1,x2 = x2,x1
    if y1 > y2:
      y1,y2 = y2,y1

    area = (x2-x1) * (y2-y1)
    if area > min_area:
      continue
      
    cnt = 0
    for x,y in zip(X,Y):
      if x1 <= x <= x2 and y1 <= y <= y2:
        cnt += 1
    if cnt < K:
      continue
      
    min_area = area
    
print(min_area)

Submission status: Time Limit Exceeded

Solution code:
#D問題
N,K=map(int,input().split())
XY=[list(map(int,input().split())) for i in range(N)]
XY.sort()
MIN=10**20
for x1 in range(N):
    xleft=XY[x1][0]
    x2=0
    for x2 in range(N):
        xright=XY[x2][0]
        y1=0
        for y1 in range(N):
            ya=XY[y1][1]
            y2=0
            for y2 in range(N):
                yb=XY[y2][1]
                yd=min(ya,yb)
                yu=max(ya,yb)
                i=0
                count=0
                for i in range(N):
                    X=XY[i][0]
                    Y=XY[i][1]
                    
                    if X>=xleft and X<=xright and Y>=yd and Y<=yu:
                        count+=1
                if count>=K:
                    Xrange=xright-xleft
                    Yrange=yu-yd
                    kari=Xrange*Yrange
                    MIN=min(MIN,kari)
print(MIN)

Submission status: Time Limit Exceeded

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

ans = 10 ** 19
for a in range(N):
    for b in range(a+1, N):
        for c in range(N):
            for d in range(c+1, N):
                x0 = data[a][0]
                x1 = data[b][0]
                y0 = data[c][1]
                y1 = data[d][1]

                if x0 > x1:
                    x0, x1 = x1, x0
                if y0 > y1:
                    y0, y1 = y1, y0

                count = 0
                for i, j in data:
                    if x0 <= i <= x1 and y0 <= j <= y1:
                        count += 1
                if count >= K:
                    ans = min(ans, (x1 - x0)*(y1 - y0))

print(ans)

Submission status: Time Limit Exceeded

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

ans = 10 ** 19
for a in range(N):
    for b in range(N):
        if a != b:
            for c in range(N):
                for d in range(N):
                    if c != d:
                        x0 = data[a][0]
                        x1 = data[b][0]
                        y0 = data[c][1]
                        y1 = data[d][1]

                        count = 0
                        for i, j in data:
                            if x0 <= i <= x1 and y0 <= j <= y1:
                                count += 1
                        if count >= K:
                            ans = min(ans, (x1 - x0)*(y1 - y0))

print(ans)

Submission status: Time Limit Exceeded

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

ans = 10 ** 19
for a in range(N):
    for b in range(N):
        for c in range(N):
            for d in range(N):
                x0 = data[a][0]
                x1 = data[b][0]
                y0 = data[c][1]
                y1 = data[d][1]
                if x0 < x1 and y0 < y1:
                    count = 0
                    for i, j in data:
                        if x0 <= i <= x1 and y0 <= j <= y1:
                            count += 1
                    if count >= K:
                        ans = min(ans, (x1 - x0)*(y1 - y0))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# encoding:utf-8
import copy
import numpy as np
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import math

import itertools

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

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

positions.sort()

def check(x_min,x_max,y_min,y_max):
    cnt = 0
    for i in range(N):
        x,y = positions[i]
        if x_min <= x <= x_max:
            if y_min <= y <= y_max:
                cnt += 1
                if cnt == K:
                    return True
        elif x>x_max:
            break

    return False


ans = 10**40
for i in range(2,4+1):
    edges =itertools.combinations(positions,i)

    for edge in edges:
        # x_min = 10**10
        # x_max = -10**10
        # y_min = 10**10
        # y_max = -10**10

        xs = sorted(x for x, y in edge)
        ys = sorted(y for x, y in edge)
        x_min, x_max = xs[0], xs[-1]
        y_min, y_max = ys[0], ys[-1]


        # for j in range(i):
            # x,y = edge[j]

            # y_min = min(y_min,y)
            # y_max = max(y_max,y)
            # if j==0:
            #     x_min = x
            # elif j==i-1:
            #     x_max = x

        area = (x_max-x_min)*(y_max-y_min)
        if area < ans:
            if check(x_min,x_max,y_min,y_max):
                ans = area

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# encoding:utf-8
import copy
import numpy as np
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import math

import itertools

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

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

positions.sort()

def check(x_min,x_max,y_min,y_max):
    cnt = 0
    for i in range(N):
        x,y = positions[i]
        if x_min <= x <= x_max:
            if y_min <= y <= y_max:
                cnt += 1
                if cnt == K:
                    return True
        elif x>x_max:
            break

    return False


ans = 10**40
for i in range(2,4+1):
    edges =itertools.combinations(positions,i)

    for edge in edges:
        x_min = 10**10
        x_max = -10**10
        y_min = 10**10
        y_max = -10**10

        for j in range(i):
            x,y = edge[j]

            y_min = min(y_min,y)
            y_max = max(y_max,y)
            if j==0:
                x_min = x
            elif j==i-1:
                x_max = x

        area = (x_max-x_min)*(y_max-y_min)
        if area < ans:
            if check(x_min,x_max,y_min,y_max):
                ans = area

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# encoding:utf-8
import copy
import numpy as np
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import math

import itertools

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

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

positions.sort()

def check(x_min,x_max,y_min,y_max):
    cnt = 0
    for i in range(N):
        x,y = positions[i]
        if x_min <= x <= x_max:
            if y_min <= y <= y_max:
                cnt += 1
        elif x>x_max:
            break

    if cnt >= K:
        return True
    else:
        return False


ans = 10**40
for i in range(2,4+1):
    edges =itertools.combinations(positions,i)

    for edge in edges:
        x_min = 10**10
        x_max = -10**10
        y_min = 10**10
        y_max = -10**10

        for j in range(i):
            x,y = edge[j]

            y_min = min(y_min,y)
            y_max = max(y_max,y)
            if j==0:
                x_min = x
            elif j==i-1:
                x_max = x

        area = (x_max-x_min)*(y_max-y_min)
        if area < ans:
            if check(x_min,x_max,y_min,y_max):
                ans = area


print(ans)

Submission status: Time Limit Exceeded

Solution code:
# encoding:utf-8
import copy
import numpy as np
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import math

import itertools

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

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

positions.sort()

def check(x_min,x_max,y_min,y_max):
    cnt = 0
    for i in range(N):
        x,y = positions[i]
        if x_min <= x <= x_max:
            if y_min <= y <= y_max:
                cnt += 1
        elif x>x_max:
            break

    if cnt >= K:
        return True
    else:
        return False


ans = 10**40
for i in range(2,4+1):
    edges =itertools.combinations(positions,i)

    for edge in edges:
        x_min = 10**10
        x_max = -10**10
        y_min = 10**10
        y_max = -10**10

        for j in range(i):
            x,y = edge[j]
            x_min = min(x_min,x)
            x_max = max(x_max,x)
            y_min = min(y_min,y)
            y_max = max(y_max,y)

        area = (x_max-x_min)*(y_max-y_min)
        if area < ans:
            if check(x_min,x_max,y_min,y_max):
                ans = area


print(ans)

Submission status: Time Limit Exceeded

Solution code:
# encoding:utf-8
import copy
import numpy as np
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import math

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

import itertools




def check(x_min,x_max,y_min,y_max):
    cnt = 0
    for i in range(N):
        x,y = positions[i]
        if x_min <= x <= x_max:
            if y_min <= y <= y_max:
                cnt += 1

    if cnt >= K:
        return True
    else:
        return False


ans = 10**100
for i in range(2,4+1):
    edges =itertools.combinations(positions,i)

    for edge in edges:
        x_min = 10**10
        x_max = -10**10
        y_min = 10**10
        y_max = -10**10

        for j in range(i):
            x,y = edge[j]
            x_min = min(x_min,x)
            x_max = max(x_max,x)
            y_min = min(y_min,y)
            y_max = max(y_max,y)

        area = (x_max-x_min)*(y_max-y_min)
        if area < ans:
            if check(x_min,x_max,y_min,y_max):
                ans = area


print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
 
n, k = [int(item) for item in input().split()]
xy = [[int(item) for item in input().split()] for _ in range(n)]
 
xsort = sorted(xy, key=lambda x: x[0])
ysort = sorted(xy, key=lambda x: x[1])
l = [i for i in range(n)]
 
def count_points_in_rec(x0, x1, y0, y1):
    count = 0
    for x, y in xy:
        if x < x0 or x1 < x or y < y0 or y1 < y:
            continue
        count += 1
    return count

ans = 5 * 10**18
comb = []
for a, b in combinations(l, 2):
    if b - a >= k-1:
        comb.append([a, b])
for a, b in comb:
    for c, d in comb:
        if count_points_in_rec(xsort[a][0], xsort[b][0], ysort[c][1], ysort[d][1]) == k:
            ans = min(ans, (xsort[b][0]-xsort[a][0]) * (ysort[d][1]-ysort[c][1]))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
 
n, k = [int(item) for item in input().split()]
xy = [[int(item) for item in input().split()] for _ in range(n)]
 
xsort = sorted(xy, key=lambda x: x[0])
ysort = sorted(xy, key=lambda x: x[1])
l = [i for i in range(n)]
 
def count_points_in_rec(x0, x1, y0, y1):
    count = 0
    for x, y in xy:
        if x < x0 or x1 < x:
            continue
        elif y < y0 or y1 < y:
            continue
        count += 1
    return count

ans = 5 * 10**18
comb = []
for a, b in combinations(l, 2):
    if b - a >= k-1:
        comb.append([a, b])

for a, b in comb:
    x0 = xsort[a][0]
    x1 = xsort[b][0]
    for c, d in comb:
        y0 = ysort[c][1]
        y1 = ysort[d][1]
        if count_points_in_rec(x0, x1, y0, y1) == k:
            ans = min(ans, (x1-x0) * (y1-y0))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
 
n, k = [int(item) for item in input().split()]
xy = [[int(item) for item in input().split()] for _ in range(n)]
 
xsort = sorted(xy, key=lambda x: x[0])
ysort = sorted(xy, key=lambda x: x[1])
l = [i for i in range(n)]
 
def count_points_in_rec(x0, x1, y0, y1):
    count = 0
    for x, y in xy:
        if x < x0 or x1 < x:
            continue
        elif y < y0 or y1 < y:
            continue
        count += 1
    return count

ans = 5 * 10**18
for a, b in combinations(l, 2):
    if b - a < k-1:
        continue
    x0 = xsort[a][0]
    x1 = xsort[b][0]
    for c, d in combinations(l, 2):
        if d - c < k-1:
            continue
        y0 = ysort[c][1]
        y1 = ysort[d][1]
        if count_points_in_rec(x0, x1, y0, y1) == k:
            ans = min(ans, (x1-x0) * (y1-y0))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from numpy import cumsum
from itertools import combinations
import bisect

n, k = [int(item) for item in input().split()]
xy = [[int(item) for item in input().split()] for _ in range(n)]

xsort = sorted([xy[i][0] for i in range(n)])
ysort = sorted([xy[i][1] for i in range(n)])

l = [0] * n
cumsum_id = [[0] * n for _ in range(n)]
for i, (x, y) in enumerate(xy):
    l[i] = i
    xid = bisect.bisect_left(xsort, x)
    yid = bisect.bisect_left(ysort, y)
    cumsum_id[xid][yid] = 1
cumsum_id = cumsum(cumsum_id, axis=0)
cumsum_id = cumsum(cumsum_id, axis=1)

def count_points_in_rec(x0, x1, y0, y1):
    count = 0
    count += cumsum_id[x1][y1]
    if x0 > 0:
        count -= cumsum_id[x0-1][y1]
        if y0 > 0:
            count += cumsum_id[x0-1][y0-1]
    if y0 > 0:
        count -= cumsum_id[x1][y0-1]
    return count

ans = 5 * 10**18
for a, b in combinations(l, 2):
    if b - a < k-1:
        continue
    for c, d in combinations(l, 2):
        if d - c < k-1:
            continue
        if count_points_in_rec(a, b, c, d) == k:
            ans = min(ans, (xsort[b]-xsort[a]) * (ysort[d]-ysort[c]))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from numpy import cumsum
from itertools import combinations
import bisect

n, k = [int(item) for item in input().split()]
xy = [[int(item) for item in input().split()] for _ in range(n)]

xsort = sorted([xy[i][0] for i in range(n)])
ysort = sorted([xy[i][1] for i in range(n)])

xid = [0] * n
yid = [0] * n
l = [0] * n
cumsum_id = [[0] * n for _ in range(n)]
for i, (x, y) in enumerate(xy):
    l[i] = i
    xid[i] = bisect.bisect_left(xsort, x)
    yid[i] = bisect.bisect_left(ysort, y)
    cumsum_id[xid[i]][yid[i]] = 1
cumsum_id = cumsum(cumsum_id, axis=0)
cumsum_id = cumsum(cumsum_id, axis=1)

def count_points_in_rec(x0, x1, y0, y1):
    count = 0
    count += cumsum_id[x1][y1]
    if x0 > 0:
        count -= cumsum_id[x0-1][y1]
        if y0 > 0:
            count += cumsum_id[x0-1][y0-1]
    if y0 > 0:
        count -= cumsum_id[x1][y0-1]
    return count

ans = 5 * 10**18
for a, b in combinations(l, 2):
    x0 = a
    x1 = b
    for c, d in combinations(l, 2):
        y0 = c
        y1 = d
        if count_points_in_rec(x0, x1, y0, y1) >= k:
            ans = min(ans, (xsort[x1]-xsort[x0]) * (ysort[y1]-ysort[y0]))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations

n, k = [int(item) for item in input().split()]
xy = [[int(item) for item in input().split()] for _ in range(n)]

xsort = sorted(xy, key=lambda x: x[0])
ysort = sorted(xy, key=lambda x: x[1])

def count_points_in_rec(x0, x1, y0, y1):
    count = 0
    for x, y in xy:
        if x < x0 or x1 < x:
            continue
        elif y < y0 or y1 < y:
            continue
        count += 1
    return count

ans = 5 * 10**18
for a, b in combinations(xsort, 2):
    x0 = a[0]
    x1 = b[0]
    for c, d in combinations(ysort, 2):
        y0 = c[1]
        y1 = d[1]
        if count_points_in_rec(x0, x1, y0, y1) >= k:
            ans = min(ans, (x1-x0) * (y1-y0))

print(ans)

Submission status: Time Limit Exceeded

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

XY = []
X = []
Y = []
for i in range(N):
    x, y = map(int, input().split())
    XY.append([x, y])
    X.append(x)
    Y.append(y)
    
X.sort()
Y.sort()
ans = float('inf')
for i in range(N):
    for j in range(i + 1, N):
        for k in range(N):
            for l in range(k + 1, N):
                cnt = 0
                for x, y in XY:
                    if X[i] <= x <= X[j] and Y[k] <= y <= Y[l]:
                        cnt += 1
                if cnt >= K:
                    ans = min(ans, (X[j] - X[i]) * (Y[l] - Y[k]))
                    
print(ans)

Submission status: Time Limit Exceeded

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

XY = []
X = []
Y = []
for i in range(N):
    x, y = map(int, input().split())
    XY.append([x, y])
    X.append(x)
    Y.append(y)
    
ans = float('inf')
for i in X:
    for j in X:
        for k in Y:
            for l in Y:
                if i < j and k < l:
                    cnt = 0
                    for x, y in XY:
                        if i <= x <= j and k <= y <= l:
                            cnt += 1
                    if cnt >= K:
                        ans = min(ans, (j - i) * (l - k))
                    
print(ans)

Submission status: Time Limit Exceeded

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")
 
for i, j, l, m in product(range(n), repeat=4):
    cnt = 0
    for g in range(n):
        if p[i][0] <= p[g][0] <= p[j][0] and p[l][1] <= p[g][1] <= p[m][1]:
            cnt += 1
    if cnt >= k:
        ans = min(ans, (p[j][0] - p[i][0]) * (p[m][1] - p[l][1]))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from itertools import combinations

def main():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    X = []
    Y = []
    A = []
    for _ in range(N):
        x, y = map(int, input().split())
        A.append((x, y))
        X.append(x)
        Y.append(y)

    X = [(i, x) for i, x in enumerate(sorted(X))]
    Y = [(i, y) for i, y in enumerate(sorted(Y))]

    ans = float('inf')
    for x in combinations(X, 2):
        i1, i2 = x[0][0], x[1][0]
        x1, x2 = x[0][1], x[1][1]
        if i2 - i1 < K-1:
            continue
        for y in combinations(Y, 2):
            j1, j2 = y[0][0], y[1][0]
            y1, y2 = y[0][1], y[1][1]
            if j2 - j1 < K-1:
                continue

            c = 0
            for a in A:
                if x1 <= a[0] <= x2 and y1 <= a[1] <= y2:
                    c += 1

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

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from itertools import combinations, product

def main():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    X = []
    Y = []
    A = []
    for _ in range(N):
        x, y = map(int, input().split())
        A.append((x, y))
        X.append(x)
        Y.append(y)

    X = sorted(X)
    Y = sorted(Y)
    XC = list(combinations(X, 2))
    YC = list(combinations(Y, 2))
    Z = product(XC, YC)

    ans = float('inf')
    for z in Z:
        x1, x2 = z[0][0], z[0][1]
        y1, y2 = z[1][0], z[1][1]

        c = 0
        for a in A:
            if x1 <= a[0] <= x2 and y1 <= a[1] <= y2:
                c += 1

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

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from itertools import combinations

def main():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    X = []
    for _ in range(N):
        x, y = map(int, input().split())
        X.append((x, y))

    X = sorted(X, key=lambda x:x[0])

    ans = float('inf')
    for x in combinations(X, K):
        y1 = 10**10
        y2 = -10**10
        for a in x:
            y1 = min(y1, a[1])
            y2 = max(y2, a[1])

        x1, x2 = x[0][0], x[-1][0]
        area = (x2 - x1) * (y2 - y1)
        ans = min(ans, area)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from itertools import combinations

def main():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    X = []
    for _ in range(N):
        x, y = map(int, input().split())
        X.append((x, y))

    X = sorted(X, key=lambda x:x[0])

    ans = float('inf')
    for x in combinations(X, K):
        yval = []
        for a in x:
            yval.append(a[1])

        x1, x2 = x[0][0], x[-1][0]
        y1, y2 = min(yval), max(yval)
        area = (x2 - x1) * (y2 - y1)
        ans = min(ans, area)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from itertools import combinations

def main():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    X = []
    for _ in range(N):
        x, y = map(int, input().split())
        X.append((x, y))

    ans = float('inf')
    for x in combinations(X, K):
        xval = []
        yval = []
        for a in x:
            xval.append(a[0])
            yval.append(a[1])

        x1, x2 = min(xval), max(xval)
        y1, y2 = min(yval), max(yval)
        area = (x2 - x1) * (y2 - y1)
        ans = min(ans, area)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

for i, j, l, m in product(range(n), repeat=4):
    cnt = 0
    for g in range(n):
        if p[i][0] <= p[g][0] <= p[j][0] and p[l][1] <= p[g][1] <= p[m][1]:
            cnt += 1
    if cnt >= k:
        ans = min(ans, (p[j][0] - p[i][0]) * (p[m][1] - p[l][1]))
print(ans)