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 main():
    n, num = map(int, input().split())
    point1 = []
    for i in range(n):
        point1.append(tuple(map(int, input().split())))

    point2 = point1[:]
    point1.sort(key=lambda tup: tup[0])
    point2.sort(key=lambda tup: tup[1])

    min_s = 10 ** 19
    for i in range(n):
        for j in range(i, n):
            for k in range(n):
                for l in range(k, n):
                    s = (point1[j][0]-point1[i][0]) * (point2[l][1]-point2[k][1])
                    if s < min_s:
                        cnt = 0
                        for m in range(i, j+1):
                            if point1[i][0] <= point1[m][0] <= point1[j][0]:
                                if point2[k][1] <= point1[m][1] <= point2[l][1]:
                                    cnt += 1

                        if cnt >= num:
                            min_s = s

    print(min_s)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    n, num = map(int, input().split())
    point1 = []
    for i in range(n):
        point1.append(tuple(map(int, input().split())))

    point2 = point1[:]
    point1.sort(key=lambda tup: tup[0])
    point2.sort(key=lambda tup: tup[1])

    min_s = 10 ** 19
    for i in range(n):
        for j in range(i, n):
            for k in range(n):
                for l in range(k, n):
                    s = (point1[j][0]-point1[i][0]) * (point2[l][1]-point2[k][1])
                    if s < min_s:
                        cnt = 0
                        for m in range(n):
                            if point1[i][0] <= point1[m][0] <= point1[j][0]:
                                if point2[k][1] <= point1[m][1] <= point2[l][1]:
                                    cnt += 1

                        if cnt >= num:
                            min_s = s

    print(min_s)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
P= [list(map(int, input().split())) for i in range(N)]
xset=set([x[0] for x in P])
yset=set([x[1] for x in P])

minA=float('inf')
for l in xset:
    for r in xset:
        if r<=l:continue
        for d in yset:
            for u in yset:
                if u<=d:continue
                area=(r-l)*(u-d)
                if area>=minA:continue
                if len([p for p in P if l<=p[0]<=r and d<=p[1]<=u])==K:
                    area=(r-l)*(u-d)
                    minA=area
print(minA)

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
P= [list(map(int, input().split())) for i in range(N)]
xset=set([x[0] for x in P])
yset=set([x[1] for x in P])

minA=float('inf')
for l in xset:
    for r in xset:
        if r<=l:continue
        for d in yset:
            for u in yset:
                if u<=d:continue
                if len([p for p in P if l<=p[0]<=r and d<=p[1]<=u])==K:
                    area=(r-l)*(u-d)
                    if area<minA:
                        minA=area
print(minA)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
n,k = (int(i) for i in input().split())
p = [[int(i) for i in input().split()] for i in range(n)]
p,ans = sorted(p),float("inf")
for q in combinations(p,min(4,k)):
	r = sorted(j for i,j in q)
	xa,xb,ya,yb = q[0][0],q[-1][0],r[0],r[-1]
	num = sum(1 for i,j in p if xa<=i<=xb and ya<=j<=yb)
	if num>=k: ans = min(ans,(xb-xa)*(yb-ya))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import product
n, k = map(int, input().split())
dots = [list(map(int, input().split())) for _ in range(n)]

ans = float("inf")
for a, b, c, d in product(dots, repeat=4):
	upper = max(a[1], b[1], c[1], d[1])
	lower = min(a[1], b[1], c[1], d[1])
	left = min(a[0], b[0], c[0], d[0])
	right = max(a[0], b[0], c[0], d[0])

	area = (upper - lower) * (right - left)
	num = 0
	for dot in dots:
		if left <= dot[0] <= right and lower <= dot[1] <= upper:
			num += 1
	if num >= k and area < ans:
		ans = area

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

N, K = map(int, input().split())
X, Y = [], []
for i in range(N):
    xi, yi = map(int, sys.stdin.readline().split())
    X.append(xi)
    Y.append(yi)

ans = float('inf')
for i in range(N):  # 左
    for j in range(N):  # 右
        if X[i] >= X[j]:
            continue
        for k in range(N):  # 下
            for l in range(N):  # 上
                if Y[k] >= Y[l]:
                    continue
                cnt = 0
                for x, y in zip(X, Y):  # 含まれてるかカウント
                    if X[i] <= x <= X[j] and Y[k] <= y <= Y[l]:
                        cnt += 1
                        if cnt == K:
                            ans = min(ans, (X[j] - X[i]) * (Y[l] - Y[k]))
                            break

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
X, Y = [], []
for i in range(N):
    xi, yi = map(int, input().split())
    X.append(xi)
    Y.append(yi)

ans = float('inf')
for i in range(N):  # 左
    for j in range(N):  # 右
        if X[i] >= X[j]:
            continue
        for k in range(N):  # 下
            for l in range(N):  # 上
                if Y[k] >= Y[l]:
                    continue
                cnt = 0
                for x, y in zip(X, Y):  # 含まれてるかカウント
                    if X[i] <= x <= X[j] and Y[k] <= y <= Y[l]:
                        cnt += 1
                if cnt >= K:
                    ans = min(ans, (X[j]-X[i]) * (Y[l]-Y[k]))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations

N, K = map(int, input().split())
points = []
for i in range(N):
    points.append(list(map(int, input().split())))

xl = list(map(lambda p: p[0],
              points))
yl = list(map(lambda p: p[1],
              points))

def contained(point, xmin, xmax, ymin, ymax):
    return (xmin <= point[0] <= xmax) and (ymin <= point[1] <= ymax)

def count_contained(xmin, xmax, ymin, ymax):
    count = 0
    for point in points:
        if contained(point, xmin, xmax, ymin, ymax):
            count += 1
    return count

min_area = 10**20
for xs in combinations(xl, 2):
    xmin = min(xs)
    xmax = max(xs)
    for ys in combinations(yl, 2):
        ymin = min(ys)
        ymax = max(ys)
        if count_contained(xmin, xmax, ymin, ymax) >= K:
            area = (xmax-xmin) * (ymax-ymin)
            min_area = min(area, min_area)
print(min_area)

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split())
x = []
y = []
for i in range(n):
	a,b = map(int,input().split())
	x.append(a)
	y.append(b)
ans = 10 ** 100
for j in range(n):
	for f in range(n):
		for h in range(n):
			for g in range(n):
				cou = 0
				for t in range(n):
					if x[j] <= x[t] <= x[f] and y[h] <= y[t] <= y[g]:
						cou += 1
				if cou >= k:
					ans = min(ans,abs(x[j] - x[f]) * abs(y[h] - y[g]))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split())
x = []
y = []
for i in range(n):
	a,b = map(int,input().split())
	x.append(a)
	y.append(b)
ans = 10 ** 100
for j in range(n):
	for f in range(n):
		for h in range(n):
			for g in range(n):
				cou = 0
				ri_x = x[j]
				le_x = x[f]
				up_y = y[h]
				do_y = y[g]
				for t in range(n):
					if le_x <= x[t] <= ri_x and do_y <= y[t] <= up_y:
						cou += 1
				if cou >= k:
					ans = min(ans,(ri_x - le_x) * (up_y - do_y))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
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 = 10**20
listN = [x for x in range(N)]
combX = list(combinations(listN,2))
combY = list(combinations(listN,2))
for x1,x2 in combX:
    for y1,y2 in combY:
        cnt = 0
        minX = min(X[x1],X[x2],X[y1],X[y2])
        maxX = max(X[x1],X[x2],X[y1],X[y2])
        minY = min(Y[x1],Y[x2],Y[y1],Y[y2])
        maxY = max(Y[x1],Y[x2],Y[y1],Y[y2])
        for i in range(N):
            if minX<=X[i] and X[i]<=maxX and minY<=Y[i] and Y[i]<=maxY:
                cnt += 1
        if cnt >= K:
            Ans = min(Ans,(maxX-minX)*(maxY-minY))
print(Ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
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 = 10**20
listN = [x for x in range(N)]
combX = list(combinations(listN,2))
combY = list(combinations(listN,2))
for x1,x2 in combX:
    for y1,y2 in combY:
        cnt = 0
        minX = min(X[x1],X[x2],X[y1],X[y2])
        maxX = max(X[x1],X[x2],X[y1],X[y2])
        minY = min(Y[x1],Y[x2],Y[y1],Y[y2])
        maxY = max(Y[x1],Y[x2],Y[y1],Y[y2])
        for i in range(N):
            if (X[i]-minX)*(maxX-X[i]) > 0 and (Y[i]-minY)*(maxY-Y[i]) > 0:
                cnt += 1
            elif X[i] in (minX,maxX) or Y[i] in (minY,maxY):
                cnt += 1
        if cnt >= K:
            Ans = min(Ans,(maxX-minX)*(maxY-minY))
print(Ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
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 = 10**20
listN = [x for x in range(N)]
combX = list(combinations(listN,2))
for x1,x2 in combX:
    tmpN = listN[:]
    #tmpN.remove(x1)
    #tmpN.remove(x2)
    combY = list(combinations(tmpN,2))
    for y1,y2 in combY:
        cnt = 0
        minX = min(X[x1],X[x2],X[y1],X[y2])
        maxX = max(X[x1],X[x2],X[y1],X[y2])
        minY = min(Y[x1],Y[x2],Y[y1],Y[y2])
        maxY = max(Y[x1],Y[x2],Y[y1],Y[y2])
        for i in range(N):
            if (X[i]-minX)*(maxX-X[i]) > 0 and (Y[i]-minY)*(maxY-Y[i]) > 0:
                cnt += 1
            elif X[i] in (minX,maxX) or Y[i] in (minY,maxY):
                cnt += 1
        if cnt >= K:
            Ans = min(Ans, (maxX-minX)*(maxY-minY))
print(Ans)

Submission status: Time Limit Exceeded

Solution code:
import math
INF = 10000000000000000000000000000000000
N, K = map(int, input().split())
points = []
to_search_x = []
to_search_y = []
for i in range(N):
    xi, yi = map(int, input().split())
    points.append([xi, yi])
    to_search_x.append(xi)
    to_search_y.append(yi)

to_search_x.sort()
to_search_y.sort()

def count(xmin, xmax, ymin, ymax):
    num = 0
    for i in range(N):
        x,y = points[i]
        if (xmin <= x and xmax >= x) and (ymin <= y and ymax >= y):
            num += 1
    return num

ans = INF
for i in range(N):
    for j in range(i,N):
        for k in range(N):
            for l in range(k,N):
                if count(to_search_x[i], to_search_x[j], to_search_y[k], to_search_y[l]) >= K:
                    ans = min(ans, (to_search_x[j]-to_search_x[i])*(to_search_y[l]-to_search_y[k]))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
INF = 10000000000000000000000000000000000
N, K = map(int, input().split())
points = []
to_search_x = []
to_search_y = []
for i in range(N):
    xi, yi = map(int, input().split())
    points.append([xi, yi])
    to_search_x.append(xi)
    to_search_y.append(yi)

to_search_x.sort()
to_search_y.sort()

def is_between(x1, x2, x):
    if x >= x1 and x <= x2:
        return True
    elif x <= x1 and x >= x2:
        return True
    else:
        return False

def count(x1, x2, y1, y2):
    num = 0
    for i in range(N):
        if is_between(x1, x2, points[i][0]) and is_between(y1, y2, points[i][1]):
            num += 1
    return num

ans = INF
for i in range(N):
    for j in range(i,N):
        for k in range(N):
            for l in range(k,N):
                if count(to_search_x[i], to_search_x[j], to_search_y[k], to_search_y[l]) >= K:
                    ans = min(ans, (to_search_x[j]-to_search_x[i])*(to_search_y[l]-to_search_y[k]))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
INF = 10000000000000000000000000000000000
N, K = map(int, input().split())
points = []
to_search_x = []
to_search_y = []
for i in range(N):
    xi, yi = map(int, input().split())
    points.append([xi, yi])
    to_search_x.append(xi)
    to_search_y.append(yi)

to_search_x.sort()
to_search_y.sort()

def is_between(x1, x2, x):
    if x >= x1 and x <= x2:
        return True
    elif x <= x1 and x >= x2:
        return True
    else:
        return False

def count(x1, x2, y1, y2):
    num = 0
    for i in range(N):
        if is_between(x1, x2, points[i][0]) and is_between(y1, y2, points[i][1]):
            num += 1
    return num

ans = INF
for i in range(N):
    for j in range(i,N):
        for k in range(N):
            for l in range(k,N):
                if count(to_search_x[i], to_search_x[j], to_search_y[k], to_search_y[l]) >= K:
                    ans = min(ans, abs((to_search_x[i]-to_search_x[j])*(to_search_y[k]-to_search_y[l])))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
INF = 10000000000000000000000000000000000
N, K = map(int, input().split())
points = []
to_search_x = []
to_search_y = []
for i in range(N):
    xi, yi = map(int, input().split())
    points.append([xi, yi])
    to_search_x.append(xi)
    to_search_y.append(yi)

to_search_x.sort()
to_search_y.sort()

def is_between(x1, x2, x):
    if x >= x1 and x <= x2:
        return True
    elif x <= x1 and x >= x2:
        return True
    else:
        return False

def count(x1, x2, y1, y2):
    num = 0
    for i in range(N):
        if is_between(x1, x2, points[i][0]) and is_between(y1, y2, points[i][1]):
            num += 1
    return num

ans = INF
for i in range(N):
    for j in range(N):
        for k in range(N):
            for l in range(N):
                if count(to_search_x[i], to_search_x[j], to_search_y[k], to_search_y[l]) >= K:
                    ans = min(ans, abs((to_search_x[i]-to_search_x[j])*(to_search_y[k]-to_search_y[l])))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
A=[]
for i in range(N):
  a=[int(x) for x in input().split()]
  A.append(a)
ans=float('inf')
for i in range(N):
  for j in range(i+1,N):
    for k in range(N):
      for l in range(k+1,N):
        miX=10000000000
        maX=-10000000000
        miY=10000000000
        maY=-10000000000
        cnt=0
        for m in range(N):
          if min(A[i][0],A[j][0])<= A[m][0] <= max(A[i][0],A[j][0]) and min(A[k][1],A[l][1])<= A[m][1] <= max(A[k][1],A[l][1]):
            cnt+=1
            miX=min(A[m][0],miX)
            maX=max(A[m][0],maX)
            miY=min(A[m][1],miY)
            maY=max(A[m][1],maY)
        if cnt>=K:
          ans=min(ans,(maX-miX)*(maY-miY))
print(ans)

Submission status: Time Limit Exceeded

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

def filt(p, ps, pl):
    (nx, ny) = p
    return ps[0] <= nx and nx <= pl[0] \
        and ps[1] <= ny and ny <= pl[1]



pos = [0]*N
xs = [0]*N
ys = [0]*N
for i in range(N):
    x, y = map(int, input().split())
    pos[i] = (x, y)
    xs[i] = x
    ys[i] = y


def check(n, tri):
    ix, jx, iy = tri
    a = list(filter(lambda a: filt(a, (xs[ix], ys[iy]), (xs[jx], ys[n])), pos))
    return len(a) >= K
    

def binarySearch(small, big, tri):
    mid = (big + small) // 2
    if big - small <= 1:
        if check(small, tri): return small
        else:            return big
    else:
        if check(mid, tri):
            return binarySearch(small, mid,tri)
        else:
            return binarySearch(mid, big,tri)


ans = 9223372036854775800

xs.sort()
ys.sort()

for ix in range(N-1):
    for jx in range(ix+1, N):
        for iy in range(N-1):
            if len(list(filter(lambda a: filt(a, (xs[ix], ys[iy]), (xs[jx], ys[N-1])), pos))) >= K:
                jy = binarySearch(iy+1, N-1, (ix, jx, iy))
                hoge = list(filter(lambda a: filt(a, (xs[ix], ys[iy]), (xs[jx], ys[jy])), pos))

                if len(hoge) >= K:
                    ans = min(ans, (xs[jx]-xs[ix])*(ys[jy]-ys[iy]))
                
print(ans)

Submission status: Time Limit Exceeded

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

def check(p, ps, pl):
    (nx, ny) = p
    return ps[0] <= nx and nx <= pl[0] \
        and ps[1] <= ny and ny <= pl[1]

pos = [0]*N
xs = [0]*N
ys = [0]*N
for i in range(N):
    x, y = map(int, input().split())
    pos[i] = (x, y)
    xs[i] = x
    ys[i] = y


ans = 9223372036854775800

xs.sort()
ys.sort()

for ix in range(N):
    for jx in range(ix+1, N):
        for iy in range(N):
            for jy in range(iy+1, N):
                hoge = list(filter(lambda a: check(a, (xs[ix], ys[iy]), (xs[jx], ys[jy])), pos))
                
                if len(hoge) >= K:
                    ans = min(ans, (xs[jx]-xs[ix])*(ys[jy]-ys[iy]))
                
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
XY = [list(map(int, input().split())) for i in range(N)]
ans = float('inf')
for i in range(N):
    for j in range(N):
        for k in range(N):
            for l in range(N):
                cnt = 0
                if (XY[i][0] >= XY[j][0]) or (XY[k][1] >= XY[l][1]):
                    continue
                for x, y in XY:
                    if (XY[i][0] <= x <= XY[j][0]) & (XY[k][1] <= y <= XY[l][1]):
                        cnt += 1
                if cnt >= K:
                    ans = min(ans, (XY[j][0]-XY[i][0]) * (XY[l][1]-XY[k][1]))

print(ans)

Submission status: Time Limit Exceeded

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

    f(N, K, x, y)


def f(N, K, x, y):
    """
    TLEのため、考察はpypy3のD directoryに移行
    codeの見た目のためにgeneratorを使ったが遅いので愚直にloop
    """
    sorted_x = sorted(x)
    sorted_y = sorted(y)
    ans = (sorted_x[-1] - sorted_x[0]) * (sorted_y[-1] - sorted_y[0])
    for xi in range(N):
        for xj in range(xi + 1, N):
            for yi in range(N):
                for yj in range(yi + 1, N):
                    min_x, max_x = sorted_x[xi], sorted_x[xj]
                    min_y, max_y = sorted_y[yi], sorted_y[yj]
                    contains_count = 0
                    for x3, y3 in zip(x, y):
                        if min_x <= x3 <= max_x and min_y <= y3 <= max_y:
                            contains_count += 1
                    if contains_count >= K:
                        s = (max_x - min_x) * (max_y - min_y)
                        ans = min(ans, s)

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

    f(N, K, x, y)


def f(N, K, x, y):
    ans = abs(max(x) - min(x)) * abs(max(y) - min(y))
    if K == N:
        print(ans)
        return

    def r(x, y, x_start=0, y_start=0):
        for xi in range(x_start, N):
            for yi in range(y_start, N):
                yield x[xi], y[yi], xi, yi

    # for x1, y1 in zip(x, y):
    #     for x2, y2 in zip(x, y):
    # for x1, y1 in r(x, y):
    #     for x2, y2 in r(x, y):
    sorted_x = sorted(x)
    sorted_y = sorted(y)
    for min_x, min_y, xi, yi in r(sorted_x, sorted_y):
        for max_x, max_y, _, _ in r(sorted_x, sorted_y, x_start=xi+1, y_start=yi+1):

            # s = abs(x1-x2) * abs(y1-y2)
            # if s == 0:
            #     continue

            # min_x = min(x1, x2)
            # max_x = max(x1, x2)
            # min_y = min(y1, y2)
            # max_y = max(y1, y2)

            contains_count = 0
            for x3, y3 in zip(x, y):
                if min_x <= x3 <= max_x and min_y <= y3 <= max_y:
                    contains_count += 1
            if contains_count >= K:
                s = (max_x - min_x) * (max_y - min_y)
                ans = min(ans, s)

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:


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

    f(N, K, x, y)


def f(N, K, x, y):
    """
    制約
    * 2≦K≦N≦50
    * −10^9≦xi,yi≦10^9 (1≦i≦N)
    * xi≠xj (1≦i<j≦N)
    * yi≠yj (1≦i<j≦N)
    * 入力値はすべて整数である。(21:50 追記)

    長方形の内部にN点のうち
    K個以上の点を含みつつ、
    それぞれの辺がX軸かY軸に平行な長方形を考えます。
    →最小の面積

    制約より、
    xyの範囲を全探索はTLE
    点は重ならないかつ、50以下
    →点の座標から求めれば間に合いそう

    例題1より、
    全ての点を含む場合、
    abs(x_max-x_min) * abs(y_max-y_min)
    => 追記:
        これを分かったのに図示しなかったため、
        点が角ではなく辺上にのることに気づかず…
        点同士の組合せになってしまった(座標同士の組合せと気づけたはず)

    例題2より
    １つの場合1、ただし1*1の長方形より最大4点含む
    →この例の場合、4点から2点以上で面積1

    (x_2nd-x_min)*(y_max-y_min)
    →x_maxを除いた点が含まれる
    →50*50では済まない

    y
    ↑
    |*...
    |.*..
    |...*
    |*...
    ------→x
    (0,0)
    (0,4)
    (1,3)
    (3,1)

    各点を結んだときの面積の個数：O(N*N)
    面積求めたあとの点が含まれる個数の計算量: O(N)
    => O(N^3) => 50^3 => 1.25 * 10^5 => OK
      点を必ず含む場所からの面積
      => そこからでなくてよい, むしろ広くなる

    => 
    """
    ans = abs(max(x) - min(x)) * abs(max(y) - min(y))
    if K == N:
        print(ans)
        return

    def r(x, y):
        for _x in x:
            for _y in y:
                yield _x, _y

    # for x1, y1 in zip(x, y):
    #     for x2, y2 in zip(x, y):
    for x1, y1 in r(x, y):
        for x2, y2 in r(x, y):

            s = abs(x1-x2) * abs(y1-y2)
            if s == 0:
                continue

            min_x = min(x1, x2)
            max_x = max(x1, x2)
            min_y = min(y1, y2)
            max_y = max(y1, y2)

            contains_count = 0
            for x3, y3 in zip(x, y):
                if min_x <= x3 <= max_x and min_y <= y3 <= max_y:
                    contains_count += 1
            if contains_count >= K:
                ans = min(ans, s)

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from itertools import product, combinations
from operator import itemgetter
def inpl(): return tuple(map(int, input().split()))
 
# B以下の数-A未満の数→bisect(L, B) - bisect_left(L, A)
N, K = inpl()
X = []
Y = []
Px = []
Py = []
 
for i in range(N):
    x, y = inpl()
    X.append(x)
    Y.append(y)
    Px.append((x, i))
    Py.append((y, i))
 
X = sorted(X)
Y = sorted(Y)
 
dX = {x:i for i, x in enumerate(X)}
dY = {y:i for i, y in enumerate(Y)}
Px = sorted(Px)
Py = sorted(Py)
 
get = itemgetter(1)
res = 5 * 10**18
 
for (l, r), (d, u) in product(combinations(X, 2), combinations(Y, 2)):
    if (dX[r] - dX[l] < K-1) or (dY[u] - dY[d] < K-1):
        continue
    sx = sum([1 << i for i in map(get, Px[dX[l]:dX[r]+1])])
    sy = sum([1 << i for i in map(get, Py[dY[d]:dY[u]+1])])
    if bin(sx&sy).count("1") >= K:
        res = min(res, (r-l)*(u-d))
 
print(res)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from itertools import product, combinations
from operator import itemgetter
def inpl(): return tuple(map(int, input().split()))

# B以下の数-A未満の数→bisect(L, B) - bisect_left(L, A)
N, K = inpl()
X = []
Y = []
Px = []
Py = []

for i in range(N):
    x, y = inpl()
    X.append(x)
    Y.append(y)
    Px.append((x, i))
    Py.append((y, i))

X = sorted(X)
Y = sorted(Y)

dX = {x:i for i, x in enumerate(X)}
dY = {y:i for i, y in enumerate(Y)}
Px = sorted(Px)
Py = sorted(Py)

get = itemgetter(1)
res = 5 * 10**18

for (l, r), (d, u) in product(combinations(X, 2), combinations(Y, 2)):
    if (dX[r] - dX[l] < K-1) or (dY[u] - dY[d] < K-1):
        continue
    sx = set(map(get, Px[dX[l]:dX[r]+1]))
    sy = set(map(get, Py[dY[d]:dY[u]+1]))
    if len(sx.intersection(sy)) >= K:
        res = min(res, (r-l)*(u-d))

print(res)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from itertools import product, combinations
from operator import itemgetter
def inpl(): return tuple(map(int, input().split()))

# B以下の数-A未満の数→bisect(L, B) - bisect_left(L, A)
N, K = inpl()
X = []
Y = []
Px = []
Py = []

for i in range(N):
    x, y = inpl()
    X.append(x)
    Y.append(y)
    Px.append((x, i))
    Py.append((y, i))

X = sorted(X)
Y = sorted(Y)

dX = {x:i for i, x in enumerate(X)}
dY = {y:i for i, y in enumerate(Y)}
Px = sorted(Px)
Py = sorted(Py)

get = itemgetter(1)
res = 5 * 10**18

for (l, r), (d, u) in product(combinations(X, 2), combinations(Y, 2)):
    if (dX[r] - dX[l] < K-1) or (dY[u] - dY[d] < K-1):
        continue
    sx = sum([1 << i for i in map(get, Px[dX[l]:dX[r]+1])])
    sy = sum([1 << i for i in map(get, Py[dY[d]:dY[u]+1])])
    if bin(sx&sy).count("1") >= K:
        res = min(res, (r-l)*(u-d))

print(res)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from itertools import product, combinations
from operator import itemgetter
def inpl(): return tuple(map(int, input().split()))

# B以下の数-A未満の数→bisect(L, B) - bisect_left(L, A)
N, K = inpl()
X = []
Y = []
Px = []
Py = []

for i in range(N):
    x, y = inpl()
    X.append(x)
    Y.append(y)
    Px.append((x, i))
    Py.append((y, i))

X = sorted(X)
Y = sorted(Y)

dX = {x:i for i, x in enumerate(X)}
dY = {y:i for i, y in enumerate(Y)}
Px = sorted(Px)
Py = sorted(Py)

get = itemgetter(1)
res = []

for (l, r), (d, u) in product(combinations(X, 2), combinations(Y, 2)):
    sx = sum([2**i for i in map(get, Px[dX[l]:dX[r]+1])])
    sy = sum([2**i for i in map(get, Py[dY[d]:dY[u]+1])])
    if bin(sx&sy).count("1") >= K:
        res.append((r-l)*(u-d))

print(min(res))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from itertools import product, combinations
from operator import itemgetter
def inpl(): return tuple(map(int, input().split()))

N, K = inpl()
X = []
Y = []
Px = []
Py = []

for i in range(N):
    x, y = inpl()
    X.append(x)
    Y.append(y)
    Px.append((x, i))
    Py.append((y, i))

X = sorted(X)
Y = sorted(Y)

dX = {x:i for i, x in enumerate(X)}
dY = {y:i for i, y in enumerate(Y)}
Px = sorted(Px)
Py = sorted(Py)

get = itemgetter(1)
res = []

for (l, r), (d, u) in product(combinations(X, 2), combinations(Y, 2)):
    sx = set(map(get, Px[dX[l]:dX[r]+1]))
    sy = set(map(get, Py[dY[d]:dY[u]+1]))
    if len(sx.intersection(sy)) >= K:
        res.append((r-l)*(u-d))

print(min(res))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from bisect import bisect, bisect_left
from itertools import product, combinations
from operator import itemgetter
def inpl(): return tuple(map(int, input().split()))

# B以下の数-A未満の数→bisect(L, B) - bisect_left(L, A)
N, K = inpl()
X = []
Y = []
Px = []
Py = []

for i in range(N):
    x, y = inpl()
    X.append(x)
    Y.append(y)
    Px.append((x, i))
    Py.append((y, i))

X = sorted(X)
Y = sorted(Y)
Px = sorted(Px)
Py = sorted(Py)

get = itemgetter(1)
res = []

for (l, r), (d, u) in product(combinations(X, 2), combinations(Y, 2)):
    sx = set(map(get, Px[bisect_left(X, l):bisect(X, r)]))
    sy = set(map(get, Py[bisect_left(Y, d):bisect(Y, u)]))
    if len(sx.intersection(sy)) >= K:
        res.append((r-l)*(u-d))

print(min(res))

Submission status: Time Limit Exceeded

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

for i in range(N):
	x,y = map(int,input().split(" "))
	point.append((x,y))

ans = float('inf')

for num in combinations(range(N),K):
	x_min = y_min = float('inf')
	x_max = y_max = -float('inf')

	for i in num:
		x_min = min([x_min,point[i][0]])
		x_max = max([x_max,point[i][0]])
		y_min = min([y_min,point[i][1]])
		y_max = max([y_max,point[i][1]])
		
	x = x_max - x_min
	y = y_max - y_min
	ans = min([ans,x*y])

print(ans)

Submission status: Time Limit Exceeded

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

def judge(minX,minY,maxX,maxY):
        count=0
        for p in xy:
                if minX<=p[0] and p[0]<=maxX and minY<=p[1] and p[1]<=maxY:
                        #print(p)
                        count+=1
        if count>=K:
                #print("a")
                return (maxX-minX)*(maxY-minY)
        else:
                return INF

#辺集合の生成する長方形の四辺を計算
def calc(edges):
        minX=INF
        minY=INF
        maxX=-INF
        maxY=-INF
        for edge in edges:
                if edge[0]<minX:
                        minX=edge[0]
                if edge[0]>maxX:
                        maxX=edge[0]
                if edge[1]<minY:
                        minY=edge[1]
                if edge[1]>maxY:
                        maxY=edge[1]
        return judge(minX,minY,maxX,maxY)


#辺集合を作って、計算に回す
def produceEdges(edges,last):
        #print(edges)
        #四辺が決まってたら、計算に回す
        if len(edges)==min(4,K):
                return calc(edges)
        #決まってないなら、辺集合を生成
        ans=INF
        for i in range(last,N):
                edges.append(xy[i])
                ans=min(ans,produceEdges(edges,i+1))
                edges.pop(-1)
        return ans

print(produceEdges([],0))

Submission status: Time Limit Exceeded

Solution code:
import itertools
n, k = map(int, input().split())
p = []

vy = set()
vx = set()
for i in range(n):
    x, y = map(int, input().split())
    p.append((y,x))
    vy.add(y)
    vx.add(x)
vy = sorted(list(vy))
vx = sorted(list(vx))

min_area = float('inf')


for y in itertools.combinations(vy, r=2):
    for x in itertools.combinations(vx, r=2):
        cnt = 0
        for i in range(n):
            if y[0] <= p[i][0] <= y[1] and x[0] <= p[i][1] <= x[1]:
                cnt += 1
        if cnt >= k:
            min_area = min(min_area, (y[1]-y[0]) * (x[1]-x[0]))
print(min_area)