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:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, atan, degrees
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, K = MAP()
xy = [LIST() for _ in range(N)]
ans = INF
xy.sort()
for l in range(N-K+1):  # 長方形に含まれる最も左の点
    for r in range(l+K, N+1):  # 長方形に含まれる最も右の点
        y = sorted(xy[l:r], key = lambda x: x[1])  # lからrの中でのyのとりうる値をソート
        for i in range(r-l-K+1):
            sq = (xy[r-1][0] - xy[l][0]) * (y[i+K-1][1] - y[i][1])  # 下からKこ選んだときの面積
            ans = min(ans, sq)
print(ans)

Submission status: Accepted

Solution code:
#coding: utf-8
import math
import heapq
import bisect
import numpy as np
from collections import Counter
#from scipy.misc import comb

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

ans = 10**20

for lx in range(N):
    for rx in range(lx+1,N+1):
        L2 = L[lx:rx]
        L2 = sorted(L2, key=lambda x:x[1])
        for ly in range(len(L2)):
            L3 = L2[ly:ly+K]
            if len(L3) >= K:
                ans = min(ans, (L[rx-1][0]-L[lx][0])*(L3[-1][1]-L3[0][1]))

print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations
N, K, *L = map(int, open(0).read().split())
L = [(x,y) for x,y in zip(*[iter(L)]*2)]
ans = float('inf')
for m in combinations(L,2):
  for n in combinations(L,2):
    mx = min(m,key=lambda x:x[0])[0]
    Mx = max(m,key=lambda x:x[0])[0]
    my = min(n,key=lambda x:x[1])[1]
    My = max(n,key=lambda x:x[1])[1]
    cnt = 0
    for x,y in L:
      if mx<=x<=Mx and my<=y<=My:
        cnt += 1
    if cnt>=K:
      ans = min(ans, (Mx-mx)*(My-my))
print(ans)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
xy = [list(map(int, input().split())) for _ in range(n)]
INF = 10 ** 19

xy.sort()

ans = INF
for i in range(n):
	for j in range(i + k - 1, n):
		width = xy[j][0] - xy[i][0]

		y = [xy[idx][1] for idx in range(i, j + 1)]
		y.sort()

		for e1, e2 in zip(y, y[k-1:]):
			height = e2 - e1
			area = width * height
			ans = min(ans, area)

print(ans)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()

def count_inside(x1, x2, y1, y2, points):
    cnt = 0
    if x2 < x1:
        x1, x2 = x2, x1
    if y2 < y1:
        y1, y2 = y2, y1

    for p in points:
        if x1 <= p[0] <= x2 and y1 <= p[1] <= y2:
            cnt += 1
    return cnt

def main():
    N, K = LI()
    points = []
    for _ in range(N):
        x, y = LI()
        points.append((x, y))
    points = sorted(points, key=lambda x: (x[0], x[1]))
    X = [p[0] for p in points]
    Y = [p[1] for p in points]
    area = inf
    for i in range(N):
        x1 = X[i]
        for j in range(i+1, N):
            x2 = X[j]
            for k in range(N):
                y1 = Y[k]
                for l in range(k+1, N):
                    y2 = Y[l]
                    if K == count_inside(x1, x2, y1, y2, points):
                        _area = abs(x1-x2) * abs(y1-y2)
                        area = min(_area, area)
    print(area)

main()

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()

def count_inside(p1, p2, points):
    cnt = 0
    min_x = min(p1[0], p2[0])
    min_y = min(p1[1], p2[1])
    max_x = max(p1[0], p2[0])
    max_y = max(p1[1], p2[1])
    for p in points:
        if min_x <= p[0] <= max_x and min_y <= p[1] <= max_y:
            cnt += 1
    return cnt

def main():
    N, K = LI()
    points = []
    X, Y = [], []
    for i, _ in enumerate(range(N)):
        x, y = LI()
        points.append((x, y))
        X.append((x, i))
        Y.append((y, i))
    X = sorted(X, key=lambda x: x[0])
    Y = sorted(Y, key=lambda x: x[0])
    mapOrder2x = {}
    mapOrder2y = {}

    zaatsu_X = [-1 for _ in range(N)]
    zaatsu_Y = [-1 for _ in range(N)]

    for order, (x, i) in enumerate(X):
        zaatsu_X[i] = order
        mapOrder2x[order] = x

    for order, (y, i) in enumerate(Y):
        zaatsu_Y[i] = order
        mapOrder2y[order] = y

    assert(-1 not in zaatsu_X)
    assert(-1 not in zaatsu_Y)

    G = [[0 for _ in range(N)] for __ in range(N)]
    cumsum = [[0 for _ in range(N+1)] for __ in range(N+1)]

    for x, y in zip(zaatsu_X, zaatsu_Y):
        G[x][y] = 1

    for x in range(N):
        for y in range(N):
            cumsum[x+1][y+1] = cumsum[x+1][y] + cumsum[x][y+1] - cumsum[x][y] + G[x][y]

    def query_cumsum2d(s, r1, r2, c1, c2):
        if c2 < c1:
            c1, c2 = c2, c1
        if r2 < r1:
            r1, r2 = r2, r1
        return s[r2][c2] - s[r2][c1] - s[r1][c2] +s[r1][c1]

    def calc_area(x1, x2, y1, y2, mapx, mapy):
        return abs(mapx[x1] - mapx[x2]) * abs(mapy[y1] - mapy[y2])

    area = inf
    for r1 in range(0, N):
        for r2 in range(r1, N+1):
            for c1 in range(0, N):
                for c2 in range(c1, N+1):
                    if K == query_cumsum2d(cumsum, r1, r2, c1, c2):
                        
                        _area = calc_area(r1, r2-1, c1, c2-1, mapOrder2x, mapOrder2y)
                        area = min(area, _area)
    print(area)
main()

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
x = [0] * N
y = [0] * N
for i in range(N):
    x[i], y[i] = map(int, input().split())
ans = float('inf')
for x1 in x:
    for x2 in x:
        if x1 > x2:
            continue
        for y1 in y:
            for y2 in y:
                if y1 > y2:
                    continue
                area = (x2 - x1) * (y2 - y1)
                if area >= ans:
                    continue
                cnt = 0
                for i in range(N):
                    if x1 <= x[i] <= x2 and y1 <= y[i] <= y2:
                        cnt += 1
                if cnt >= K:
                    ans = area
print(ans)

Submission status: Accepted

Solution code:
n, kosuu = map(int, input().split())
XY, X, Y = [], [], []

for _ in range(n):
    x, y = map(int, input().split())
    X.append(x)
    Y.append(y)
    XY.append([x,y])

X = sorted(X, reverse=True)
Y = sorted(Y, reverse=True)

s_min = 10**20
for i in range(n):
    for j in range(n):
        for k in range(n):
            for l in range(n):
                count = 0
                x_max = X[i]
                x_min = X[-1*(j+1)]
                if x_max <= x_min:
                    continue
                y_max = Y[k]
                y_min = Y[-1*(l+1)]
                if y_max <= y_min:
                    continue

                s = abs(x_max-x_min)*abs(y_max-y_min)

                for m in range(n):
                    x = XY[m][0]
                    y = XY[m][1]
                    if (x <= x_max and x >= x_min) and (y <= y_max and y >= y_min):
                        count += 1
                if count >= kosuu:
                    s_min = min(s, s_min)

print(s_min)

Submission status: Accepted

Solution code:
#!/usr/bin/env pypy3
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N,K=MI()
    xy=[[0,0] for _ in range(N)]
    y=[0]*N
    
    for i in range(N):
        xy[i][0],xy[i][1]=MI()
        y[i]=xy[i][1]
        
    xy.sort()
    y.sort()
    
    def count(l,r,d,u):
        cnt=0
        for i in range(N):
            if l<=xy[i][0]<=r:
                if d<=xy[i][1]<=u:
                    cnt+=1
        return cnt
    
    ans=10**20
    for i in range(N):
        for j in range(i+1,N):
            for ii in range(N):
                for jj in range(ii+1,N):
                    l=xy[i][0]
                    r=xy[j][0]
                    d=y[ii]
                    u=y[jj]
                    if count(l,r,d,u)==K:
                        ans=min(ans,(r-l)*(u-d))
    print(ans)

main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from itertools import combinations

def _solve(y1, y2, sorted_points, K):
    y1, y2 = tuple(sorted([y1, y2]))
    x = tuple(x for x, y in sorted_points if y1 <= y <= y2)
    if len(x) < K:
        return float('inf')
    return min((y2 - y1) * (x2 - x1) for x1, x2 in zip(x, x[K-1:]))

def solve(N: int, K: int, x: "List[int]", y: "List[int]"):
    sorted_points = tuple(sorted(zip(x, y)))
    return min(_solve(y1, y2, sorted_points, K) for y1, y2 in combinations(y, 2))

# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    x = [int()] * (N)  # type: "List[int]"
    y = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        x[i] = int(next(tokens))
        y[i] = int(next(tokens))
    print(solve(N, K, x, y))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
x_y = []
x = []
y = []
for i in range(n):
    a,b = map(int, input().split())
    x.append(a)
    y.append(b)
    x_y.append([a,b])
ans = 10**19
def check(a,b,c,d):
    count = 0
    for i in range(n):
        s,t = x_y[i]
        if a <= s <= b and c <= t <= d:
            count += 1
    if count >= k:
        return True
    else:
        return False
x.sort()
y.sort()
for x_1 in range(n):
    for x_2 in range(x_1+1,n):
        for y_1 in range(n):
            for y_2 in range(y_1+1,n):
                if check(x[x_1],x[x_2],y[y_1],y[y_2]):
                    rect_area = (x[x_2] - x[x_1]) * (y[y_2] - y[y_1])
                    ans = min(ans, rect_area)
print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate
n, k = map(int, input().split())
XY = [list(map(int, input().split())) for _ in range(n)]
X, Y = zip(*XY)
def compress(arr):
    *XS, = set(arr)
    XS.sort()
    return {e: i+1 for i, e in enumerate(XS)}
Xlabel = compress(X)
Ylabel = compress(Y)
rX = {j:i for i,j in Xlabel.items()}
rY = {j:i for i,j in Ylabel.items()}
lX = len(Xlabel)
lY = len(Ylabel)
F = [[0]*(lX+1) for _ in range(lY+1)]
for x, y in XY:
  F[Ylabel[y]][Xlabel[x]] = 1
for i in range(lY):
  F[i+1] = list(accumulate(F[i+1]))
F = list(zip(*F))
for j in range(lY):
  F[j+1] = list(accumulate(F[j+1]))
F = list(zip(*F))
ans = float("inf")
for y1 in range(lY):
  for y2 in range(y1+1, lY+1):
    for x1 in range(lX):
      for x2 in range(x1+1, lX+1):
        count = F[y2][x2] - F[y1][x2] - F[y2][x1] + F[y1][x1]
        if count >= k:
          temp = (rX[x2]-rX[x1+1]) * (rY[y2]-rY[y1+1])
          ans = min(ans, temp)
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from functools import lru_cache
import bisect
import re
import queue


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [input() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [int(input()) for i in range(n)]


class Math():
    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

    @staticmethod
    def roundUp(a, b):
        return -(-a // b)

    @staticmethod
    def toUpperMultiple(a, x):
        return Math.roundUp(a, x) * x

    @staticmethod
    def toLowerMultiple(a, x):
        return (a // x) * x

    @staticmethod
    def nearPow2(n):
        if n <= 0:
            return 0
        if n & (n - 1) == 0:
            return n
        ret = 1
        while(n > 0):
            ret <<= 1
            n >>= 1
        return ret

    @staticmethod
    def sign(n):
        if n == 0:
            return 0
        if n < 0:
            return -1
        return 1

    @staticmethod
    def isPrime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3, d + 1, 2):
            if n % i == 0:
                return False
        return True


class PriorityQueue:
    def __init__(self, l=[]):
        self.__q = l
        heapq.heapify(self.__q)
        return

    def push(self, n):
        heapq.heappush(self.__q, n)
        return

    def pop(self):
        return heapq.heappop(self.__q)


sys.setrecursionlimit(1000000)
MOD = int(1e09) + 7
INF = int(1e30)


def main():
    # sys.stdin = open("Sample.txt")
    N, K = Scanner.map_int()
    X = [0] * N
    Y = [0] * N
    for i in range(N):
        x, y = Scanner.map_int()
        X[i] = x
        Y[i] = y
    sx = sorted(X)
    sy = sorted(Y)
    ans = INF
    for l in range(N-1):
        for r in range(l+1, N):
            for b in range(N-1):
                for t in range(b+1, N):
                    left = sx[l]
                    right = sx[r]
                    bottom = sy[b]
                    top = sy[t]
                    cnt = 0
                    for i in range(N):
                        if left <= X[i] <= right and bottom <= Y[i] <= top:
                            cnt += 1
                    if cnt >= K:
                        ans = min(ans, (right-left)*(top-bottom))
    print(ans)
    return


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def MI(N,num):
    if N<=0:
        return [[] for _ in range(num)]
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [LI() for _ in range(N)]
        return map(list, zip(*read_all))

#################

from bisect import bisect_left
from itertools import product,combinations

from operator import itemgetter
def index_sort(A):
    A_sort = sorted(enumerate(A),key=itemgetter(1))
    index = [a[0] for a in A_sort]
    sorted_A = [a[1] for a in A_sort]
    return index, sorted_A

N,K = LI()
x,y = MI(N,2)

index,_ = index_sort(x)
x2 = [x[i] for i in index]
y2 = [y[i] for i in index]

A = list(product(combinations(range(N),2),repeat=2))
ans = float('inf')
for a in A:
    xmin = min(x[a[0][0]],x[a[0][1]])
    xmax = max(x[a[0][0]],x[a[0][1]])
    ymin = min(y[a[1][0]],y[a[1][1]])
    ymax = max(y[a[1][0]],y[a[1][1]])
    S = (xmax-xmin)*(ymax-ymin)
    if S >= ans:
        continue
    l = bisect_left(x2,xmin)
    r = bisect_left(x2,xmax)
    num = 0
    for i in range(l,r+1):
        if ymin <= y2[i] <= ymax:
            num += 1
    if num >= K:
        ans = S

print(ans)

Submission status: Accepted

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

ans = 1e30
for lx in range(N):
    for rx in range(lx+K, N+1):
        Q = sorted(P[lx:rx], key=lambda x:x[1])
        for ly in range(len(Q)):
            R = Q[ly:ly+K]
            if len(R)>=K: ans = min(ans, (P[rx-1][0]-P[lx][0])*(R[-1][1]-R[0][1]))
print(ans)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
ls = []
for i in range(N):
  x, y = map(int, input().split())
  ls += [(x,y)]
m = -1
for i in range(N):
  for j in range(i+1,N):
    for p in range(N):
      for q in range(p+1,N):
        
        x1, y1 = ls[i]
        x2, y2 = ls[j]
        x3, y3 = ls[p]
        x4, y4 = ls[q]
        cnt = 0
        flag = False
        X1 = min(x1, x2)
        X2 = max(x1, x2)
        Y1 = min(y3, y4)
        Y2 = max(y3, y4)
        for a in range(N):
          x, y = ls[a]
          """
          print('"""""""')
          print(cnt)
          print(X1,X2,x)
          print(Y1,Y2,y)
          """
          if X1<=x<=X2 and Y1<=y<=Y2:
            cnt += 1
          if cnt>=K:
            n = (X2-X1)*(Y2-Y1)
            if m==-1 or n<m:
              m = n
            break
print(m)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
XY = [list(map(int, input().split())) for _ in [0] * n]
a = XY.sort()
ans = float("inf")
for i in range(n - k + 1):
    for j in range(i + k, 1 + n):
        x = XY[j - 1][0] - XY[i][0]
        now = XY[i:j]
        now.sort(key=lambda x: x[1])
        for w in range(j - i - k + 1):
            ans = min(ans, x * (now[w + k - 1][1] - now[w][1]))

print(ans)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
XY = [list(map(int, input().split())) for _ in range(N)]
x_sort = sorted(XY, key=lambda x: x[0])


def check(l, r, b, t):
    cnt = 0
    for x, y in XY:
        if r >= x and x >= l and t >= y and b >= y:
            cnt += 1
    return cnt >= K


ans = 10**20

for i in range(N - K + 1):
    xl = x_sort[i][0]
    for j in range(i + K - 1, N):
        dx = x_sort[j][0] - xl

        points = sorted(x_sort[i: j+1], key=lambda x: x[1])

        rest = j - i + 1
        for p in range(rest - K + 1):
            yd = points[p][1]
            for q in range(p + K - 1, rest):
                dy = points[q][1] - yd
                ans = min(ans, dx*dy)

print(ans)

Submission status: Accepted

Solution code:
from sys import stdout
printn = lambda x: stdout.write(str(x))
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**19
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

n,k = inm()
x = []
y = []
for i in range(n):
    xx,yy = inm()
    x.append(xx)
    y.append(yy)
mn = BIG
for i in range(n-1):
    for j in range(i+1,n):
        xn = min(x[i],x[j])
        xx = max(x[i],x[j])
        for ii in range(n-1):
            for jj in range(ii+1,n):
                yn = min(y[ii],y[jj])
                yx = max(y[ii],y[jj])
                cnt = 0
                for m in range(n):
                    if xn<=x[m]<=xx and yn<=y[m]<=yx:
                        cnt += 1
                if cnt>=k:
                    mn = min(mn, (xx-xn)*(yx-yn))
print(mn)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline
from operator import itemgetter

def main():
    N,K = map(int,input().split())
    INF = float('inf')
    dot = []
    for _ in range(N):
        x,y = map(int,input().split())
        dot.append((x,y))
    
    dot.sort(key = itemgetter(0,1))
    ans = INF
    for xdown in range(N):
        for xup in range(N):
            if xup - xdown + 1 < K:
                continue
            else:
                use = dot[xdown:xup+1]
                a,b = use[-1][0],use[0][0]
                use.sort(key = itemgetter(1))
                l = len(use)
                for udown in range(l):
                    for uup in range(l):
                        if uup - udown + 1 == K:
                            two = use[udown:uup+1]
                            c,d = two[-1][1],two[0][1]
                            S = (a-b)*(c-d)
                            ans = min(ans,S)
                            
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
import itertools

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, K = lr()
XY = [lr() for _ in range(N)]
XY.sort()
answer = float('inf')
# 端の4点、まずはx軸の2点を選ぶ
for i, j in itertools.combinations(range(N), 2):
    xleft = XY[i][0]
    xright = XY[j][0]
    candidate = sorted(XY[i:j+1], key=lambda xy: xy[1])
    if len(candidate) < K:
        continue
    for s in range(len(candidate) - K + 1):
        yup = candidate[s+K-1][1]
        ylow = candidate[s][1]
        area = (xright - xleft) * (yup - ylow)
        if area < answer:
            answer = area

print(answer)
# 31

Submission status: Accepted

Solution code:
import sys
import itertools

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, K = lr()
XY = [lr() for _ in range(N)]
XY.sort()
answer = float('inf')
# 端の4点、まずはx軸の2点を選ぶ
for left,right in itertools.combinations(range(N),2):
  xleft = XY[left][0]
  xright = XY[right][0]
  pts = sorted(XY[left:right+1], key = lambda xy: xy[1])
  if len(pts) < K:
    continue
  for D in range(len(pts) - K + 1):
    y_max = pts[D+K-1][1]
    y_min = pts[D][1]
    area = (y_max - y_min) * (xright - xleft)
    if area < answer:
      answer = area
    
print(answer)

Submission status: Accepted

Solution code:
import sys
import itertools

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, K = lr()
XY = [lr() for _ in range(N)]
XY.sort()
answer = float('inf')
# 端の4点、まずはx軸の2点を選ぶ
for left,right in itertools.combinations(range(N),2):
  width = XY[right][0] - XY[left][0]
  pts = sorted(XY[left:right+1], key = lambda xy: xy[1])
  if len(pts) < K:
    continue
  for D in range(len(pts) - K + 1):
    y_max = pts[D+K-1][1]
    y_min = pts[D][1]
    area = (y_max - y_min) * width
    if area < answer:
      answer = area
    
print(answer)

Submission status: Accepted

Solution code:
import sys
import itertools

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, K = lr()
XY = [lr() for _ in range(N)]
XY.sort()
answer = float('inf')
# 端の4点、まずはx軸の2点を選ぶ
for left,right in itertools.combinations(range(N),2):
  width = XY[right][0] - XY[left][0]
  pts = sorted(XY[left:right+1], key = lambda xy: xy[1])
  if len(pts) < K:
    continue
  for D in range(len(pts) - K + 1):
    if D + K - 1 >= len(pts):
      break
    y_max = pts[D+K-1][1]
    y_min = pts[D][1]
    area = (y_max - y_min) * width
    if area < answer:
      answer = area
    
print(answer)

Submission status: Accepted

Solution code:
import sys
import itertools

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, K = lr()
XY = [lr() for _ in range(N)]
XY.sort()
answer = float('inf')
# 端の4点、まずはx軸の2点を選ぶ
for left,right in itertools.combinations(range(N),2):
  width = XY[right][0] - XY[left][0]
  pts = sorted(XY[left:right+1], key = lambda xy: xy[1])
  for D in range(len(pts)):
    if D + K - 1 >= len(pts):
      break
    y_max = pts[D+K-1][1]
    y_min = pts[D][1]
    area = (y_max - y_min) * width
    if area < answer:
      answer = area
    
print(answer)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
x = [0]*n
y = [0]*n
for i in range(n):
    a, b = map(int, input().split())
    x[i] = a
    y[i] = b

ans = 10**30
for i in range(n):
    for j in range(i):
        for k in range(n):
            for l in range(k):

                left = min(x[i], x[j])
                right = max(x[i], x[j])
                down = min(y[k], y[l])
                up = max(y[k], y[l])

                if left == right or up == down:
                    continue

                cnt = 0
                for r in range(n):
                    if left <= x[r] and x[r] <= right and down <= y[r] and y[r] <= up:
                        cnt += 1
                if cnt >= m:
                    ans = min(ans, (right - left) * (up - down))
print(ans)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
x,y=[[0,0] for i in range(n)],[[0,0] for i in range(n)]
xy=[list(map(int,input().split())) for i in range(n)]
for i in range(n):
    x_sub,y_sub=xy[i]
    x[i][0]=x_sub
    x[i][1]=i
    y[i][0]=y_sub
    y[i][1]=i
x.sort()
y.sort()
ans=(10**18)*5
for i1 in range(n):
    for l1 in range(n-i1,1,-1):
        for i2 in range(n):
            for l2 in range(n-i2,1,-1):
                x_sub1=x[i1][0]
                x_sub2=x[i1+l1-1][0]
                y_sub1=y[i2][0]
                y_sub2=y[i2+l2-1][0]
                z=[0]*n
                for i in range(n):
                    if x_sub1<=xy[i][0]<=x_sub2 and y_sub1<=xy[i][1]<=y_sub2:
                        z[i]=1
                if sum(z)>=k:
                    ans=min((x_sub2-x_sub1)*(y_sub2-y_sub1),ans)
print(ans)

Submission status: Accepted

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

X.sort()
Y.sort()
ans=(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):
        x1=X[i]
        x2=X[j]
        y1=Y[k]
        y2=Y[l]
        count=0
        for a in range(N):
          if x1<=A[a][0] and A[a][0]<=x2:
            if y1<=A[a][1] and A[a][1]<=y2:
              count+=1
        if count>=K:
          ans=min(ans, (y2-y1)*(x2-x1))
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()
#print("XY:", XY)

answer = []
for i in range(N):
  for k in range(K, N + 1):
    if i + k - 1 >= N:
      break
    dx = XY[i + k - 1][0] - XY[i][0]
    Y = []
    for x, y in XY[i: i + k]:
      Y.append(y)
    Y.sort()
    lenY = len(Y)
    for j in range(k):
      if j + K - 1 == lenY:
        break
      dy = Y[j + K - 1] - Y[j]
      answer.append(dx * dy)

print(min(answer))

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
XY=[list(map(int,input().split())) for i in range(N)]
XY=sorted(XY,key=lambda x:x[0])
Mlst=[]

if N>=2:
    for s1 in range(N-1):
        for s2 in range(s1+1,N):
            x1,y1=XY[s1]
            x2,y2=XY[s2]
            y1,y2=min(y1,y2),max(y1,y2)
            count=2
            for i in range(s1+1,s2):
                count+=y1<=XY[i][1]<=y2
            if count>=K:
                Mlst.append((y2-y1)*(x2-x1))
if N>=3:
    for s1 in range(N-2):
        for s2 in range(s1+1,N-1):
            for s3 in range(s2+1,N):
                x1,y1=XY[s1]
                x2,y2=XY[s2]
                x3,y3=XY[s3]
                x1,x2=x1,x3
                y1,y2=min(y1,y2,y3),max(y1,y2,y3)
                count=2
                for i in range(s1+1,s3):
                    count+=y1<=XY[i][1]<=y2
                if count>=K:
                    Mlst.append((y2-y1)*(x2-x1))
if N>=4:
    for s1 in range(N-3):
        for s2 in range(s1+1,N-2):
            for s3 in range(s2+1,N-1):
                for s4 in range(s3+1,N):
                    x1,y1=XY[s1]
                    x2,y2=XY[s2]
                    x3,y3=XY[s3]
                    x4,y4=XY[s4]
                    x1,x2=x1,x4
                    y1,y2=min(y1,y2,y3,y4),max(y1,y2,y3,y4)
                    count=2
                    for i in range(s1+1,s4):
                        count+=y1<=XY[i][1]<=y2
                    if count>=K:
                        Mlst.append((y2-y1)*(x2-x1))
print(min(Mlst))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
N, K = map(int, input().split(' '))
points = [list(map(int, input().split(' '))) for i in range(N)]

X = list(set([x for x, y in points]))
Y = list(set([y for x, y in points]))

X.sort()
Y.sort()

ans = float('inf')
for i, min_x in enumerate(X):
    for max_x in X[i+1:]:
        for j, min_y in enumerate(Y):
            for max_y in Y[j + 1:]:
                m = (max_x - min_x) * (max_y - min_y)
                internal_points = [(x, y) for x, y in points if min_x <= x <= max_x and min_y <= y <= max_y]
                if len(internal_points) >= K:
                    ans = min(ans, m)

print(ans)

Submission status: Accepted

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

pts.sort()
ys.sort()

ans = 10**20
for i, y1 in enumerate(ys):
    for y2 in ys[i+1:]:
        for j, (x1, _) in enumerate(pts):
            num = 0
            for x, y in pts[j:]:
                if y1 <= y <= y2:
                    num += 1
                if num >= K:
                    area = (x-x1) * (y2-y1)
                    ans = min(ans, area)
                    break

print(ans)