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 = list(list(map(int,input().split()))for i in range(N))

ans = float('inf')

for i in range(N):
    lx = XY[i][0]
    for j in range(N):
        rx = XY[j][0]
        for k in range(N):
            dy = XY[k][1]
            for l in range(N):
                uy = XY[l][1]
                hoge = 0
                for x,y in XY:
                    if lx <= x and rx >= x and uy >= y and dy <= y:
                        hoge += 1
                if hoge >= K:
                    ans = min(ans,(rx-lx)*(uy-dy))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
INF = float("inf")


def solve(N: int, K: int, x: "List[int]", y: "List[int]"):
    sx = sorted(x)
    sy = sorted(y)
    acc = [[0]*N for _ in range(N)]

    for i, x1 in enumerate(sx):
        for j, y1 in enumerate(sy):
            acc[i][j] = sum([True for xx, yy in zip(x, y)
                             if xx <= x1 and yy <= y1])

    m = INF

    for i, x1 in enumerate(sx[:-K+1]):
        for j, y1 in enumerate(sy[:-K+1]):
            # 始点を固定
            for x2 in sx[i+1:]:
                for y2 in sy[j+1:]:
                    # 終点を固定
                    counter = 0
                    for xx, yy in zip(x, y):
                        if (x1 <= xx <= x2) and (y1 <= yy <= y2):
                            counter += 1
                    if counter >= K:
                        flag = True
                        area = abs((y2-y1)*(x2-x1))
                        if area < m:
                            m = area
                        break   # これ以上yをあげたところで面積は増える一方なので抜ける
    print(m)
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    x = [int()] * (N)  # type: "List[int]"
    y = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        x[i] = int(next(tokens))
        y[i] = int(next(tokens))
    solve(N, K, x, y)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
INF = float("inf")


def solve(N: int, K: int, x: "List[int]", y: "List[int]"):
    sx = sorted(x)
    sy = sorted(y)
    acc = [[0]*N for _ in range(N)]

    for i, x1 in enumerate(sx):
        for j, y1 in enumerate(sy):
            acc[i][j] = sum([True for xx, yy in zip(x, y)
                             if xx <= x1 and yy <= y1])

    m = INF

    for i, x1 in enumerate(sx):
        for j, y1 in enumerate(sy):
            # 始点を固定
            for x2 in sx[i+1:]:
                for y2 in sy[j+1:]:
                    # 終点を固定
                    counter = 0
                    for xx, yy in zip(x, y):
                        if (x1 <= xx <= x2) and (y1 <= yy <= y2):
                            counter += 1
                    if counter >= K:
                        flag = True
                        area = abs((y2-y1)*(x2-x1))
                        if area < m:
                            m = area
                        break   # これ以上yをあげたところで面積は増える一方なので抜ける
    print(m)
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    x = [int()] * (N)  # type: "List[int]"
    y = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        x[i] = int(next(tokens))
        y[i] = int(next(tokens))
    solve(N, K, x, y)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
INF = float("inf")


def solve(N: int, K: int, x: "List[int]", y: "List[int]"):
    sx = sorted(x)
    sy = sorted(y)

    m = INF
    for i, x1 in enumerate(sx):
        for j, y1 in enumerate(sy):
            # 始点を固定
            for x2 in sx[i:]:
                for y2 in sy[j:]:
                    # 終点を固定
                    counter = 0
                    for xx, yy in zip(x, y):
                        if (x1 <= xx <= x2) and (y1 <= yy <= y2):
                            counter += 1
                    if counter >= K:
                        area = abs((y2-y1)*(x2-x1))
                        if area < m:
                            m = area
    print(m)
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    x = [int()] * (N)  # type: "List[int]"
    y = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        x[i] = int(next(tokens))
        y[i] = int(next(tokens))
    solve(N, K, x, y)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

if __name__ == '__main__':
    N, K = map(int, input().split())
    xy_list = [list(map(int, input().split())) for i in range(N)]

    all_x = sorted(list(set([xy[0] for xy in xy_list])))
    all_y = sorted(list(set([xy[1] for xy in xy_list])))

    answer = sys.maxsize
    for i in range(len(all_x)):
        x1 = all_x[i]
        for j in range(i+1, len(all_x)):
            x2 = all_x[j]
            for k in range(len(all_y)):
                y1 = all_y[k]
                for l in range(k+1, len(all_y)):
                    y2 = all_y[l]
                    if answer > (x2-x1) * (y2-y1) and K <= sum(map(lambda xy: (x1 <= xy[0] <= x2) and (y1 <= xy[1] <= y2), xy_list)):
                        answer = (x2-x1) * (y2-y1)

    print(answer)

Submission status: Time Limit Exceeded

Solution code:
import sys

if __name__ == '__main__':
    N, K = map(int, input().split())
    xy_list = [list(map(int, input().split())) for i in range(N)]

    all_x = sorted(list(set([xy[0] for xy in xy_list])))
    all_y = sorted(list(set([xy[1] for xy in xy_list])))

    answer = sys.maxsize
    for i in range(len(all_x)):
        x1 = all_x[i]
        for j in range(i+1, len(all_x)):
            x2 = all_x[j]
            for k in range(len(all_y)):
                y1 = all_y[k]
                for l in range(k+1, len(all_y)):
                    y2 = all_y[l]
                    if answer > (x2-x1) * (y2-y1) and K <= len([xy for xy in xy_list if (x1 <= xy[0] <= x2) and (y1 <= xy[1] <= y2)]):
                        answer = (x2-x1) * (y2-y1)

    print(answer)

Submission status: Time Limit Exceeded

Solution code:
import sys

if __name__ == '__main__':
    N, K = map(int, input().split())
    xy_list = [list(map(int, input().split())) for i in range(N)]

    all_x = sorted(list(set([xy[0] for xy in xy_list])))
    all_y = sorted(list(set([xy[1] for xy in xy_list])))

    answer = sys.maxsize
    for i in range(len(all_x)):
        x1 = all_x[i]
        for j in range(i+1, len(all_x)):
            x2 = all_x[j]
            for k in range(len(all_y)):
                y1 = all_y[k]
                for l in range(k+1, len(all_y)):
                    y2 = all_y[l]
                    if K <= len([xy for xy in xy_list if (x1 <= xy[0] <= x2) and (y1 <= xy[1] <= y2)]) and answer > (x2-x1) * (y2-y1):
                        answer = (x2-x1) * (y2-y1)

    print(answer)

Submission status: Time Limit Exceeded

Solution code:
import sys

if __name__ == '__main__':
    N, K = map(int, input().split())
    xy_list = [list(map(int, input().split())) for i in range(N)]

    all_x = sorted(list(set([xy[0] for xy in xy_list])))
    all_y = sorted(list(set([xy[1] for xy in xy_list])))

    answer = sys.maxsize
    for x1 in all_x:
        for x2 in [x2 for x2 in all_x if x2 > x1]:
            for y1 in all_y:
                for y2 in [y2 for y2 in all_y if y2 > y1]:
                    if K <= len([xy for xy in xy_list if (x1 <= xy[0] <= x2) and (y1 <= xy[1] <= y2)]) and answer > (x2-x1) * (y2-y1):
                        answer = (x2-x1) * (y2-y1)

    print(answer)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
xy = []
for i in range(n):
    xy.append(list(map(int, input().split())))
s = []
x = [xy[i][0] for i in range(n)]
y = [xy[i][1] for i in range(n)]
x.sort()
y.sort()
for i in range(n):
    for j in range(n):
        for l in range(i + 1, n):
            x1 = x[i]
            y1 = y[j]
            x2 = x[l]
            y2 = j - 1
            count = 0
            while count < k:
                y2 += 1
                if y2 >= n:
                    break
                for m in range(n):
                    if y[y2] == y1:
                        if x1 <= xy[m][0] <= x2 and xy[m][1] == y1:
                            count += 1
                    elif x1 <= xy[m][0] <= x2 and y[y2 - 1] < xy[m][1] <= y[y2]:
                        count += 1
            else:
                s.append((x2 - x1) * (y[y2] - y1))
print(min(s))

Submission status: Time Limit Exceeded

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


import itertools
ans = float("inf")

for xx in itertools.combinations(x,2):
    for yy in itertools.combinations(y,2):

        num = 0
        for i in range(N):
            if l[i][0] >= min(xx) and l[i][0] <= max(xx) and l[i][1] >= min(yy) and l[i][1] <= max(yy):
                num += 1

        if K > num:
            continue

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

Submission status: Time Limit Exceeded

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

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

import itertools
ans = float("inf")

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

    if x[xai] > x[xbi]:
        continue

    if abs(x[xai] - x[xbi]) + 1 < K:
        continue

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

        if y[yai] > y[ybi]:
            continue

        if abs(y[yai] - y[ybi]) + 1 < K:
            continue

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

        if K > num:
            continue

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

Submission status: Time Limit Exceeded

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

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

import itertools
ans = float("inf")

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

    if x[xai] > x[xbi]:
        continue

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

        if y[yai] > y[ybi]:
            continue

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

        if K > num:
            continue

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

Submission status: Time Limit Exceeded

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

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

import itertools
ans = float("inf")

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

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

        if x[xai] > x[xbi] and y[yai] > y[ybi]:
            continue

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

        if K > num:
            continue

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

Submission status: Time Limit Exceeded

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

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

import itertools
ans = float("inf")

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

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

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

        if K > num:
            continue

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

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
xy=[]
x=[]
y=[]
ans=10**100
for i in range(n):
    tmp=[int(j) for j in input().split()]
    xy.append(tmp)
    x.append(tmp[0])
    y.append(tmp[1])

import itertools
for xx in itertools.combinations(x,2):
    for yy in itertools.combinations(y,2):
        p=0
        for i,j in xy:
            if min(xx)<=i and i<=max(xx) and min(yy)<=j and j<=max(yy):
                p+=1
        if p==k:
            ans=min(ans,(max(xx)-min(xx))*(max(yy)-min(yy)))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations

N, K = map(int, input().split())
coord = [tuple(map(int, input().split())) for _ in range(N)]
ans = float('inf')
for points in combinations(coord, K):
    x_coords, y_coords = [x for x, _ in points], [y for _, y in points]
    x_min, x_max, y_min, y_max = min(x_coords), max(x_coords), min(y_coords), max(y_coords)
    cand = (x_max - x_min)*(y_max - y_min)
    inside = 0
    for p in coord:
        inside += 1 if p[0] in range(x_min, x_max+1) and p[1] in range(y_min, y_max+1) else 0
        if inside == K:
            break
    else:
        continue
    ans = min(ans, cand)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
x, y = zip(*((map(int, input().split())) for _ in range(N)))

area_min = 10 ** 20
for i1 in range(N):
    for i2 in range(i1 + 1, N):
        for j1 in range(N):
            for j2 in range(j1 + 1, N):
                x1 = min(x[i1], x[i2])
                x2 = max(x[i1], x[i2])
                y1 = min(y[j1], y[j2])
                y2 = max(y[j1], y[j2])
                count_interior = 0
                for k in range(N):
                    if x1 <= x[k] and x[k] <= x2 and y1 <= y[k] and y[k] <= y2:
                        count_interior += 1
                if count_interior >= K:
                    area = (x2 - x1) * (y2 - y1)
                    area_min = min(area_min, area)
print(area_min)

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

Solution code:
n,c=map(int,input().split())
xpos=[]
ypos=[]
pos=[]
for _ in range(n):
  x,y=map(int,input().split())
  xpos.append(x)
  ypos.append(y)
  pos.append([x,y])
xpos=sorted(xpos)
ypos=sorted(ypos)
ans=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):
        lx,rx=xpos[i],xpos[j]
        ly,ry=ypos[k],ypos[l]
        cnt=0
        for tx,ty in pos:
          if lx<=tx<=rx and ly<=ty<=ry:
            cnt+=1
        if cnt>=c:
          ans=min(ans,(rx-lx)*(ry-ly))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,c=map(int,input().split())
pos=[list(map(int,input().split())) for _ in range(n)]
if c==2:
  ans=10**20
  for i in range(n):
    x1,y1=pos[i]
    for j in range(i+1,n):
      x2,y2=pos[j]
      w=abs(x1-x2)
      h=abs(y1-y2)
      ans=min(ans,w*h)
  print(ans)
elif c==3:
  ans=10**20
  for i in range(n):
    x1,y1=pos[i]
    for j in range(i+1,n):
      x2,y2=pos[j]
      for k in range(j+1,n):
        x3,y3=pos[k]
        rx1,rx2=min(x1,x2,x3),max(x1,x2,x3)
        ry1,ry2=min(y1,y2,y3),max(y1,y2,y3)
        cnt=0
        for l in range(n):
          if rx1<=pos[l][0]<=rx2 and ry1<=pos[l][1]<=ry2:
            cnt+=1
        if cnt>=c:
          w=abs(rx1-rx2)
          h=abs(ry1-ry2)
          ans=min(ans,w*h)
  print(ans)
else:
  ans=10**20
  for i in range(n):
    x1,y1=pos[i]
    for j in range(i+1,n):
      x2,y2=pos[j]
      for k in range(j+1,n):
        x3,y3=pos[k]
        for l in range(k+1,n):
          x4,y4=pos[l]
          rx1,rx2=min(x1,x2,x3,x4),max(x1,x2,x3,x4)
          ry1,ry2=min(y1,y2,y3,y4),max(y1,y2,y3,y4)
          cnt=0
          for l in range(n):
            if rx1<=pos[l][0]<=rx2 and ry1<=pos[l][1]<=ry2:
              cnt+=1
          if cnt>=c:
            w=abs(rx1-rx2)
            h=abs(ry1-ry2)
            ans=min(ans,w*h)
  print(ans)

Submission status: Time Limit Exceeded

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

    ans = float('INF')
    for l in range(N):
        for r in range(l + 1, N):
            for d in range(N):
                for t in range(d + 1, N):
                    lx = X[l]
                    rx = X[r]
                    ty = Y[t]
                    dy = Y[d]
                    c = 0
                    for x, y in XY:
                        if lx <= x <= rx and dy <= y <= ty:
                            c += 1
                    if c >= K:
                        ans = min(ans, abs(rx - lx) * abs(ty - dy))
    print(ans)


main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    N, K = map(int, input().split())
    X = []
    Y = []
    XY = []
    for _ in range(N):
        x, y = map(int, input().split())
        X.append(x)
        Y.append(y)
        XY.append((x, y))
    X.sort()
    Y.sort()
    ans = float('INF')
    for l in range(N):
        for r in range(N):
            for t in range(N):
                for d in range(N):
                    lx = X[l]
                    rx = X[r]
                    ty = Y[t]
                    dy = Y[d]
                    c = 0
                    for x, y in XY:
                        if lx <= x <= rx and dy <= y <= ty:
                            c += 1
                    if c >= K:
                        ans = min(ans, abs(rx - lx) * abs(ty - dy))
    print(ans)


main()

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())

xys = {}
xs = []
ys = []
for i in range(n):
  x, y = map(int, input().split())
  xys[i] = (x, y)
  xs.append(x)
  ys.append(y)
xs = sorted(xs)
ys = sorted(ys)
min_area = float('inf')

for li in range(n):
  for ri in range(li+1, n):
    left = xs[li]
    right = xs[ri]
    for bi in range(n):
      for ti in range(bi+1, n):
        bottom = ys[bi]
        top = ys[ti]
        area = (top - bottom) * (right - left)
        cnt = 0
        for i in range(n):
          xi, yi = xys[i]
          if (left <= xi <= right) and (bottom <= yi <= top):
            cnt += 1
            if cnt >= k:
              break
        if cnt >= k:
          min_area = min([min_area, area])

print(min_area)

Submission status: Time Limit Exceeded

Solution code:
import itertools
from functools import lru_cache

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

XY = [[int(x) for x in input().split()] for _ in range(N)]
XY.sort()
X,Y = zip(*XY)

@lru_cache(None)
def cnt(x,y):
  c = 0
  for x1,y1 in XY:
    if x1 > x:
      break
    if y1 <= y:
      c += 1
  return c

min_area = 5*10**18

for x1,x2 in itertools.combinations(X,2):
  for y1,y2 in itertools.combinations(Y,2):
    if y1 > y2:
      y1,y2 = y2,y1
    area = (x2-x1) * (y2-y1)
    if area > min_area:
      continue
    
    c = cnt(x2,y2) - cnt(x2,y1-1) - cnt(x1-1,y2) + cnt(x1-1,y1-1)
    if c < K:
      continue
      
    min_area = area
    
print(min_area)

Submission status: Time Limit Exceeded

Solution code:
import itertools
from functools import lru_cache

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

XY = [[int(x) for x in input().split()] for _ in range(N)]
X,Y = zip(*XY)

@lru_cache(None)
def cnt(x,y):
  c = 0
  for x1,y1 in XY:
    if x1 <= x and y1 <= y:
      c += 1
  return c

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
    
    c = cnt(x2,y2) - cnt(x2,y1-1) - cnt(x1-1,y2) + cnt(x1-1,y1-1)
    if c < K:
      continue
      
    min_area = area
    
print(min_area)

Submission status: Time Limit Exceeded

Solution code:
import sys
import itertools

N,K=map(int, sys.stdin.readline().split())
X=[]
Y=[]
XY=[]

for _ in range(N):
	x,y=map(int, sys.stdin.readline().split())
	X.append(x)
	Y.append(y)
	XY.append( (x,y) )
X.sort()
Y.sort()

L=list( itertools.product(X,Y ) )

ans=float("inf")

for x1,y1 in L:
	for x2,y2 in L:
		cnt=0
		for x, y in XY:
			if x1<=x<=x2 and y1<=y<=y2:
				cnt+=1
	
		menseki=abs(x1-x2)*abs(y1-y2)
		if K<=cnt:
			ans=min(ans, menseki)

print ans

Submission status: Time Limit Exceeded

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

X = sorted(list(set([x for x,y in XY])))
Y = sorted(list(set([y for x,y in XY])))

from itertools import combinations

ans = 10**19
for xl,xu in combinations(X,2):
  for yl,yu in combinations(Y,2):
    if sum([xl<=x<=xu and yl<=y<=yu for x,y in XY])>=K:
      ans = min(ans, (xu-xl)*(yu-yl))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
N,K=map(int,input().split())

xs = set()
ys = set()
inl = []

for i in range(N):
    x,y=map(int,input().split())
    inl.append((x,y))
    xs.add(x)
    ys.add(y)

xs = list(xs)
ys = list(ys)
xs.sort()
ys.sort()

res = 9223372036854775807
for xlow, xhi in combinations(xs,2):
    for ylow, yhi in combinations(ys,2):
        cnt = 0
        for x, y in inl:
            cnt += (x >= xlow and x <= xhi and y >= ylow and y <= yhi)
        if cnt == K:
            res = min(res,(xhi - xlow) * (yhi - ylow))
print(res)

Submission status: Time Limit Exceeded

Solution code:
from itertools import* #permutations("AB",repeat=2) combinations("AB",2) product("AB",2) groupby accumulate
import sys
#input=sys.stdin.readline  #危険！基本オフにしろ！
sys.setrecursionlimit(10**6)



def main():
    n,k=map(int,input().split())
    grid=[tuple(map(int,input().split()))for i in range(n)]
    x=set(s for s,t in grid)
    y=set(t for s,t in grid)
    ans=[]
    for i in combinations(x,2):
        for j in combinations(y,2):
            xx=max(i)
            xxx=min(i)
            yy=max(j)
            yyy=min(j)
            if sum(xxx<=s<=xx and yyy<=t<=yy for s,t in grid)>=k:
                ans.append(abs((yy-yyy)*(xx-xxx)))
    print(min(ans))
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#from numpy import*
#from scipy import*
from collections import* #defaultdict Counter deque appendleft
from fractions import gcd
from functools import* #reduce
from itertools import* #permutations("AB",repeat=2) combinations("AB",2) product("AB",2) groupby accumulate
from operator import mul
from bisect import* #bisect_left bisect_right
from heapq import* #heapify heappop heappushpop
from math import factorial,pi
from copy import deepcopy
import sys
#input=sys.stdin.readline  #危険！基本オフにしろ！
sys.setrecursionlimit(10**6)



def main():
    n,k=map(int,input().split())
    grid=[list(map(int,input().split()))for i in range(n)]
    x=set(s for s,t in grid)
    y=set(t for s,t in grid)
#    print(x,y)
    ans=[]
    for i in combinations(x,2):
        for j in combinations(y,2):
            xx=max(i)
            xxx=min(i)
            yy=max(j)
            yyy=min(j)
#            print(xx,xxx,yy,yyy)
            if sum(xxx<=s<=xx and yyy<=t<=yy for s,t in grid)>=k:
                ans.append(abs((yy-yyy)*(xx-xxx)))
    print(min(ans))
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
l=[list(map(int,input().split())) for i in range(n)]
x=[l[i][0] for i in range(n)]
y=[l[i][1] for i in range(n)]
ans=[]
for i1 in range(n):
  for i2 in range(i1+1,n):
    for i3 in range(n):
      for i4 in range(i3+1,n):
        ct=0
        for i5 in range(n):
          if min(x[i1],x[i2])<=l[i5][0]<=max(x[i1],x[i2]) and min(y[i3],y[i4])<=l[i5][1]<=max(y[i3],y[i4]):ct+=1
        if ct>=k:
          ans.append(abs(x[i1]-x[i2])*abs(y[i3]-y[i4]))
print(min(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)]
x=[l[i][0] for i in range(n)]
x.sort()
y=[l[i][1] for i in range(n)]
y.sort()
ans=[]
for i1 in range(n):
  for i2 in range(i1,n):
    for i3 in range(n):
      for i4 in range(i3,n):
        ct=0
        for i5 in range(n):
          if min(x[i1],x[i2])<=l[i5][0]<=max(x[i1],x[i2]) and min(y[i3],y[i4])<=l[i5][1]<=max(y[i3],y[i4]):ct+=1
        if ct>=k:
          ans.append(abs(x[i1]-x[i2])*abs(y[i3]-y[i4]))
print(min(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)]
x=[l[i][0] for i in range(n)]
x.sort()
y=[l[i][1] for i in range(n)]
y.sort()
ans=[]
for i1 in range(n):
  for i2 in range(n):
    for i3 in range(n):
      for i4 in range(n):
        ct=0
        for i5 in range(n):
          if min(x[i1],x[i2])<=l[i5][0]<=max(x[i1],x[i2]) and min(y[i3],y[i4])<=l[i5][1]<=max(y[i3],y[i4]):ct+=1
        if ct>=k:
          ans.append(abs(x[i1]-x[i2])*abs(y[i3]-y[i4]))
print(min(ans))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

ans = float("inf")

for a in L :
    left = a[1]
    for b in L :
        right = b[1]
        for c in L :
            ceil = c[0]
            for d in L :
                floor = d[0]
                
                cnt = 0
                for y,x in L :
                    if (left <= x <= right) and (floor <= y <= ceil) :
                        cnt += 1
                
                if cnt >= K :
                    square = (right - left) * (ceil - floor)
                    ans = min(ans, square)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
import sys

import numpy as np

sys.setrecursionlimit(10000)
INF = float('inf')

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

X = XY[:, 0]
Y = XY[:, 1]
X = X[Y.argsort()]
Y = Y[Y.argsort()]

ans = INF
for xi, xj in itertools.combinations(range(N), r=2):
    L, r = min(X[xi], X[xj]), max(X[xi], X[xj])
    xconds = (L <= X) & (X <= r)

    yi = 0
    yj = 1
    while yj < N:
        b, u = min(Y[yi], Y[yj]), max(Y[yi], Y[yj])
        count = np.sum(xconds & (b <= Y) & (Y <= u))
        if count >= K:
            ans = min(ans, (r - L) * (u - b))
            yi += 1
        else:
            yj += 1
        if yi == yj:
            yj += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
import sys

import numpy as np

sys.setrecursionlimit(10000)
INF = float('inf')

N, K = list(map(int, input().split()))
XY = np.array([list(map(int, input().split())) for _ in range(N)])
X = XY[:, 0]
Y = XY[:, 1]

ans = INF
for xi, xj in itertools.combinations(range(N), r=2):
    for yi, yj in itertools.combinations(range(N), r=2):
        L, r = min(X[xi], X[xj]), max(X[xi], X[xj])
        b, u = min(Y[yi], Y[yj]), max(Y[yi], Y[yj])
        count = np.sum((L <= X) & (X <= r) & (b <= Y) & (Y <= u))
        if count >= K:
            ans = min(ans, (r - L) * (u - b))
print(ans)