Problem:


Score : 400 points

Problem Statement

We have N points in a two-dimensional plane.

The coordinates of the i-th point (1 \leq i \leq N) are (x_i,y_i).

Let us consider a rectangle whose sides are parallel to the coordinate axes that contains K or more of the N points in its interior.

Here, points on the sides of the rectangle are considered to be in the interior.

Find the minimum possible area of such a rectangle.  

Constraints

2 \leq K \leq N \leq 50 

-10^9 \leq x_i,y_i \leq 10^9 (1 \leq i \leq N) 

x_i≠x_j (1 \leq i<j \leq N) 

y_i≠y_j (1 \leq i<j \leq N) 

All input values are integers. (Added at 21:50 JST)  

Input

Input is given from Standard Input in the following format:  

N K  
x_1 y_1
:  
x_{N} y_{N}

Output

Print the minimum possible area of a rectangle that satisfies the condition.  

Sample Input 1

4 4
1 4
3 3
6 2
8 1

Sample Output 1

21

One rectangle that satisfies the condition with the minimum possible area has the following vertices: (1,1), (8,1), (1,4) and (8,4).

Its area is (8-1) × (4-1) = 21.  

Sample Input 2

4 2
0 0
1 1
2 2
3 3

Sample Output 2

1

Sample Input 3

4 3
-1000000000 -1000000000
1000000000 1000000000
-999999999 999999999
999999999 -999999999

Sample Output 3

3999999996000000001

Watch out for integer overflows.  



Sample input:
4 4
1 4
3 3
6 2
8 1


Sample output:
21

Submission status: Time Limit Exceeded

Solution code:

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

xy_list = []
for i in range(N):
    xy_list.append(list(map(int,input().split())))
min_s = 10**28    
for i in range(N):
    for j in range(i+1,N):
        for k in range(N):
            for l in range(k+1,N):
                max_x = max(xy_list[i][0],xy_list[j][0])
                min_x = min(xy_list[i][0],xy_list[j][0])
                max_y = max(xy_list[k][1],xy_list[l][1])
                min_y = min(xy_list[k][1],xy_list[l][1])
                count = 0
                for m in range(N):
                    if max_x>=xy_list[m][0] and min_x<=xy_list[m][0] and max_y>=xy_list[m][1] and min_y<=xy_list[m][1]:
                        count+=1
                if count==K:
                    min_s = min((max_x-min_x)*(max_y-min_y),min_s)

print(min_s)

Submission status: Time Limit Exceeded

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

x = [0 for _ in range(n)]
y = [0 for _ in range(n)]
for i in range(n):
    x[i], y[i] = map(int, input().split())

min_x = min(x)
min_y = min(y)
for i in range(n):
    x[i] -= min_x
    y[i] -= min_y

sx = sorted(x)
sy = sorted(y)

if n == k:
    print(sx[n - 1] * sy[n - 1])
    exit()

a = 0
b = 1
ans = sx[n - 1] * sy[n - 1]
temp = 0
for p in range(n):
    for q in range(p + 1, n):
        for a in range(n):
            for b in range(a + 1, n):
                count = 0
                for i in range(n):
                    if sx[a] <= x[i] <= sx[b] and sy[p] <= y[i] <= sy[q]:
                        count += 1
                if count >= k:
                    ans = min(ans, (sx[b] - sx[a]) * (sy[q] - sy[p]))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, k = [int(_) for _ in input().split()]
x, y = [], []
for _ in range(n):
    temp = [int(_) for _ in input().split()]
    x.append(temp[0])
    y.append(temp[1])
xs = sorted(x)
ys = sorted(y)

answer = 4 * 10**18
for i0 in range(n):
    for j0 in range(i0 + 1, n):
        xi = xs[i0]
        xj = xs[j0]
        for i1 in range(n):
            for j1 in range(i1 + 1, n):
                yi = ys[i1]
                yj = ys[j1]
                c = 0
                for l in range(n):
                    if xi <= x[l] and x[l] <= xj and yi <= y[l] and y[l] <= yj:
                        c += 1
                s = (xj - xi) * (yj - yi)
                if s < answer and c >= k:
                    answer = s

print(answer)

Submission status: Time Limit Exceeded

Solution code:
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()

S = float("inf")
for i in range(N-1): #左辺の候補
    for j in range(i+1, N): #右辺
        for k in range(N-1): #下辺
            for l in range(k+1, N):
                Inside = 0
                for p in range(N):
                    if X[i] <= P[p][0] <= X[j] and Y[k] <= P[p][1] <= Y[l]:
                        Inside += 1
                if Inside >= K:
                    S = min(S, (X[j]-X[i]) * (Y[l]-Y[k]))
print(S)

Submission status: Time Limit Exceeded

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

X = sorted(X)
Y = sorted(Y)
num = float("inf")
for i in range(N - 1):
    for j in range(i + 1, N):
        for k in range(N - 1):
            for l in range(k + 1, N):
                tmp = 0
                for m in range(N):
                    if X[i] <= D[m][0] <= X[j] and Y[k] <= D[m][1] <= Y[l]:
                        tmp += 1
                if tmp >= K:
                    num = min(num, (X[j] - X[i]) * (Y[l] - Y[k]))

print(num)

Submission status: Time Limit Exceeded

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

res=[]
for i in range(n):
    for j in range(n):
        for a in range(n):
            for b in range(n):
                l=min(x[i],x[j])
                r=max(x[i],x[j])
                d=min(y[a],y[b])
                u=max(y[a],y[b])
                tk=0
                for t in xy:
                    if l<=t[0]<=r and d<=t[1]<=u:
                        tk+=1
                if tk>=k:
                    res.append((r-l)*(u-d))
print(min(res))

Submission status: Time Limit Exceeded

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

ans = float('inf')
for i in range(n):
    for j in range(i, n):
        for l in range(n):
            for m in range(l, n):
                pos.sort(key=lambda x: x[0])
                xmin = pos[i][0]
                xmax = pos[j][0]
                pos.sort(key=lambda x: x[1])
                ymin = pos[l][1]
                ymax = pos[m][1]
                count = 0
                for x, y in pos:
                    if xmin <= x and x <= xmax and ymin <= y and y <= ymax:
                        count += 1
                if count >= k:
                    ans = min(ans, (xmax - xmin)*(ymax - ymin))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import product

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

ans = float('inf')
for i, j, k, l in product(range(N), repeat=4):
    x1, x2 = x[i], x[j]
    y1, y2 = y[k], y[l]
    cnt = 0
    for xx, yy in zip(x, y):
        if x1 <= xx <= x2 and y1 <= yy <= y2:
            cnt += 1
    if cnt >= K:
        s = abs(x1 - x2) * abs(y1 - y2)
        ans = min(ans, s)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from itertools import combinations

n,k = map(int, input().split())
pary = []
xary = []
yary = []
for _ in range(n):
    x,y = map(int, input().split())
    pary.append([x,y])
    xary.append(x)
    yary.append(y)

ret = None
for x in combinations(range(n),2):
    for y in combinations(range(n),2):
        xc = [xary[x[0]], xary[x[1]]]
        yc = [yary[y[0]], yary[y[1]]]
        cnt = 0
        for p in pary:
            if (min(xc[0],xc[1])<=p[0]<=max(xc[0],xc[1])
                and min(yc[0],yc[1])<=p[1]<=max(yc[0],yc[1])):
                cnt += 1
            if cnt==k:
                break
        if cnt>=k:
            s = abs(xc[0]-xc[1]) * (abs(yc[0]-yc[1]))
            if ret is None:
                ret = s
            else:
                ret = min(ret,s)

print(ret)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())

N,K = inpl()
xys = []
xx = set()
yy = set()
for i in range(N):
    x,y = inpl()
    xys.append([x,y])
    xx.add(x)
    yy.add(y)

ans = INF
xx = sorted(list(xx))
yy = sorted(list(yy))
Lx = len(xx)
Ly = len(yy)
for i1 in range(Lx):
    x1 = xx[i1]
    for i2 in range(i1,Lx):
        x2 = xx[i2]
        for j1 in range(Ly):
            y1 = yy[j1]
            for j2 in range(j1,Ly):
                y2 = yy[j2]
                tmp = 0
                for x,y in xys:
                    if x1 <= x <= x2 and y1 <= y <= y2:
                        tmp += 1
                if K <= tmp:
                    ans = min(ans,(x2-x1)*(y2-y1))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int,input().split())
p = [list(map(int,input().split())) for k in range(N)]
ans = float("inf")
for x1 in range(N):
    for x2 in range(N):
        for y1 in range(N):
            for y2 in range(N):
                hidari = min(p[x1][0],p[x2][0])
                migi = max(p[x1][0],p[x2][0])
                ue = max(p[y1][1],p[y2][1])
                shita = min(p[y1][1],p[y2][1])
                t = 0
                for k in range(N):
                    if hidari <= p[k][0] <= migi and shita <= p[k][1] <= ue:
                        t += 1
                if t >= K:
                    ans = min(ans,(ue-shita)*(migi-hidari))
print(ans)

Submission status: Time Limit Exceeded

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

from itertools import combinations

ans = float('inf')
for s in combinations(xy, K):
    x, y = zip(*s)
    ans = min(ans, (max(x) - min(x)) * (max(y) - min(y)))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
"""
D - Axis-Parallel Rectangle
各点を頂点とする長方形じゃだめなの？
解説どおり、各点と平行な線を引いて解いた
"""

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

p_x = []
p_y = []
for n in range(N):
    line = input().split()
    p_x.append(int(line[0]))
    p_y.append(int(line[1]))

points_x = sorted(p_x)
points_y = sorted(p_y)

all_min = (points_x[N-1] - points_x[0]) * (points_y[N-1] - points_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):
                
                inner_point = 0
                left_x = points_x[xi]
                right_x = points_x[xj]
                left_y = points_y[yi]
                right_y = points_y[yj]
                
                for i in range(N):
                    if (left_x <= p_x[i]
                    and p_x[i] <= right_x
                    and left_y <= p_y[i]
                    and p_y[i] <= right_y):

                        inner_point += 1
                
                if inner_point >= K:
                    all_min = min(all_min, (right_x - left_x) * (right_y - left_y))

print(all_min)

Submission status: Time Limit Exceeded

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

ans = float("inf")
for a, b in combinations(dots, 2):
	for c, d in combinations(dots, 2):
		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 0 < area < ans:
			ans = area

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 0 < area < ans:
		ans = area

print(ans)

Submission status: Time Limit Exceeded

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

def calc(a,b,c,d):
  lx=min(o[a][0],o[b][0])
  rx=max(o[a][0],o[b][0])
  dy=min(o[c][1],o[d][1])
  uy=max(o[c][1],o[d][1])

  cnt=0
  for i in o:
    if lx<=i[0]<=rx and dy<=i[1]<=uy:
      cnt+=1
  if cnt>=k:
    return (rx-lx)*(uy-dy)
  return float("inf")

v=float("inf")
for (a,c) in pd(range(n),repeat=2):
  for (b,d) in pd(range(n),repeat=2):
    v=min(v,calc(a,b,c,d))
print(v)

Submission status: Time Limit Exceeded

Solution code:
from itertools import product as pd
g=lambda x,y:(min(x,y),max(x,y))
n,k=map(int,input().split())
o=[tuple(map(int,input().split())) for _ in range(n)]

def f(a,b,c,d):
  lx,rx=g(o[a][0],o[b][0])
  dy,uy=g(o[c][1],o[d][1])
  cnt=0
  for i in o:
    if lx<=i[0]<=rx and dy<=i[1]<=uy:
      cnt+=1
  if cnt>=k:
    return (rx-lx)*(uy-dy)
  return float("inf")

v=float("inf")
for (a,c) in pd(range(n),repeat=2):
  for (b,d) in pd(range(n),repeat=2):
    v=min(v,f(a,b,c,d))
print(v)

Submission status: Time Limit Exceeded

Solution code:
from itertools import product as pd
f=lambda x,y:(x,y) if x<y else (y,x) 
n,k=map(int,input().split())
o=[tuple(map(int,input().split())) for _ in range(n)]

def calc(a,b,c,d):
  lx,rx=f(o[a][0],o[b][0])
  dy,uy=f(o[c][1],o[d][1])
  cnt=0
  for i in o:
    if lx<=i[0]<=rx and dy<=i[1]<=uy:
      cnt+=1
  if cnt>=k:
    return (rx-lx)*(uy-dy)
  return float("inf")

v=float("inf")
for (a,c) in pd(range(n),repeat=2):
  for (b,d) in pd(range(n),repeat=2):
    v=min(v,calc(a,b,c,d))
print(v)

Submission status: Time Limit Exceeded

Solution code:
from itertools import product as pd
f=lambda x,y:(x,y) if x<y else (y,x) 
n,k=map(int,input().split())
o=[tuple(map(int,input().split())) for _ in range(n)]

v=float("inf")
for (a,c) in pd(range(n),repeat=2):
  for (b,d) in pd(range(n),repeat=2):
    lx,rx=f(o[a][0],o[b][0])
    dy,uy=f(o[c][1],o[d][1])
    cnt=0
    for i in o:
      if lx<=i[0]<=rx and dy<=i[1]<=uy:
        cnt+=1
    if cnt>=k:
      v=min(v,(rx-lx)*(uy-dy))
print(v)

Submission status: Time Limit Exceeded

Solution code:
from itertools import product as pd
f=lambda x,y:(x,y) if x<y else (y,x) 
n,k=map(int,input().split())
o=[tuple(map(int,input().split())) for _ in range(n)]

v=float("inf")
for (a,c) in pd(range(n),repeat=2):
  for (b,d) in pd(range(n),repeat=2):
    lx,rx=f(o[a][0],o[b][0])
    dy,uy=f(o[c][1],o[d][1])
    cnt=sum(1 for i in range(n) if lx<=o[i][0]<=rx and dy<=o[i][1]<=uy)
    if cnt==k:
      v=min(v,(rx-lx)*(uy-dy))
print(v)

Submission status: Time Limit Exceeded

Solution code:
from itertools import product as pd
f=lambda x,y:(x,y) if x<y else (y,x) 
n,k=map(int,input().split())
o=[tuple(map(int,input().split())) for _ in range(n)]

v=float("inf")
for (a,b,c,d) in pd(range(n),repeat=4):
  lx,rx=f(o[a][0],o[b][0])
  dy,uy=f(o[c][1],o[d][1])
  if lx==rx or dy==uy:continue
  cnt=sum(1 for i in range(n) if lx<=o[i][0]<=rx and dy<=o[i][1]<=uy)
  if cnt==k:
    v=min(v,(rx-lx)*(uy-dy))
print(v)

Submission status: Time Limit Exceeded

Solution code:
import itertools
n,k = map(int,input().split())
x = []
a = []
b = []
for i in range(n):
    x1,y1=[int(i) for i in input().split()]
    x.append([x1,y1])
    a.append(x1)
    b.append(y1)
ue = list(itertools.combinations(a,2))
mi = list(itertools.combinations(b,2))
ans = float("inf")
for u,d in ue:
  for m,h in mi:
    kazu = 0
    if u > d:
      UP = u
      DO = d
    else:
      UP = d
      DO = u
    if m > h:
      RI = m
      LE = h
    else:
      RI = h
      LE = m
    for i in  x:
      if (UP >= i[0] and i[0]>= DO and RI >= i[1] and i[1] >= LE):
        kazu += 1
    if kazu >= k:
      ans = min(ans,(UP-DO)*(RI-LE))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
AtoZ = [chr(i) for i in range(65,65+26)]
atoz = [chr(i) for i in range(97,97+26)]

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

N,K = inpl()
xys = []
xx = []
yy = []
ans = INF

for i in range(N):
	x,y = inpl()
	xys.append([x,y])

xys.sort()
for x,y in xys:
	xx.append(x)
	yy.append(y)



for i1 in range(N):
	for j1 in range(N):
		for i2 in range(i1+1,N):
			for j2 in range(j1+1,N):
				x1,x2 = xx[i1],xx[i2]
				y1,y2 = yy[j1],yy[j2]
				if y1 > y2:
					y1,y2 = y2,y1
				tmp = 0
				for ix in range(i1,i2+1):
					y = xys[ix][1]
					if y1 <= y <= y2:
						tmp += 1
				if tmp == K:
					S = abs(x1-x2)*abs(y1-y2)
					ans = min(ans,S)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
px = [0 for _ in range(N)]
py = [0 for _ in range(N)]
for i in range(N):
  px[i],py[i] = list(map(int,input().split()))
a=10**20
for xi in range(N):
  for xj in range(xi+1,N):
    for yi in range(N):
      for yj in range(yi+1,N):
        x0,x1,y0,y1=px[xi],px[xj],py[yi],py[yj]
        dx,dy = abs(x0-x1),abs(y0-y1)
        if a < dx*dy: continue
        cnt = 0
        for i in range(N):
          if (x0-px[i])*(px[i]-x1)>=0 and (y0-py[i])*(py[i]-y1)>=0: cnt += 1
        if cnt >= K: a = min(a, dx*dy)
print(a)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
N,K=map(int,input().split())
px = [0 for _ in range(N)]
py = [0 for _ in range(N)]
for i in range(N):
  px[i],py[i] = list(map(int,input().split()))
a=10**20
for c in combinations(range(N), min(K,4)):
  px_ = [px[i] for i in c]
  py_ = [py[i] for i in c]
  px0,px1 = min(px_),max(px_)
  py0,py1 = min(py_),max(py_)
  dx,dy = px1-px0,py1-py0
  if a < dx*dy: continue
  cnt = 0
  for i in range(N):
    if px0<=px[i] and px[i]<=px1 and py0<=py[i] and py[i]<=py1:
      cnt += 1
  if K <= cnt: a = min(a, dx*dy)
print(a)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
N,K=map(int,input().split())
px = [0 for _ in range(N)]
py = [0 for _ in range(N)]
for i in range(N):
  px[i],py[i] = list(map(int,input().split()))
a=10**20
for c in combinations(range(N), K):
  px_ = [px[i] for i in c]
  py_ = [py[i] for i in c]
  dx = max(px_)-min(px_)
  dy = max(py_)-min(py_)
  a  = min(a, dx*dy)
print(a)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
import copy

from math import *

def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N, K] =  [long(input_raw[0]), long(input_raw[1])]
    x_list = [0 for i in range(N)]
    y_list = [0 for i in range(N)]
    point_set = set([])
    for i in range(N):
        input_raw = read_func().strip().split()
        [x, y] =  [long(input_raw[0]), long(input_raw[1])]
        x_list[i] = x
        y_list[i] = y
        point_set.add((x, y))
    h = {}
    gx = {}
    gy = {}
    for x in x_list:
        for y in y_list:
            num = 0
            num_gx = 0
            num_gy = 0
            for i in range(N):
                if x <= x_list[i] and y <= y_list[i]:
                    num += 1
                if x == x_list[i] and y <= y_list[i]:
                    num_gx += 1
                if y == y_list[i] and x <= x_list[i]:
                    num_gy += 1
            h[(x, y)] = num
            gx[(x, y)] = num_gx
            gy[(y, x)] = num_gy
##    for point in point_set:
##        for y in y_list: #count x point num of more y
##            if (point[0], y) not in gx:
##                gx[(point[0], y)] = 0
##            if point[1] >= y:
##                gx[(point[0], y)] += 1L
##
##    for point in point_set:
##        for x in x_list: #count y point num of more x
##            if (point[1], x) not in gy:
##                gy[(point[1], x)] = 0
##            if point[0] >= x:
##                gy[(point[1], x)] += 1L


    min_S = long(sys.maxint) * long(sys.maxint)
    for i in range(N):
        for j in range(i + 1, N):
            for m in range(N):
                for n in range(m + 1, N):
                    x1 = min(x_list[i], x_list[j])
                    x2 = max(x_list[i], x_list[j])
                    y1 = min(y_list[m], y_list[n])
                    y2 = max(y_list[m], y_list[n])
                    in_num =  (h[(x1, y1)] - h[(x2, y1)] - h[(x1, y2)] + h[(x2, y2)] +
                                gx[(x2, y1)] - gx[(x2, y2)] + gy[(y2, x1)] - gy[(y2, x2)] +
                                  (1 if (x2, y2) in point_set else 0))
##                    in_num = 0
##                    for k in range(N):
##                        xk = x_list[k]
##                        yk = y_list[k]
##                        if (xk <= max(x1, x2) and xk >= min(x1, x2) and
##                            yk <= max(y1, y2) and yk >= min(y1, y2)):
##                                in_num += 1
##                        if in_num >= K:
##                            break
                    if in_num >= K:
                        S= abs(x1 - x2) * abs(y1 - y2)
                        if S < min_S:
                            min_S = S
    print min_S



if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
import copy

from math import *

def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N, K] =  [long(input_raw[0]), long(input_raw[1])]
    x_list = []
    y_list = []
    point_set = set([])
    for i in range(N):
        input_raw = read_func().strip().split()
        [x, y] =  [long(input_raw[0]), long(input_raw[1])]
        x_list.append(x)
        y_list.append(y)
        point_set.add((x, y))
    h = {}
    gx = {}
    gy = {}
    for x in x_list:
        for y in y_list:
            num = 0
            num_gx = 0
            num_gy = 0
            for i in range(N):
                if x <= x_list[i] and y <= y_list[i]:
                    num += 1
                if x == x_list[i] and y <= y_list[i]:
                    num_gx += 1
                if y == y_list[i] and x <= x_list[i]:
                    num_gy += 1
            h[(x, y)] = num
            gx[(x, y)] = num_gx
            gy[(y, x)] = num_gy


    min_S = long(sys.maxint) * long(sys.maxint)
    for i in range(N):
        for j in range(i + 1, N):
            for m in range(N):
                for n in range(m + 1, N):
                    x1 = min(x_list[i], x_list[j])
                    x2 = max(x_list[i], x_list[j])
                    y1 = min(y_list[m], y_list[n])
                    y2 = max(y_list[m], y_list[n])
                    in_num =  (h[(x1, y1)] - h[(x2, y1)] - h[(x1, y2)] + h[(x2, y2)] +
                                gx[(x2, y1)] - gx[(x2, y2)] + gy[(y2, x1)] - gy[(y2, x2)] +
                                  (1 if (x2, y2) in point_set else 0))

                    if in_num >= K:
                        S= abs(x1 - x2) * abs(y1 - y2)
                        if S < min_S:
                            min_S = S
    print min_S



if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
import copy

from math import *

def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N, K] =  [long(input_raw[0]), long(input_raw[1])]
    x_list = []
    y_list = []
    point_set = set([])
    for i in range(N):
        input_raw = read_func().strip().split()
        [x, y] =  [long(input_raw[0]), long(input_raw[1])]
        x_list.append(x)
        y_list.append(y)
        point_set.add((x, y))
    h = {}
    gx = {}
    gy = {}
    for x in x_list:
        for y in y_list:
            num = 0
            num_gx = 0
            num_gy = 0
            for i in range(N):
                if x <= x_list[i] and y <= y_list[i]:
                    num += 1
                if x == x_list[i] and y <= y_list[i]:
                    num_gx += 1
                if y == y_list[i] and x <= x_list[i]:
                    num_gy += 1
            h[(x, y)] = num
            gx[(x, y)] = num_gx
            gy[(y, x)] = num_gy
##    for point in point_set:
##        for y in y_list: #count x point num of more y
##            if (point[0], y) not in gx:
##                gx[(point[0], y)] = 0
##            if point[1] >= y:
##                gx[(point[0], y)] += 1L
##
##    for point in point_set:
##        for x in x_list: #count y point num of more x
##            if (point[1], x) not in gy:
##                gy[(point[1], x)] = 0
##            if point[0] >= x:
##                gy[(point[1], x)] += 1L


    min_S = long(sys.maxint) * long(sys.maxint)
    for i in range(N):
        for j in range(i, N):
            for m in range(N):
                for n in range(m, N):
                    x1 = min(x_list[i], x_list[j])
                    x2 = max(x_list[i], x_list[j])
                    y1 = min(y_list[m], y_list[n])
                    y2 = max(y_list[m], y_list[n])
                    in_num =  (h[(x1, y1)] - h[(x2, y1)] - h[(x1, y2)] + h[(x2, y2)] +
                                gx[(x2, y1)] - gx[(x2, y2)] + gy[(y2, x1)] - gy[(y2, x2)] +
                                  (1 if (x2, y2) in point_set else 0))
##                    in_num = 0
##                    for k in range(N):
##                        xk = x_list[k]
##                        yk = y_list[k]
##                        if (xk <= max(x1, x2) and xk >= min(x1, x2) and
##                            yk <= max(y1, y2) and yk >= min(y1, y2)):
##                                in_num += 1
##                        if in_num >= K:
##                            break
                    if in_num >= K:
                        S= abs(x1 - x2) * abs(y1 - y2)
                        if S < min_S:
                            min_S = S
    print min_S



if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
import copy

from math import *

def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N, K] =  [long(input_raw[0]), long(input_raw[1])]
    x_list = []
    y_list = []
    for i in range(N):
        input_raw = read_func().strip().split()
        [x, y] =  [long(input_raw[0]), long(input_raw[1])]
        x_list.append(x)
        y_list.append(y)

    min_S = long(sys.maxint) * long(sys.maxint)
    for i in range(N):
        for j in range(i, N):
            for m in range(N):
                for n in range(m, N):
                    x1 = x_list[i]
                    x2 = x_list[j]
                    y1 = y_list[m]
                    y2 = y_list[n]
                    in_num = 0
                    for k in range(N):
                        xk = x_list[k]
                        yk = y_list[k]
                        if (xk <= max(x1, x2) and xk >= min(x1, x2) and
                            yk <= max(y1, y2) and yk >= min(y1, y2)):
                                in_num += 1
                        if in_num >= K:
                            break
                    if in_num >= K:
                        S= abs(x1 - x2) * abs(y1 - y2)
                        if S < min_S:
                            min_S = S
    print min_S



if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
import copy

from math import *

def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N, K] =  [long(input_raw[0]), long(input_raw[1])]
    x_list = []
    y_list = []
    for i in range(N):
        input_raw = read_func().strip().split()
        [x, y] =  [long(input_raw[0]), long(input_raw[1])]
        x_list.append(x)
        y_list.append(y)

    min_S = long(sys.maxint) * long(sys.maxint)
    for i in range(N):
        for j in range(N):
            for m in range(N):
                for n in range(N):
                    x1 = x_list[i]
                    x2 = x_list[j]
                    y1 = y_list[m]
                    y2 = y_list[n]
                    in_num = 0
                    for k in range(N):
                        xk = x_list[k]
                        yk = y_list[k]
                        if (xk <= max(x1, x2) and xk >= min(x1, x2) and
                            yk <= max(y1, y2) and yk >= min(y1, y2)):
                                in_num += 1
                        if in_num >= K:
                            break
                    if in_num >= K:
                        S= abs(x1 - x2) * abs(y1 - y2)
                        if S < min_S:
                            min_S = S
    print min_S



if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import itertools
x=input().split()
n=int(x[0])
k=int(x[1])
coor=[[0]*2 for i in range(n)]
for i in range(n):
    co=input().split()
    coor[i][0]=int(co[0])
    coor[i][1]=int(co[1])
xs=[0]*k
ys=[0]*k
area=99999999999999999999
for i in itertools.combinations(range(n),k):
    xx=0
    for j in i:
        xs[xx]=coor[j][0]
        ys[xx]=coor[j][1]
        xx+=1
    area=min(area, (max(xs)-min(xs))*(max(ys)-min(ys)))
print(area)

Submission status: Time Limit Exceeded

Solution code:
nk=input().split()
n=int(nk[0])
pts=int(nk[1])
xlist=[]
ylist=[]
ans=99999999999999999999999999999
points=0
for t in range(n):
	xy=input().split()
	xlist.append(int(xy[0]))
	ylist.append(int(xy[1]))
for i in (xlist):
	for j in xlist:
		for k in ylist:
			for l in ylist:
				points=0
				for m in range(len(xlist)):
					if ((xlist[m]>=i and xlist[m]<=j) or (xlist[m]<=i and xlist[m]>=j))and ((ylist[m]>=k and ylist[m]<=l) or (ylist[m]<=k and ylist[m]>=l)):
						points=points+1
				if points>=pts:
					ans=min(ans,(abs(i-j))*(abs(k-l)))
print(ans)