Problem:


Score : 400 points

Problem Statement

We have N points in a two-dimensional plane.

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

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

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

Find the minimum possible area of such a rectangle.  

Constraints

2 \leq K \leq N \leq 50 

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

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

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

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

Input

Input is given from Standard Input in the following format:  

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

Output

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

Sample Input 1

4 4
1 4
3 3
6 2
8 1

Sample Output 1

21

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

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

Sample Input 2

4 2
0 0
1 1
2 2
3 3

Sample Output 2

1

Sample Input 3

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

Sample Output 3

3999999996000000001

Watch out for integer overflows.  



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


Sample output:
21

Submission status: Time Limit Exceeded

Solution code:
s = input().split(" ")
N = int(s[0])
K = int(s[1])
x = []
y = []
for i in range(N):
    s = input().split(" ")
    x.append(int(s[0]))
    y.append(int(s[1]))
res = 4 * 10**18
for i in range(N):
    for j in range(N):
        for k in range(N):
            for l in range(N):
                x0 = min(x[i], x[j])
                x1 = max(x[i], x[j])
                y0 = min(y[k], y[l])
                y1 = max(y[k], y[l])
                cnt = 0
                for m in range(N):
                    if x0 <= x[m] and x[m] <= x1 and y0 <= y[m] and y[m] <= y1:
                        cnt += 1
                if cnt >= K:
                    res = min(res, (x1 - x0) * (y1 - y0))
print(res)

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
p=[]
for i in range(n):
    x,y=map(int,input().split())
    p.append([x,y])
ret=10**25
for a in range(n):
    for b in range(n):
        for c in range(n):
            for d in range(n):
                l=min(p[a][0],p[b][0],p[c][0],p[d][0])
                r=max(p[a][0],p[b][0],p[c][0],p[d][0])
                u=min(p[a][1],p[b][1],p[c][1],p[d][1])
                t=max(p[a][1],p[b][1],p[c][1],p[d][1])
                cnt=0
                for i in range(n):
                    if l<=p[i][0]<=r and u<=p[i][1]<=t:
                        cnt+=1
                if cnt>=k:
                    ret=min(ret,(r-l)*(t-u))
print(ret)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
X = set(); Y = set()
P = set()
for i in range(n):
    x, y = map(int, input().split())
    X.add(x); Y.add(y)
    P.add((x, y))

X = sorted(X); w = len(X)
Y = sorted(Y); h = len(Y)
MX = {x: i for i, x in enumerate(X)}
MY = {y: i for i, y in enumerate(Y)}
Q = {(MX[x], MY[y]) for x, y in P}
S = [[0]*(w+1) for i in range(h+1)]
for i in range(h):
    tmp = 0
    for j in range(w):
        if (j, i) in Q:
            tmp += 1
        S[i+1][j+1] = S[i][j+1] + tmp

ans = 10**100
for y1 in range(h):
    for x1 in range(w):
        for y2 in range(h):
            for x2 in range(w):
                count = S[y2+1][x2+1] - S[y2+1][x1] - S[y1][x2+1] + S[y1][x1]
                if count >= k:
                    ans = min(ans, (X[x2]-X[x1])*(Y[y2]-Y[y1]))
print(ans)

Submission status: Time Limit Exceeded

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

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

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 main():
    n,k = LI()
    xs = set()
    ys = set()
    a = []
    for _ in range(n):
        x,y = LI_()
        a.append((x,y))
        xs.add(x)
        ys.add(y)
    xd = {}
    yd = {}
    for x,i in zip(sorted(list(xs)), range(n)):
        xd[x] = i
    for y,i in zip(sorted(list(ys)), range(n)):
        yd[y] = i
    xis = sorted(list(xs))
    yis = sorted(list(ys))

    b = []
    for x,y in a:
        b.append((xd[x],yd[y]))

    if k == 1:
        return 0

    r = inf
    for i in range(n):
        xi = xis[i]
        for j in range(n-1,i-1,-1):
            xj = xis[j]
            xf = True
            for l in range(n):
                yl = yis[l]
                for m in range(n-1,l-1,-1):
                    t = 0
                    for x,y in b:
                        if i <= x <= j and l <= y <= m:
                            t += 1
                    if t >= k:
                        tr = (xj-xi) * (yis[m]-yl)
                        if tr < r:
                            r = tr
                        xf = False
                    else:
                        break
            if xf:
                break

    return r


print(main())

Submission status: Accepted

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

S.sort()
T.sort()
ans = float("inf")
for i in range(N):
    for j in range(i+1, N):
        for k in range(N):
            for l in range(k+1, N):
                c = 0
                for x, y in A:
                    if S[i] <= x <= S[j]:
                        if T[k] <= y <= T[l]:
                            c += 1
                if c >= K:
                    ans = min(ans, (S[j] - S[i])*(T[l] - T[k]))
print(ans)

Submission status: Accepted

Solution code:
N, K = list(map(int, input().split()))
X = [0]*N
Y = [0]*N
for i in range(N):
    X[i], Y[i] = list(map(int, input().split()))
YS = [[Y[i], i] for i in range(N)]
YS.sort()
# print(YS)

ans = 10**20
for i in range(N):
    for j in range(i+1, N):
        l, r = X[i], X[j]
        if l > r:
            l, r = r, l
        u = 0
        d = 0
        A = [(l <= X[k] <= r) for k in range(N)]
        # print(A)
        ct = A[YS[0][1]]
        for d in range(N):
            while ct < K:
                u += 1
                if u >= N:
                    break
                ct += A[YS[u][1]]
                # print(ct)
            else:
                S = (r-l)*(YS[u][0]-YS[d][0])
                ans = min(ans, S)
                ct -= A[YS[d][1]]
print(ans)

Submission status: Accepted

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

xv = sorted(xv)
yv = sorted(yv)
ans = (xv[n-1] - xv[0]) * (yv[n-1] - yv[0])
for l in range(n):
    lx = xv[l]
    for r in range(l+1, n):
        rx = xv[r]
        for b in range(n):
            by = yv[b]
            for t in range(b+1, n):
                ty = yv[t]
                cnt = 0
                for x, y in xy:
                    if lx <= x <= rx and by <= y <= ty:
                        cnt += 1
                if cnt >= k:
                    ans = min(ans, (rx - lx)*(ty - by))
print(ans)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce, lru_cache
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()))
def TUPLE(): return tuple(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
#from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

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])
			ans = min(ans, sq)
print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations, product
import bisect as bs

def tuple_int(iterable):
    return tuple(map(int, iterable.split()))

def S_with_K_plots(plots, K):
    result = []
    X, Y = sorted([x for x,y in plots]), sorted([y for x,y in plots])
    for xinf, xsup in combinations(X,2):
        for yinf in Y:
            ysup = [y for x,y in plots if xinf<=x<=xsup and y >= yinf]
            if len(ysup) < K: continue
            ysup.sort()
            result.append((xsup-xinf)*(ysup[K-1]-yinf))
    return result

if __name__ == '__main__':
    with open(0) as f:
        N, K = map(int, f.readline().split())
        plots = list(map(tuple_int, f.readlines()))
    print(min(S_with_K_plots(plots, K)))

Submission status: Accepted

Solution code:
import sys
from collections import deque
from functools import lru_cache
import bisect
import copy
import heapq
import itertools
import math
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


def main():
    N, K = read_values()
    P = [tuple(read_values()) for _ in range(N)]

    X = sorted([x for x, _ in P])
    Y = sorted([y for _, y in P])

    res = 10 ** 20
    for xl in range(N):
        for xr in range(xl + 1, N):
            for yl in range(N):
                for yr in range(yl + 1, N):
                    k = sum(X[xl] <= x <= X[xr] and Y[yl] <= y <= Y[yr] for x, y in P)
                    # print(f"X[{xl}, {xr}], Y[{yl}, {yr}] -> k:{k}")
                    if K <= k:
                        res = min(res, (X[xr] - X[xl]) * (Y[yr] - Y[yl]))
    print(res)



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#atcoder -take a rest-(easy)

def main():
    N,K = map(int,input().split())
    que = []
    que_x =  []
    que_y = []
    for i in range(N):
        x,y = map(int,input().split())
        que_x.append(x)
        que_y.append(y)
        que.append((x,y))
    que_x.sort()
    que_y.sort()
    ans = 10**100
    for i in range(N):
        for j in range(i,N):
            for _i in range(N):
                for _j in range(_i,N):
                    h,w = que_x[j]-que_x[i],que_y[_j] -que_y[_i]
                    cnt = 0
                    for x,y in que:
                        if que_x[i]<=x<=que_x[j] and que_y[_i]<=y<=que_y[_j]:
                            cnt += 1
                    if cnt >=K:
                        ans = min(ans,h*w)
    print(ans)
    return




if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def solve():
  n, k = map(int, input().split())
  p = [tuple(map(int, input().split())) for i in range(n)]
  p.sort()
  ans = 4000000000000000000
  for i in range(k, n + 1):
      for j in range(n - i + 1):
          x = p[i + j - 1][0] - p[j][0]
          s = [p[a][1] for a in range(j, i + j)]
          s.sort()
          y = 4000000000
          for a in range(i - k + 1):
            y = min(y, s[a + k - 1] - s[a])
          ans = min(ans, x * y)
  print(ans)
solve()

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
p = [tuple(map(int, input().split())) for i in range(n)]
p.sort()
ans = 4000000000000000000
for i in range(k, n + 1):
    for j in range(n - i + 1):
        x = p[i + j - 1][0] - p[j][0]
        s = [p[a][1] for a in range(j, i + j)]
        s.sort()
        y = 4000000000
        for a in range(i - k + 1):
          y = min(y, s[a + k - 1] - s[a])
        ans = min(ans, x * y)
print(ans)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())

dot=[]
xxx=[]
yyy=[]

ans=float('inf')

for i in range(n):
  x,y=map(int,input().split())
  dot.append([x,y])
  xxx.append(x)
  yyy.append(y)

xxx.sort()
yyy.sort()

for sx in range(n):
  for sy in range(n):
    for gx in range(sx+1,n):
      for gy in range(sy+1,n):
        cnt=0
        for lst in dot:
          if xxx[sx]<=lst[0]<=xxx[gx]:
            if yyy[sy]<=lst[1]<=yyy[gy]:
              cnt+=1
      
        if cnt>=k:
          if xxx[sx]==xxx[gx] or yyy[sy]==yyy[gy]:
            continue
          ans=min(ans,(xxx[gx]-xxx[sx])*(yyy[gy]-yyy[sy]))


print(ans)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
nodes=[]
for i in range(N):
  x,y=map(int,input().split())
  nodes.append((x,y))
nodes.sort()
import math
ans=math.inf
count=0
for i in range(N):
  for j in range(i+1,N):
    for k in range(N):
      for l in range(i+1,N):
        count=0
        for m in range(N):
          small=min(nodes[k][1],nodes[l][1])
          big=max(nodes[k][1],nodes[l][1])
          if nodes[i][0]<=nodes[m][0]<=nodes[j][0] and small<=nodes[m][1]<=big:
            count+=1
        if count>=K:
          ans=min(ans,(nodes[j][0]-nodes[i][0])*(big-small))
print(ans)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
p = sorted([tuple(map(int, input().split())) for i in range(n)])
ans = 4 * 10**18
for i in range(k, n + 1):
    for j in range(n - i + 1):  # x座標に関して j から i + j まで含む
        x = p[i + j - 1][0] - p[j][0]
        s = sorted([p[a][1] for a in range(j, i + j)])
        y = min(s[a + k - 1] - s[a] for a in range(i - k + 1))
        ans = min(ans, x * y)
print(ans)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
point=[list(map(int,input().split())) for _ in range(N)]
ans=10**30
#print(ans)
#print(Decimal(1999999999)*Decimal(1999999999))
#print(1999999999*1999999999)
for i in range(N):
    for j in range(i,N):
        x1,_=point[i]
        x2,_=point[j]
        minx=min(x1,x2)
        maxx=max(x1,x2)
        for k in range(N):
            for l in range(k,N):
                _,y1= point[k]
                _,y2= point[l]
                miny = min(y1,y2)
                maxy = max(y1,y2)
                cnt=0
                menseki=(maxx-minx)*(maxy-miny)
                for m in range(N):
                    x,y=point[m]
                    if (minx<=x<=maxx)and(miny<=y<=maxy):
                        cnt=cnt+1
                if cnt>=K:
                    ans=min(ans,menseki)
print(ans)

"""
for i in range(N):
    for j in range(i+1,N):
        #print(i,j)
        menseki=Decimal(1)
        x1,y1=point[i]
        x2,y2=point[j]
        if x1<x2:
            abx=Decimal(x2)-Decimal(x1)
        else:
            abx=Decimal(x1)-Decimal(x2)
        if y1<y2:
            aby=Decimal(y2)-Decimal(y1)
        else:
            aby=Decimal(y1)-Decimal(y2)
        print("")
        print(abx,aby)
        menseki=abx*aby
        print(menseki)
        minx=min(x1,x2)
        maxx=max(x1,x2)
        miny=min(y1,y2)
        maxy=max(y1,y2)
        pnum=0
        print(minx,maxx,miny,maxy)
        for x,y in point:
            #print(x,y)
            if (minx<=x<=maxx)and(miny<=y<=maxy):
                pnum=pnum+1
        print(pnum)
        if pnum>=K:
            ans=ans.min(menseki)
            print(ans)
print(ans)
"""

Submission status: Accepted

Solution code:
def abc075_d():
    n, k = map(int, input().split())
    P = []
    xarr = []
    yarr = []
    for _ in range(n):
        x, y = (int(x) for x in input().split())
        P.append((x, y))
        xarr.append(x)
        yarr.append(y)
    xarr.sort()
    yarr.sort()

    ans = 5*10**18
    for s, xi in enumerate(xarr):
        for xj in xarr[s+1:]:
            cand = [(x, y) for x, y in P if xi <= x and x <= xj]
            for t, yi in enumerate(yarr):
                for yj in yarr[t+1:]:
                    cnt = len([y for x, y in cand if yi <= y and y <= yj])
                    if cnt >= k:
                        area = (xj - xi) * (yj - yi)
                        ans = min(ans, area)
    print(ans)

if __name__ == '__main__':
    abc075_d()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
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, sub, itemgetter, attrgetter


import sys
# sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


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


def read_float():
    return float(buff_readline())


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


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().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


def ref(N, M, XY):
    ans = INF
    for i in combinations(range(N), r=M):
        minx = INF
        miny = INF
        maxx = -INF
        maxy = -INF
        for j in i:
            x, y = XY[j]
            minx = min(minx, x)
            maxx = max(maxx, x)
            miny = min(miny, y)
            maxy = max(maxy, y)
        ans = min(ans, (maxx-minx)*(maxy-miny))
    return ans

@mt
def slv(N, M, XY):
    XY.sort(key=itemgetter(1))
    XY.sort()
    # print(XY)

    ans = INF
    for i, (x, y) in enumerate(XY):
        yl = [y]
        for j in range(i+1, N):
            x2, y2 = XY[j]
            lx = x2-x
            yl.append(y2)

            if len(yl) >= M:
                yl.sort()
                for k in range(len(yl)-M+1):
                    ly = yl[k+M-1] -  yl[k]
                    ans = min(ans, lx*ly)
    return ans

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



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from sys import stdin
def input():
    return stdin.readline().strip()

n, k = map(int, input().split())
xy  = []
for _ in range(n):
    i, j = map(int, input().split())
    xy.append((i, j))

xy.sort()

# decide left, right, down
ans = 10 ** 19
for left in range(n-k+1):
    for right in range(left+k-1, n):
        horiz = xy[right][0] - xy[left][0]

        choose = sorted(xy[left:right+1], key=lambda x: x[1])
        for down in range(len(choose)-k+1):
            # up = down + k - 1
            # vert = choose[down+k-1][1] - choose[down][1]
            area = horiz * (choose[down+k-1][1] - choose[down][1])
            if area < ans:
                ans = area

print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
def input():
    return stdin.readline().strip()

n, k = map(int, input().split())
xy  = []
for _ in range(n):
    i, j = map(int, input().split())
    xy.append((i, j))

xy.sort()

# decide left, right, down
ans = float('inf')
for left in range(n-k+1):
    for right in range(left+k-1, n):
        choose = sorted(xy[left:right+1], key=lambda x: x[1])
        for down in range(len(choose)-k+1):
            area = (xy[right][0] - xy[left][0]) * (choose[down+k-1][1] - choose[down][1])
            if area < ans:
                ans = area

print(ans)

Submission status: Accepted

Solution code:
n,k = map(int, input().split())
xs = []
ys = []
ps = []
for i in range(n):
    x,y = map(int, input().split())
    xs.append(x)
    ys.append(y)
    ps.append((x,y))
# 座圧
xs = sorted(list(set(xs)))
ys = sorted(list(set(ys)))
xdic = {x:i for i, x in enumerate(xs)}
ydic = {y:i for i, y in enumerate(ys)}
xrdic = {i:x for i, x in enumerate(xs)}
yrdic = {i:y for i, y in enumerate(ys)}
nx = len(xs)
ny = len(ys)


fs = [[0] * (1+ny) for i in range(nx+1)]
for x,y in ps:
    ix = xdic[x]
    iy = ydic[y]
    fs[ix][iy] += 1

acc = [[0] * (1+ny) for i in range(nx+1)]
for i in range(nx):
    for j in range(ny):
        acc[i+1][j+1] = acc[i+1][j] + acc[i][j+1] - acc[i][j] + fs[i][j]

def calc(sx,sy,tx,ty):
    ix1 = xrdic[sx]
    ix2 = xrdic[tx]
    iy1 = yrdic[sy]
    iy2 = yrdic[ty]
    return (ix2-ix1) * (iy2-iy1)

# print(xs,xdic,".",ys,ydic)
ans = 10**20
for sx in range(nx+1):
    for sy in range(ny+1):
        for tx in range(sx+1, nx+1):
            for ty in range(sy+1, ny+1):
                cnt = acc[tx][ty] - acc[sx][ty] - acc[tx][sy] + acc[sx][sy]
                if cnt >= k:
                    S = calc(sx,sy,tx-1,ty-1)
                    ans = min(ans, S)
print(ans)

Submission status: Accepted

Solution code:
import sys
from itertools import combinations 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N, K = map(int, readline().split())
X = []
Y = []
XY = []
for _ in range(N):
    x,y = map(int,readline().split())
    X.append(x)
    Y.append(y)
    XY.append((x,y))
INF = 10**31
ans = INF
for x1,x2 in combinations(X,2):
    for y1,y2 in combinations(Y,2):
        if x1 > x2:
            x1,x2 = x2,x1
        if y1 > y2:
            y1,y2 = y2,y1
        cnt = 0 
        for x,y in XY:
            if x1 <= x <= x2 and y1 <= y <= y2:
                cnt += 1 
        if cnt >= K:
            tmp = (x2-x1)*(y2-y1)
            ans = min(ans,tmp)

print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
x=[0]*n
y=[0]*n
for i in range(n):
  x[i],y[i]=map(int,input().split())
ans=10**19
for i in range(n):
  for j in range(i,n):
    for k in range(j,n):
      for l in range(k,n):
        xl=min(x[i],x[j],x[k],x[l])
        xr=max(x[i],x[j],x[k],x[l])
        yl=min(y[i],y[j],y[k],y[l])
        yh=max(y[i],y[j],y[k],y[l])
        cnt=0
        for c in range(n):
          cnt+=xl<=x[c]<=xr and yl<=y[c]<=yh
        if cnt>=m:ans=min(ans,(xr-xl)*(yh-yl))
print(ans)

Submission status: Accepted

Solution code:
import collections, itertools, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def S(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()

def resolve():
    N, K = LI()
    xy = [LI() for _ in range(N)]

    # 全ての長方形候補に対して、2次元累積和を使って内部の点の個数を算出する
    x_coord = [i[0] for i in xy]
    x_coord.sort()
    x_val_num = {x_coord[i]: i for i in range(N)}
    y_coord = [i[1] for i in xy]
    y_coord.sort()
    y_val_num = {y_coord[i]: i for i in range(N)}

    # 2次元累積和の計算
    xy_cnt = [[0] * N for _ in range(N)]
    for x, y in xy:
        xy_cnt[y_val_num[y]][x_val_num[x]] = 1
    # for i in xy_cnt:
    #     print(i)
    xy_acm = [[0] * (N + 1) for _ in range(N + 1)]
    for i in range(N):
        for j in range(N):
            xy_acm[i+1][j+1] = xy_cnt[i][j] + xy_acm[i+1][j] + xy_acm[i][j+1] - xy_acm[i][j]
    # for i in xy_acm:
    #     print(i)

    ans = INF
    for yl, yu in itertools.combinations(range(N + 1), 2):
        for xl, xu in itertools.combinations(range(N + 1), 2):
            cnt = xy_acm[yu][xu] - xy_acm[yu][xl] - xy_acm[yl][xu] + xy_acm[yl][xl]
            # print(cnt, yl, yu, xl, xu)
            if cnt >= K:
                ans = min((x_coord[xu-1] - x_coord[xl]) * (y_coord[yu-1] - y_coord[yl]), ans)

    print(ans)

if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
import collections, itertools, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def S(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()

def resolve():
    N, K = LI()
    xy = [LI() for _ in range(N)]

    # x, y全ての重複あり組み合わせに対して含まれる点の個数を算出する

    x_coord = [i[0] for i in xy]
    x_coord.sort()
    x_val_num = {x_coord[i]: i for i in range(N)}
    y_coord = [i[1] for i in xy]
    y_coord.sort()
    y_val_num = {y_coord[i]: i for i in range(N)}

    # 2次元累積和
    xy_cnt = [[0] * N for _ in range(N)]
    for x, y in xy:
        xy_cnt[y_val_num[y]][x_val_num[x]] = 1
    # for i in xy_cnt:
    #     print(i)
    xy_acm = [[0] * (N + 1) for _ in range(N + 1)]
    for i in range(N):
        for j in range(N):
            xy_acm[i+1][j+1] = xy_cnt[i][j] + xy_acm[i+1][j] + xy_acm[i][j+1] - xy_acm[i][j]
    # for i in xy_acm:
    #     print(i)

    ans = INF
    for yl, yu in itertools.combinations(range(N + 1), 2):
        for xl, xu in itertools.combinations(range(N + 1), 2):
            cnt = xy_acm[yu][xu] - xy_acm[yu][xl] - xy_acm[yl][xu] + xy_acm[yl][xl]
            # print(cnt, yl, yu, xl, xu)
            if cnt >= K:
                ans = min((x_coord[xu-1] - x_coord[xl]) * (y_coord[yu-1] - y_coord[yl]), ans)

    print(ans)

if __name__ == '__main__':
    resolve()

Submission status: Accepted

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

# H - x - i
# W - y - j

xs_decode = sorted(map(lambda t: t[0], xys))
ys_decode = sorted(map(lambda t: t[1], xys))
xs_encode = {e:i for i, e in enumerate(xs_decode)}
ys_encode = {e:i for i, e in enumerate(ys_decode)}

H = len(xs_encode)
W = len(ys_encode)

field_csum = [[0] * (W+1) for _ in range(H+1)]
for x, y in xys:
    i = xs_encode[x]
    j = ys_encode[y]
    field_csum[i+1][j+1] += 1
for i in range(H+1):
    for j in range(W):
        field_csum[i][j+1] += field_csum[i][j]
for i in range(H):
    for j in range(W+1):
        field_csum[i+1][j] += field_csum[i][j]


ans = 1 << 63 # INF
# bi < i <= ei and bj < j <= ej
for bi in range(H):
    for ei in range(bi + 1, H + 1):
        for bj in range(W):
            for ej in range(bj + 1, W + 1):
                if field_csum[ei][ej] - field_csum[bi][ej] - field_csum[ei][bj] + field_csum[bi][bj] >= K:
                    area = (xs_decode[ei-1] - xs_decode[bi]) * (ys_decode[ej-1] - ys_decode[bj])
                    ans = min(ans, area)
                    break # don't have to check larger ej 

print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations
def main():
    N, K = map(int, input().split())
    P = [list(map(int, input().split())) for _ in range(N)]
    ans = 1<<62
    for t in combinations(P, min(4, K)):
        xs, ys = zip(*t)
        xmin = min(xs)
        xmax = max(xs)
        ymin = min(ys)
        ymax = max(ys)
        area = (xmax-xmin) * (ymax-ymin)
        if ans < area:
            continue
        k = 0
        for x, y in P:
            if xmin <= x <= xmax and ymin <= y <= ymax:
                k += 1
        if k >= K:
            ans = area
    print(ans)

main()

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
xy = []
X = []
Y = []
for i in range(n):
    x, y = map(int, input().split())
    X.append(x)
    Y.append(y)
    xy.append([x, y])
X.sort()
Y.sort()
ans = float("inf")
for i in range(n):
    for j in range(i + 1, n):
        for l in range(n):
            for m in range(l + 1, n):
                count = 0
                for o in range(n):
                    if X[i] <= xy[o][0] <= X[j] and Y[l] <= xy[o][1] <= Y[m]:
                        count += 1
                if count >= k:
                    ans = min(ans, (X[j] - X[i]) * (Y[m] - Y[l]))
print(ans)

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
A = sorted([list(map(int,input().split()))for n in range(N)])
ans = float("inf")

for i in range(N-K+1):
  for j in range(i+K-1,N):
    P = A[j][0]-A[i][0]
    C = sorted([a[1] for a in A[i:j+1]])
    for k in range(j-i-K+2):
      Q = C[k+K-1]-C[k]
      ans = min(ans,P*Q)

print(ans)

Submission status: Accepted

Solution code:
N, K = (int(x) for x in input().split())
Plot = [tuple(int(x) for x in input().split()) for _ in range(N)]
X = [p[0] for p in Plot]
Y = [p[1] for p in Plot]
X.sort()
Y.sort()
#全2点間で長方形の辺を作り、その内内部点がK個のものだけ面積を比較する。
ans = 10e20
from itertools import combinations
for x1, x2 in combinations(X, 2):
    for y1 in Y:
        y2 = [y for x,y in Plot if x1 <= x <= x2 and y1 <= y]
        if len(y2) < K:
            break
        y2.sort()
        S = (x2-x1)*(y2[K-1]-y1)
        ans = min(ans, S)
print(ans)

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,K = list(map(int, input().split()))
xy = [tuple(map(int, input().split())) for _ in range(n)]
xs = list(set([item[0] for item in xy]))
ys = list(set([item[1] for item in xy]))
xs.sort()
ys.sort()
dx = {x:i for i,x in enumerate(xs)}
dy = {y:i for i,y in enumerate(ys)}
lx = len(xs)
ly = len(ys)
c = [[0]*ly for _ in range(lx)]
for x,y in xy:
    c[dx[x]][dy[y]] += 1
from itertools import combinations, combinations_with_replacement
def cumsum2(v):
    # v: h*wの2次元リスト
    h,w = len(v), len(v[0])
    v.insert(0, [0]*w)
    for l in v:
        l.insert(0, 0)
    for i in range(1,h+1):
        for j in range(1,w+1):
            v[i][j] = v[i-1][j] + v[i][j-1] - v[i-1][j-1] + v[i][j]
    return v
cumsum2(c)
ans = float("inf")
for i,j,k,l in combinations_with_replacement(range(n),4):
#     for k,l in combinations(range(n),2):
    mx = min(xy[i][0], xy[j][0], xy[k][0], xy[l][0])
    my = min(xy[i][1], xy[j][1], xy[k][1], xy[l][1])
    Mx = max(xy[i][0], xy[j][0], xy[k][0], xy[l][0])
    My = max(xy[i][1], xy[j][1], xy[k][1], xy[l][1])
    ix,iy = dx[mx], dy[my]
    Ix,Iy = dx[Mx], dy[My]
    count = c[Ix+1][Iy+1] - c[Ix+1][iy] - c[ix][Iy+1] + c[ix][iy]
    if count>=K:
        ans = min(ans, (Mx-mx)*(My-my))
#         print(count, i,j,k,l, (Mx-mx)*(My-my))
print(ans)

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
xy = [list(map(int,input().split())) for i in range(N)]
xy.sort()
ans = 10**20
for l in range(N):
    for r in range(l,N,1):
        tmp=[]
        for i in range(l,r+1,1):
            tmp.append(xy[i][1])
        tmp.sort()
        for d in range(0,len(tmp)-K+1,1):
            ans = min(ans,(tmp[d+K-1]-tmp[d])*(xy[r][0]-xy[l][0]))

print(ans)