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:
#!/usr/bin/env python3

import sys
# import time
# import math
# import numpy as np
# import scipy.sparse.csgraph as cs            # csgraph_from_dense(ndarray, null_value=inf), bellman_ford(G, return_predecessors=True), dijkstra, floyd_warshall
# import random                                # random, uniform, randint, randrange, shuffle, sample
# import string                                # ascii_lowercase, ascii_uppercase, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from datetime import date, datetime          # date.today(), date(year,month,day) => date obj; datetime.now(), datetime(year,month,day,hour,second,microsecond) => datetime obj; subtraction => timedelta obj
# from datetime.datetime import strptime       # strptime('2019/01/01 10:05:20', '%Y/%m/%d/ %H:%M:%S') returns datetime obj
# from datetime import timedelta               # td.days, td.seconds, td.microseconds, td.total_seconds(). abs function is also available.
# from copy import copy, deepcopy              # use deepcopy to copy multi-dimentional matrix without reference
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from fractions import gcd                    # for Python 3.4 (previous contest @AtCoder)



def main():
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79...e+308
    # inf = 2 ** 64 - 1             # (for fast JIT compile in PyPy) 1.84...e+19
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    
    

    # class TwoDimNode:
    #     def __init__(self, x=None, y=None, parent=None, left=None, right=None):
    #         '''
    #         2 次元二分探索木のためのノード
    #         '''        
    #         self.x = x
    #         self.y = y
    #         self.parent = parent
    #         self.left = left
    #         self.right = right
    #         self.flag = True
    
    # class TwoDimTree:
    #     def __init__(self, points=[]):
    #         '''
    #         2 次元二分探索木 (kD tree) を作成する
    #         root の深さを 0 として、深さが偶数の場合そこでは x を基準に、奇数の場合 y を基準に二分探索木条件を満たすようにする
    #         '''
    #         # nil の設定
    #         self.nil = TwoDimNode()
    #         self.nil.parent = self.nil
    #         self.nil.left = self.nil
    #         self.nil.right = self.nil
    #         # root の設定
    #         self.root = self.nil
    #         # もし予め一次元の点の集合が与えられるのならバランスする形で kD tree を構築する
    #         self._balance_insert(points)
        
    #     # def preorder_traverse(self, node=None):
    #     #     node = self.root if node is None else node
    #     #     if node != self.nil:
    #     #         print(f'({node.x},{node.y})', end=' ')
    #     #         self.preorder_traverse(node=node.left)
    #     #         self.preorder_traverse(node=node.right)
            
    #     # def postorder_traverse(self, node=None):
    #     #     node = self.root if node is None else node
    #     #     if node != self.nil:
    #     #         self.preorder_traverse(node=node.left)
    #     #         self.preorder_traverse(node=node.right)
    #     #         print(f'({node.x},{node.y})', end=' ')
    
    #     # def inorder_traverse(self, node=None):
    #     #     node = self.root if node is None else node
    #     #     if node != self.nil:
    #     #         self.preorder_traverse(node=node.left)
    #     #         print(f'({node.x},{node.y})', end=' ')
    #     #         self.preorder_traverse(node=node.right)
        
    #     def _balance_insert(self, seq, depth=0):
    #         # 毎回 x or y をキーとしてソートを行い、中央値をとって insert すれば平衡になる
    #         if seq:
    #             arranged = sorted(seq, key=itemgetter(depth % 2))
    #             mid = len(seq) // 2
    #             self.insert(arranged[mid][0], arranged[mid][1])
    #             self._balance_insert(arranged[:mid], depth+1)
    #             self._balance_insert(arranged[mid+1:], depth+1)
    
    
    #     def insert(self, x, y):
    #         '''
    #         kD tree に値が (x, y) であるノードを O(depth) で挿入する
    #         (コンストラクタで生成した kD tree は平衡であることが保証されるが、insert により生成した部分の平衡性は保証されないことに注意)        
    #         '''
    #         trailer = self.nil    # (x, y) を挿入するべき nil の一つ前のノードを保存するトレーラポインタ
    #         pos = self.root    # (x, y) を挿入するべき nil の場所を探す
    #         depth = 0
    #         while pos != self.nil:
    #             trailer = pos
    #             k, pos_k = (x, pos.x) if depth % 2 == 0 else (y, pos.y)
    #             if k < pos_k:
    #                 pos = pos.left
    #             elif pos_k < k:
    #                 pos = pos.right
    #             else:
    #                 pos.flag ^= pos.flag
    #                 pos = pos.left if pos.flag else pos.right
    #             depth += 1
    #         inserted_node = TwoDimNode(x, y, trailer, self.nil, self.nil)
    #         # trailer の depth
    #         depth -= 1
    #         k, trailer_k = (x, trailer.x) if depth % 2 == 0 else (y, trailer.y)
    #         # tree is empty
    #         if trailer == self.nil:
    #             self.root = inserted_node
    #         # どこかのノードの子供の位置に挿入する時
    #         elif k < trailer_k or (k == trailer_k and trailer.flag):
    #             trailer.left = inserted_node
    #         else:
    #             trailer.right = inserted_node
        
    #     def two_dim_search(self, sx, tx, sy, ty, node=None, depth=0):
    #         '''
    #         kD tree に対し閉区間 D = {(x, y) | sx<=x<=tx, sy<=y<=ty} 内に存在する点を探してリストにまとめて返す (対応する点の個数 k として O(√n + k))
    #         下記のように検索必要性を判断し再帰的に左右の子に対し探索を行えば良い
    
    #         <-------- node.x -------->
    #         <----------->
    #         少しでも [sx,tx] が左側ゾーン ((-inf, node.x]) に被っていたら検索しておく必要がある
    #                     <----->
    #                     少しでも [sx, tx] が右側ゾーン ([node.x, inf)) に被っていたら検索しておく必要がある
    #         '''        
    #         # buf = []
    #         # node = self.root if node is None else node
    #         # # print(f'{node.x} {node.y}')
    #         # if depth % 2 == 0:
    #         #     if node.left != self.nil and sx <= node.x:
    #         #         buf += self.two_dim_search(sx, tx, sy, ty, node.left, depth+1)
    #         #     if sx <= node.x <= tx and sy <= node.y <= ty:
    #         #         buf.append((node.x, node.y))
    #         #     if node.right != self.nil and tx >= node.x:
    #         #         buf += self.two_dim_search(sx, tx, sy, ty, node.right, depth+1)
    #         # else:
    #         #     if node.left != self.nil and sy <= node.y:
    #         #         buf += self.two_dim_search(sx, tx, sy, ty, node.left, depth+1)
    #         #     if sx <= node.x <= tx and sy <= node.y <= ty:
    #         #         buf.append((node.x, node.y))
    #         #     if node.right != self.nil and ty >= node.y:
    #         #         buf += self.two_dim_search(sx, tx, sy, ty, node.right, depth+1)
    #         # return buf
    #         cnt = 0
    #         node = self.root if node is None else node
    #         if depth % 2 == 0:
    #             if node.left != self.nil and sx <= node.x:
    #                 cnt += self.two_dim_search(sx, tx, sy, ty, node.left, depth+1)
    #             if sx <= node.x <= tx and sy <= node.y <= ty:
    #                 cnt += 1
    #             if node.right != self.nil and tx >= node.x:
    #                 cnt += self.two_dim_search(sx, tx, sy, ty, node.right, depth+1)
    #         else:
    #             if node.left != self.nil and sy <= node.y:
    #                 cnt += self.two_dim_search(sx, tx, sy, ty, node.left, depth+1)
    #             if sx <= node.x <= tx and sy <= node.y <= ty:
    #                 cnt += 1
    #             if node.right != self.nil and ty >= node.y:
    #                 cnt += self.two_dim_search(sx, tx, sy, ty, node.right, depth+1)
    #         return cnt

    def count_inner_points(points, sx, tx, sy, ty):
        cnt = 0
        for x, y in points:
            if sx <= x <= tx and sy <= y <= ty:
                cnt += 1
        return cnt
    

    n, num_of_points = mi()
    points = [lmi() for _ in range(n)]
    x_sorted_p = sorted(points, key=itemgetter(0))
    y_sorted_p = sorted(points, key=itemgetter(1))
    # kd = TwoDimTree(points)

    area = inf
    for i in range(n-1):
        for j in range(i+1, n):
            sx, tx = x_sorted_p[i][0], x_sorted_p[j][0]
            # # 枝刈り、TLE ケースを 10 -> 3 にしてくれた
            # if kd.two_dim_search(sx, tx, y_sorted_p[0][1], y_sorted_p[-1][1]) < num_of_points:
            #     continue
            if count_inner_points(points, sx, tx, y_sorted_p[0][1], y_sorted_p[-1][1]) < num_of_points:
                continue
            for k in range(n-1):
                for l in range(k+1, n):
                    sy, ty = y_sorted_p[k][1], y_sorted_p[l][1]
                    # if kd.two_dim_search(sx, tx, sy, ty) >= num_of_points:
                    #     # print(f"{sx} {tx} {sy} {ty} {kd.two_dim_search(sx, tx, sy, ty)}")
                    #     area = min(area, abs(tx - sx) * abs(ty - sy))
                    cnt = count_inner_points(points, sx, tx, sy, ty)
                    # if cnt > num_of_points:
                    #     continue
                    if cnt == num_of_points:
                        area = min(area, abs(tx - sx) * abs(ty - sy))
    print(area)
    


if __name__ == "__main__":
    main()

Submission status: Accepted

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

import sys
# import time
# import math
# import numpy as np
# import scipy.sparse.csgraph as cs            # csgraph_from_dense(ndarray, null_value=inf), bellman_ford(G, return_predecessors=True), dijkstra, floyd_warshall
# import random                                # random, uniform, randint, randrange, shuffle, sample
# import string                                # ascii_lowercase, ascii_uppercase, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from datetime import date, datetime          # date.today(), date(year,month,day) => date obj; datetime.now(), datetime(year,month,day,hour,second,microsecond) => datetime obj; subtraction => timedelta obj
# from datetime.datetime import strptime       # strptime('2019/01/01 10:05:20', '%Y/%m/%d/ %H:%M:%S') returns datetime obj
# from datetime import timedelta               # td.days, td.seconds, td.microseconds, td.total_seconds(). abs function is also available.
# from copy import copy, deepcopy              # use deepcopy to copy multi-dimentional matrix without reference
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from fractions import gcd                    # for Python 3.4 (previous contest @AtCoder)



def main():
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79...e+308
    # inf = 2 ** 64 - 1             # (for fast JIT compile in PyPy) 1.84...e+19
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    
    

    # class TwoDimNode:
    #     def __init__(self, x=None, y=None, parent=None, left=None, right=None):
    #         '''
    #         2 次元二分探索木のためのノード
    #         '''        
    #         self.x = x
    #         self.y = y
    #         self.parent = parent
    #         self.left = left
    #         self.right = right
    #         self.flag = True
    
    # class TwoDimTree:
    #     def __init__(self, points=[]):
    #         '''
    #         2 次元二分探索木 (kD tree) を作成する
    #         root の深さを 0 として、深さが偶数の場合そこでは x を基準に、奇数の場合 y を基準に二分探索木条件を満たすようにする
    #         '''
    #         # nil の設定
    #         self.nil = TwoDimNode()
    #         self.nil.parent = self.nil
    #         self.nil.left = self.nil
    #         self.nil.right = self.nil
    #         # root の設定
    #         self.root = self.nil
    #         # もし予め一次元の点の集合が与えられるのならバランスする形で kD tree を構築する
    #         self._balance_insert(points)
        
    #     # def preorder_traverse(self, node=None):
    #     #     node = self.root if node is None else node
    #     #     if node != self.nil:
    #     #         print(f'({node.x},{node.y})', end=' ')
    #     #         self.preorder_traverse(node=node.left)
    #     #         self.preorder_traverse(node=node.right)
            
    #     # def postorder_traverse(self, node=None):
    #     #     node = self.root if node is None else node
    #     #     if node != self.nil:
    #     #         self.preorder_traverse(node=node.left)
    #     #         self.preorder_traverse(node=node.right)
    #     #         print(f'({node.x},{node.y})', end=' ')
    
    #     # def inorder_traverse(self, node=None):
    #     #     node = self.root if node is None else node
    #     #     if node != self.nil:
    #     #         self.preorder_traverse(node=node.left)
    #     #         print(f'({node.x},{node.y})', end=' ')
    #     #         self.preorder_traverse(node=node.right)
        
    #     def _balance_insert(self, seq, depth=0):
    #         # 毎回 x or y をキーとしてソートを行い、中央値をとって insert すれば平衡になる
    #         if seq:
    #             arranged = sorted(seq, key=itemgetter(depth % 2))
    #             mid = len(seq) // 2
    #             self.insert(arranged[mid][0], arranged[mid][1])
    #             self._balance_insert(arranged[:mid], depth+1)
    #             self._balance_insert(arranged[mid+1:], depth+1)
    
    
    #     def insert(self, x, y):
    #         '''
    #         kD tree に値が (x, y) であるノードを O(depth) で挿入する
    #         (コンストラクタで生成した kD tree は平衡であることが保証されるが、insert により生成した部分の平衡性は保証されないことに注意)        
    #         '''
    #         trailer = self.nil    # (x, y) を挿入するべき nil の一つ前のノードを保存するトレーラポインタ
    #         pos = self.root    # (x, y) を挿入するべき nil の場所を探す
    #         depth = 0
    #         while pos != self.nil:
    #             trailer = pos
    #             k, pos_k = (x, pos.x) if depth % 2 == 0 else (y, pos.y)
    #             if k < pos_k:
    #                 pos = pos.left
    #             elif pos_k < k:
    #                 pos = pos.right
    #             else:
    #                 pos.flag ^= pos.flag
    #                 pos = pos.left if pos.flag else pos.right
    #             depth += 1
    #         inserted_node = TwoDimNode(x, y, trailer, self.nil, self.nil)
    #         # trailer の depth
    #         depth -= 1
    #         k, trailer_k = (x, trailer.x) if depth % 2 == 0 else (y, trailer.y)
    #         # tree is empty
    #         if trailer == self.nil:
    #             self.root = inserted_node
    #         # どこかのノードの子供の位置に挿入する時
    #         elif k < trailer_k or (k == trailer_k and trailer.flag):
    #             trailer.left = inserted_node
    #         else:
    #             trailer.right = inserted_node
        
    #     def two_dim_search(self, sx, tx, sy, ty, node=None, depth=0):
    #         '''
    #         kD tree に対し閉区間 D = {(x, y) | sx<=x<=tx, sy<=y<=ty} 内に存在する点を探してリストにまとめて返す (対応する点の個数 k として O(√n + k))
    #         下記のように検索必要性を判断し再帰的に左右の子に対し探索を行えば良い
    
    #         <-------- node.x -------->
    #         <----------->
    #         少しでも [sx,tx] が左側ゾーン ((-inf, node.x]) に被っていたら検索しておく必要がある
    #                     <----->
    #                     少しでも [sx, tx] が右側ゾーン ([node.x, inf)) に被っていたら検索しておく必要がある
    #         '''        
    #         # buf = []
    #         # node = self.root if node is None else node
    #         # # print(f'{node.x} {node.y}')
    #         # if depth % 2 == 0:
    #         #     if node.left != self.nil and sx <= node.x:
    #         #         buf += self.two_dim_search(sx, tx, sy, ty, node.left, depth+1)
    #         #     if sx <= node.x <= tx and sy <= node.y <= ty:
    #         #         buf.append((node.x, node.y))
    #         #     if node.right != self.nil and tx >= node.x:
    #         #         buf += self.two_dim_search(sx, tx, sy, ty, node.right, depth+1)
    #         # else:
    #         #     if node.left != self.nil and sy <= node.y:
    #         #         buf += self.two_dim_search(sx, tx, sy, ty, node.left, depth+1)
    #         #     if sx <= node.x <= tx and sy <= node.y <= ty:
    #         #         buf.append((node.x, node.y))
    #         #     if node.right != self.nil and ty >= node.y:
    #         #         buf += self.two_dim_search(sx, tx, sy, ty, node.right, depth+1)
    #         # return buf
    #         cnt = 0
    #         node = self.root if node is None else node
    #         if depth % 2 == 0:
    #             if node.left != self.nil and sx <= node.x:
    #                 cnt += self.two_dim_search(sx, tx, sy, ty, node.left, depth+1)
    #             if sx <= node.x <= tx and sy <= node.y <= ty:
    #                 cnt += 1
    #             if node.right != self.nil and tx >= node.x:
    #                 cnt += self.two_dim_search(sx, tx, sy, ty, node.right, depth+1)
    #         else:
    #             if node.left != self.nil and sy <= node.y:
    #                 cnt += self.two_dim_search(sx, tx, sy, ty, node.left, depth+1)
    #             if sx <= node.x <= tx and sy <= node.y <= ty:
    #                 cnt += 1
    #             if node.right != self.nil and ty >= node.y:
    #                 cnt += self.two_dim_search(sx, tx, sy, ty, node.right, depth+1)
    #         return cnt

    def count_inner_points(points, sx, tx, sy, ty):
        cnt = 0
        for x, y in points:
            if sx <= x <= tx and sy <= y <= ty:
                cnt += 1
        return cnt
    

    n, num_of_points = mi()
    points = [lmi() for _ in range(n)]
    x_sorted_p = sorted(points, key=itemgetter(0))
    y_sorted_p = sorted(points, key=itemgetter(1))
    # kd = TwoDimTree(points)

    area = inf
    for i in range(n-1):
        for j in range(i+1, n):
            sx, tx = x_sorted_p[i][0], x_sorted_p[j][0]
            # # 枝刈り、TLE ケースを 10 -> 3 にしてくれた
            # if kd.two_dim_search(sx, tx, y_sorted_p[0][1], y_sorted_p[-1][1]) < num_of_points:
            #     continue
            if count_inner_points(points, sx, tx, y_sorted_p[0][1], y_sorted_p[-1][1]) < num_of_points:
                continue
            for k in range(n-1):
                for l in range(k+1, n):
                    sy, ty = y_sorted_p[k][1], y_sorted_p[l][1]
                    # if kd.two_dim_search(sx, tx, sy, ty) >= num_of_points:
                    #     # print(f"{sx} {tx} {sy} {ty} {kd.two_dim_search(sx, tx, sy, ty)}")
                    #     area = min(area, abs(tx - sx) * abs(ty - sy))
                    cnt = count_inner_points(points, sx, tx, sy, ty)
                    if cnt > num_of_points:
                        continue
                    elif cnt == num_of_points:
                        area = min(area, abs(tx - sx) * abs(ty - sy))
    print(area)
    


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from itertools import combinations

N, K = map(int,input().split())
points = []
X = []
Y = []

for _ in range(N):
    x, y = map(int,input().split())
    points.append((x, y))
    X.append(x)
    Y.append(y)

X.sort()
Y.sort()

ans = float('inf')

for x1, x2 in combinations(X, 2):
    for y1, y2 in combinations(Y, 2):
        cnt = 0
        for point in points:
            if x1 <= point[0] <= x2 and y1 <= point[1] <= y2:
                cnt += 1
        if cnt >= K:
            ans = min(ans, (x2 - x1) * (y2 - y1))

print(ans)

Submission status: Accepted

Solution code:
def main():
    N, K = list(map(int, input().split(' ')))
    points = [list(map(int, input().split(' '))) for _ in range(N)]
    points.sort(key=lambda p: p[1])
    ans = 10**19
    for b in range(N):
        bottom = points[b][1]
        for t in range(b + K - 1, N):
            top = points[t][1]
            target_points = points[b:(t+1)].copy()
            target_points.sort(key=lambda p: p[0])
            M = len(target_points)
            for left in range(M):
                right = left + K - 1
                if right >= M:
                    break
                width = target_points[right][0] - target_points[left][0]
                ans = min([ans, width * (top - bottom)])
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,K=map(int,input().split())
xy=[]
x=[]
y=[]
for _ in range(n):
	X,Y=map(int,input().split())
	x.append(X+10**9)
	y.append(Y+10**9)
	xy.append((X+10**9,Y+10**9))
x.sort();y.sort();xy.sort()
num=[[0]*(n+1)for _ in range(n+1)]
for xx in xy:
	for i in range(n):
		if x[i]==xx[0]:
			break
	for j in range(n):
		if y[j]==xx[1]:
			break
	num[i+1][j+1]+=1
for i in range(n):
	for j in range(n):
		num[i+1][j+1]+=num[i+1][j]
for i in range(n):
	for j in range(n):
		num[i+1][j+1]+=num[i][j+1]
ans=10**20
for i in range(n):
	for j in range(n):
		for k in range(i+1,n+1):
			for l in range(j+1,n+1):
				if num[k][l]-num[i][l]-num[k][j]+num[i][j]>=K:
					r=(y[l-1]-y[j])*(x[k-1]-x[i])
					ans=min(ans,r)
print(ans)

Submission status: Accepted

Solution code:


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

Xs = set()
Ys = set()
for x,y in XY:
    Xs.add(x)
    Ys.add(y)


Xs = list(Xs)
Xs.sort()

Ys = list(Ys)
Ys.sort()

LX = len(Xs)
LY = len(Ys)
ans = 10**20

for i in range(LX):
    for j in range(i+1, LX):
        for k in range(LY):
            for l in range(k+1, LY):
                cnt = 0
                for x,y in XY:
                    if Xs[i] <= x <= Xs[j] and Ys[k] <= y <= Ys[l]:
                        cnt += 1

                if cnt >= K:
                    ans = min(ans, (Xs[j] - Xs[i])*(Ys[l] - Ys[k]))


print(ans)

Submission status: Accepted

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

xarray.sort()
yarray.sort()

ans = 4*(10**18)+10
for xi in range(n):
    for xj in range(xi+1, n):
        for yi in range(n):
            for yj in range(yi+1, n):
                lx, rx = xarray[xi], xarray[xj]
                by, ay = yarray[yi], yarray[yj]
                num = 0
                for i in range(n):
                    x, y = point[i]
                    if lx <= x <= rx and by <= y <= ay:
                        num += 1
                if num >= k:
                    ans = min(ans, (rx-lx)*(ay-by))
print(ans)

Submission status: Accepted

Solution code:
n,K = map(int,input().split())
xy = [[int(i) for i in input().split()] for j in range(n)]

ans = 10**20

for i in range(n):
    for j in range(i+1,n):
        if K == 2:
            ans = min(ans,abs(xy[i][0]-xy[j][0])*abs(xy[i][1]-xy[j][1]))
        for k in range(j+1,n):
            if K == 2:
                break
            max_x_old = max(xy[i][0],xy[j][0],xy[k][0])
            min_x_old = min(xy[i][0],xy[j][0],xy[k][0])
            max_y_old = max(xy[i][1],xy[j][1],xy[k][1])
            min_y_old = min(xy[i][1],xy[j][1],xy[k][1])
            if K == 3:
                #max_x = max(xy[i][0],xy[j][0],xy[k][0])
                #min_x = min(xy[i][0],xy[j][0],xy[k][0])
                #max_y = max(xy[i][1],xy[j][1],xy[k][1])
                #min_y = min(xy[i][1],xy[j][1],xy[k][1])
                ans = min(ans,abs(max_x_old-min_x_old)*abs(max_y_old-min_y_old))
            for l in range(k+1,n):
                if K == 2 or K == 3:
                    break
                cnt = 0
                max_x = max(max_x_old,xy[l][0])
                min_x = min(min_x_old,xy[l][0])
                max_y = max(max_y_old,xy[l][1])
                min_y = min(min_y_old,xy[l][1])
                for m in range(n):
                    if xy[m][0] >= min_x and xy[m][0] <= max_x\
                       and xy[m][1] >= min_y and xy[m][1] <= max_y:
                           cnt += 1
                if cnt >= K:
                    #print(cnt,K)
                    ans = min(ans,(max_x-min_x)*(max_y-min_y))
                
print(ans)

Submission status: Accepted

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

XY.sort(key=lambda x: x[0])

ans = float("INF")
for i in range(N):
    for j in range(i+K-1, N):
        W = XY[j][0] - XY[i][0]
        Y = [XY[x][1] for x in range(i, j+1)]
        Y.sort()
        for k in range(len(Y)-K+1):
            H = Y[k+K-1] - Y[k]
            ans = min(ans, W*H)

print(ans)

Submission status: Accepted

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

XY.sort(key=lambda x: x[0])

ans = float("INF")
for i in range(N):
    for j in range(i+K-1, N):
        W = XY[j][0] - XY[i][0]
        Y = [XY[x][1] for x in range(i, j+1)]
        Y.sort()
        for l, k in zip(Y, Y[K-1:]):
                H = k - l
                ans = min(ans, W*H)

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from itertools import combinations,product
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N,K=map(int,input().split())
    x,y=[0]*N,[0]*N
    for i in range(N):
        x[i],y[i]=map(int,input().split())
    unique_x,unique_y=list(sorted(list(set(x)))),list(sorted(list(set(y))))
    d_x={z:i for i,z in enumerate(unique_x)}
    d_y={z:i for i,z in enumerate(unique_y)}
    xx=[d_x[z] for z in x]
    yy=[d_y[z] for z in y]
    c=[[0]*N for _ in range(N)]
    for i,j in zip(yy,xx):
        c[i][j]+=1
    s=[[0]*(N+1) for _ in range(N+1)]
    for i in range(N):
        for j in range(N):
            s[i+1][j+1]+=s[i][j+1]+s[i+1][j]-s[i][j]+c[i][j]
    xx.sort()
    yy.sort()
    ans=INF*10
    for (x0,x1),(y0,y1) in product(combinations(xx,2),combinations(yy,2)):
        if s[y1+1][x1+1]-s[y1+1][x0]-s[y0][x1+1]+s[y0][x0]>=K:
            ans=min(ans,(unique_y[y1]-unique_y[y0])*(unique_x[x1]-unique_x[x0]))
    print(ans)

if __name__ == '__main__':
    main()