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:
def countInside(x1, y1, x2, y2, XY):
    minX = min(x1, x2)
    maxX = max(x1, x2)
    minY = min(y1, y2)
    maxY = max(y1, y2)
    ret = 0
    for x, y in XY:
        if minX <= x and x <= maxX and minY <= y and y <= maxY:
            ret += 1
    return ret


N, K = [int(x) for x in input().split()]

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

X = list(X)
Y = list(Y)
X.sort()
Y.sort()

import itertools
XY2 = list(itertools.product(X, Y))

ans = float("inf")

for i in range(len(XY2)):
    for j in range(len(XY2)):
        if i > j:
            x1, y1 = XY2[i][0], XY2[i][1]
            x2, y2 = XY2[j][0], XY2[j][1]
            if K <= countInside(x1, y1, x2, y2, XY):
                area = abs(x1 - x2) * abs(y1 - y2)
                ans = min(area, ans)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def countInside(x1, y1, x2, y2, XY):
    minX = min(x1, x2)
    maxX = max(x1, x2)
    minY = min(y1, y2)
    maxY = max(y1, y2)
    ret = 0
    for x, y in XY:
        if minX <= x and x <= maxX and minY <= y and y <= maxY:
            ret += 1
    return ret


N, K = [int(x) for x in input().split()]

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

X = list(X)
Y = list(Y)
X.sort()
Y.sort()

import itertools
XY2 = list(itertools.product(X, Y))

ans = float("inf")

for i in range(len(XY2)):
    for j in range(len(XY2)):
        if i > j:
            x1, y1 = XY2[i][0], XY2[i][1]
            x2, y2 = XY2[j][0], XY2[j][1]
            if K == countInside(x1, y1, x2, y2, XY):
                area = abs(x1 - x2) * abs(y1 - y2)
                ans = min(area, ans)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

"""
参考：https://img.atcoder.jp/abc075/editorial.pdf
・自力ACしたのがO(N^4)でこれはO(N^5)の愚直解
・制約からして何とかなりそうだし、こっちのが実装全然軽いし実戦向きぽいね。
"""

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

X, Y = [0]*N, [0]*N
for i in range(N):
    X[i], Y[i] = map(int, input().split())

X2 = sorted(set(X))
Y2 = sorted(set(Y))

ans = float('inf')
# 可能性のある全長方形ループ
for x1 in X2:
    for y1 in Y2:
        for x2 in X2:
            for y2 in Y2:
                cnt = 0
                # 各頂点ループで範囲内にあるか1つずつ確認する
                for i in range(N):
                    if x1 <= X[i] <= x2 and y1 <= Y[i] <= y2:
                        cnt += 1
                if cnt >= K:
                    ans = min((x2 - x1) * (y2 - y1), ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left
N, K = map(int, input().split())
Points = []
X, Y = [], []
for i in range(N):
    x, y = map(int, input().split())
    Points.append([x, y])
    X.append(x)
    Y.append(y)

# 座標圧縮
X.sort()
Y.sort()
Points_compressed = []
for x, y in Points:
    cx, cy = bisect_left(X, x), bisect_left(Y, y)
    Points_compressed.append([cx, cy])


class Ruisekiwa2D:
    def __init__(self, h, w):
        self.H = h
        self.W = w
        self.G = [[0] * w for _ in range(h)]

    def load(self, points):
        # 問題によってイメージしやすいよう書き換えてください
        for x, y in points:
            self.G[x][y] += 1

    def load_imos(self, points):
        # pointsは[[左上h, 左上w, 右下h, 右下w], ...]であること
        for i1, j1, i2, j2 in points:
            self.G[i1][j1] += 1  # 左上
            if j2 + 1 < self.W:  # 右上
                self.G[i1][j2+1] -= 1
            if i2 + 1 < self.H:
                self.G[i2+1][j1] -= 1  # 左下
            if j2 + 1 < self.W and i2 + 1 < self.H:  # 右下
                self.G[i2+1][j2+1] += 1

    def calc(self):
        for y in range(self.W):
            for x in range(1, self.H):
                self.G[x][y] += self.G[x-1][y]

        for y in range(1, self.W):
            for x in range(self.H):
                self.G[x][y] += self.G[x][y-1]

    def get(self, i1, j1, i2, j2):
        if i1 > i2 or j1 > j2 or i1 < 0 or j1 < 0 or i2 < 0 or j2 < 0:
            return 0
        elif i1 > 0 and j1 > 0:
            return self.G[i2][j2] - self.G[i1-1][j2] - self.G[i2][j1-1] + self.G[i1-1][j1-1]
        elif i1 <= 0 < j1:
            return self.G[i2][j2] - self.G[i2][j1-1]
        elif j1 <= 0 < i1:
            return self.G[i2][j2] - self.G[i1 - 1][j2]
        else:
            return self.G[i2][j2]


# 二次元累積和
R2D = Ruisekiwa2D(N, N)
R2D.load(Points_compressed)
R2D.calc()


ans = float('inf')
for yi in range(N):
    for yj in range(N):
        for xi in range(N):
            for xj in range(N):
                cx1, cx2 = Points_compressed[xi][0], Points_compressed[xj][0]
                cy1, cy2 = Points_compressed[yi][1], Points_compressed[yj][1]

                x1, x2 = Points[xi][0], Points[xj][0]
                y1, y2 = Points[yi][1], Points[yj][1]

                # 二次元累積和で高速に長方形内部に含まれる点の数を数える
                inside = R2D.get(cx1, cy1, cx2, cy2)
                if inside >= K:
                    ans = min(ans,  abs(x2 - x1) * abs(y2 - y1))

print(ans)

Submission status: Time Limit Exceeded

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

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

    print(ans)


main()

Submission status: Time Limit Exceeded

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

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

    print(ans)


main()

Submission status: Time Limit Exceeded

Solution code:
import itertools

n, k = map(int, input().split())
xy = [tuple(map(int, input().split())) for i in range(n)]
ans = float("INF")
for a, b in itertools.combinations(xy, 2):
    for c, d in itertools.combinations(xy, 2):
        x1, x2 = sorted([a[0], b[0]])
        y1, y2 = sorted([c[1], d[1]])
        count = 0
        for x, y in xy:
            if x1 <= x <= x2 and y1 <= y <= y2:
                count += 1
        if count >= k:
            ans = min(ans, (x2 - x1) * (y2 - y1))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools

n, k = map(int, input().split())
xy = [tuple(map(int, input().split())) for i in range(n)]
ans = float("INF")
for a, b in itertools.combinations(xy, 2):
    for c, d in itertools.combinations(xy, 2):
        x1, x2 = a[0], b[0]
        y1, y2 = c[1], d[1]
        count = 0
        for x, y in xy:
            if min(x1, x2) <= x <= max(x1, x2) and min(y1, y2) <= y <= max(y1, y2):
                count += 1
        if count >= k:
            ans = min(ans, abs(x1 - x2) * abs(y1 - y2))
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)]
ans = float("INF")
for x1, _ in xy:
    for x2, _ in xy:
        for _, y1 in xy:
            for _, y2 in xy:
                count = 0
                for x, y in xy:
                    if min(x1, x2) <= x <= max(x1, x2) and min(y1, y2) <= y <= max(y1, y2):
                        count += 1
                if count >= k:
                    ans = min(ans, abs(x1 - x2) * abs(y1 - y2))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
N, K = [int(_) for _ in input().split()]
XY = [[int(_) for _ in input().split()] for _ in range(N)]
X, Y = sorted([x for x, y in XY]), sorted([y for x, y in XY])
ans = float('inf')
for x1, x2 in itertools.combinations(X, 2):
    for y1, y2 in itertools.combinations(Y, 2):
        k = sum([x1 <= XY[i][0] <= x2 and y1 <= XY[i][1] <= y2 for i in range(N)])
        if k >= K:
            ans = min(ans, (x2 - x1) * (y2 - y1))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
N, K = [int(_) for _ in input().split()]
X = [0] * N
Y = [0] * N
for i in range(N):
    X[i], Y[i] = [int(_) for _ in input().split()]
ans = float('inf')
for x1, x2 in itertools.combinations(X, 2):
    if x1 > x2:
        x1, x2 = x2, x1
    for y1, y2 in itertools.combinations(Y, 2):
        if y1 > y2:
            y1, y2 = y2, y1
        k = sum([x1 <= X[i] <= x2 and y1 <= Y[i] <= y2 for i in range(N)])
        if k >= K:
            ans = min(ans, (x2 - x1) * (y2 - y1))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from collections import defaultdict
from pprint import pprint as pp
import itertools

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

rui = defaultdict(lambda: defaultdict(int))
sumnum = defaultdict(lambda: defaultdict(int))

for x,y in xy:
    rui[x][y] += 1

xlist = list(sorted(rui.keys()))
ylist = []
for x in xlist:
    ylist.extend(list(rui[x].keys()))
ylist = sorted(list(set(ylist)))

for x in xlist:
    tmp = 0
    for y in ylist:
        tmp += rui[x][y]
        sumnum[x][y] = tmp

for y in ylist:
    tmp = 0
    for x in xlist:
        tmp += sumnum[x][y]
        sumnum[x][y] = tmp

xdict = {v: i for i, v in enumerate(xlist)}
ydict = {v: i for i, v in enumerate(ylist)}

sqmin = -1
for x1, y1 in itertools.product(xlist[:-1], ylist[:-1]):
    for x2, y2 in itertools.product(xlist[1:], ylist[1:]):
        if x1 < x2 and y1 < y2:
            if xdict[x1] - 1 < 0:
                xb = (10**9 + 1)*(-1)
            else:
                xb = xlist[max([0, xdict[x1] - 1])]
            if ydict[y1] - 1 < 0:
                yb = (10**9 + 1)*(-1)
            else:
                yb = ylist[max([0, ydict[y1] - 1])]
            tmp = sumnum[x2][y2] - sumnum[xb][y2] - sumnum[x2][yb] + sumnum[xb][yb]
            if tmp >= K:
                area = abs(x2 - x1)*abs(y2 - y1)
                if sqmin > area or sqmin == -1:
                    sqmin = area

print(sqmin)

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:
# -*- coding: utf-8 -*-
from itertools import combinations

n,k = map(int, input().split())

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

res = None
for cx in combinations(xl, 2):
    for cy in combinations(yl, 2):
        x1,x2 = cx
        y1,y2 = cy

        if x2>x1:
            x1,x2 = x2,x1
        if y2>y1:
            y1,y2 = y2,y1

        cnt = 0
        for cc in xy:
            x,y = cc
            if x1>=x>=x2 and y1>=y>=y2:
                cnt += 1
            if cnt>=k:
                break
        if cnt>=k:
            s = (x1-x2)*(y1-y2)
            if res is None:
                res = s
            else:
                res = min(res, s)

print(res)

Submission status: Time Limit Exceeded

Solution code:
N, K = map( int, input().split())
X = [0]*N
Y = [0]*N
for i in range(N):
    x, y = map( int, input().split())
    X[i] = x
    Y[i] = y
SX = sorted(X)
SY = sorted(Y)
ans = 10**19
for xleft in range(N-1):
    a = SX[ xleft]
    for xright in range(xleft, N):
        b = SX[ xright]
        for yunder in range(N-1):
            c = SY[ yunder]
            for yabove in range(yunder, N):
                d = SY[ yabove]
                cnt = 0
                for i in range(N):
                    if a <= X[i] and X[i] <= b and c <= Y[i] and Y[i] <= d:
                        cnt += 1
                if cnt >= K:
                    ans = min( ans, (b-a)*(d-c))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int,input().split())
p = [list(map(int,input().split())) for i in range(N)]
used = [False for i in range(N)]
def dfs(p,K,d=0,ans=[[],[]],s=float('inf')):
    if K==d:
        s = abs(max(ans[0])-min(ans[0]))*abs(max(ans[1])-min(ans[1]))
        return s
    for i in range(len(p)):
        if used[i]:
            continue
        used[i] = True
        ans[0].append(p[i][0])
        ans[1].append(p[i][1])
        s = min(s,dfs(p,K,d+1,ans))
        del ans[0][d]
        del ans[1][d]
        used[i] = False
    return s
print(dfs(p,K))

Submission status: Time Limit Exceeded

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

N, K=map(int,input().strip().split(' '))
x=[]
y=[]
p=[]
for i in range(N):
    xt,yt=map(int,input().strip().split(' '))
    x.append(xt)
    y.append(yt)
    p.append([xt,yt])
ans=10**20
x.sort()
y.sort()
p.sort(key=lambda xt:xt[0])

for i in range(N):
    for j in range(i+1,N):
        xmin=x[i]
        xmax=x[j]
        for k in range(N):
            for l in range(k+1,N):
                ymin=y[k]
                ymax=y[l]
                A=(xmax-xmin)*(ymax-ymin)
                ct=0
                for m in range(N):
                    if xmin<=p[m][0] and p[m][0]<=xmax and ymin<=p[m][1] and p[m][1]<=ymax:
                        ct+=1
                if ct==K:
                    ans=min(ans,A)
                    break
print(ans)

Submission status: Time Limit Exceeded

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

N, K=map(int,input().strip().split(' '))
x=[]
y=[]
p=[]
for i in range(N):
    xt,yt=map(int,input().strip().split(' '))
    x.append(xt)
    y.append(yt)
    p.append([xt,yt])
ans=10**20
x.sort()
y.sort()
for i in range(N):
    for j in range(i+1,N):
        xmin=x[i]
        xmax=x[j]
        for k in range(N):
            for l in range(k+1,N):
                ymin=y[k]
                ymax=y[l]
                A=(xmax-xmin)*(ymax-ymin)
                ct=0
                for m in range(N):
                    if xmin<=p[m][0] and p[m][0]<=xmax and ymin<=p[m][1] and p[m][1]<=ymax:
                        ct+=1
                if ct==K:
                    ans=min(ans,A)
                    break
print(ans)

Submission status: Time Limit Exceeded

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

N, K=map(int,input().strip().split(' '))
xl=[]
yl=[]
for i in range(N):
    xt,yt=map(int,input().strip().split(' '))
    xl.append(xt)
    yl.append(yt)
ans=10**20
x=sorted(xl)
y=sorted(yl)
for i in range(N):
    for j in range(i+1,N):
        xmin=x[i]
        xmax=x[j]
        for k in range(N):
            for l in range(k+1,N):
                ymin=y[k]
                ymax=y[l]
                A=(xmax-xmin)*(ymax-ymin)
                ct=0
                for m in range(N):
                    if xmin<=xl[m] and xl[m]<=xmax and ymin<=yl[m] and yl[m]<=ymax:
                        ct+=1
                if ct==K:
                    ans=min(ans,A)
                    break
print(ans)

Submission status: Time Limit Exceeded

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

N, K=map(int,input().strip().split(' '))
xl=[]
yl=[]
for i in range(N):
    xt,yt=map(int,input().strip().split(' '))
    xl.append(xt)
    yl.append(yt)
ans=10**20
x=sorted(xl)
y=sorted(yl)
for i in range(N):
    for j in range(i+1,N):
        xmin=x[i]
        xmax=x[j]
        for k in range(N):
            for l in range(k+1,N):
                ymin=y[k]
                ymax=y[l]
                A=(xmax-xmin)*(ymax-ymin)
                ct=0
                for m in range(N):
                    if xmin<=xl[m] and xl[m]<=xmax and ymin<=yl[m] and yl[m]<=ymax:
                        ct+=1
                if ct>=K:
                    ans=min(ans,A)
print(ans)

Submission status: Time Limit Exceeded

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

N, K=map(int,input().strip().split(' '))
x=[]
y=[]
for i in range(N):
    xt,yt=map(int,input().strip().split(' '))
    x.append(xt)
    y.append(yt)
ans=10**20
for i in range(N):
    for j in range(N):
        if i!=j and x[i]<x[j]:
            xmin=x[i]
            xmax=x[j]
        else:
            continue
        for k in range(N):
            for l in range(N):
                if k!=l and y[k]<y[l]:
                    ymin=y[k]
                    ymax=y[l]
                else:
                    continue
                A=(xmax-xmin)*(ymax-ymin)
                ct=0
                for m in range(N):
                    if xmin<=x[m] and x[m]<=xmax and ymin<=y[m] and y[m]<=ymax:
                        ct+=1
                if ct>=K:
                    ans=min(ans,A)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
s = []
for i in range(n):#h:高さ
    s.append([int(m) for m in input().split()])

count = 0
recli = []
if k == 2:
    for i in range(n):
        for j in range(i + 1, n):
            larx = max(s[i][0], s[j][0])
            smax = min(s[i][0], s[j][0])
            lary = max(s[i][1], s[j][1])
            smay = min(s[i][1], s[j][1])
            rec = (larx - smax) * (lary - smay)
            for l in range(n):
                if smax <= s[l][0] <= larx and smay <= s[l][1] <= lary:
                    count += 1
            if count >= k:
                recli.append(rec)
            count = 0

elif k == 3:
    for i in range(n):
        for j in range(i + 1, n):
            for p in range(j + 1, n):
                larx = max(s[i][0], s[j][0], s[p][0])
                smax = min(s[i][0], s[j][0], s[p][0])
                lary = max(s[i][1], s[j][1], s[p][1])
                smay = min(s[i][1], s[j][1], s[p][1])
                rec = (larx - smax) * (lary - smay)
                for l in range(n):
                    if smax <= s[l][0] <= larx and smay <= s[l][1] <= lary:
                        count += 1
                if count >= k:
                    recli.append(rec)
                count = 0
else:
    for i in range(n):
        for j in range(i + 1, n):
            for p in range(j + 1, n):
                for q in range(p + 1, n):
                    larx = max(s[i][0], s[j][0], s[p][0], s[q][0])
                    smax = min(s[i][0], s[j][0], s[p][0], s[q][0])
                    lary = max(s[i][1], s[j][1], s[p][1], s[q][1])
                    smay = min(s[i][1], s[j][1], s[p][1], s[q][1])
                    rec = (larx - smax) * (lary - smay)
                    for l in range(n):
                        if smax <= s[l][0] <= larx and smay <= s[l][1] <= lary:
                            count += 1
                    if count >= k:
                        recli.append(rec)
                    count = 0

print(min(recli))

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
N, K = map(int, input().split())
P, X, Y = [], [], []
for i in range(N):
    x, y = map(int, input().split())
    P.append((x, y))
    X.append(x)
    Y.append(y)
X.sort()
Y.sort()

Area = 10**20
for V in combinations(X, 2):
    for H in combinations(Y, 2):
        Count = 0
        for p in P:
            if V[0] <= p[0] <= V[1] and H[0] <= p[1] <= H[1]:
                Count += 1
        if Count >= K:
            Area = min(Area, (V[1]-V[0])*(H[1]-H[0]))
print(Area)

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
x = [0] * N
y = [0] * N
for i in range(N):
    x[i], y[i] = map(int, input().split())

ans = (max(x) - min(x)) * (max(y) - min(y))

for i in range(N):
    for j in range(N):
        lx = x[i]
        rx = x[j]

        if lx >= rx:
            continue

        for k in range(N):
            for l in range(N):
                cnt = 0
                uy = y[k]
                dy = y[l]

                if dy >= uy:
                    continue

                for m in range(N):
                    if lx <= x[m] <= rx and dy <= y[m] <= uy:
                        cnt += 1

                if cnt >= K:
                    ans = min(ans, (rx - lx) * (uy - dy))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
x = [0] * N
y = [0] * N
for i in range(N):
    x[i], y[i] = map(int, input().split())

ans = (max(x) - min(x)) * (max(y) - min(y))

for i in range(N):
    for j in range(N):
        for k in range(N):
            for l in range(N):
                cnt = 0

                lx = x[i]
                rx = x[j]
                uy = y[k]
                dy = y[l]

                if lx >= rx or dy >= uy:
                    continue

                for m in range(N):
                    if lx <= x[m] <= rx and dy <= y[m] <= uy:
                        cnt += 1

                if cnt >= K:
                    ans = min(ans, (rx - lx) * (uy - dy))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
Points=[[int(i) for i in input().split()] for i in range(N)]
List_x=[Points[i][0] for i in range(N)]
List_x.sort(key=lambda x:x)
List_y=[Points[i][1] for i in range(N)]
List_y.sort(key=lambda x:x)
n=0
S=[]
for x1 in range(N-1):
  for x2 in range(x1+K-1,N):
    for y1 in range(N-1):
      for y2 in range(y1+K-1,N):
        for p in Points:
          if List_x[x1]<=p[0]<=List_x[x2] and List_y[y1]<=p[1]<=List_y[y2]:
            n+=1
          if n>=K:
            x_delta=List_x[x2]-List_x[x1]
            y_delta=List_y[y2]-List_y[y1]
            S.append(x_delta*y_delta)
            break
        if n>=K:
          n=0
          break  
        n=0
print(min(S))

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
Points=[[int(i) for i in input().split()] for i in range(N)]
List_x=[Points[i][0] for i in range(N)]
List_x.sort(key=lambda x:x)
List_y=[Points[i][1] for i in range(N)]
List_y.sort(key=lambda x:x)
n=0
S=[]
for x1 in range(N-1):
  for x2 in range(x1+K-1,N):
    for y1 in range(N-1):
      for y2 in range(y1+K-1,N):
        for p in Points:
          if List_x[x1]<=p[0]<=List_x[x2] and List_y[y1]<=p[1]<=List_y[y2]:
            n+=1
        if n>=K:
          x_delta=List_x[x2]-List_x[x1]
          y_delta=List_y[y2]-List_y[y1]
          S.append(x_delta*y_delta)
          n=0
          break
        n=0
print(min(S))

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
Points=[[int(i) for i in input().split()] for i in range(N)]
List_x=[Points[i][0] for i in range(N)]
List_x.sort(key=lambda x:x)
List_y=[Points[i][1] for i in range(N)]
List_y.sort(key=lambda x:x)
n=0
S=[]
for x1 in range(N-1):
  for x2 in range(x1+K-1,N):
    for y1 in range(N-1):
      for y2 in range(y1+K-1,N):
        for p in Points:
          if List_x[x1]<=p[0]<=List_x[x2] and List_y[y1]<=p[1]<=List_y[y2]:
            n+=1
        if n>=K:
          x_delta=List_x[x2]-List_x[x1]
          y_delta=List_y[y2]-List_y[y1]
          S.append(x_delta*y_delta)
        n=0
print(min(S))

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
Points=[[int(i) for i in input().split()] for i in range(N)]
List_x=[Points[i][0] for i in range(N)]
List_x.sort(key=lambda x:x)
List_y=[Points[i][1] for i in range(N)]
List_y.sort(key=lambda x:x)
n=0
S=[]
for x1 in range(N-1):
  for x2 in range(x1+1,N):
    for y1 in range(N-1):
      for y2 in range(y1+1,N):
        for p in Points:
          if List_x[x1]<=p[0]<=List_x[x2] and List_y[y1]<=p[1]<=List_y[y2]:
            n+=1
        if n>=K:
          x_delta=List_x[x2]-List_x[x1]
          y_delta=List_y[y2]-List_y[y1]
          S.append(x_delta*y_delta)
        n=0
print(min(S))

Submission status: Time Limit Exceeded

Solution code:
import itertools
from operator import itemgetter

[point_num , inside_point_num] = list(map(int,input().split()))
points = []

for i in range(point_num):
	points.append( list(map(int,input().split())))



combinations = []
cand_points = []
x,y = zip(*points)
for x_tmp,y_tmp in itertools.product(x,y):
	cand_points.append([ x_tmp,y_tmp ] )

combinations = list(itertools.combinations(cand_points,2))



def calc_rect_area( point1, point2 ,points , inside_points_num ):
	inside_cnt = 0
	for i in range(len(points)):
		if( (points[i][0] <= point1[0] or points[i][0] <= point2[0])
		       and  (points[i][0] >= point1[0] or points[i][0] >= point2[0])
			and (points[i][1] <= point2[1] or points[i][1] <= point1[1])
			and (points[i][1] >= point2[1] or points[i][1] >= point1[1]) ):
			inside_cnt += 1

		if(inside_cnt >= inside_points_num):
			return abs(point1[0]-point2[0]) * abs(point1[1] - point2[1])
	return -1

min_rect = -1

for i in range( len(combinations) ):
	rect = calc_rect_area( combinations[i][0], combinations[i][1],points, inside_point_num )
	if( (min_rect > rect  or min_rect == -1) and rect != -1 ):
		min_rect = rect
		
print(min_rect)

Submission status: Time Limit Exceeded

Solution code:
import itertools
from operator import itemgetter

[point_num , inside_point_num] = list(map(int,input().split()))
points = []

for i in range(point_num):
	points.append( list(map(int,input().split())))

combinations = list(itertools.combinations(points,inside_point_num))


def calc_rect_area( points_rect, points_num ):
	x_sort = []
	y_sort = []
	x_sort = sorted( points_rect , key=itemgetter(0) )
	y_sort = sorted( points_rect , key=itemgetter(1) )
	# 左上の点：(x_sort[0][0],y_sort[points_num-1][1])
	# 右下の点：(x_sort[point_num-1][0],y_sort[0][1])
	return  (x_sort[points_num-1][0] - x_sort[0][0]) * (y_sort[points_num-1][1] - y_sort[0][1])

min_rect = -1

for i in range( len(combinations) ):
	rect = calc_rect_area( combinations[i] , inside_point_num)
	if(min_rect > rect  or min_rect == -1):
		min_rect = rect

print(min_rect)

Submission status: Time Limit Exceeded

Solution code:
def in_rectangle(p, l, r, d, u):
    if (l <= p[0] <= r) and (d <= p[1] <= u):
        return True
    else:
        return False

n, k = map(int, input().split())
p = [list(map(int, input().split())) for _ in range(n)]
p.sort()
s = []
for g in range(n - 1):
    l = p[g][0]
    for h in range(g + 1, n):
        r = p[h][0]
        dd = min(p[g][1], p[h][1])
        uu = max(p[g][1], p[h][1])
        for i in range(n):
            if p[i][1] <= dd:
                d = p[i][1]
                for j in range(n):
                    if p[j][1] >= uu:
                        u = p[j][1]
                        m = 0
                        for t in range(g, h + 1):
                            if in_rectangle(p[t], l, r, d, u):
                                m += 1
                        if m >= k:
                            s.append((r - l) * (u - d))
print(min(s))

Submission status: Time Limit Exceeded

Solution code:
def in_rectangle(p, l, r, d, u):
    if (l <= p[0] <= r) and (d <= p[1] <= u):
        return True
    else:
        return False

n, k = map(int, input().split())
p = [list(map(int, input().split())) for _ in range(n)]
p.sort()
s = []
for g in range(n - 1):
    l = p[g][0]
    for h in range(g + 1, n):
        r = p[h][0]
        for i in range(n):
            if min(p[g][1], p[h][1]) >= p[i][1]:
                d = p[i][1]
                for j in range(n):
                    if max(p[g][1], p[h][1]) <= p[j][1]:
                        u = p[j][1]
                        m = 0
                        for t in range(g, h + 1):
                            if in_rectangle(p[t], l, r, d, u):
                                m += 1
                        if m >= k:
                            s.append((r - l) * (u - d))
print(min(s))

Submission status: Time Limit Exceeded

Solution code:
def in_rectangle(p, l, r, d, u):
    if (l <= p[0] <= r) and (d <= p[1] <= u):
        return True
    else:
        return False

n, k = map(int, input().split())
p = [list(map(int, input().split())) for _ in range(n)]
p.sort()
s = []
for g in range(n - 1):
    l = p[g][0]
    for h in range(g + 1, n):
        r = p[h][0]
        for i in range(n):
            if min(p[g][1], p[h][1]) >= p[i][1]:
                d = p[i][1]
                for j in range(n):
                    if max(p[g][1], p[h][1]) <= p[j][1]:
                        u = p[j][1]
                        m = 0
                        for t in range(n):
                            if in_rectangle(p[t], l, r, d, u):
                                m += 1
                        if m >= k:
                            s.append((r - l) * (u - d))
print(min(s))

Submission status: Time Limit Exceeded

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

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