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: Runtime Error

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, A):
    EC = []
    for i, r in enumerate(A):
        for j, c in enumerate(r):
            if c == 0:
                break
            EC.append((c, i, j))

    EC.sort()
    ans = 0
    for c, i, j in EC:
        q = [(0, i)]
        min_path = c
        f = True
        while q:
            c2, k = q.pop()
            if k != i and c2 + A[k][j] <= min_path:
                min_path = c2 + A[k][j]
                f = False
            else:
                for l, c3 in enumerate(A[k]):
                    if l != i and c3 != 0 and c2 + c3 < c:
                        q.append((c2 + c3, l))

        if min_path != c:
            return -1
        elif f:
            ans += c
    return ans


def main():
    N = read_int()
    A = [read_int_n() for _ in range(N)]

    print(slv(N, A))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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-1]
        points_tmp.sort(key=lambda p:p[1])
        for m in range(0, N-K+1):
            points_selected = points_tmp[m, m+K-1]
            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: Runtime Error

Solution code:
def solve():
    from itertools import combinations
    N, K = map(int, input().split())
    v = [tuple(map(int, input().split())) for _ in [0]*N]
    sorted_v = sorted(v)
    ans = float('inf')
    #print(v)
    
    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 v if min_x <= x <= max_x and min_y <= y <= max_y) >= K:
            s = (max_x - min_x) * (max_y - min_y)
        if ans > s:
            ans = s
    
    print(ans)
    
if __name__ == '__main__':
    solve()

Submission status: Runtime Error

Solution code:
import bisect
# x or y で sortしてK個見る
# これだけだと同一xに対して複数の選択がある時に落ちる
# 群数列てきな考えがいる？
n, k = map(int, input().split())

point = []
for i in range(n):
    point.append(list(map(int, input().split())))
point.sort()

# Xのポイント
dic = {}
for i in set([j[0] for j in point]):
    dic[i] = []
for i in point:
    dic[i[0]].append(i[1])
for i in set([j[0] for j in point]):
    dic[i].sort()

ans_prob = []
for i in range(n - k + 1):
    xmin = point[i][0]
    xmax = point[i + k - 1][0]
    #
    if xmin == xmax:
        print(0)
        exit()
    else:
        mid_flag = 0
        _y = []
        for j in range(i, i+k):
            if point[j][0] != xmin and point[j][0] != xmax:
                mid_flag = 1
                _y.append(point[j][1])

        #xminとxmaxの間に要素が存在しない時
        if mid_flag == 0:
            ret = 4*10**18
            for j in dic[xmin]:
                for k in dic[xmax]:
                    ret = min(ret, abs(j - k))
            ans_prob.append(ret)
        else:
            ymax_other = max(_y)
            ymin_other = min(_y)
            #これがどこに入るか考えなければいけない
            #xminについて
            flag = 0
            #xminが入らない時
            if dic[xmin][0] > ymax_other:
                ymax_other = dic[xmin][0]
            elif dic[xmin][-1] < ymin_other:
                ymin_other = dic[xmin][-1]
            else:
                xmin_point_min = bisect.bisect_left(dic[xmin], ymin_other)
                xmin_point_max = bisect.bisect_left(dic[xmin], ymax_other)
                #途中で入れないとき  xminが[1,5]のときに[2,3]のとき
                if xmin_point_max == xmin_point_min:
                    flag = 1
                    xmin_left = dic[xmin][xmin_point_max - 1]
                    xmin_right = dic[xmin][xmin_point_max]
                    hozon = ymin_other
                    ymin_other = xmin_left
                    #xmin_rightが採用される時を追加で判定すればいい
                # 入る時つまりymin, ymaxに変化なし
                else:
                    pass
            #xmaxについて
            #xmaxが入らない時
            if dic[xmax][0] > ymax_other:
                ymax_other = dic[xmax][0]
            elif dic[xmax][-1] < ymin_other:
                ymin_other = dic[xmax][-1]
            else:
                xmax_point_min = bisect.bisect_left(dic[xmax], ymin_other)
                xmax_point_max = bisect.bisect_left(dic[xmax], ymax_other)
                #途中で入れないとき  xmaxが[1,5]のときに[2,3]のとき
                if xmax_point_max == xmax_point_min:
                    xmax_left = dic[xmax][xmax_point_max]
                    xmax_right = dic[xmax][xmax_point_max + 1]
                    if ymin_other - xmax_left < xmax_right - ymax_other:
                        ymin_other = xmax_left
                    else:
                        ymax_other = xmax_right
                # 入る時つまりymin, ymaxに変化なし
                else:
                    pass
            ans_prob.append((xmax - xmin)*(ymax_other - ymin_other))

            if flag != 0:
                ymin_other = hozon
                ymax_other = xmin_right

                if dic[xmax][0] > ymax_other:
                    ymax_other = dic[xmax][0]
                elif dic[xmax][-1] < ymin_other:
                    ymin_other = dic[xmax][-1]
                else:
                    xmax_point_min = bisect.bisect_left(dic[xmax], ymin_other)
                    xmax_point_max = bisect.bisect_left(dic[xmax], ymax_other)
                    #途中で入れないとき  xmaxが[1,5]のときに[2,3]のとき
                    if xmax_point_max == xmax_point_min:
                        xmax_left = dic[xmax][xmax_point_max]
                        xmax_right = dic[xmax][xmax_point_max + 1]
                        if ymin_other - xmax_left < xmax_right - ymax_other:
                            ymin_other = xmax_left
                        else:
                            ymax_other = xmax_right
                    # 入る時つまりymin, ymaxに変化なし
                    else:
                        pass
                ans_prob.append((xmax - xmin)*(ymax_other - ymin_other))

ans_prob.sort()
print(ans_prob[0])

Submission status: Runtime Error

Solution code:
import bisect
# x or y で sortしてK個見る
# これだけだと同一xに対して複数の選択がある時に落ちる
# 群数列てきな考えがいる？
n, k = map(int, input().split())

point = []
for i in range(n):
    point.append(list(map(int, input().split())))
point.sort()

# Xのポイント
dic = {}
for i in set([j[0] for j in point]):
    dic[i] = []
for i in point:
    dic[i[0]].append(i[1])
for i in set([j[0] for j in point]):
    dic[i].sort()

ans_prob = []
for i in range(n - k + 1):
    xmin = point[i][0]
    xmax = point[i + k - 1][0]
    #
    if xmin == xmax:
        print(0)
        exit()
    else:
        mid_flag = 0
        _y = []
        for j in range(i, i+k):
            if point[j][0] != xmin and point[j][0] != xmax:
                mid_flag = 1
                _y.append(point[j][1])

        #xminとxmaxの間に要素が存在しない時
        if mid_flag == 0:
            ret = 4*10**18
            for j in dic[xmin]:
                for k in dic[xmax]:
                    ret = min(ret, abs(j - k))
            ans_prob.append(ret)
        else:
            ymax_other = max(_y)
            ymin_other = min(_y)
            #これがどこに入るか考えなければいけない
            #xminについて
            flag = 0
            #xminが入らない時
            if dic[xmin][0] > ymax_other:
                ymax_other = dic[xmin][0]
            elif dic[xmin][-1] < ymin_other:
                ymin_other = dic[xmin][-1]
            else:
                xmin_point_min = bisect.bisect_left(dic[xmin], ymin_other)
                xmin_point_max = bisect.bisect_left(dic[xmin], ymax_other)
                #途中で入れないとき  xminが[1,5]のときに[2,3]のとき
                if xmin_point_max == xmin_point_min:
                    flag = 1
                    xmin_left = dic[xmin][xmin_point_max - 1]
                    xmin_right = dic[xmin][xmin_point_max]
                    hozon = ymin_other
                    ymin_other = xmin_left
                    #xmin_rightが採用される時を追加で判定すればいい
                # 入る時つまりymin, ymaxに変化なし
                else:
                    pass
            #xmaxについて
            #xmaxが入らない時
            if dic[xmax][0] > ymax_other:
                ymax_other = dic[xmax][0]
            elif dic[xmax][-1] < ymin_other:
                ymin_other = dic[xmax][-1]
            else:
                xmax_point_min = bisect.bisect_left(dic[xmax], ymin_other)
                xmax_point_max = bisect.bisect_left(dic[xmax], ymax_other)
                #途中で入れないとき  xmaxが[1,5]のときに[2,3]のとき
                if xmax_point_max == xmax_point_min:
                    xmax_left = dic[xmin][xmin_point_max]
                    xmax_right = dic[xmin][xmin_point_max + 1]
                    if ymin_other - xmax_left < xmax_right - ymax_other:
                        ymin_other = xmax_left
                    else:
                        ymax_other = xmax_right
                # 入る時つまりymin, ymaxに変化なし
                else:
                    pass
            ans_prob.append((xmax - xmin)*(ymax_other - ymin_other))

            if flag != 0:
                ymin_other = hozon
                ymax_other = xmin_right

                if dic[xmax][0] > ymax_other:
                    ymax_other = dic[xmax][0]
                elif dic[xmax][-1] < ymin_other:
                    ymin_other = dic[xmax][-1]
                else:
                    xmax_point_min = bisect.bisect_left(dic[xmax], ymin_other)
                    xmax_point_max = bisect.bisect_left(dic[xmax], ymax_other)
                    #途中で入れないとき  xmaxが[1,5]のときに[2,3]のとき
                    if xmax_point_max == xmax_point_min:
                        xmax_left = dic[xmin][xmin_point_max]
                        xmax_right = dic[xmin][xmin_point_max + 1]
                        if ymin_other - xmax_left < xmax_right - ymax_other:
                            ymin_other = xmax_left
                        else:
                            ymax_other = xmax_right
                    # 入る時つまりymin, ymaxに変化なし
                    else:
                        pass
                ans_prob.append((xmax - xmin)*(ymax_other - ymin_other))

ans_prob.sort()
print(ans_prob[0])

Submission status: Runtime Error

Solution code:
import bisect
# x or y で sortしてK個見る
# これだけだと同一xに対して複数の選択がある時に落ちる
# 群数列てきな考えがいる？
n, k = map(int, input().split())

point = []
for i in range(n):
    point.append(list(map(int, input().split())))
point.sort()

# Xのポイント
dic = {}
for i in set([j[0] for j in point]):
    dic[i] = []
for i in point:
    dic[i[0]].append(i[1])
for i in set([j[0] for j in point]):
    dic[i].sort()

ans_prob = []
for i in range(n - k + 1):
    xmin = point[i][0]
    xmax = point[i + k - 1][0]
    #
    if xmin == xmax:
        print(0)
        exit()
    else:
        mid_flag = 0
        _y = []
        for j in range(i, i+k):
            if point[j][0] != xmin and point[j][0] != xmax:
                mid_flag = 1
                _y.append(point[j][1])

        #xminとxmaxの間に要素が存在しない時
        if mid_flag == 0:
            ret = 4*10**18
            for j in dic[xmin]:
                for k in dic[xmax]:
                    ret = min(ret, abs(j - k))
            ans_prob.append(ret)
        else:
            ymax_other = max(_y)
            ymin_other = min(_y)
            #これがどこに入るか考えなければいけない
            #xminについて
            flag = 0
            #xminが入らない時
            if dic[xmin][0] > ymax_other:
                ymax_other = dic[xmin][0]
            elif dic[xmin][-1] < ymin_other:
                ymin_other = dic[xmin][-1]
            else:
                xmin_point_min = bisect.bisect_left(dic[xmin], ymin_other)
                xmin_point_max = bisect.bisect_left(dic[xmin], ymax_other)
                #途中で入れないとき  xminが[1,5]のときに[2,3]のとき
                if xmin_point_max == xmin_point_min:
                    flag = 1
                    xmin_left = dic[xmin][xmin_point_max]
                    xmin_right = dic[xmin][xmin_point_max + 1]
                    hozon = ymin_other
                    ymin_other = xmin_left
                    #xmin_rightが採用される時を追加で判定すればいい
                # 入る時つまりymin, ymaxに変化なし
                else:
                    pass
            #xmaxについて
            #xmaxが入らない時
            if dic[xmax][0] > ymax_other:
                ymax_other = dic[xmax][0]
            elif dic[xmax][-1] < ymin_other:
                ymin_other = dic[xmax][-1]
            else:
                xmax_point_min = bisect.bisect_left(dic[xmax], ymin_other)
                xmax_point_max = bisect.bisect_left(dic[xmax], ymax_other)
                #途中で入れないとき  xmaxが[1,5]のときに[2,3]のとき
                if xmax_point_max == xmax_point_min:
                    xmax_left = dic[xmin][xmin_point_max]
                    xmax_right = dic[xmin][xmin_point_max + 1]
                    if ymin_other - xmax_left < xmax_right - ymax_other:
                        ymin_other = xmax_left
                    else:
                        ymax_other = xmax_right
                # 入る時つまりymin, ymaxに変化なし
                else:
                    pass
            ans_prob.append((xmax - xmin)*(ymax_other - ymin_other))

            if flag != 0:
                ymin_other = hozon
                ymax_other = xmin_right

                if dic[xmax][0] > ymax_other:
                    ymax_other = dic[xmax][0]
                elif dic[xmax][-1] < ymin_other:
                    ymin_other = dic[xmax][-1]
                else:
                    xmax_point_min = bisect.bisect_left(dic[xmax], ymin_other)
                    xmax_point_max = bisect.bisect_left(dic[xmax], ymax_other)
                    #途中で入れないとき  xmaxが[1,5]のときに[2,3]のとき
                    if xmax_point_max == xmax_point_min:
                        xmax_left = dic[xmin][xmin_point_max]
                        xmax_right = dic[xmin][xmin_point_max + 1]
                        if ymin_other - xmax_left < xmax_right - ymax_other:
                            ymin_other = xmax_left
                        else:
                            ymax_other = xmax_right
                    # 入る時つまりymin, ymaxに変化なし
                    else:
                        pass
                ans_prob.append((xmax - xmin)*(ymax_other - ymin_other))

ans_prob.sort()
print(ans_prob[0])

Submission status: Runtime Error

Solution code:
import bisect
# x or y で sortしてK個見る
# これだけだと同一xに対して複数の選択がある時に落ちる
# 群数列てきな考えがいる？
n, k = map(int, input().split())

point = []
for i in range(n):
    point.append(list(map(int, input().split())))
point.sort()

# Xのポイント
dic = {}
for i in set([j[0] for j in point]):
    dic[i] = []
for i in point:
    dic[i[0]].append(i[1])
for i in set([j[0] for j in point]):
    dic[i].sort()

ans_prob = []
for i in range(n - k + 1):
    xmin = point[i][0]
    xmax = point[i + k - 1][0]
    #
    if xmin == xmax:
        print(0)
        exit()
    #もしmidが無いところなら
    elif xmax == xmin + 1:
        ret = 4*10**18
        for j in dic[xmin]:
            for k in dic[xmax]:
                ret = min(ret, abs(j - k))
        ans_prob.append(ret)
    else:
        _y = []
        for j in range(i, i+k):
            if point[j][0] != xmin and point[j][0] != xmax:
                _y.append(point[j][1])
        ymax_other = max(_y)
        ymin_other = min(_y)
        #これがどこに入るか考えなければいけない
        #xminについて
        flag = 0
        #xminが入らない時
        if dic[xmin][0] > ymax_other:
            ymax_other = dic[xmin][0]
        elif dic[xmin][-1] < ymin_other:
            ymin_other = dic[xmin][-1]
        else:
            xmin_point_min = bisect.bisect_left(dic[xmin], ymin_other)
            xmin_point_max = bisect.bisect_left(dic[xmin], ymax_other)
            #途中で入れないとき  xminが[1,5]のときに[2,3]のとき
            if xmin_point_max == xmin_point_min:
                flag = 1
                xmin_left = dic[xmin][xmin_point_max]
                xmin_right = dic[xmin][xmin_point_max + 1]
                hozon = ymin_other
                ymin_other = xmin_left
                #xmin_rightが採用される時を追加で判定すればいい
            # 入る時つまりymin, ymaxに変化なし
            else:
                pass
        #xmaxについて
        #xmaxが入らない時
        if dic[xmax][0] > ymax_other:
            ymax_other = dic[xmax][0]
        elif dic[xmax][-1] < ymin_other:
            ymin_other = dic[xmax][-1]
        else:
            xmax_point_min = bisect.bisect_left(dic[xmax], ymin_other)
            xmax_point_max = bisect.bisect_left(dic[xmax], ymax_other)
            #途中で入れないとき  xmaxが[1,5]のときに[2,3]のとき
            if xmax_point_max == xmax_point_min:
                xmax_left = dic[xmin][xmin_point_max]
                xmax_right = dic[xmin][xmin_point_max + 1]
                if ymin_other - xmax_left < xmax_right - ymax_other:
                    ymin_other = xmax_left
                else:
                    ymax_other = xmax_right
            # 入る時つまりymin, ymaxに変化なし
            else:
                pass
        ans_prob.append((xmax - xmin)*(ymax_other - ymin_other))

        if flag != 0:
            ymin_other = hozon
            ymax_other = xmin_right

            if dic[xmax][0] > ymax_other:
                ymax_other = dic[xmax][0]
            elif dic[xmax][-1] < ymin_other:
                ymin_other = dic[xmax][-1]
            else:
                xmax_point_min = bisect.bisect_left(dic[xmax], ymin_other)
                xmax_point_max = bisect.bisect_left(dic[xmax], ymax_other)
                #途中で入れないとき  xmaxが[1,5]のときに[2,3]のとき
                if xmax_point_max == xmax_point_min:
                    xmax_left = dic[xmin][xmin_point_max]
                    xmax_right = dic[xmin][xmin_point_max + 1]
                    if ymin_other - xmax_left < xmax_right - ymax_other:
                        ymin_other = xmax_left
                    else:
                        ymax_other = xmax_right
                # 入る時つまりymin, ymaxに変化なし
                else:
                    pass
            ans_prob.append((xmax - xmin)*(ymax_other - ymin_other))

ans_prob.sort()
print(ans_prob[0])

Submission status: Runtime Error

Solution code:
N,K = [int(_) for _ in input().split()]
arealist = []
xlist = []
ylist = []
xylist =[]
count = 0
count2 = 0
count3 = 0
#print(N,K)
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):
    #print("i={}".format(i))
    xw = xsorted[i]
    count = 1
    temp = []
    temp.append(xw)
    #print(count)
    for j in range(i+1,N):
        #print("j={}".format(j))
        xe = xsorted[j]
        temp.append(xe)
        count += 1
        if count < K:
            continue
        for k in range(N-1):
            ys = ysorted[k]
            if k >= 1:
                if xlist[ylist.index(ysorted[k-1])] in temp:
                    count -= 1
                    count3 +=1
            if count < K or k == N-2:
                count += count3
                count3 = 0
                break
            for l in reversed(range(k+1, N)):
                yn = ysorted[l]
                if l < N-1:
                    if xlist[ylist.index(ysorted[l+1])] in temp:
                        count -= 1
                        count2 += 1
                if count >= K:
                    arealist.append((xe-xw)*(yn-ys))

                if count<K or l ==k +1 :
                    count += count2
                    count2 = 0
                    break
#print(arealist)
print(sorted(arealist)[0])

Submission status: Runtime Error

Solution code:
N,K = [int(_) for _ in input().split()]
arealist = []
xlist = []
ylist = []
xylist =[]
count = 0
count2 = 0
count3 = 0
#print(N,K)
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):
    #print("i={}".format(i))
    xw = xsorted[i]
    count = 1
    temp = []
    temp.append(xsorted[i])
    #print(count)
    for j in range(i+1,N):
        #print("j={}".format(j))
        xe = xsorted[j]
        temp.append(xsorted[j])
        count += 1
        #print(count)
        if count < K:
            #print("hi+1")
            continue
        for k in range(N-1):
            ys = ysorted[k]
            if k >= 1:
                if xlist[ylist.index(ysorted[k-1])] in temp:
                    count -= 1
                    count3 +=1
            #print("k={}".format(k))
            #print(count)
            if count < K or k == N-2:
                count += count3
                count3 = 0
                break
            for l in range(N-k-1):
                #print("l={}".format(l))
                yn = ysorted[N-l-1]
                if l >= 1:
                    if xlist[ylist.index(ysorted[N-l])] in temp:
                        count -= 1
                        count2 += 1
                    #print(count)
                if count >= K:
                    #print(xw,xe)
                    #print(ys,yn)
                    arealist.append((xe-xw)*(yn-ys))

                if count<K or l == N-k-2:
                    count += count2
                    count2 = 0
                    break
#print(arealist)
print(sorted(arealist)[0])

Submission status: Runtime Error

Solution code:
N,K = [int(_) for _ in input().split()]
arealist = []
xlist = []
ylist = []
xylist =[]
count = 0
count2 = 0
count3 = 0
#print(N,K)
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):
    #print("i={}".format(i))
    xw = xsorted[i]
    count = 1
    temp = []
    temp.append(xsorted[i])
    #print(count)
    for j in range(i+1,N):
        #print("j={}".format(j))
        xe = xsorted[j]
        temp.append(xsorted[j])
        count += 1
        #print(count)
        if count < K:
            #print("hi+1")
            continue
        for k in range(N-1):
            ys = ysorted[k]
            if k >= 1:
                if xlist[ylist.index(ysorted[k-1])] in temp:
                    count -= 1
                    count3 +=1
            #print("k={}".format(k))
            #print(count)
            if count < K or k == N-2:
                count += count3
                count3 = 0
                break
            for l in range(N-k-1):
                #print("l={}".format(l))
                yn = ysorted[N-l-1]
                if l >= 1:
                    if xlist[ylist.index(ysorted[N-l])] in temp:
                        count -= 1
                        count2 += 1
                    #print(count)
                if count >= K:
                    #print(xw,xe)
                    #print(ys,yn)
                    arealist.append((xe-xw)*(yn-ys))

                if count<K or (l == N-k-2):
                    count += count2
                    count2 = 0
                    break
#print(arealist)
print(sorted(arealist)[0])

Submission status: Runtime Error

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 = xlist[i]
                xe = xlist[j]
                ys = ylist[k]
                yn = ylist[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)
sorted(arealist)
print(sorted(arealist)[0])

Submission status: Runtime Error

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])
#print(xlist,ylist)
for i in range(N):
    for j in range(i+1,N):
        count = 0
        a = xylist[i]
        b = xylist[j]
        SW = [min(a[0],b[0]),min(a[1],b[1])]
        SE = [max(a[0], b[0]), min(a[1], b[1])]
        NW = [min(a[0], b[0]), max(a[1], b[1])]
        NE = [max(a[0], b[0]), max(a[1], b[1])]
        #print(SW,SE,NW,NE)
        for k in range(N):
            if (SW[0] <= xlist[k] <= SE[0]) and (SW[1] <= ylist[k] <= NW[1]):
                count += 1
        if count >= K:
            #print(count)
            arealist.append((NW[1]-SW[1])*(NE[0]-NW[0]))
#print(arealist)
sorted(arealist)
print(arealist[0])

Submission status: Runtime Error

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 i, j in a:
                    if i >= x1 and i <= x2 and j <= y2 and j >= y1:
                        cnt += 1
                if cnt >= k1:
                    area = min(area, atot)

print(area)

Submission status: Runtime Error

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(lx<=x[z]<=rx and ly<=y[z]<=ry for z in range(i,j+1)): r=q
print(r)

Submission status: Runtime Error

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

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


 S = 99999999999999999999
 for xi in range(N):
     for xj in range(N):
         for yi in range(N):
             for yj in range(N):
                 l = abs(co[xi][0] - co[xj][0])
                 m = abs(co[yi][1] - co[yj][1])

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

Submission status: Runtime Error

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

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


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