Problem:


Score : 400 points

Problem Statement

We have N points in a two-dimensional plane.

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

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

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

Find the minimum possible area of such a rectangle.  

Constraints

2 \leq K \leq N \leq 50 

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

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

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

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

Input

Input is given from Standard Input in the following format:  

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

Output

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

Sample Input 1

4 4
1 4
3 3
6 2
8 1

Sample Output 1

21

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

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

Sample Input 2

4 2
0 0
1 1
2 2
3 3

Sample Output 2

1

Sample Input 3

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

Sample Output 3

3999999996000000001

Watch out for integer overflows.  



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


Sample output:
21

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, raw_input().split())
x = [map(int, raw_input().split()) for i in range(N)]
ans = 10**30
for i in range(N):
    for j in range(N):
        for k in range(N):
            for l in range(N):
                x0, y0 = x[i]
                x1, y1 = x[j]
                x2, y2 = x[k]
                x3, y3 = x[l]
                x_min = min([x0, x1, x2, x3])
                x_max = max([x0, x1, x2, x3])
                y_min = min([y0, y1, y2, y3])
                y_max = max([y0, y1, y2, y3])
                cnt = 0
                for m in range(N):
                    x4, y4 = x[m]
                    if (x_min <= x4 <= x_max) and (y_min <= y4 <= y_max):
                        cnt += 1
                if cnt >= K:
                    S = (x_max - x_min) * (y_max - y_min)
                    ans = min(S, ans)
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)
x_sorted = sorted(x)
y_sorted = sorted(y)


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


ans = 4 * 10 ** 18
for i in range(N):
    for j in range(i + 1, N):
        for k in range(N):
            for l in range(k + 1, N):
                num = included(x_sorted[i], x_sorted[j], y_sorted[k], y_sorted[l])
                if num > K:
                    break
                elif num == K:
                    s = (x_sorted[j] - x_sorted[i]) * (y_sorted[l] - y_sorted[k])
                    if ans > s:
                        ans = s
                else:
                    continue
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,K = [int(i) for i in input().split()]
arealist = []
xlist = []
ylist = []
xylist =[]
count = 0
for i in range(N):
    xylist.append(list(int(k) for k in input().split()))
for i in range(N):
    xlist.append(xylist[i][0])
    ylist.append(xylist[i][1])
xsorted = sorted(xlist)
ysorted = sorted(ylist)
#print(xlist,ylist)
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):
                count = 0
                xw = xsorted[i]
                xe = xsorted[j]
                ys = ysorted[k]
                yn = ysorted[l]

                for m in range(N):
                    if (xw <= xlist[m] <= xe) and (ys <= ylist[m] <= yn):
                            count += 1
                            #print(count)
                if count >= K:
                    arealist.append((xe-xw)*(yn-ys))
#print(arealist)
#print(arealist)
print(sorted(arealist)[0])

Submission status: Time Limit Exceeded

Solution code:
n,kk=[int(i) for i in input().split()]
x=[0 for i in range(n)]
y=[0 for i in range(n)]
S=10**20

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

xx=x[:]
yy=y[:]
xx.sort()
yy.sort()


for i in range(n):
    for j in range(i+1,n):
        for k in range(n):
            for l in range(k+1,n):
                num=0
                x_min=xx[i]
                x_max=xx[j]
                y_min=yy[k]
                y_max=yy[l]
                for m in range(n):
                    if (x[m]>=x_min and x[m]<=x_max and y[m]>=y_min and y[m]<=y_max):
                        num=num+1
                if num>=kk:
                    S=min(S, (x_max-x_min)*(y_max-y_min))

print(S)

Submission status: Time Limit Exceeded

Solution code:
n,kk=[int(i) for i in input().split()]
x=[0 for i in range(n)]
y=[0 for i in range(n)]
S=10**20

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

for i in x:
    for j in y:
        for k in y:
            for l in x:
                num=0
                x_min=i
                x_max=l
                y_min=j
                y_max=k
                for m in range(n):
                    if (x_min<=x_max and y_min<=y_max and x[m]>=x_min and x[m]<=x_max and y[m]>=y_min and y[m]<=y_max):
                        num=num+1
                if num>=kk:
                    S=min(S, (x_max-x_min)*(y_max-y_min))

print(S)
#print(max(x),min(x),max(y),min(y))
#print((max(x)-min(x))*(max(y)-min(y)))

Submission status: Time Limit Exceeded

Solution code:
import itertools

N, K = map(int, input().split())
point = [tuple(map(int, input().split())) for i in range(N)]

ans = float('inf')

for i, j, k, l in itertools.product(point, repeat=4):
    x1, x2, y1, y2 = i[0], j[0], k[1], l[1]
    if x2 <= x1 or y2 <= y1:
        continue
    count = 0
    for p in point:
        if x1 <= p[0] <= x2 and y1 <= p[1] <= y2:
            count += 1
    if count >= K:
        ans = min((x2-x1) * (y2-y1), ans)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools

N, K = map(int, input().split())
point = [tuple(map(int, input().split())) for i in range(N)]

ans = float('inf')

for i, j, k, l in itertools.product(point, repeat=4):
    x1, x2, y1, y2 = i[0], j[0], k[1], l[1]
    if x2 < x1 or y2 < y1:
        continue
    count = 0
    for p in point:
        if x1 <= p[0] <= x2 and y1 <= p[1] <= y2:
            count += 1
    if count >= K:
        ans = min((x2-x1) * (y2-y1), ans)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools

N, K = map(int, input().split())
point = [tuple(map(int, input().split())) for i in range(N)]

ans = float('inf')

for i, j, k, l in itertools.product(point, repeat=4):
    x1, x2, y1, y2 = i[0], j[0], k[1], l[1]
    count = 0
    for p in point:
        if x1 <= p[0] <= x2 and y1 <= p[1] <= y2:
            count += 1
    if count >= K:
        ans = min((x2-x1) * (y2-y1), ans)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python

# AtCoder Beginner Contest 075
# D - Axis-Parallel Rectangle

from sys import stdin

def nPointsInRect(y0, y1, points):
  return len([p for p in points if y0 <= p[1] <= y1])

def solve(K, points):
  points.sort()  # sort the points by x-coordinates
  xs = [p[0] for p in points]          # sorted x-coordinates
  ys = sorted([p[1] for p in points])  # sorted y-coordinates
  minArea = (xs[-1] - xs[0]) * (ys[-1] - ys[0])  # the biggest rect
  for i0 in range(len(points)):
    for i1 in range(i0 + K - 1, len(points)):
      for j in range(len(ys)):
        y0 = ys[j]
        for y1 in ys[j + K - 1:]:
          if nPointsInRect(y0, y1, points[i0 : i1 + 1]) >= K:
            area = (xs[i1] - xs[i0]) * (y1 - y0)
            minArea = min(minArea, area)
  return minArea

def splitToInt(line):
  words = line.strip().split()
  return [int(w) for w in words]

N, K = splitToInt(stdin.readline())
points = []
for i in range(N):
  x, y = splitToInt(stdin.readline())
  points.append((x, y))
print(solve(K, points))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python

# AtCoder Beginner Contest 075
# D - Axis-Parallel Rectangle

from sys import stdin

def nPointsInRect(x0, y0, x1, y1, points):
  return len([p for p in points
              if x0 <= p[0] <= x1 and y0 <= p[1] <= y1])

def solve(K, points):
  xs = sorted([p[0] for p in points])  # sorted x-coordinates
  ys = sorted([p[1] for p in points])  # sorted y-coordinates
  minArea = (xs[-1] - xs[0]) * (ys[-1] - ys[0])  # the biggest rect
  for i in range(len(ys)):
    y0 = ys[i]
    for y1 in ys[i + K - 1:]:
      for j in range(len(xs)):
        x0 = xs[j]
        for x1 in xs[j + K - 1:]:
          if nPointsInRect(x0, y0, x1, y1, points) >= K:
            area = (x1 - x0) * (y1 - y0)
            minArea = min(minArea, area)
  return minArea

def splitToInt(line):
  words = line.strip().split()
  return [int(w) for w in words]

N, K = splitToInt(stdin.readline())
points = []
for i in range(N):
  x, y = splitToInt(stdin.readline())
  points.append((x, y))
print(solve(K, points))

Submission status: Time Limit Exceeded

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



def main():
    N, K = map(int, input().split(" "))

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

    sorted_xary = xary.copy()
    sorted_yary = yary.copy()
    sorted_xary.sort()
    sorted_yary.sort()

    ans = (sorted_xary[N - 1] - sorted_xary[0]) * (sorted_yary[N - 1] - sorted_yary[0])

    for xi in range(len(sorted_xary)):
        for xj in range(xi + 1, len(sorted_xary)):
            for yi in range(len(sorted_yary)):
                for yj in range(yi + 1, len(sorted_yary)):
                    lx = sorted_xary[xi]
                    rx = sorted_xary[xj]
                    by = sorted_yary[yi]
                    uy = sorted_yary[yj]

                    num_k = 0
                    for i in range(N):
                        if lx <= xary[i] and xary[i] <= rx and uy >= yary[i] and yary[i] >= by:
                            num_k += 1
                    if num_k >= K:
                        area = (rx - lx) * (uy - by)
                        if area < ans:
                            ans = area
    print(ans)
       

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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



def main():
    N, K = map(int, input().split(" "))

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

    sorted_xary = xary.copy()
    sorted_yary = yary.copy()
    sorted_xary.sort()
    sorted_yary.sort()

    ans = (sorted_xary[N - 1] - sorted_xary[0]) * (sorted_yary[N - 1] - sorted_yary[0])

    for xi in range(len(sorted_xary)):
        for xj in range(xi + 1, len(sorted_xary)):
            for yi in range(len(sorted_yary)):
                for yj in range(yi + 1, len(sorted_yary)):
                    lx = sorted_xary[xi]
                    rx = sorted_xary[xj]
                    by = sorted_yary[yi]
                    uy = sorted_yary[yj]

                    num_k = 0
                    for i in range(N):
                        if lx <= xary[i] and xary[i] <= rx and uy >= yary[i] and yary[i] >= by:
                            num_k += 1
                    if num_k >= K:
                        area = (rx - lx) * (uy - by)
                        ans = min([ans, area])
                        break
    print(ans)
       

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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



def main():
    N, K = map(int, input().split(" "))

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

    sorted_xary = xary.copy()
    sorted_yary = yary.copy()
    sorted_xary.sort()
    sorted_yary.sort()

    ans = (sorted_xary[N - 1] - sorted_xary[0]) * (sorted_yary[N - 1] - sorted_yary[0])

    for xi in range(len(sorted_xary)):
        for xj in range(xi + 1, len(sorted_xary)):
            for yi in range(len(sorted_yary)):
                for yj in range(yi + 1, len(sorted_yary)):
                    lx = sorted_xary[xi]
                    rx = sorted_xary[xj]
                    by = sorted_yary[yi]
                    uy = sorted_yary[yj]

                    num_k = 0
                    for i in range(N):
                        if lx <= xary[i] and xary[i] <= rx and uy >= yary[i] and yary[i] >= by:
                            num_k += 1
                    if num_k >= K:
                        area = (rx - lx) * (uy - by)
                        ans = min([ans, area])
    print(ans)
       

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
area=19000000000000000000

n,k1=[int(i) for i in input().split()]
a=[]

for _ in range(n):
    a.append([int(i) for i in input().split()])

for i in range(n):
    for j in range(n):
        la=0
        for k in range(n):
            for l in range(n):
                x1=min(a[i][0],a[j][0],a[k][0],a[l][0])
                x2=max(a[i][0],a[j][0],a[k][0],a[l][0])
                y1=min(a[i][1],a[j][1],a[k][1],a[l][1])
                y2=max(a[i][1],a[j][1],a[k][1],a[l][1])


                atot = abs((x1 - x2) * (y1 - y2))
                cnt = 0
                for i1, j1 in a:
                    if i1 >= x1 and i1 <= x2 and j1 <= y2 and j1 >= y1:
                        cnt += 1
                if cnt >= k1:
                    area = min(area, atot)

print(area)

Submission status: Time Limit Exceeded

Solution code:
area=19000000000000000000
def check(x1,y1,x2,y2,k):
    global area
    atot = abs((x1-x2)*(y1-y2))
    cnt=0
    for i,j in a:
        if i>=x1 and i<=x2 and j<=y2 and j>=y1:
            cnt+=1
    if cnt>=k:
        area=min(area,atot)
n,k1=[int(i) for i in input().split()]
a=[]

for _ in range(n):
    a.append([int(i) for i in input().split()])

for i in range(n):
    for j in range(n):
        la=0
        for k in range(n):
            for l in range(n):
                x1=min(a[i][0],a[j][0],a[k][0],a[l][0])
                x2=max(a[i][0],a[j][0],a[k][0],a[l][0])
                y1=min(a[i][1],a[j][1],a[k][1],a[l][1])
                y2=max(a[i][1],a[j][1],a[k][1],a[l][1])

                check(x1,y1,x2,y2,k1)

print(area)

Submission status: Time Limit Exceeded

Solution code:
area=19000000000000000000
def check(x1,y1,x2,y2,x3,y3,x4,y4,k):
    global area
    atot = abs((x1-x3)*(y1-y3))
    cnt=0
    for i,j in a:
        a1=abs((x1-i)*(y1-j))
        a2 = abs((x2 - i) * (y2 - j))
        a3 = abs((x3 - i) * (y3 - j))
        a4 = abs((x4 - i) * (y4 - j))
        if a1+a2+a3+a4==atot:
            cnt+=1
    if cnt>=k:
        area=min(area,atot)
n,k1=[int(i) for i in input().split()]
a=[]

for _ in range(n):
    a.append([int(i) for i in input().split()])


for i in range(n):
    for j in range(n):
        la=0
        for k in range(n):
            for l in range(n):
                x1=min(a[i][0],a[j][0],a[k][0],a[l][0])
                x2=max(a[i][0],a[j][0],a[k][0],a[l][0])
                y1=min(a[i][1],a[j][1],a[k][1],a[l][1])
                y2=max(a[i][1],a[j][1],a[k][1],a[l][1])

                check(x1,y1,x2,y1,x2,y2,x1,y2,k1)

print(area)

Submission status: Time Limit Exceeded

Solution code:
area=19000000000000000000
def check(x1,y1,x2,y2,x3,y3,x4,y4,k):
    global area
    atot = abs((x1-x3)*(y1-y3))
    cnt=0
    for i,j in a:
        a1=abs((x1-i)*(y1-j))
        a2 = abs((x2 - i) * (y2 - j))
        a3 = abs((x3 - i) * (y3 - j))
        a4 = abs((x4 - i) * (y4 - j))
        if a1+a2+a3+a4==atot:
            cnt+=1
    if cnt>=k:
        area=min(area,atot)
n,k1=[int(i) for i in input().split()]
a=[]

for _ in range(n):
    a.append([int(i) for i in input().split()])
for i in range(n):
    for j in range(n):
        la=0
        check(a[i][0],a[i][1],a[j][0],a[i][1],a[j][0],a[j][1],a[i][0],a[j][1],k1)

for i in range(n):
    for j in range(n):
        la=0
        for k in range(n):
            x1=min(a[i][0],a[j][0],a[k][0])
            x2=max(a[i][0],a[j][0],a[k][0])
            y1=min(a[i][1],a[j][1],a[k][1])
            y2=max(a[i][1],a[j][1],a[k][1])

            check(x1,y1,x2,y1,x2,y2,x1,y2,k1)

for i in range(n):
    for j in range(n):
        la=0
        for k in range(n):
            for l in range(n):
                x1=min(a[i][0],a[j][0],a[k][0],a[l][0])
                x2=max(a[i][0],a[j][0],a[k][0],a[l][0])
                y1=min(a[i][1],a[j][1],a[k][1],a[l][1])
                y2=max(a[i][1],a[j][1],a[k][1],a[l][1])

                check(x1,y1,x2,y1,x2,y2,x1,y2,k1)

print(area)

Submission status: Time Limit Exceeded

Solution code:
import sys
N,K=map(int,sys.stdin.readline().split())
A=sorted([int(e) for e in sys.stdin.readline().split()] for _ in range(N))
x,y=zip(*A)
Y=sorted(y)
r=(x[-1]-x[0])*(Y[-1]-Y[0])
for i in range(N):
 for j in range(i+1,N):
  for k in range(N):
   for l in range(k+1,N):
    ly=Y[k];ry=Y[l];q=(x[j]-x[i])*(ry-ly)
    if r>q and K<=(j-i+1) and K<=sum(ly<=y[z]<=ry for z in range(i,j+1)): r=q
print(r)

Submission status: Time Limit Exceeded

Solution code:
import sys
N,K=map(int,sys.stdin.readline().split())
A=[[int(e) for e in sys.stdin.readline().split()] for _ in range(N)]
x,y=zip(*A)
X,Y=map(sorted,[x,y])
r=(X[-1]-X[0])*(Y[-1]-Y[0])
for i in range(N):
 for j in range(i+1,N):
  for k in range(N):
   for l in range(k+1,N):
    lx=X[i];rx=X[j];ly=Y[k];ry=Y[l]
    if K<=sum(lx<=x[z]<=rx and ly<=y[z]<=ry for z in range(N)): r=min(r,(rx-lx)*(ry-ly))
print(r)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, raw_input().split())
x = []
y = []
xsorted = []
ysorted = []
for _ in xrange(n):
    a, b = map(int,raw_input().split())
    a -= 1
    b -= 1
    x.append(a)
    y.append(b)
    xsorted.append(a)
    ysorted.append(b)
    xsorted.sort()
    ysorted.sort()

ans = (xsorted[-1] - xsorted[0]) * (ysorted[-1] - ysorted[0])
for xi in xrange(n):
    for xj in xrange(xi+1, n):
        for yi in xrange(n):
            for yj in xrange(yi+1, n):
                num = 0
                ax = xsorted[xi]
                bx = xsorted[xj]
                cy = ysorted[yi]
                dy = ysorted[yj]
                for i in xrange(n):
                    if x[i] >= ax and x[i] <= bx and y[i] >= cy and y[i] <= dy:
                        num += 1
                if(num >= k):
                    ans = min(ans, (bx - ax)*(dy - cy))

print ans

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
import itertools

n, k = map(int, input().split())
xs = set()
ys = set()
rects = []
for _ in range(n):
    (x, y) = map(int, input().split())
    rects.append((x, y))
    xs.add(x)
    ys.add(y)

def cntdot(xlist, ylist):
    cnt = 0
    for x, y in rects:
        if xlist[0] <= x <= xlist[1] and ylist[0] <= y <= ylist[1]:
            cnt += 1
    return cnt

minarea = float('inf')
for xset in itertools.combinations(sorted(xs), 2):
    for yset in itertools.combinations(sorted(ys), 2):
        xlist = list(xset)
        ylist = list(yset)
        area = (xlist[1] - xlist[0]) * (ylist[1] - ylist[0])
        if minarea <= area:
            continue
        cnt = cntdot(xlist, ylist)
        if cnt < k:
            continue
        minarea = min(minarea, area)

print(minarea)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
import itertools

n, k = map(int, input().split())
xs = set()
ys = set()
rects = []
for _ in range(n):
    (x, y) = map(int, input().split())
    rects.append((x, y))
    xs.add(x)
    ys.add(y)

def cntdot(xlist, ylist):
    cnt = 0
    for x, y in rects:
        if xlist[0] <= x <= xlist[1] and ylist[0] <= y <= ylist[1]:
            cnt += 1
    return cnt

minarea = float('inf')
for xset in itertools.combinations(sorted(xs), 2):
    for yset in itertools.combinations(sorted(ys), 2):
        xlist = list(xset)
        ylist = list(yset)
        cnt = cntdot(xlist, ylist)
        if cnt < k:
            continue
        area = (xlist[1] - xlist[0]) * (ylist[1] - ylist[0])
        minarea = min(minarea, area)

print(minarea)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations

def count(x1,y1,x2,y2):
    res = 0
    for i in range(N):
        s1 = x[i]
        s2 = y[i]
        if x1 <= s1 <= x2 and y1 <= s2 <= y2:
            res += 1
    return res 

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

x = []
y = []
y_dict = {}

for i in range(N):
    a,b = map(int,input().split())
    x.append(a)
    y.append(b)
    y_dict[a] = b

number = [i for i in range(N)]
x_2 = sorted(x)
ans = 10**20

for i,j in list(combinations(number,2)):
#for i in range(len(x_2)-1):#長方系の左の辺をx座標を取得し,固定
#    for j in range(i+1,len(x_2)):#長方形の右の辺のx座標を取得し,固定

    y_list = []

    for k in range(i,j+1):#xの指定区間内にある点のy座標を取得しy_listに入れる
        y_list.append(y_dict[x_2[k]])
        
    y_list = sorted(y_list)
        

    if 2 <= len(y_list):
        #for l in range(len(y_list)-1):#yの大きい値から順に組み合わせを試す
            #for m in range(l+1,len(y_list)):
        number2 = [i for i in range(len(y_list))]
        for l,m in list(combinations(number2,2)):        
                x1 = x_2[i]
                y1 = y_list[l]
                x2 = x_2[j]
                y2 = y_list[m]
                point = count(x1,y1,x2,y2)#区間内の点の数
                
                    
                if K <= point :
                    ans = min(ans,(x2-x1)*(y2-y1)) 


               
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def count(x1,y1,x2,y2):
    res = 0
    for i in range(N):
        s1 = x[i]
        s2 = y[i]
        if x1 <= s1 <= x2 and y1 <= s2 <= y2:
            res += 1
    return res 

    
N,K = map(int,input().split())
x = []
y = []
y_dict = {}
for i in range(N):
    a,b = map(int,input().split())
    x.append(a)
    y.append(b)
    y_dict[a] = b
x_2 = sorted(x)
y_2 = sorted(y)
ans = 10**20

for i in range(len(x_2)-1):#長方系の左の辺をx座標を取得し,固定
    for j in range(i+1,len(x_2)):#長方形の右の辺のx座標を取得し,固定

        y_list = []

        for k in range(i,j+1):#区間内にある点のy座標を取得しy_listに入れる
            y_list.append(y_dict[x_2[k]])
        
        y_list = sorted(y_list)
        

        if 2 <= len(y_list):
            for l in range(len(y_list)-1):#yの大きい値から順に組み合わせを試す
                for m in range(l+1,len(y_list)):
                
                    x1 = x_2[i]
                    y1 = y_list[l]
                    x2 = x_2[j]
                    y2 = y_list[m]
                    point = count(x1,y1,x2,y2)#区間内の点の数
                    
                    
                    if K <= point :
                        ans = min(ans,(x2-x1)*(y2-y1)) 


               
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
import copy

if __name__ == '__main__':
    N, K = map(int, input().split())
    plots = []
    for i in range(N):
        tmp_x, tmp_y = map(int, input().split())
        plots.append((tmp_x, tmp_y))
    combi_x = list(itertools.combinations(plots, 2))
    combi_y = list(itertools.combinations(plots, 2))
    menseki = float('inf')
    for x1, x2 in combi_x:
        for y1, y2 in combi_y:
            left_x = min(x1[0], x2[0], y1[0], y2[0])
            right_x = max(x1[0], x2[0], y1[0], y2[0])
            bottom_y = min(x1[1], x2[1], y1[1], y2[1])
            top_y = max(x1[1], x2[1], y1[1], y2[1])
            in_num = 0
            for x, y in plots:
                if left_x <= x <= right_x and bottom_y <= y <= top_y:
                    in_num += 1

            if K <= in_num:
                if (right_x - left_x) * (top_y - bottom_y) < menseki:
                    menseki = (right_x - left_x) * (top_y - bottom_y)

    print(menseki)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
N, K = map(int, input().split())
xs = []
ys = []
v = []
for i in range(N):
    x, y = map(int, input().split())
    v.append([x, y])
    xs.append(x)
    ys.append(y)

def f(v, min_x, max_x, min_y, max_y):
    sum = 0
    for x, y in v:
        if min_x <= x <= max_x and min_y <= y <= max_y:
            sum = sum + 1
    return sum

areas = []
for cx in combinations(xs, 2):
    for cy in combinations(ys, 2):
        sum = f(v, min(cx), max(cx), min(cy), max(cy))
        if sum >= K:
            areas.append((max(cx) - min(cx)) * (max(cy) - min(cy)))
print(min(areas))

Submission status: Time Limit Exceeded

Solution code:
import itertools

N,K=list(map(int,raw_input().split()))
x=[]
y=[]
sx=[]
sy=[]
for i in range(N):
	a1,a2=map(int,raw_input().split())
	x.append(a1)
	sx.append(a1)
	y.append(a2)
	sy.append(a2)

#print "# x,y"
#print x
#print y


ans=10**20
#print ans
for i in range(N):
	for j in range(N):
		for k in range(N):
			for l in range(N):
				cnt=0
				if x[i]<x[j] and y[k]<y[l]:
					#print i,j,k,l,x[i],y[k],x[j],y[l],sx.index(x[i]),sx.index(x[j]),abs(x[i]-x[j])*abs(y[k]-y[l])
					for m in range(N):
						x_t=x[m]
						y_t=y[m]
						if (x_t>=x[i] and x_t<=x[j]) or (x_t>=x[j] and x_t<=x[i]):
							if (y_t>=y[k] and y_t<=y[l]) or (y_t>=y[l] and y_t<=y[k]):
								cnt+=1
					
				
				#print cnt
				if cnt>=K:
					#print x[i],y[k],x[j],y[l],cnt,abs(x[i]-x[j])*abs(y[k]-y[l])
					ans=min(ans,abs(x[i]-x[j])*abs(y[k]-y[l]))


print ans

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split())
xlist = []
ylist = []
for _ in range(n):
    x,y = map(int,input().split())
    xlist.append(x)
    ylist.append(y)

xsort = sorted(xlist)
ysort = sorted(ylist)

ret = 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):
                ctr = 0
                for i in range(n):
                    if xsort[xi] <= xlist[i] <= xsort[xj] and ysort[yi] <= ylist[i] <= ysort[yj]:
                        ctr += 1
                if ctr >= k:
                    ret = min(ret,(xsort[xj]-xsort[xi])*(ysort[yj]-ysort[yi]))
print(ret)

Submission status: Time Limit Exceeded

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

X = []
Y = []
P = []
for i in range(N):
	coor = tuple(map(int, input().split()))
	P.append(coor)
	X.append(coor[0])
	Y.append(coor[1])
	
X.sort()
Y.sort()

answer = (X[-1] - X[0])*(Y[-1] - Y[0])

for xmin in range(N):
	for xmax in range(xmin+1, N):
			for ymin in range(N):
				for ymax in range(ymin+1, N):
						cnt = 0
						for i in range(N):
							if X[xmin] <= P[i][0] and P[i][0] <= X[xmax] and Y[ymin] <= P[i][1] and P[i][1] <= Y[ymax]:
								cnt += 1
						if cnt >= K:
							answer = min(answer, (X[xmax]-X[xmin])*(Y[ymax]-Y[ymin]))
print(int(answer))

Submission status: Time Limit Exceeded

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

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

answer = 2**69
for i in range(N):
	for j in range(N):
		for k in range(N):
			for l in range(N):
				xmin = min(P[i][0], P[j][0], P[k][0], P[l][0]);
				xmax = max(P[i][0], P[j][0], P[k][0], P[l][0]);
				ymin = min(P[i][1], P[j][1], P[k][1], P[l][1]);
				ymax = max(P[i][1], P[j][1], P[k][1], P[l][1]);
				cnt = 0
				for x in range(N):
					if xmin <= P[x][0] and P[x][0] <= xmax and ymin <= P[x][1] and P[x][1] <= ymax:
						cnt += 1
				if cnt >= K:
					answer = min(answer, (xmax-xmin)*(ymax-ymin))
print(int(answer))

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
z = [list(map(int, input().split())) for i in range(N)]
zx = sorted(z)
zy = sorted(z,key=lambda x:x[1])
ans = float('inf')
for i in range(N):
    for j in range(i+1, N):
        x1 = zx[i][0]
        x2 = zx[j][0]
        w = abs(x1-x2)
        for k in range(N):
            for l in range(k+1, N):
                num = 0
                y1 = zy[k][1]
                y2 = zy[l][1]
                for m in range(N):
                    if x1 <= z[m][0] and z[m][0] <= x2 and\
                    y1 <= z[m][1] and z[m][1] <= y2:
                        num += 1
                if num >= K:
                    h = abs(y1-y2)
                    ans = min(ans, w*h)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools

N,K=list(map(int,raw_input().split()))
x=[]
y=[]
for i in range(N):
	a1,a2=map(int,raw_input().split())
	x.append(a1)
	y.append(a2)
#print x
#print y


ans=100000000000000000000
for i in range(N):
	for j in range(i,N):
		for k in range(N):
			for l in range(k,N):
				cnt=0
				for m in range(N):
					x_t=x[m]
					y_t=y[m]
					if (x_t>=x[i] and x_t<=x[j]) or (x_t>=x[j] and x_t<=x[i]):
						if (y_t>=y[k] and y_t<=y[l]) or (y_t>=y[l] and y_t<=y[k]):
							cnt+=1
				#print x[i],y[k],x[j],y[l],cnt,abs(x[i]-x[j])*abs(y[k]-y[l])
				#print cnt
				if cnt>=K:
					#print x[i],y[k],x[j],y[l],cnt,abs(x[i]-x[j])*abs(y[k]-y[l])
					ans=min(ans,abs(x[i]-x[j])*abs(y[k]-y[l]))


print ans

Submission status: Time Limit Exceeded

Solution code:
import itertools

N,K=list(map(int,raw_input().split()))
x=[]
y=[]
for i in range(N):
	a1,a2=map(int,raw_input().split())
	x.append(a1)
	y.append(a2)
#print x
#print y


ans=100000000000000000000
for i in range(N):
	for j in range(N):
		for k in range(N):
			for l in range(N):
				if i<=j and k<=l:
					cnt=0
					for m in range(N):
						x_t=x[m]
						y_t=y[m]
						if (x_t>=x[i] and x_t<=x[j]) or (x_t>=x[j] and x_t<=x[i]):
							if (y_t>=y[k] and y_t<=y[l]) or (y_t>=y[l] and y_t<=y[k]):
								cnt+=1
					#print x[i],y[k],x[j],y[l],cnt,abs(x[i]-x[j])*abs(y[k]-y[l])
					#print cnt
					if cnt>=K:
						#print x[i],y[k],x[j],y[l],cnt,abs(x[i]-x[j])*abs(y[k]-y[l])
						ans=min(ans,abs(x[i]-x[j])*abs(y[k]-y[l]))


print ans

Submission status: Time Limit Exceeded

Solution code:
import itertools

N,K=list(map(int,raw_input().split()))
x=[]
y=[]
for i in range(N):
	a1,a2=map(int,raw_input().split())
	x.append(a1)
	y.append(a2)
#print x
#print y


ans=100000000000000000000
for i in range(N):
	for j in range(N):
		for k in range(N):
			for l in range(N):
				cnt=0
				for m in range(N):
					x_t=x[m]
					y_t=y[m]
					if (x_t>=x[i] and x_t<=x[j]) or (x_t>=x[j] and x_t<=x[i]):
						if (y_t>=y[k] and y_t<=y[l]) or (y_t>=y[l] and y_t<=y[k]):
							cnt+=1
				#print cnt
				if cnt>=K:
					#print x[i],y[k],x[j],y[l],cnt,abs(x[i]-x[j])*abs(y[k]-y[l])
					ans=min(ans,abs(x[i]-x[j])*abs(y[k]-y[l]))


print ans

Submission status: Time Limit Exceeded

Solution code:
# web解説を見て
N, K = map(int, input().split())
plot = []
plot_x = []
plot_y = []

for _ in range(N):
    plot.append(list(map(int, input().split())))
    plot_x.append(plot[_][0])
    plot_y.append(plot[_][1])

plot_x.sort()
plot_y.sort()
S = float("inf")
for i in range(N):
    for j in range(N):
        for k in range(N):
            for l in range(N):
                left = plot_x[i]
                right = plot_x[-(j+1)]
                down = plot_y[k]
                up = plot_y[-(l+1)]
                if right > left and up > down:
                    cnt = 0
                    for m in range(N):
                        p = plot[m]
                        if left <= p[0] <= right and down <= p[1] <= up:
                            cnt += 1
                    if cnt >= K:
                        S = min(S, ((right - left)*(up - down)))
                    
print(S)