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: Accepted

Solution code:
from itertools import product,combinations
N,K=map(int,input().split())
L=[tuple(map(int,input().split())) for i in range(N)]
ans=10**37
def f(i,j,k,l):
    n=0
    s=min(L[j][0],L[i][0])
    t=max(L[j][0],L[i][0])
    u=min(L[k][1],L[l][1])
    w=max(L[k][1],L[l][1])
    for e in L:
        if s<=e[0]<=t and u<=e[1]<=w:
            n+=1
    if n>=K:
        return (t-s)*(w-u)
    return 10**37
for i,j in combinations(range(N),2):
    for k,l in combinations(range(N),2):
        #print(i,j,k,l)
        ans=min(ans,f(i,j,k,l))
print(ans)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
p = sorted([[int(_) for _ in input().split()] for i in range(N)])
a=10**20
for xi in range(N-K+1):
  for xj in range(xi+K-1,N):
    q = sorted(y for x,y in p[xi:xj+1])
    for yi,yj in zip(q,q[K-1:]):
      if yi<=p[xi][1] and p[xj][1]<=yj:
        a = min(a, (p[xi][0]-p[xj][0])*(yi-yj))
print(a)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
p = sorted([[int(_) for _ in input().split()] for i in range(N)])
a=10**20
for xi in range(N-K+1):
  for xj in range(xi+K-1,N):
    q = sorted(y for x,y in p[xi:xj+1])
    for yi in range(xj-(xi+K-1)+1):
      yj = yi+K-1 #Is the number always K?
      if q[yi]<=p[xi][1] and p[xj][1]<=q[yj]:
        a = min(a, (p[xi][0]-p[xj][0])*(q[yi]-q[yj]))
print(a)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, K, XY):
    X = sorted(map(lambda x: x[0], XY))
    RX = X[::-1]
    Y = sorted(map(lambda x: x[1], XY))
    RY = Y[::-1]

    ans = sys.maxsize
    for lx in X:
        for rx in RX:
            if lx > rx:
                break
            for by in Y:
                for ty in RY:
                    if by > ty:
                        break

                    k = 0
                    for x, y in XY:
                        if lx <= x <= rx and by <= y <= ty:
                            k += 1
                    if k >= K:
                        ans = min(ans, (rx-lx)*(ty-by))
                    else:
                        break

    return ans


def main():
    N, K = read_int_n()
    XY = [read_int_n() for _ in range(N)]

    print(slv(N, K, XY))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, K, XY):
    X = sorted(map(lambda x: x[0], XY))
    Y = sorted(map(lambda x: x[1], XY))

    ans = sys.maxsize
    for lx in X:
        for rx in X[::-1]:
            if lx > rx:
                break
            for by in Y:
                for ty in Y[::-1]:
                    if by > ty:
                        break

                    # print(lx, rx, by, ty)
                    k = 0
                    for x, y in XY:
                        if lx <= x <= rx and by <= y <= ty:
                            k += 1
                    # print(k)
                    if k >= K:
                        ans = min(ans, (rx-lx)*(ty-by))
                    else:
                        break

    return ans


def main():
    N, K = read_int_n()
    XY = [read_int_n() for _ in range(N)]

    # N = random.randint(2, 50)
    # N = 50
    # K = random.randint(2, N)
    # cm = int(1e+9)
    # XY = [(random.randint(-cm, cm), random.randint(-cm, cm)) for _ in range(N)]
    # print(N, K)
    print(slv(N, K, XY))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
point = []
y_list = []

for _ in range(N):
    x,y = map(int, input().split())
    point.append((x,y))
    y_list.append(y)
point = sorted(point,key=lambda tup: tup[0])
y_list.sort()
min_area = (y_list[N-1] - y_list[0]) * (point[N-1][0] - point[0][0])

for by in range(N):
    for ty in range(by+1,N):
        size=0
        idx = [0 for _ in range(N)]
        for i in range(N):
            if (y_list[by] <= point[i][1] and y_list[ty] >= point[i][1]):
                idx[size] = i
                size +=1
        lb = 0
        while(lb + K -1 < size):
            min_area = min(min_area, (y_list[ty] - y_list[by]) * (point[idx[lb + K - 1]][0] - point[idx[lb]][0]))
            lb+=1
print(min_area)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
P= [list(map(int, input().split())) for i in range(N)]
P=sorted(P)
pi=list(enumerate(P))
minA=float("inf")
for il,xyl in pi[:N-1]:
    left=xyl[0]
    for ir,xyr in pi[il+1:]:
        right=xyr[0]
        insd=[xy_ for i,xy_ in pi if xyl[0]<=xy_[0]<=xyr[0]]
        insd=sorted(insd,key=lambda xx:xx[1])
        in_L=len(insd)
        if in_L<K:continue
        for jd in range(in_L-K+1):
            ju=jd+K-1
            down=insd[jd][1]
            upper=insd[ju][1]
            minA=min(minA,(upper-down)*(right-left))

print(minA)

Submission status: Accepted

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

xy.sort()

result = (10**11)**2

for i in range(N):
    xl, _ = xy[i]
    for j in range(i + 1, N):
        xh, _ = xy[j]
        ys = sorted(y for x, y in xy if xl <= x <= xh)
        if len(ys) >= K:
            d = min(ys[i + K - 1] - ys[i] for i in range(len(ys) - K + 1))
            r = d * (xh - xl)
            result = min(result, r)
print(result)

Submission status: Accepted

Solution code:
n,k = (int(i) for i in input().split())
p = [[int(i) for i in input().split()] for i in range(n)]
p,ans = sorted(p),float("inf")
q = list(enumerate(p))
for i,(a,b) in q[:n-k+1]:
	for j,(c,d) in q[i+k-1:]:
		r = sorted(y for x,y in p[i:j+1])
		r2 = r[k-1:]
		for i2,j2 in zip(r,r2):
			if i2<=b and d<=j2: ans = min(ans,(c-a)*(j2-i2))
print(ans)

Submission status: Accepted

Solution code:
import sys

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

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

print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations

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

points.sort(key=lambda p:p[0])


min_area = 10**20
for k in range(K, N+1):
    for l in range(0, N-k+1):
        points_tmp = points[l:l+k]
        points_tmp.sort(key=lambda p:p[1])
        for m in range(0, k-K+1):
            points_selected = points_tmp[m: m+K]
            ymin = points_selected[0][1]
            ymax = points_selected[-1][1]
            points_selected.sort(key=lambda p:p[0])
            xmin = points_selected[0][0]
            xmax = points_selected[-1][0]
            area = (xmax-xmin) * (ymax-ymin)
            min_area = min(area, min_area)

print(min_area)

Submission status: Accepted

Solution code:
n, k = map(int, raw_input().split())
p = [map(int, raw_input().split()) for i in range(n)]
p = sorted(p, key=lambda _: _[0])
ans = 10**30
for b in range(n):
    x_b, y_b = p[b]
    for t in range(n):
        x_t, y_t = p[t]
        if y_t <= y_b:
            continue
        v = filter(lambda _: y_b <= _[1] <= y_t, p)
        for i in range(len(v) - k + 1):
            x_i, y_i = v[i]
            x_j, y_j = v[i+k-1]
            ans = min(ans, (x_j - x_i) * (y_t - y_b))
print ans

Submission status: Accepted

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

ans=10**50
for i in range(N-(K-1)):
  for j in range(i+(K-1),N):
    x,y=XY[i]
    x1,y1=XY[j]
    YX=sorted(XY[i:j+1], key=lambda x:x[1])
    for k in range(len(YX)-(K-1)):
      for l in range(k+(K-1),len(YX)):
        if YX[k][1] <= y and y1 <= YX[l][1]:
          ans=min(ans,(x1-x)*(YX[l][1]-YX[k][1]))

print(ans)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
xy = [list(map(int, input().split())) for _ in range(N)]
xy_xmin = sorted(xy,key=lambda x:x[0])
ans = float("INF")
for i in range(N):
    for j in range(i+K-1,N):
        X = xy_xmin[j][0] - xy_xmin[i][0]
        xy_ymin = sorted(xy_xmin[i:j+1],key=lambda x:x[1])
        Y = float("INF")
        for k in range(0,j-i-K+2):
            Y = min(Y,xy_ymin[k+K-1][1]-xy_ymin[k][1])
        ans = min(ans,X*Y)
print(ans)

Submission status: Accepted

Solution code:
import sys
N, K = [int(x) for x in input().split()]
p = [ list(map( int, input().split()) ) for i in range(N)]
p.sort( key=lambda x:x[1])
area_min = sys.maxsize
for i in range(N):
    for j in range( i+1, N):
        xmin = min( p[i][0], p[j][0])
        xmax = max( p[i][0], p[j][0])
        tmp = [ p[x] for x in range(N) if xmin<=p[x][0]<=xmax]
        num = len(tmp)
        if num < K:
            continue
        area = sys.maxsize
        for k in range( num-K+1):
            area = min( area, abs( (xmax-xmin)*(tmp[k][1]-tmp[K-1+k][1]) ) )
            # print( tmp[k], tmp[K-1+k], p[i], p[j], "area =", area, tmp[k:k+K])
        area_min = min( area_min, area)

print( "{}".format(area_min))

Submission status: Accepted

Solution code:
def d_axis_parallel_rectangle(N, K, P):
    x_array, y_array = [], []  # 点のx,y座標
    for x, y in P:
        x_array.append(x)
        y_array.append(y)

    x_sorted = sorted(x_array)
    y_sorted = sorted(y_array)  # 個別にソートしたため、点の座標と無関係

    # すべての点を内部に含む、最大の面積を持つ矩形が初期値
    ans = (x_sorted[N - 1] - x_sorted[0]) * (y_sorted[N - 1] - y_sorted[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):
                    num = 0
                    left = x_sorted[xi]
                    right = x_sorted[xj]
                    bottom = y_sorted[yi]
                    top = y_sorted[yj]

                    for i in range(N):
                        if left <= x_array[i] <= right and bottom <= y_array[i] <= top:
                            num += 1
                            if num == K:
                                ans = min(ans, (right - left) * (top - bottom))
                                break
    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: Accepted

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

to_search_x.sort()
to_search_y.sort()

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

for n in range(N):
    for i in range(N):
        for j in range(N):
            if points[n][0] <= to_search_x[i] and points[n][1] <= to_search_y[j]:
                points_matrix[i+1][j+1] += 1

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

print(ans)

Submission status: Accepted

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

sx = sorted(ps,key = lambda x: x[0]) # x座標でソート
nx = list(enumerate(sx)) # 頂点番号を付加
ans = 5e18

for f, (x1,y1) in nx[:n-k+1]: # 左辺の頂点
    for e, (x2,y2) in nx[f+k-1:]: # 右辺の頂点
        dx = x2 - x1 # 横
        sy = sorted(y for x,y in sx[f:e+1]) # 含まれる頂点をy座標でソート
        for y3,y4 in zip(sy,sy[k-1:]): # y3=下辺の頂点，y4=上辺の頂点
            if y3 <= y1 and y4 >= y2: # 左右辺の頂点を含むこと
                ans = min(ans, dx * (y4 - y3))

print(ans)

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
x = [0 for i in range(N)]
y = [0 for i in range(N)]
p = [0 for i in range(N)]
q = [0 for i in range(N)]
for i in range(N):
    x[i],y[i] = map(int, input().split())
    p[i]=x[i]
    q[i]=y[i]
x.sort()
y.sort()
S = [[0 for i in range(N+1)]for i in range(N+1)]
for n in range(N):
    for i in range(N):
        for j in range(N):
            if p[n]<=x[i] and q[n]<=y[j]:
                S[i+1][j+1]+=1
R=(x[N-1]-x[0])*(y[N-1]-y[0])
for a in range(N):
    for b in range(N):
        for c in range(a,N):
            for d in range(b,N):
                if (S[a][b]+S[c+1][d+1]-S[a][d+1]-S[c+1][b])>=K:
                    if (x[c]-x[a])*(y[d]-y[b])<R:
                        R=(x[c]-x[a])*(y[d]-y[b])
print(R)

Submission status: Accepted

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

x_order = {}
for xo, p in enumerate(XY):
    x, y, i = p
    x_order[i] = xo

cums = [[0 for j in range(N+1)] for i in range(N+1)]
for i in range(N):
    y, x, pi = YX[i]
    xo = x_order[pi]
    for j in range(N + 1):
        cums[i + 1][j] = cums[i][j] + (1 if j > xo else 0)

ans = 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):
                if cums[l+1][j+1] - cums[l+1][i] - cums[k][j+1] + cums[k][i] >= K:
                        ans = min(ans, (XY[j][0]-XY[i][0]) * (YX[l][0]-YX[k][0]))

print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations as comb
N, K = map(int, input().split())
ans = (2 * 10 ** 9) ** 2 + 1
choice = min(K, 4)
xs = [0] * N
ys = [0] * N
for i in range(N):
	xs[i], ys[i] = map(int, input().split())

for idxs in comb(range(N), choice):
	x_mx = y_mx = - 10 ** 9
	x_mn = y_mn = 10 ** 9
	for i in idxs:
		x_mx = max(x_mx, xs[i])
		y_mx = max(y_mx, ys[i])
		x_mn = min(x_mn, xs[i])
		y_mn = min(y_mn, ys[i])
	in_num = sum(x_mn <= xs[i] <= x_mx and y_mn <= ys[i] <= y_mx for i in range(N))
	area = (x_mx - x_mn) * (y_mx - y_mn)
	if in_num >= K and area < ans:
		ans = area
print(ans)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
ps = [tuple(map(int, input().split())) for i in range(n)]
sx = sorted(ps)
nx = list(enumerate(sx))

ans = 5e18
for l, (x1, y1) in nx[:n - k + 1]:
    for r, (x2, y2) in nx[l + k - 1:]:
        dx = x2 - x1
        sy = sorted(y for x, y in sx[l:r + 1])
        for y3, y4 in zip(sy, sy[k - 1:]):
            if y3 <= y1 and y2 <= y4:
                ans = min(ans, dx * (y4 - y3))
print(ans)

Submission status: Accepted

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

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

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

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

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

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

for (l, r), (d, u) in product(combinations(X, 2), combinations(Y, 2)):
    if (dX[r] - dX[l] < K-1) or (dY[u] - dY[d] < K-1):
        continue
    if res < (r-l)*(u-d):
        continue

    sx = set(map(get, Px[dX[l]:dX[r]+1]))
    sy = set(map(get, Py[dY[d]:dY[u]+1]))
    if len(sx.intersection(sy)) >= K:
        res = min(res, (r-l)*(u-d))

print(res)

Submission status: Accepted

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

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

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

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

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

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

for (l, r), (d, u) in product(combinations(X, 2), combinations(Y, 2)):
    if res < (r-l)*(u-d):
        continue
    if (dX[r] - dX[l] < K-1) or (dY[u] - dY[d] < K-1):
        continue

    sx = set(map(get, Px[dX[l]:dX[r]+1]))
    sy = set(map(get, Py[dY[d]:dY[u]+1]))
    if len(sx.intersection(sy)) >= K:
        res = min(res, (r-l)*(u-d))

print(res)

Submission status: Accepted

Solution code:
from itertools import combinations

def solve():
  N, K = map(int, input().split())
  vertices = [tuple(map(int, input().split())) for _ in [0]*N]
  sorted_v = sorted(vertices)
  result = float("inf")

  for l in combinations(sorted_v, min(4, K)):
    xs = sorted(x for x, y in l)
    ys = sorted(y for x, y in l)
    min_x, max_x = xs[0], xs[-1]
    min_y, max_y = ys[0], ys[-1]
    if sum(1 for x, y in vertices if min_x <= x <= max_x and min_y <= y <= max_y) >= K:
      s = (max_x - min_x) * (max_y - min_y)
      if result > s:
        result = s
  print(result)

if __name__ == "__main__":
  solve()

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
X, Y, XY = [], [], []
for i in range(N):
  x, y = map(int,input().split())
  X += [x]
  Y += [y]
  XY += [[x,y]]
  
ans = float("inf")

for x1 in range(N):
  for x2 in range(x1+1,N):
    for y1 in range(N):
      for y2 in range(y1+1,N):
        boxed = 0
        for i in range(N):
          if (X[x1] - X[i])*(X[x2]-X[i])<=0 and (Y[y1] - Y[i])*(Y[y2]-Y[i])<=0:
            boxed+= 1
        if boxed >= K: 
          ans = min(ans,abs(X[x1]-X[x2])*abs(Y[y1]-Y[y2]))
          #print(abs(X[x1]-X[x2])*abs(Y[y1]-Y[y2]))
print(ans)

Submission status: Accepted

Solution code:
def solve():
    from itertools import combinations
    N, K = map(int, input().split())
    vertices = [tuple(map(int, input().split())) for _ in [0]*N]
    sorted_v = sorted(vertices)
    result = float("inf")
 
    for l in combinations(sorted_v, min(4, K)):
        xs = sorted(x for x, y in l)
        ys = sorted(y for x, y in l)
        min_x, max_x = xs[0], xs[-1]
        min_y, max_y = ys[0], ys[-1]
        if sum(1 for x, y in vertices if min_x <= x <= max_x and min_y <= y <= max_y) >= K:
            s = (max_x-min_x)*(max_y-min_y)
            if result > s:
                result = s
 
    print(result)
 
 
if __name__ == "__main__":
    solve()

Submission status: Accepted

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)

S_l = [[0 for i in range(N)] for j in range(N)]
S_rs = [[0 for i in range(N)] for j in range(N)]
S_ts = [[0 for i in range(N)] for j in range(N)]
S_s = [[0 for i in range(N)] for j in range(N)]
for i in range(N):
    for j in range(N):
        count_l = 0
        count_rs = 0
        count_ts = 0
        count_s = 0
        for k in range(N):
            if -10 ** 9 <= x[k] <= x_sorted[i] and -10 ** 9 <= y[k] <= y_sorted[j]:
                count_l += 1
            if -10 ** 9 <= x[k] < x_sorted[i] and -10 ** 9 <= y[k] <= y_sorted[j]:
                count_rs += 1
            if -10 ** 9 <= x[k] <= x_sorted[i] and -10 ** 9 <= y[k] < y_sorted[j]:
                count_ts += 1
            if -10 ** 9 <= x[k] < x_sorted[i] and -10 ** 9 <= y[k] < y_sorted[j]:
                count_s += 1
        S_l[i][j] = count_l
        S_rs[i][j] = count_rs
        S_ts[i][j] = count_ts
        S_s[i][j] = count_s


def included(i, j, k, l):
    return S_l[j][l] - S_rs[i][l] - S_ts[j][k] + S_s[i][k]

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(i, j, k, 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: Accepted

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

points = []
pointsx = []
pointsy = []

smin = 0

for i in range(N):
    x,y = map(int, raw_input().split(" "))
    pointsx.append(x)
    pointsy.append(y)

spx = sorted(pointsx)

for i in range(N-K+1):
    for h in range(N-K-i+1):
        yneed = []
        for k in range(N):
            if pointsx[k]>=spx[i] and pointsx[k]<=spx[i+K+h-1]:
                yneed.append(pointsy[k])
        spy = sorted(yneed)
        ylength = 0
        xlength = spx[i+K+h-1]-spx[i]
        for k in range(len(spy) - K + 1):
            if ylength == 0: ylength = spy[k+K-1]-spy[k]
            elif ylength > spy[k+K-1]-spy[k]: ylength = spy[k+K-1]-spy[k]
        if smin == 0: smin = ylength * xlength
        elif smin > ylength * xlength:
            smin = ylength * xlength


print smin

Submission status: Accepted

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)
            break  # no other rects for the same i0, i1, y0 are unnecessary
  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: Accepted

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

sx = sorted(ps) #xの順にソート
nx = list(enumerate(sx)) #それぞれの点に番号をつける0〜
ans = 5e18

for l, (x1, y1) in nx[:n - k + 1]: #4つ中3つなら先頭2つまで見ればいい
    for r, (x2, y2) in nx[l + k - 1:]: #0番目を見てる時は2番目以降、
        dx = x2 - x1
        sy = sorted(y for x, y in sx[l:r + 1])

        for y3, y4 in zip(sy, sy[k - 1:]):
            if y3 <= y1 and y2 <= y4:
                ans = min(ans, dx * (y4 - y3))
print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations as comb

def count(x1,y1,x2,y2):
    res = 0
    for x,y in point:
        if x1 <= x <= x2 and y1 <= y <= y2:
            res += 1
    return res 
    
N,K = map(int,input().split())

x = []
point = []
y_dict = {}

for i in range(N):
    a,b = map(int,input().split())
    x.append(a)
    point.append((a,b))
    y_dict[a] = b#yの値はxの値と紐づけしておく

x = sorted(x)
ans = 10**20

number = [i for i in range(N)]
C = list(comb(number,2))

for i,j in C:#組合せで調べる
    y_list = []

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

    if 2 <= len(y_list):
        number2 = [i for i in range(len(y_list))]
        C_2 = list(comb(number2,2))

        for l,m in C_2:        
                x1 = x[i]
                y1 = y_list[l]
                x2 = x[j]
                y2 = y_list[m]
                n = count(x1,y1,x2,y2)#区間内の点の数
                   
                if K <= n :
                    ans = min(ans,(x2-x1)*(y2-y1)) 
               
print(ans)

Submission status: Accepted

Solution code:
import itertools

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

#print "# x,y"
x.sort()
y.sort()
#print x
#print y

#print "# pts"
#print pts
pts.sort(key=lambda x:x[0])
#print pts

ans=10**20


for y1 in y:
	for y2 in y:
		if y1>=y2:
			continue
		for x1 in x:
			cnt=0
			for p in pts:
				if p[0]>=x1 and p[1]>=y1 and p[1]<=y2:
					#print p[0],p[1],x1,y1,y2
					cnt+=1
					if cnt==K:
						x2=p[0]
						#print x1,y1,x2,y2,cnt,abs(x2-x1)*abs(y2-y1)
						ans=min(ans,abs(x2-x1)*abs(y2-y1))
						break

print ans

Submission status: Accepted

Solution code:
N,K = map(int, input().split())
p = []
for i in range(N):
    a,b = map(int, input().split())
    p.append((a,b))
    
sx = sorted(p)
ans = 10**50
for x1,y1 in sx:
    for x2,y2 in sx:
        if x2 <= x1:
            continue
        l = sx.index((x1, y1))
        r = sx.index((x2, y2))
        if r-l+1 < K:
            continue
        sy = sorted(sx[l:r+1],key=lambda coor: coor[1])
        for j in range(len(sy)-K+1):
            if sy[j][1] <= y1 and y2 <= sy[j+K-1][1]:
                ans = min(ans, (x2 - x1) * (sy[j+K-1][1]-sy[j][1])) 
print(ans)

Submission status: Accepted

Solution code:
import sys
def LI(): return [int(x) for x in sys.stdin.readline().split()]
 
N,K = LI()
p = []
for i in range(N):
    a,b = LI()
    p.append((a,b))
sx = sorted(p)
ans = 10**50
for x,y in sx:
    for x2,y2 in sx:
        if x2 <= x:
            continue
        points = sx.index((x2,y2)) - sx.index((x,y)) + 1
        if points < K:
            continue
        sy = sorted(sx[sx.index((x,y)):sx.index((x2,y2))+1],key=lambda coor: coor[1])
        for j in range(len(sy)-K, -1, -1):
            if sy[j][1] <= y and y2 <= sy[j+K-1][1]:
                ans = min(ans, (x2 - x) * (sy[j+K-1][1]-sy[j][1])) 
print(ans)

Submission status: Accepted

Solution code:
import sys
def LI(): return [int(x) for x in sys.stdin.readline().split()]
 
N,K = LI()
p = []
for i in range(N):
    a,b = LI()
    p.append((a,b))
sx = sorted(p)
ans = 10**50
for x,y in sx:
    for x2,y2 in sx:
        if x2 <= x:
            continue
        points = sx.index((x2,y2)) - sx.index((x,y)) + 1
        if points < K:
            continue
        sy = sorted(sx[sx.index((x,y)):sx.index((x2,y2))+1],key=lambda sx: sx[1])
        for j in range(len(sy)-K+1):
            if sy[j][1] <= y and y2 <= sy[j+K-1][1]:
                ans = min(ans, (x2 - x) * (sy[j+K-1][1]-sy[j][1])) 
print(ans)

Submission status: Accepted

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

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

x_order = {}
for xo,p in enumerate(xs):
    x,y,i = p
    x_order[i] = xo

cums = [[0 for j in range(N+1)] for i in range(N+1)]
for i in range(N):
    y,x,pi = ys[i]
    xo = x_order[pi]
    for j in range(N+1):
        cums[i+1][j] = cums[i][j] + (1 if j > xo else 0)

ans = float('inf')
for x1 in range(N-1):
    for x2 in range(x1+1,N):
        for y1 in range(N-1):
            for y2 in range(y1+1,N):
                if cums[y2+1][x2+1] - cums[y2+1][x1] - cums[y1][x2+1] + cums[y1][x1] < K:
                    continue
                area = (xs[x2][0] - xs[x1][0]) * (ys[y2][0] - ys[y1][0])
                ans = min(ans, area)
print(ans)

Submission status: Accepted

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 iLeft, ptLeft in enumerate(ptsX):
    setX = set(ptsX[iLeft:])

    for ptRight in ptsX[iLeft + 1:][::-1]:
        if len(setX) < K: break
        lenX = ptRight[0] - ptLeft[0]

        for iBottom, ptBottom in enumerate(ptsY):
            setY = set(ptsY[iBottom:])

            for ptTop in ptsY[iBottom + 1:][::-1]:
                if len(setY) < K: break

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

                if num == K:
                    lenY = ptTop[1] - ptBottom[1]
                    area = lenX * lenY
                    ans = min(ans, area)

                setY.remove(ptTop)

        setX.remove(ptRight)

print(ans)