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 = [[int(i) for i in input().split()] for j in range(n)]

ans = 10**20

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

Submission status: Time Limit Exceeded

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

ans = 10**20

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

Submission status: Time Limit Exceeded

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

ans = 10**20

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

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

n, k = map(int, readline().split())
xy = [list(map(int, readline().split())) for _ in range(n)]
ans = float('inf')
for i, (ix, _) in enumerate(xy):
    for jx, _ in xy[i + 1:]:
        for j, (_, iy) in enumerate(xy):
            for _, jy in xy[j + 1:]:
                cnt = 0
                for x, y in xy:
                    if (ix <= x <= jx or jx <= x <= ix) and (iy <= y <= jy or jy <= y <= iy):
                        cnt += 1
                if cnt >= k:
                    ans = min(ans, abs(jx - ix) * abs(jy - iy))
print(ans)

Submission status: Time Limit Exceeded

Solution code:



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

"""
辺の上に点が乗っていても四角形の中に含まれると見なされるので、辺はいずれかの点の上を通るように引くと面積を小さくできる
各点のx,yをsetで持っておいて、全探索できるか？
→ N <= 50なので4つの辺の選び方が50**4、この範囲にK個以上入っているかでさらに *50なので間に合うか微妙？
小さい値で ^5 なので、間に合うかも
"""

LR = [] # left,right
TB = [] # top, bottom
for x,y in XY:
    LR.append(x)
    TB.append(y)


LR = list(set(LR))
LR.sort()
TB = list(set(TB))
TB.sort()


def more_than_K(l,r,t,b):
    cnt = 0
    for x,y in XY:
        if l <= x <= r and b <= y <= t:
            cnt += 1
    return cnt >= K

ans = float("inf")
for p in range(len(LR)):
    for q in range(p+1, len(LR)):
        for r in range(len(TB)):
            for s in range(r+1, len(TB)):

                if more_than_K(LR[p], LR[q], TB[s], TB[r]):
                    ans = min(ans, (LR[q] - LR[p]) * (TB[s] - TB[r]))


print(ans)

Submission status: Time Limit Exceeded

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

x = sorted(v for v, _ in X)
y = sorted(v for _, v in X)
ans = 10 ** 20
for x1 in x:
    for x2 in x:
        for y1 in y:
            for y2 in y:
                num = 0
                for i in range(N):
                    if x1 <= X[i][0] <= x2 and y1 <= X[i][1] <= y2:
                        num += 1
                if num >= K:
                    ans = min(ans, abs(x1 - x2) * abs(y1 - y2))
                    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations

N, K = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(N)]

ans = 10 ** 20
for t in combinations(range(N), K):
    x = []
    y = []
    for i in t:
        x.append(X[i][0])
        y.append(X[i][1])
    ans = min(ans, (max(x) - min(x)) * (max(y) - min(y)))

print(ans)

Submission status: Time Limit Exceeded

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

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

xy_prod_list=[]
for x in xlist:
  for y in ylist:
    xy_prod_list.append((x,y))
xy_prod_list.sort()
#print(xy_prod_list)    

answer=float("inf")
for i in range(len(xy_prod_list)):
  x1,y1=xy_prod_list[i]
  for j in range(i+1,len(xy_prod_list)):
    x2,y2=xy_prod_list[j]    
    
    num_inbox=0
    for x,y in xylist:
      if min(x1,x2)<=x<=max(x1,x2) and min(y1,y2)<=y<=max(y1,y2):
        num_inbox+=1
    
    if num_inbox>=K:
      answer=min(answer,abs(x2-x1)*abs(y2-y1))
    
print(answer)

Submission status: Time Limit Exceeded

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

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

ans = float('INF')

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

n, k = map(int, input().split())
xy = [0] * n
for i in range(n):
    xy[i] = list(map(int, input().split()))
ABC075D(n, k, xy)

Submission status: Time Limit Exceeded

Solution code:
import itertools

n,k = map(int, input().split())
xy = [list(map(int, input().split())) for i in range(n)]
INF = 10 ** 20
ans = INF
for i in itertools.combinations(xy,2):
  max_x,min_x = -INF,INF
  for x,Y in i:
    max_x = max(max_x,x)
    min_x = min(min_x,x)
  for j in itertools.combinations(xy,2):
    max_y,min_y = -INF,INF
    for X,y in j:
      max_y = max(max_y,y)
      min_y = min(min_y,y)
    inrec = 0
    for x,y in xy:
      if  min_x <= x <= max_x and min_y <= y <= max_y:
        inrec += 1
    if inrec >= k:
      ans = min(ans,(max_x-min_x)*(max_y-min_y))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
n,k = map(int,input().split())
XY = [list(map(int,input().split())) for _ in range(n)]
ans = 1e100
for l,r in combinations(range(n),2):
  for b,t in combinations(range(n),2):
    left,right = sorted([XY[l][0], XY[r][0]])
    bottom,top = sorted([XY[b][1], XY[t][1]])
    cnt = 0
    for x,y in XY:
      if left <= x <= right and bottom <= y <= top:
        cnt += 1
    if cnt >= k:
      ans = min(ans, (top - bottom)*(right - left))
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)]

MAX = 10**9
MIN = -1 * MAX
def check(x_r, x_l, y_t, y_b):
    tl = [MIN, MAX]
    br = [MAX, MIN]
    if x_r == x_l or y_t == y_b:
        return False, -1

    tl[0] = max(tl[0], xy[x_l][0])
    tl[1] = min(tl[1], xy[y_t][1])
    br[0] = min(br[0], xy[x_r][0])
    br[1] = max(br[1], xy[y_b][1])

    # count k
    cnt = 0
    for i in range(n):
        if tl[0] <= xy[i][0] <= br[0] and br[1] <= xy[i][1] <= tl[1]:
            cnt += 1
    if cnt < k:
        return False, -1
    area = (br[0] - tl[0]) * (tl[1] - br[1])
    return True, area

INF = 10**20
ans = INF
for a in range(n):
    for b in range(n):
        for c in range(n):
            for d in range(n):
                f, area = check(a, b, c, d)
                if f:
                    ans = min(ans, area)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)


############ ---- Input Functions ---- ############
def in_int():
    return (int(input()))


def in_list():
    return (list(map(int, input().split())))


def in_str():
    s = input()
    return (list(s[:len(s) - 1]))


def in_ints():
    return (map(int, input().split()))


n, k = in_ints()


l = []
lx = []
ly = []
for nn in range(n):
    x, y = in_ints()
    l.append((x,y))
    lx.append(x)
    ly.append(y)


ans = sys.maxsize

lx = sorted(lx)
ly = sorted(ly)

for xi in range(n):
    for xj in range(xi+1,n):
        for yi in range(n):
            for yj in range(yi+1,n):

                x = lx[xi]
                xxx = lx[xj]

                y = ly[yi]
                yyy = ly[yj]

                count  = 0
                for xx, yy in l:
                    if x <= xx  and xx <= xxx and y <= yy and yy <= yyy:
                        count +=1

                if count >=k:
                    ans  = min(ans, (x-xxx)*(y-yyy))


print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)


############ ---- Input Functions ---- ############
def in_int():
    return (int(input()))


def in_list():
    return (list(map(int, input().split())))


def in_str():
    s = input()
    return (list(s[:len(s) - 1]))


def in_ints():
    return (map(int, input().split()))


n, k = in_ints()


l = []
lx = []
ly = []
for nn in range(n):
    x, y = in_ints()
    l.append((x,y))
    lx.append(x)
    ly.append(y)


ans = sys.maxsize


for x in lx:
    for xxx in lx:
        for y in ly:
            for yyy in ly:
                if x >= xxx or y >= yyy:
                    continue
                count  = 0
                for xx, yy in l:
                    if x <= xx  and xx <= xxx and y <= yy and yy <= yyy:
                        count +=1

                if count >=k:
                    ans  = min(ans, (x-xxx)*(y-yyy))


print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import *
import heapq
import math
import bisect
import copy
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

n,k=map(int,input().split())
xy=[list(map(int,input().split())) for i in range(n)]
lst=[0]*n
lst2=[0]*n
for i in range(n):
    x,y=xy[i]
    lst[i],lst2[i]=x,y
lst,lst2=list(permutations(lst,2)),list(permutations(lst2,2))
ans=float('inf')
for i in range(len(lst)):
    xl,xr=min(lst[i]),max(lst[i])
    for j in range(len(lst2)):
        yl,yr=min(lst2[j]),max(lst2[j])
        cnt=0
        for l in range(n):
            x,y=xy[l]
            if xl<=x<=xr and yl<=y<=yr:
                cnt+=1
        if cnt>=k:
            ans=min(ans,(xr-xl)*(yr-yl))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

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

xc = list(combinations(x,2))
yc = list(combinations(y,2))
ans = 4*10**18

for yy in yc:
    u = max(yy)
    d = min(yy)
    for xx in xc:
        r = max(xx)
        l = min(xx)
        count = 0
        for i in range(n):
            if l <= x[i] <=r and d <= y[i] <=u: count += 1
        if count >= k:
            ans = min(ans, (u-d)*(r-l))

print(ans)

Submission status: Time Limit Exceeded

Solution code:

import itertools as it
import numpy as np
from functools import *
import sys
sys.setrecursionlimit(100000)
input = sys.stdin.readline


def acinput():
    return list(map(int, input().split(" ")))


def II():
    return int(input())


directions = np.array([[1, 0], [0, 1], [-1, 0], [0, -1]])
directions = list(map(np.array, directions))

mod = 10**9+7


def factorial(n):
    fact = 1
    for integer in range(1, n + 1):
        fact *= integer
    return fact


def serch(x, count):
    #print("top", x, count)

    for d in directions:
        nx = d+x
        # print(nx)
        if np.all(0 <= nx) and np.all(nx < (H, W)):
            if field[nx[0]][nx[1]] == "E":
                count += 1
                field[nx[0]][nx[1]] = "V"
                count = serch(nx, count)
                continue
            if field[nx[0]][nx[1]] == "#":
                field[nx[0]][nx[1]] = "V"
                count = serch(nx, count)

    return count


N, K = acinput()


ary = [acinput() for i in range(N)]
x = list(map(lambda x: x[0], sorted(ary, key=lambda s: s[0])))
y = list(map(lambda x: x[1], sorted(ary, key=lambda x: x[1])))


#print(list(it.combinations(y,2)))
#print(list(x))

res = 10**20
for sy in it.combinations(y, 2):
    #print(sy)
    for sx in it.combinations(x, 2):
        #print(sx)
        #print(sy, sx)
        count = 0
        for sa in ary:
            
            if sy[0] <= sa[1] and sa[1] <= sy[1]:
                if sx[0] <= sa[0] and sa[0] <= sx[1]:
                    count += 1

        #print(count)
        if count >= K:
            dx = np.diff(sx)[0]
            dy = np.diff(sy)[0]
            #print(dx,dy)
            res = min(res, dx*dy)
            #print(res)

print(res)

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby
    #from itertools import product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

    n,k = map(int, input().split())
    xy = [list(map(int, input().split())) for _ in range(n)]
    x = sorted(xy, key=lambda a: a[0])
    y = sorted(xy, key=lambda a: a[1])

    res = 10**20
    for l in range(n):
        for r in range(l+1, n):
            for b in range(n):
                for t in range(b+1, n):
                    cnt = 0
                    for vx, vy in xy:
                        if x[l][0] <= vx <= x[r][0] and y[b][1] <= vy <= y[t][1]:
                            cnt += 1
                        if cnt >= k:
                            res = min(res, (x[r][0]-x[l][0])*(y[t][1]-y[b][1]))
                            break
    print(res)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby
    #from itertools import product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

    n,k = map(int, input().split())
    xy = [list(map(int, input().split())) for _ in range(n)]
    x = sorted(xy, key=lambda a: a[0])
    y = sorted(xy, key=lambda a: a[1])

    res = 10**20
    for l in range(n):
        for r in range(l+1, n):
            for b in range(n):
                for t in range(b+1, n):
                    cnt = 0
                    for vx, vy in xy:
                        if x[l][0] <= vx <= x[r][0] and y[b][1] <= vy <= y[t][1]:
                            cnt += 1
                    if cnt >= k:
                        res = min(res, (x[r][0]-x[l][0])*(y[t][1]-y[b][1]))
    print(res)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
x=[0]*n
y=[0]*n
a=[]
for i in range(n):
  x[i],y[i]=map(int,input().split())
  a.append((x[i],y[i]))
ans=4*(10**18)
x.sort()
y.sort()
for i in range(n-1):
  for j in range(i+1,n):
    for l in range(n-1):
      for m in range(l+1,n):
        L=x[i]
        R=x[j]
        D=y[l]
        U=y[m]
        if L==R or U==D:
          continue
        cnt=0
        for s in a:
          if L<=s[0]<=R and D<=s[1]<=U:
            cnt+=1
        if cnt>=k:
          ans=min(ans,(R-L)*(U-D))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions
from decimal import Decimal
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n,k = inpl()
xary = []; yary = []
a = []
for i in range(n):
    x,y = inpl()
    xary += [x]; yary += [y]
    a += [[x,y]]
xary.sort(); yary.sort()
res = INF
for xi in range(n-1):
    for xj in range(xi+1,n):
        for yi in range(n-1):
            for yj in range(yi+1,n):
                cnt = 0
                l = xary[xi]; r = xary[xj]
                d = yary[yi]; u = yary[yj]
                # print(l,r,d,u)
                for i in range(n):
                    x,y = a[i]
                    if l<=x<=r and d<=y<=u:
                        cnt += 1
                if cnt >= k:
                    res = min(res, (r-l)*(u-d))
print(res)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
N, K = map(int, input().split())
dots = sorted([tuple(map(int, input().split())) for _ in range(N)], key=lambda x: x[0])

dot_comb = combinations(dots, K)

ans = 10 ** 37
for dots in dot_comb:
    x_min = 10 ** 9 + 1
    x_max = (-1) * (10 ** 9 + 1)
    y_min = 10 ** 9 + 1
    y_max = (-1) * (10 ** 9 + 1)
    for dot in dots:
        x, y = dot
        x_min = min(x_min, x)
        x_max = max(x_max, x)
        y_min = min(y_min, y)
        y_max = max(y_max, y)
    ans = min(ans, (x_max-x_min)*(y_max-y_min))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline


def main():
    n, k = map(int, input().split())
    X, Y = [], []
    for _ in range(n):
        x, y = map(int, input().split())
        X.append(x)
        Y.append(y)
    x_min, x_max = min(X), max(X)
    y_min, y_max = min(Y), max(Y)
    res = abs(x_max - x_min) * abs(y_max - y_min)

    for x1 in range(n):
        for x2 in range(n):
            for y1 in range(n):
                for y2 in range(n):
                    lx, rx = X[x1], X[x2]
                    by, uy = Y[y1], Y[y2]
                    cnt = 0
                    for i in range(n):
                        if lx <= X[i] <= rx and by <= Y[i] <= uy:
                            cnt += 1
                    if cnt >= k:
                        res = min(res, abs(rx - lx) * abs(uy - by))
    print(res)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    n, k = map(int, input().split())
    X, Y = [], []
    for _ in range(n):
        x, y = map(int, input().split())
        X.append(x)
        Y.append(y)
    x_min, x_max = min(X), max(X)
    y_min, y_max = min(Y), max(Y)
    res = abs(x_max - x_min) * abs(y_max - y_min)

    for x1 in range(n):
        for x2 in range(n):
            for y1 in range(n):
                for y2 in range(n):
                    lx, rx = X[x1], X[x2]
                    by, uy = Y[y1], Y[y2]
                    cnt = 0
                    for i in range(n):
                        if lx <= X[i] <= rx and by <= Y[i] <= uy:
                            cnt += 1
                    if cnt >= k:
                        res = min(res, abs(rx - lx) * abs(uy - by))
    print(res)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    from itertools import combinations

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

    res = []
    for pattern in combinations(range(n), k):
        p_x = []
        p_y = []
        for i in pattern:
            x, y = xy[i]
            p_x.append(x)
            p_y.append(y)
        s = abs(max(p_x) - min(p_x)) * abs(max(p_y) - min(p_y))
        res.append(s)

    print(min(res))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
import bisect
N, K = map(int, input().split())
xy = [tuple(map(int, input().split())) for i in range(N)]
xy.sort(key=lambda x: x[0])
X = [x[0] for x in xy]

ans = 40**18
for a, b in combinations(range(N), 2):
    A, B = max(xy[a][0], xy[b][0]), min(xy[a][0], xy[b][0])
    r = bisect.bisect_right(X, A)
    l = bisect.bisect_left(X, B)
    for c, d in combinations(range(N), 2):
        tmp = 0
        C, D = max(xy[c][1], xy[d][1]), min(xy[c][1], xy[d][1])

        for i in range(l, r):
            if xy[i][1] <= C and xy[i][1] >= D:
                tmp += 1
        #     print(xy[i][1], C, D)

        if tmp >= K and ans > (A-B) * (C - D):
            ans = (A-B) * (C - D)

print(ans)

Submission status: Time Limit Exceeded

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

def is_ok(l,r,d,u):
    k = 0
    for x,y in XY:
        if l <= x <= r and d <= y <= u:
            k += 1
            if k >= K:
                return True
    return False

ans = float('inf')
for i in range(N-1):
    for j in range(i+1,N):
        for k in range(N-1):
            for l in range(k+1,N):
                l,r,d,u = xs[i],xs[j],ys[k],ys[l]
                if (r-l)*(u-d) >= ans: continue
                if is_ok(l,r,d,u):
                    ans = (r-l)*(u-d)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations

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

ans = 10**20
for rect in combinations(XY, r=min(K, 4)):
    X = [x for x, _ in rect]
    Y = [y for _, y in rect]

    miX, mxX = min(X), max(X)
    miY, mxY = min(Y), max(Y)

    cnt = len([x for x, y in XY if miY <= y <= mxY and miX <= x <= mxX])
    if cnt >= K:
        ans = min(ans, (mxX - miX) * (mxY - miY))
print(ans)

Submission status: Time Limit Exceeded

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

ans = float('inf')
for xi in range(N - 1):
    for xj in range(xi + 1, N):
        for yi in range(N - 1):
            for yj in range(yi + 1, N):
                x1 = min([P[xi][0], P[xj][0], P[yi][0], P[yj][0]])
                x2 = max([P[xi][0], P[xj][0], P[yi][0], P[yj][0]])
                y1 = min([P[xi][1], P[xj][1], P[yi][1], P[yj][1]])
                y2 = max([P[xi][1], P[xj][1], P[yi][1], P[yj][1]])
                if x1 == x2 or y1 == y2:
                    continue

                cnt = 0
                for k in range(N):
                    x3, y3 = P[k]
                    if x1 <= x3 <= x2 and y1 <= y3 <= y2:
                        cnt += 1
                if cnt >= K:
                    ans = min(ans, (x2 - x1) * (y2 - y1))

print(ans)

Submission status: Time Limit Exceeded

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

ans = 10 ** 20

for i in range(n):
    for j in range(i+1, n):
        for ii in range(n):
            for jj in range(ii+1, n):
                l = min(xy[i][0], xy[j][0])
                r = max(xy[i][0], xy[j][0])
                d = min(xy[ii][1], xy[jj][1])
                u = max(xy[ii][1], xy[jj][1])
                cnt = 0
                for x,y in xy:
                    if l <= x <= r and d <= y <= u:
                        cnt += 1
                if cnt >= k:
                    ans = min(ans, (r-l) * (u - d))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split())
l = [list(map(int,input().split())) for i in range(n)]
l.sort()
ans = float("INF")

for i in range(n-k+1):
    for j in range(i+1,n):
        for s in range(n):
            for m in range(n):
                wl = l[i][0]
                wh = l[j][0]
                hl = min(l[s][1],l[m][1])
                hh = max(l[s][1],l[m][1])
                count = 0
                for w,h in l:
                    if wl <= w <= wh and hl <= h <= hh:
                        count += 1
                if count >= k:
                    ans = min(ans,(hh-hl)*(wh-wl))
print(ans)

Submission status: Time Limit Exceeded

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()
ans=float('inf')
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: Time Limit Exceeded

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

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