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

N,K=list(map(int,raw_input().split()))
a = []
for i in range(N):
    a.append(map(int,raw_input().split()))
#print "# a"
#print a


b=[]
for i in range(N):
	for j in range(N):
		#print i,j,a[i][0],a[j][1]
		b.append([a[i][0],a[j][1]])

#print "# b"
#print b
#print len(b)


c=[]
c=list(itertools.combinations(b, 2))
#print "# c"
#print c
#print len(c)

area=[]
for i in range(len(c)):
	area.append(abs(c[i][0][0]-c[i][1][0])*abs(c[i][0][1]-c[i][1][1]))

#print area

for i in range(len(c)):
	cnt=0
	x1=c[i][0][0]
	x2=c[i][1][0]
	y1=c[i][0][1]
	y2=c[i][1][1]
	#print x1,y1,x2,y2
	for j in range(len(a)):
		#print a[j][0],a[j][1]
		if (a[j][0]>=x1 and a[j][0]<=x2) or (a[j][0]>=x2 and a[j][0]<=x1):
			if (a[j][1]>=y1 and a[j][1]<=y2) or (a[j][1]>=y2 and a[j][1]<=y1):
				cnt+=1
	#print cnt
	if cnt<K:
		area[i]=-1

#print area

min=0
for i in range(len(area)):
	if area[i]==-1:
		continue
	elif min==0:
		min=area[i]
	elif area[i]<min:
		min=area[i]

print min

Submission status: Time Limit Exceeded

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

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


S = 99999999999999999999
for xi in range(N):
    for xj in range(N):
        for yi in range(N):
            for yj in range(N):
                l = abs(co[xi][0] - co[xj][0])
                m = abs(co[yi][1] - co[yj][1])
                a = min(co[xi][0], co[xj][0])
                b = max(co[xi][0], co[xj][0])
                c = min(co[yi][1], co[yj][1])
                d = max(co[yi][1], co[yj][1])
                num = 0
                for i in range(N):
                    if (a <= co[i][0] <= b) and (c <= co[i][1] <= d):
                        num += 1
                if num >= K:
                    p = l*m
                    S = min(S,p)
print(S)

Submission status: Time Limit Exceeded

Solution code:
def main():
    N, K = map(int, input().split())
    XY = (tuple(map(int, input().split())) for _ in [0] * N)

    x = [0] * N
    y = [0] * N
    for i, (j, k) in enumerate(XY):
        x[i] = j
        y[i] = k

    ans = float('inf')
    for xi in range(N):
        for xj in range(N):
            if x[xi] >= x[xj]: continue
            for yi in range(N):
                for yj in range(N):
                    if y[yi] >= y[yj]: continue
                    cnt = 0
                    for i in range(N):
                        if x[xi] <= x[i] <= x[xj] and y[yi] <= y[i] <= y[yj]:
                            cnt += 1
                    if cnt >= K:
                        ans = min(ans, (x[xj] - x[xi]) * (y[yj] - y[yi]))

    print(ans)

main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    N, K = map(int, input().split())
    XY = (tuple(map(int, input().split())) for _ in [0] * N)

    x = [0] * N
    y = [0] * N
    for i, (j, k) in enumerate(XY):
        x[i] = j
        y[i] = k

    ans = float('inf')
    for xi in range(N):
        for xj in range(N):
            for yi in range(N):
                for yj in range(N):
                    cnt = 0
                    for i in range(N):
                        if x[xi] <= x[i] <= x[xj] and y[yi] <= y[i] <= y[yj]:
                            cnt += 1
                    if cnt >= K:
                        ans = min(ans, (x[xj] - x[xi]) * (y[yj] - y[yi]))

    print(ans)

main()

Submission status: Time Limit Exceeded

Solution code:
inputs = input().split()
N = int(inputs[0])
K = int(inputs[1])

input_list = []

for i in range(N):
    inputs = input().split()
    x = int(inputs[0])
    y = int(inputs[1])
    input_list.append([x, y])

ans = 10 ** 19 
for upper in input_list:
    for bottom in input_list:
        for left in input_list:
            for right in input_list:
                count = 0
                for inner in input_list: 
                    if upper[1] >= inner[1] and bottom[1] <= inner[1] and left[0] <= inner[0] and right[0] >= inner[0] :
                        count += 1
                if count >= K:
                    if ans > (upper[1] - bottom[1]) * (right[0]-left[0]):
                        ans = (upper[1] - bottom[1]) * (right[0]-left[0])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def D_Axis_Parallel_Rectangle(N, K, P):
    x = [0 for _ in range(N)]  # 点のx座標
    y = [0 for _ in range(N)]  # y座標
    x_array = [0 for _ in range(N)]
    y_array = [0 for _ in range(N)]
    for i in range(N):
        x[i] = P[i][0]
        y[i] = P[i][1]
        x_array[i] = x[i]
        y_array[i] = y[i]

    x_array = sorted(x_array)
    y_array = sorted(y_array)

    # すべての点を内部に含む、最大の面積を持つ矩形が初期値
    ans = (x_array[N - 1] - x_array[0]) * (y_array[N - 1] - y_array[0])

    # 全探索
    for xi in range(0, N, 1):
        for xj in range(xi + 1, N, 1):
            for yi in range(0, N, 1):
                for yj in range(yi + 1, N, 1):
                    num = 0
                    left = x_array[xi]
                    right = x_array[xj]
                    bottom = y_array[yi]
                    upper = y_array[yj]

                    for i in range(N):
                        if(left <= x[i] and x[i] <= right and bottom <= y[i] and y[i] <= upper):
                            num += 1
                    if num >= K:
                        ans = min(ans, (right - left) * (upper - bottom))
    return ans

N,K = [int(i) for i in input().split()]
P = [[int(i) for i in input().split()] for j in range(N)]
print(D_Axis_Parallel_Rectangle(N, K, P))

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations

def solve():
    n, k = map(int, input().split())
    xs, ys = [], [] 
    for _ in range(n):
        x, y = map(int, input().split())
        xs.append(x)
        ys.append(y)
    ans = ((10 ** 9) * (10 ** 9)) ** 2
    sxs, sys = set(xs), set(ys)
    for x1 in sxs:
        for x2 in sxs:
            for y1 in sys:
                for y2 in sys:
                    minX, maxX = sorted([x1, x2])
                    minY, maxY = sorted([y1, y2])
                    cnt = 0
                    for i in range(n):
                        if minX <= xs[i] <= maxX and minY <= ys[i] <= maxY:
                            cnt += 1
                    if cnt >= k:
                        ans = min(ans, (maxX - minX) * (maxY - minY))
    print(ans)

if __name__=="__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations

def solve():
    n, k = map(int, input().split())
    xs, ys = [], [] 
    for _ in range(n):
        x, y = map(int, input().split())
        xs.append(x)
        ys.append(y)
    ans = ((10 ** 9) * (10 ** 9)) ** 2
    for x1 in xs:
        for x2 in xs:
            for y1 in ys:
                for y2 in ys:
                    minX, maxX = sorted([x1, x2])
                    minY, maxY = sorted([y1, y2])
                    cnt = 0
                    for i in range(n):
                        if minX <= xs[i] <= maxX and minY <= ys[i] <= maxY:
                            cnt += 1
                    if cnt >= k:
                        ans = min(ans, (maxX - minX) * (maxY - minY))
    print(ans)

if __name__=="__main__":
    solve()

Submission status: Time Limit Exceeded

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

import sys
import itertools


def main():
    n, k = [int(x) for x in sys.stdin.readline().rstrip().split(" ")]

    data = []
    x_data = []
    y_data = []
    for line in sys.stdin:
        x, y = [int(i) for i in line.rstrip().split(" ")]
        data.append((x, y))
        x_data.append(x)
        y_data.append(y)

    s_data = []
    for x, y in itertools.product(x_data, y_data):
        for x2, y2 in itertools.product(x_data, y_data):
            x_max = max(x, x2)
            x_min = min(x, x2)
            y_max = max(y, y2)
            y_min = min(y, y2)

            s = (x_max - x_min) * (y_max - y_min)
            s_data.append(((x_min, x_max, y_min, y_max), s))
    
    for (x_min, x_max, y_min, y_max), s in sorted(s_data, key=lambda x: x[1]):
        point_count = len([True for x, y in data if x_min <= x <= x_max and y_min <= y <= y_max])
        if point_count >= k:
            print(s)
            return


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, Counter
from itertools import combinations
INF = float("inf")


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

    ans = INF
    for i in range(N):
        for j in range(N):
            for k in range(N):
                for l in range(N):
                    y1, y2, x1, x2 = points[i][0], points[j][0], points[k][1], points[l][1]

                    n = 0
                    for p in points:
                        n += y1 <= p[0] <= y2 and x1 <= p[1] <= x2
                    if n >= K:
                        ans = min(ans, abs(y1 - y2) * abs(x1 - x2))
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

import sys
import itertools


def main():
    n, k = [int(x) for x in sys.stdin.readline().rstrip().split(" ")]

    data = []
    for line in sys.stdin:
        x, y = [int(i) for i in line.rstrip().split(" ")]
        data.append((x, y))

    s_min = float("inf")
    for d in itertools.combinations(data, k):
        x_max = max(d, key=lambda x: x[0])[0]
        x_min = min(d, key=lambda x: x[0])[0]
        y_max = max(d, key=lambda x: x[1])[1]
        y_min = min(d, key=lambda x: x[1])[1]

        s = (x_max - x_min) * (y_max - y_min)
        s_min = min(s, s_min)

    print(s_min)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations

def solve():
    n, k = map(int, input().split())
    xs, ys = [], [] 
    for _ in range(n):
        x, y = map(int, input().split())
        xs.append(x)
        ys.append(y)
    ans = ((10 ** 9) * (10 ** 9)) ** 2
    for x1 in xs:
        for x2 in xs:
            for y1 in ys:
                for y2 in ys:
                    minX, maxX = sorted([x1, x2])
                    minY, maxY = sorted([y1, y2])
                    cnt = 0
                    for i in range(n):
                        if minX <= xs[i] <= maxX and minY <= ys[i] <= maxY:
                            cnt += 1
                    if cnt >= k:
                        ans = min(ans, (maxX - minX) * (maxY - minY))
    print(ans)

if __name__=="__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations

def solve():
    n, k = map(int, input().split())
    points = []
    for _ in range(n):
        a, b = map(int, input().split())
        points.append([a, b])
    ans = ((10 ** 9) * (10 ** 9)) ** 2
    kmin = min(k, 4)
    for elem in permutations(points, kmin):
        xs = [elem[i][0] for i in range(kmin)]
        ys = [elem[i][1] for i in range(kmin)]
        maxX, minX = max(xs), min(xs)
        maxY, minY = max(ys), min(ys)
        cnt = 0
        for point in points:
            if minX <= point[0] <= maxX and minY <= point[1] <= maxY:
                cnt += 1
        if cnt >= k:
            ans = min(ans, (maxX - minX) * (maxY - minY))
    print(ans)

if __name__=="__main__":
    solve()

Submission status: Time Limit Exceeded

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

points=[()]*N
points_x=[None]*N
points_y=[None]*N
for i in range(N):
    x,y=map(int,raw_input().split(' '))
    points[i]=(x,y)
    points_x[i]=x
    points_y[i]=y

def inc(p1,p2):
    if p1[0]<p2[0]:
        x_min=p1[0]
        x_lrg=p2[0]
    else:
        x_min=p2[0]
        x_lrg=p1[0]

    if p1[1]<p2[1]:
        y_min=p1[1]
        y_lrg=p2[1]
    else:
        y_min=p2[1]
        y_lrg=p1[1]
        
    k=0
    for i in range(N):
        x,y=points[i]
        if x_min<=x<=x_lrg and y_min<=y<=y_lrg:
            k+=1
    return k

s=float('inf')
for x1 in set(points_x):
    for x2 in set(points_x):
        if x1==x2:
            continue
        for y1 in set(points_y):
            for y2 in set(points_y):
                if y1==y2:
                    continue
                x_min=min(x1,x2)
                x_lrg=max(x1,x2)
                y_min=min(y1,y2)
                y_lrg=max(y1,y2)
                t=(x_lrg-x_min)*(y_lrg-y_min)
                if(inc((x_min,y_min),(x_lrg,y_lrg))>=K and t<s):
                    s=t
print s

Submission status: Time Limit Exceeded

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

ptsX = sorted(points, key=lambda t: t[0])
ptsY = sorted(points, key=lambda t: t[1])

ans = float('inf')
for sideL in range(N):
    for sideR in range(sideL + 1, N)[::-1]:

        setX = set(ptsX[sideL:sideR + 1])
        if len(setX) < K: break

        lenX = ptsX[sideR][0] - ptsX[sideL][0]

        for sideB in range(N):
            for sideT in range(sideB + 1, N)[::-1]:
                
                setY = set(ptsY[sideB:sideT + 1])
                if len(setY) < K: break

                num = len(setX & setY)
                if num < K: break

                lenY = ptsY[sideT][1] - ptsY[sideB][1]
                area = lenX * lenY

                if num == K:
                    ans = min(ans, area)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
from itertools import combinations
range = xrange
N, K = map(int, raw_input().split(' '))
O = sorted(
    [tuple(map(long, raw_input().split(' '))) for _ in range(N)],
    key=lambda x: x[0])

print min((max(x for x, _ in comb) - min(x for x, _ in comb)) *
          (max(y for _, y in comb) - min(y for _, y in comb))
          for comb in combinations(O, K))

Submission status: Time Limit Exceeded

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

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

import itertools

result = []
for pattern in itertools.combinations(xy, k):
    result.append(
            (max(pattern, key=lambda x: x[0])[0] - min(pattern, key=lambda x: x[0])[0]) *
            (max(pattern, key=lambda x: x[1])[1] - min(pattern, key=lambda x: x[1])[1])
            )
print(min(result))

Submission status: Time Limit Exceeded

Solution code:
s = input().split(" ")
N = int(s[0])
K = int(s[1])
x = []
xs = []
y = []
ys = []
for i in range(N):
    s = input().split(" ")
    x.append(int(s[0]))
    y.append(int(s[1]))
    xs.append(int(s[0]))
    ys.append(int(s[1]))
xs.sort()
ys.sort()
res = 4 * 10**18
i = 0
while i < N:
    j = i + 1
    while j < N:
        k = 0
        while k < N:
            l = k + 1
            while l < N:
                cnt = 0
                for m in range(N):
                    if xs[i] <= x[m] and x[m] <= xs[j] and ys[k] <= y[m] and y[m] <= ys[l]:
                        cnt += 1
                if cnt >= K:
                    res = min(res, (xs[j] - xs[i]) * (ys[l] - ys[k]))
                l += 1
            k += 1
        j += 1
    i += 1
print(res)

Submission status: Time Limit Exceeded

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

ptsX = sorted(points, key=lambda t: t[0])
ptsY = sorted(points, key=lambda t: t[1])

ans = float('inf')
for sideL in range(N):
    for sideR in range(sideL + 1, N):
        for sideB in range(N):
            for sideT in range(sideB + 1, N):

                area = (ptsX[sideR][0] - ptsX[sideL][0]) * (ptsY[sideT][1] - ptsY[sideB][1])

                setX = set(ptsX[sideL:sideR + 1])
                setY = set(ptsY[sideB:sideT + 1])
                num = len(setX & setY)

                if num == K:
                    ans = min(ans, area)

print(ans)

Submission status: Time Limit Exceeded

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

xDict = {}
index = 0
for x,y in points1:
	if index in xDict:
		if xDict[index] != x:
			index += 1
			xDict[index] = x
	else:
		xDict[index] = x

yDict = {}
index = 0
for y in points2:
	if index in yDict:
		if yDict[index] != y:
			index += 1 
			yDict[index] = y
	else:
		yDict[index] = y

nPoints = [[0 for j in range(len(yDict))] for i in range(len(xDict))]

for kx,vx in xDict.items():
	for ky,vy in yDict.items():
		exists = 1 if (vx,vy) in points1 else 0
		if kx == 0 and ky == 0:
			nPoints[kx][ky] += exists
		elif kx == 0 and ky > 0:
			nPoints[kx][ky] += nPoints[kx][ky-1] + exists
		elif kx > 0 and ky == 0:
			nPoints[kx][ky] += nPoints[kx-1][ky] + exists
		else:
			nPoints[kx][ky] += nPoints[kx-1][ky] + nPoints[kx][ky-1] - nPoints[kx-1][ky-1] + exists

ans = -1
for x1 in range(len(xDict)):
	for x2 in range(x1+1):
		for y1 in range(len(yDict)):
			for y2 in range(y1+1):
				point = nPoints[x1][y1]
				if x2 > 0:
					point -= nPoints[x2-1][y1]
				if y2 > 0:
					point -= nPoints[x1][y2-1]
				if x2 > 0 and y2 > 0:
					point += nPoints[x2-1][y2-1]
				if point >= K:
					area = (xDict[x1]-xDict[x2]) * (yDict[y1]-yDict[y2])
					if ans < 0:
						ans = area
					else:
						ans = min(ans, area)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
n, k = [int(x) for x in raw_input().split()]
l = []
d = {}
for x in xrange(n):
	temp_x, temp_y = [int(x) for x in raw_input().split()]
	#sq_sum = temp_x ** 2 + temp_y ** 2
	l.append((temp_x, temp_y))
o = []
s = 1
minimum = 0
for t in combinations(l, k):
	min_x, min_y, max_x, max_y = 2000000000L, 2000000000L, -2000000000L, -2000000000L
	for temp_t in t:
		temp_x, temp_y = temp_t
		if temp_x < min_x:
			min_x = temp_x
		if temp_y < min_y:
			min_y = temp_y
		if temp_x > max_x:
			max_x = temp_x
		if temp_y > max_y:
			max_y = temp_y
	square = (max_x - min_x) * (max_y - min_y)
	if s:
		minimum = square
		s = 0
	if square < minimum:
		minimum = square
print minimum

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python

import sys
from itertools import permutations


def rangeof(arr):
    return max(arr) - min(arr)


def within(a, aa):
    if(aa[0] <= a and a <= aa[1]):
        return True
    if(aa[1] <= a and a <= aa[0]):
        return True

    return False


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

x = []
y = []

for i in range(0, N):
    (x_, y_) = [int(x) for x in input().split(" ")]
    x.append(x_)
    y.append(y_)

minArea = float("inf")
for xcand in permutations(x, 2):
    for ycand in permutations(y, 2):
        pix_in_the_box = 0
        for i in range(0, N):
            if(within(x[i], xcand) and within(y[i], ycand)):
                pix_in_the_box += 1
        if(pix_in_the_box >= K):
            area = abs(rangeof(xcand) * rangeof(ycand))
            if(minArea > area):
                minArea = area

print(minArea)

Submission status: Time Limit Exceeded

Solution code:
def i1():
 return int(input())
def i2():
 return [int(i) for i in input().split()]
[n,k]=i2()
x=[]
y=[]
z=[]
for i in range(n):
 z.append(i2())
 x.append(z[-1][0])
 y.append(z[-1][1])
x.sort()
y.sort()
a=float("inf")
for i in range(n):
 for j in range(i,n):
  for kk in range(n):
    for l in range(kk,n):
      if len(list(filter(lambda xx:x[i]<=xx[0]<=x[j] and y[kk]<=xx[1]<=y[l] , z)))==k:
       a=min(a,(x[j]-x[i])*(y[l]-y[kk]))  
print(a)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations

N, K = map(int, input().split())
point = {i: list(map(int, input().split())) for i in range(N)}

comb_list = list(combinations(range(N), K))
comb_list_point = [[point[i] for i in comb_list[j]] for j in range(len(comb_list))]

answer = float('inf')
for comb in comb_list_point:
    x = [row[0] for row in comb]
    y = [row[1] for row in comb]
    area = (max(x) - min(x)) * (max(y) - min(y))
    answer = area if area < answer else answer

print(answer)

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations
n, k = [int(x) for x in raw_input().split()]
l = []
d = {}
for x in xrange(n):
	temp_x, temp_y = [int(x) for x in raw_input().split()]
	#sq_sum = temp_x ** 2 + temp_y ** 2
	l.append((temp_x, temp_y))
o = []
for t in permutations(l, k):
	min_x, min_y, max_x, max_y = 2000000000L, 2000000000L, -2000000000L, -2000000000L
	for temp_t in t:
		temp_x, temp_y = temp_t
		if temp_x < min_x:
			min_x = temp_x
		if temp_y < min_y:
			min_y = temp_y
		if temp_x > max_x:
			max_x = temp_x
		if temp_y > max_y:
			max_y = temp_y
	square = (max_x - min_x) * (max_y - min_y)
	o.append(square)
o.sort()
print o[0]

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python

import sys
from itertools import permutations


def rangeof(arr):
    return max(arr) - min(arr)


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

x = []
y = []

for i in range(0, N):
    (x_, y_) = [int(x) for x in input().split(" ")]
    x.append(x_)
    y.append(y_)

minArea = float("inf")
for cand in permutations(range(N), K):
    xx = rangeof([x[i] for i in cand])
    yy = rangeof([y[i] for i in cand])
    area = abs(xx * yy)
    if(minArea > area):
        minArea = area

print(minArea)

Submission status: Time Limit Exceeded

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

pts = []
for _ in range(n):
    (x, y) = map(int, input().split(" "))
    pts += [(x, y)]

pts.sort()

res = float("inf")
for a in pts:
    for b in pts:
        for c in pts:
            for d in pts:
                l = a[0]
                r = b[0]
                f = c[1]
                t = d[1]
                
                if not l < r or not f < t:
                    continue
        
                num = 0
                for x in pts:
                    if l <= x[0] <= r and f <= x[1] <= t:
                        num += 1
        
                if num >= k:
                    res = min(res, abs(r-l)*abs(t-f))

print(res)

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, raw_input().split())
ps = []
for i in xrange(N):
  ps.append(map(int, raw_input().split()))

xsorted = zip(*sorted(ps, key=lambda p: p[0]))[0]
ysorted = zip(*sorted(ps, key=lambda p: p[1]))[1]

ans = float('inf')
for i in xrange(N):
  bottom = ysorted[i]
  for j in xrange(i+K-1, N):
    top = ysorted[j]
    answered = False
    for k in xrange(N):
      right = xsorted[k]
      for l in xrange(k+K-1, N):
        left = xsorted[l]
        c = 0
        for a in xrange(N):
          if right <= ps[a][0] <= left and bottom <= ps[a][1] <= top:
            c += 1
            if c >= K: break
        else:
          continue
        area = (left - right) * (top - bottom)
        if area < ans:
          ans = area
        break
      else:
        continue
      answered = True

print ans

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
INF = float("inf")


memo1 = {}
memo2 = {}

def ok(y1, y2, x1, x2, yd, yd2, xd, xd2, K):
    global memo1, memo2
    if (y1, y2) in memo1:
        a, b = memo1[(y1, y2)]
    else:
        a = yd2[y1]
        b = yd[y2]
        memo1[(y1, y2)] = (a, b)
    y = b.difference(a)

    if (x1, x2) in memo2:
        c, d =memo2[(x1, x2)]
    else:
        c = xd2[x1]
        d = xd[x2]
        memo2[(x1, x2)] = (c, d)

    x = d.difference(c)
    # print(a, b, c, d)
    # print(y, x)

    n = len(y & x)

    return n >= K


def main():
    import time
    N, K = map(int, input().split())
    f = []
    ys, xs = [], []
    for i in range(N):
        x, y = map(int, input().split())
        f.append((y, x))
        ys.append((y, i))
        xs.append((x, i))

    ys.sort()
    yd = defaultdict(set)
    yd2 = defaultdict(set)
    old = set()
    for y, i in ys:
        yd2[y] = old.copy()
        old.add(i)
        yd[y] = old.copy()

    xs.sort()
    xd = defaultdict(set)
    xd2 = defaultdict(set)
    old = set()
    for x, i in xs:
        xd2[x] = old.copy()
        old.add(i)
        xd[x] = old.copy()

    ans = INF

    # print(yd)
    # print(xd)
    #
    # print(ok(1, 4, 1, 8, yd, yd2, xd, xd2, K))
    for i, j in combinations(range(N), 2):
        for k, l in combinations(range(N), 2):
            a, b, c, d = ys[i], ys[j], xs[k], xs[l]
            y1 = min([a[0], b[0]])
            y2 = max([a[0], b[0]])

            x1 = min([c[0], d[0]])
            x2 = max([c[0], d[0]])

            kkk = abs(x1 - x2) * abs(y1 - y2)
            if kkk < ans:
                # print(i, j)
                # print(x1, x2, abs(x1 - x2))
                # print(y1, y2, abs(y1 - y2))
                # print(ok(y1, y2, x1, x2, yd, yd2, xd, xd2, K))
                if ok(y1, y2, x1, x2, yd, yd2, xd, xd2, K):
                    ans = kkk

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, raw_input().split())
ps = []
for i in xrange(N):
  ps.append(map(int, raw_input().split()))

xsorted = sorted(ps, key=lambda p: p[0])
ysorted = sorted(ps, key=lambda p: p[1])

ans = float('inf')
for i in xrange(N):
  bottom = ysorted[i][1]
  for j in xrange(i+K-1, N):
    top = ysorted[j][1]
    for k in xrange(N):
      right = xsorted[k][0]
      for l in xrange(k+K-1, N):
        left = xsorted[l][0]
        c = 0
        for a in xrange(N):
          if right <= ps[a][0] <= left and bottom <= ps[a][1] <= top:
            c += 1
            if c >= K: break
        else:
          continue
        area = (left - right) * (top - bottom)
        if area < ans:
          ans = area

print ans

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
INF = float("inf")



def ok(y1, y2, x1, x2, yd, yd2, xd, xd2, K):

    a = yd2[y1]
    b = yd[y2]
    y = b.difference(a)
    c = xd2[x1]
    d = xd[x2]
    x = d.difference(c)
    # print(a, b, c, d)
    # print(y, x)

    n = len(y & x)

    return n >= K


def main():
    N, K = map(int, input().split())
    f = []
    ys, xs = [], []
    for i in range(N):
        x, y = map(int, input().split())
        f.append((y, x))
        ys.append((y, i))
        xs.append((x, i))

    ys.sort()
    yd = defaultdict(set)
    yd2 = defaultdict(set)
    old = set()
    for y, i in ys:
        yd2[y] = old.copy()
        old.add(i)
        yd[y] = old.copy()

    xs.sort()
    xd = defaultdict(set)
    xd2 = defaultdict(set)
    old = set()
    for x, i in xs:
        xd2[x] = old.copy()
        old.add(i)
        xd[x] = old.copy()

    ans = INF

    # print(yd)
    # print(xd)
    #
    # print(ok(1, 4, 1, 8, yd, yd2, xd, xd2, K))
    for i, j in combinations(range(N), 2):
        for k, l in combinations(range(N), 2):
            a, b, c, d = ys[i], ys[j], xs[k], xs[l]
            y1 = min([a[0], b[0]])
            y2 = max([a[0], b[0]])

            x1 = min([c[0], d[0]])
            x2 = max([c[0], d[0]])

            # print(i, j)
            # print(x1, x2, abs(x1 - x2))
            # print(y1, y2, abs(y1 - y2))
            # print(ok(y1, y2, x1, x2, yd, yd2, xd, xd2, K))
            if ok(y1, y2, x1, x2, yd, yd2, xd, xd2, K):
                ans = min(ans, abs(x1 - x2) * abs(y1 - y2))

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations

N, K = map(int, input().split())
point = {i: list(map(int, input().split())) for i in range(N)}

comb_list = list(combinations(range(N), K))

answer = float('inf')
for comb in comb_list:
    minimum_x = min([point[i][0] for i in comb])
    minimum_y = min([point[i][1] for i in comb])
    maximum_x = max([point[i][0] for i in comb])
    maximum_y = max([point[i][1] for i in comb])

    area = (maximum_x - minimum_x) * (maximum_y - minimum_y)
    answer = area if area < answer else answer

print(answer)

Submission status: Time Limit Exceeded

Solution code:
s = input().split(" ")
N = int(s[0])
K = int(s[1])
x = []
y = []
for i in range(N):
    s = input().split(" ")
    x.append(int(s[0]))
    y.append(int(s[1]))
res = 4 * 10**18
i = 0
while i < N:
    j = i + 1
    while j < N:
        k = 0
        while k < N:
            l = k + 1
            while l < N:
                x0 = min(x[i], x[j])
                x1 = max(x[i], x[j])
                y0 = min(y[k], y[l])
                y1 = max(y[k], y[l])
                cnt = 0
                for m in range(N):
                    if x0 <= x[m] and x[m] <= x1 and y0 <= y[m] and y[m] <= y1:
                        cnt += 1
                if cnt >= K:
                    res = min(res, (x1 - x0) * (y1 - y0))
                l += 1
            k += 1
        j += 1
    i += 1
print(res)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
n,k = map(int,stdin.readline().split())
a = []
for i in xrange(n):
 a.append(map(int,stdin.readline().split()))
def solve(i,j,u,v):
 cnt = 0
 minx = min(a[i][0],a[j][0])
 maxx =  max(a[i][0],a[j][0])
 miny = min(a[i][1],a[j][1])
 maxy = max(a[i][1],a[j][1])
 
 minx1 = min(a[u][0],a[v][0])
 maxx1 =  max(a[u][0],a[v][0])
 miny1 = min(a[u][1],a[v][1])
 maxy1 = max(a[u][1],a[v][1])
 
 minx = min(minx,minx1)
 miny = min(miny,miny1)
 maxx = max(maxx,maxx1)
 maxy = max(maxy,maxy1)
 #print "solving",i,j,u,v,minx,maxx,miny,maxy
 for m in xrange(n):
  if a[m][0]>=minx and a[m][0]<=maxx and a[m][1]>=miny and a[m][1]<=maxy:
   cnt+=1
 #print "has",cnt
 if cnt>=k:
  return (maxx-minx)*(maxy-miny)
 return 10**100
ans = 10**50
for i in xrange(n):
 for j in xrange(n):
  for u in xrange(n):
   for v in xrange(n):
    ans = min(ans,solve(i,j,u,v))
print ans