Problem:


Score : 400 points

Problem Statement

We have N points in a two-dimensional plane.

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

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

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

Find the minimum possible area of such a rectangle.  

Constraints

2 \leq K \leq N \leq 50 

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

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

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

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

Input

Input is given from Standard Input in the following format:  

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

Output

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

Sample Input 1

4 4
1 4
3 3
6 2
8 1

Sample Output 1

21

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

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

Sample Input 2

4 2
0 0
1 1
2 2
3 3

Sample Output 2

1

Sample Input 3

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

Sample Output 3

3999999996000000001

Watch out for integer overflows.  



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


Sample output:
21

Submission status: Accepted

Solution code:
from itertools import accumulate
from operator import add

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

iXs = list(range(N))
iXs.sort(key=lambda iX: xs[iX])
odrXs = [0]*(N)
for odrX, iX in enumerate(iXs):
    odrXs[iX] = odrX
iYs = list(range(N))
iYs.sort(key=lambda iY: ys[iY])
odrYs = [0]*(N)
for odrY, iY in enumerate(iYs):
    odrYs[iY] = odrY

Ass = [[0]*(N) for _ in range(N)]
for odrX, odrY in zip(odrXs, odrYs):
    Ass[odrX][odrY] = 1

def getAccAss(Ass):
    accAss = [[0] * (len(Ass[0])+1)] + [accumulate([0] + As) for As in Ass]
    for x in range(1, len(accAss)):
        accAss[x] = list(map(add, accAss[x], accAss[x-1]))
    return accAss
def getRangeSum2D(accAss, xFr, xTo, yFr, yTo):
    return accAss[xTo+1][yTo+1] - accAss[xTo+1][yFr] - accAss[xFr][yTo+1] + accAss[xFr][yFr]

accAss = getAccAss(Ass)

ans = 10**20
for xFr in range(N-1):
    for xTo in range(xFr+1, N):
        for yFr in range(N-1):
            for yTo in range(yFr+1, N):
                num = getRangeSum2D(accAss, xFr, xTo, yFr, yTo)
                if num >= K:
                    area = (xs[iXs[xTo]]-xs[iXs[xFr]]) * (ys[iYs[yTo]]-ys[iYs[yFr]])
                    ans = min(ans, area)

print(ans)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
x = []
y = []
xx = []
yy = []
for i in range(n):
    a,b = map(int,input().split())
    x.append(a)
    y.append(b)
    xx.append(a)
    yy.append(b)
ans = 10 ** 40
x.sort()
y.sort()
for i in range(n):
    for j in range(i+1,n):
        for l in range(n):
            for h in range(l+1,n):
                lx = x[i]
                rx = x[j]
                uy = y[h]
                dy = y[l]
                cnt = 0
                for ii in range(n):
                    if lx <= xx[ii] <= rx and dy <= yy[ii] <= uy:
                        cnt += 1
                if cnt >= k:
                    if (rx-lx) * (uy-dy) != 0:
                        ans = min(ans,(rx-lx)*(uy-dy))
print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations,groupby
import sys
import bisect
import string
import math
import time
import random
def S_():
    return input()
def LS():
    return [i for i in input().split()]
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)]
        rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
#sys.setrecursionlimit(10**5)
input=lambda: sys.stdin.readline().rstrip()

def ran_input():
    import random
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

show_flg=False
show_flg=True

ans=1

n,k=LI()
a=[]

for i in range(n):
    x,y=LI()
    a.append((x,y))

a.sort()

ans=inf

for lx in range(n):
    for rx in range(lx+1,n):
        for ly in range(n):
            for ry in range(ly+1,n):
                c=0
                x1,x2,y1,y2=a[lx][0],a[rx][0],a[ly][1],a[ry][1]
                if y1>y2:
                    y1,y2=y2,y1
                for i in range(lx,rx+1):
                    x,y=a[i]
                    if x1<=x<=x2 and y1<=y<=y2:
                        c+=1
                
#                show(c,(lx,rx),(ly,ry),(x1,x2,y1,y2))
                if c>=k:
                    ans=min(ans,(x2-x1)*(y2-y1))

print(ans)

Submission status: Accepted

Solution code:
n,k = map(int, input().split())
a = [list(map(int, input().split())) for i in range(n)]
ax = sorted(a)
ans = 10**19
for i in range(n-1):
    for j in range(i+1,n):
        a_use = ax[i:j+1]
        xnum = len(a_use)
        sx = a_use[-1][0]-a_use[0][0]
        a_use.sort(key = lambda x:x[1])
        if xnum<k:
            continue
        for y1 in range(xnum-k+1):
            y2 = y1+k-1
            s = sx*(a_use[y2][1]-a_use[y1][1])
            ans = min(ans,s)
print(ans)

Submission status: Accepted

Solution code:
#n,kが小さい
#xi,yi全て試す

#for ループ変更
import itertools
n,k = map(int, input().split( ))

p = []
x = []
y = []
for i in range(n):
    xi,yi = map(int, input().split( ))
    p.append((xi,yi))
    x.append(xi)
    y.append(yi)

y = list(set(y))
x = list(set(x))
x.sort()
y.sort()
lx = len(x)
ly = len(y)
ans = 10**20
for xi,xj in itertools.combinations(x,2):
    for yi,yj in itertools.combinations(y,2):
        cnt = 0
        for xk,yk in p:
            if xi <= xk and xk<=xj and yi <=yk and yk<=yj:
                        cnt += 1
        if cnt >= k:
            ans = min(ans, (xj-xi)*(yj-yi))
print(ans)

Submission status: Accepted

Solution code:
import sys

inf = float('inf')

n, k, *xy = map(int, sys.stdin.read().split())
xy = list(zip(*[iter(xy)] * 2))

def main():
    xy.sort(key=lambda x: x[0])
    x = []
    y = []
    for i in range(n):
        x.append(xy[i][0])
        y.append(xy[i][1])
    
    area = inf
    for l in range(n-k+1):
        for r in range(l+k-1, n):
            dx = x[r] - x[l]
            seq_y = sorted(y[l:r+1])
            m = r - l + 1
            for d in range(m-k+1):
                for u in range(d+k-1, m):
                    dy = seq_y[u] - seq_y[d]
                    area = min(area, dx * dy)

    return area

if __name__ == '__main__':
    ans = main()
    print(ans)

Submission status: Accepted

Solution code:
n,k,*L=map(int,open(0).read().split())
X=[];Y=[]
for x,y in sorted((x,y) for x,y in zip(*[iter(L)]*2)):
	X.append(x)
	Y.append(y)
ans=float("inf")
for i in range(n-k+1):
	for j in range(i+k-1,n):
		w=X[j]-X[i]
		l=sorted(Y[i:j+1])
		h=min(My-my for my,My in zip(l,l[k-1:]))
		ans=min(ans,w*h)
print(ans)

Submission status: Accepted

Solution code:
n,k,*L=map(int,open(0).read().split())
X=[];Y=[]
for x,y in sorted((x,y) for x,y in zip(*[iter(L)]*2)):
	X.append(x)
	Y.append(y)
ans=float("inf")
for i in range(n-k+1):
	for j in range(i+k-1,n):
		w=X[j]-X[i]
		l=sorted(Y[i:j+1])
		h=min(My-my for my,My in zip(l,l[k-1:]))
		ans=min(ans,w*h)
print(ans)

Submission status: Accepted

Solution code:
import itertools
N,K=map(int,input().split())
XY=[list(map(int,input().split())) for i in range(N)]
ans=float("inf")

for xv in itertools.combinations( [xy[0] for xy in XY] ,2):
  for yv in itertools.combinations( [xy[1] for xy in XY] ,2):
    xmax=max(xv[0],xv[1])
    xmin=min(xv[0],xv[1])
    ymax=max(yv[0],yv[1])
    ymin=min(yv[0],yv[1])

    k=0
    for xy in XY:
      x,y=xy[0],xy[1]
      if xmin<=x and x<=xmax:
        if ymin<=y and y<=ymax:
          k+=1    
    if k>=K:
      ans=min(ans,(xmax-xmin)*(ymax-ymin))
print(ans)

Submission status: Accepted

Solution code:
n,h=map(int,input().split())
p,x,y=[],[],[]
z=float("inf")
for i in range(n):
  a,b=map(int,input().split())
  p.append((a,b))
  x.append(a)
  y.append(b)
x.sort()
y.sort()
for i in range(n-1):
  for j in range(i,n):
    for k in range(n-1):
      lx,rx,dy=x[i],x[j],y[k]
      c=0
      t=[]
      for a,b in p:
        if x[i]<=a<=x[j] and y[k]<=b:c+=1;t.append(b)
      if h<=c:z=min(z,(x[j]-x[i])*(sorted(t)[h-1]-y[k]))
print(z)

Submission status: Accepted

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

ans = 10 ** 20
for xl in range(N):
    for xr in range(xl + 1, N):
        Ysub = sorted([y for x, y in XY[xl:xr + 1]])
        for i in range(xr - xl - K + 2):
            Yk = Ysub[i:i + K] + [XY[xr][1], XY[xl][1]]
            ans = min(ans, (XY[xr][0] - XY[xl][0]) * (max(Yk) - min(Yk)))

print(ans)

Submission status: Accepted

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

N, K, *xy = map(int, read().split())
xy = sorted(zip(*[iter(xy)] * 2))
X, Y = zip(*xy)
answer = 10 ** 20

for left, right in combinations(range(N), 2):
    width = X[right] - X[left]
    tmp_Y = sorted(Y[left:right + 1])
    h = len(tmp_Y)
    for i in range(h):
        if i + K > h:
            break

        S = width * (tmp_Y[i + K - 1] - tmp_Y[i])
        if S < answer:
            answer = S

print(answer)

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:
def main():
    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 i in range(N):
        for j in range(N):
            for k in range(N):
                for l in range(N):
                    if x[i] < x[j] and y[k] < y[l]:
                        right = x[j]
                        left = x[i]
                        bottom = y[k]
                        top = y[l]

                        cnt = 0

                        for n in range(N):
                            if left <= x[n] <= right and bottom <= y[n] <= top:
                                cnt += 1

                        if cnt >= K:
                            ans = min(ans, (top - bottom) * (right - left))
    print(ans)



if __name__ == "__main__":
    main()

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:
import itertools
n,k=map(int,input().split())
l=[]
for i in range(n):
    l.append(list(map(int,input().split())))
c=itertools.combinations(range(n),2)
d=itertools.combinations(range(n),2)
ans=10**25
for i0 in range(n):
    for i1 in range(i0,n):
        for j0 in range(n):
            for j1 in range(j0,n):
                i=[i0,i1]
                j=[j0,j1]
                #print(i,j)
                lx=min(l[i[0]][0],l[i[1]][0])
                rx=max(l[i[0]][0],l[i[1]][0])
                dy=min(l[j[0]][1],l[j[1]][1])
                uy=max(l[j[0]][1],l[j[1]][1])
                tk=0
                for p in l:
                    if lx<=p[0]<=rx and dy<=p[1]<=uy:
                        tk+=1
                if tk>=k:
                    ans=min(ans,(uy-dy)*(rx-lx))
print(ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def main():
    n, k = MI()
    xy = []
    xx = []
    yy = []
    for _ in range(n):
        x, y = MI()
        xy.append([x, y])
        xx.append(x)
        yy.append(y)
    xx.sort()
    yy.sort()
    #print(xx)
    #print(yy)
    xtoi = {x: i for i, x in enumerate(xx)}
    ytoj = {y: j for j, y in enumerate(yy)}
    cs2d = [[0] * (n + 1) for _ in range(n + 1)]
    for x, y in xy:
        i, j = xtoi[x], ytoj[y]
        cs2d[i + 1][j + 1] = 1
    #p2D(cs2d)
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            cs2d[i][j] += cs2d[i][j - 1]
    for j in range(1, n + 1):
        for i in range(1, n + 1):
            cs2d[i][j] += cs2d[i-1][j]
    #p2D(cs2d)
    ans = 10 ** 20
    for ri in range(n):
        r = xx[ri]
        for li in range(ri):
            l = xx[li]
            for ti in range(n):
                t = yy[ti]
                for bi in range(ti):
                    b = yy[bi]
                    cnt = cs2d[ri+1][ti+1]-cs2d[ri+1][bi]-cs2d[li][ti+1]+cs2d[li][bi]
                    if cnt >= k:
                        s = (r - l) * (t - b)
                        if s < ans: ans = s
    print(ans)

main()

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
P = [tuple(map(int, input().split())) for _ in range(N)]
X = sorted([p[0] for p in P])
Y = sorted([p[1] for p in P])

ans = 10**20
for i in range(N-1):
    for j in range(i+1, N):
        x0 = X[i]
        x1 = X[j]

        for k in range(N-1):
            for l in range(k+1, N):
                y0 = Y[k]
                y1 = Y[l]

                c = 0
                for m in range(N):
                    if x0 <= P[m][0] <= x1 and y0 <= P[m][1] <= y1:
                        c += 1

                if c >= K:
                    ans = min(ans, (x1-x0)*(y1-y0))

print(ans)

Submission status: Accepted

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

P.sort()

ans = 10**20
for i in range(N-K+1):
    X = P[i+K-1][0]
    x = P[i][0]
    Y = []
    for j in range(i, K+i):
        Y.append(P[j][1])
    Y.sort()
    ans = min(ans, (X-x)*(Y[-1]-Y[0]))
    for j in range(K+i, N):
        Y.append(P[j][1])
        Y.sort()
        for k in range(len(Y)-K+1):
            ans = min(ans, (P[j][0]-x)*(Y[k+K-1]-Y[k]))
            
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


l = []
n, k = LI()
X = []
Y = []
ans = INF
for _ in range(n):
  x, y = LI()
  X += [x]
  Y += [y]
  l.append((x,y))

X.sort()
Y.sort()
for xl,xr in combinations(X, 2):
  for yl,yr in combinations(Y, 2):
    cnt = 0
    for x,y in l:
      if xl<=x<=xr and yl<=y<=yr:
        cnt += 1
      if cnt >= k and ans > (xr - xl) * (yr - yl):
         ans = (xr - xl) * (yr - yl)
print(ans)

Submission status: Accepted

Solution code:
import copy
import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
mod = 10**9 + 7
inf = float('inf')
ans = int(0)

N, K = LI()
x = [0]*N; y = [0]*N
for i in range(N):
    x[i], y[i] = LI()

X = copy.deepcopy(x); Y = copy.deepcopy(y)
X.sort(); Y.sort()

Xcandi = [0]*2; Ycandi = [0]*2
ylower = 0; yupper = N-1; ycur = (ylower+yupper)//2
ansC = []
for i in range(N-1):
    Xcandi[0] = X[i]
    for j in range(i+1,N):
        Xcandi[1] = X[j]
        for k in range(N-1):
            ylower = k+1; yupper = N - 1; ycur = (ylower + yupper) // 2
            Ycandi[0] = Y[k]
            while(True):
                cur = int(0)
                Ycandi[1] = Y[ycur]
                for l in range(N):
                    if Xcandi[0] <= x[l] <= Xcandi[1] and Ycandi[0] <= y[l] <= Ycandi[1]:
                        cur += 1
                if yupper - ylower >= 2:
                    if cur < K:
                        ylower = ycur
                        ycur = (ycur + yupper) // 2
                    else:
                        yupper = ycur
                        ycur = (ycur + ylower) // 2
                else:
                    cur = int(0)
                    Ycandi[1] = Y[yupper]
                    for l in range(N):
                        if Xcandi[0] <= x[l] <= Xcandi[1] and Ycandi[0] <= y[l] <= Ycandi[1]:
                            cur += 1
                    if cur < K:
                        break
                    else:
                        cur = int(0)
                        Ycandi[1] = Y[ylower]
                        for l in range(N):
                            if Xcandi[0] <= x[l] <= Xcandi[1] and Ycandi[0] <= y[l] <= Ycandi[1]:
                                cur += 1
                        if cur < K:
                            Ycandi[1] = Y[ylower+1]
                    cur = (Xcandi[1] - Xcandi[0])*(Ycandi[1] - Ycandi[0])
                    ansC.append(cur)
#                    print(Xcandi,Ycandi)
                    break


#print(ansC)
print(min(ansC))

Submission status: Accepted

Solution code:
import heapq

n, k = map(int,input().split())
X = [list(map(int,input().split())) for i in range(n)]

Y = [[j for j in i] for i in X]
Z = [[j for j in i] for i in X]

X.sort()
Y.sort(key=lambda x:x[1])

ans = float("inf")
for i in range(n):
    x0 = X[i][0]
    for j in range(n):
        y0 = Y[j][1]
        Q = []
        x1_ind = 0
        for p in range(n):
            if len(Q) == k:
                break
            else:
                if X[p][0] >= x0 and X[p][1] >= y0:
                    heapq.heappush(Q, [-X[p][1], X[p][0], X[p][1]])
                    x1_ind = p
        if len(Q) == k:
            x1 = X[x1_ind][0]
            pop = heapq.heappop(Q)
            y1 = -pop[0]
            heapq.heappush(Q, pop)
            ans = min(ans, (x1-x0) * (y1-y0))
            st = x1_ind
            for p in range(st+1, n):
                if X[p][0] >= x0 and X[p][1] >= y0:
                    heapq.heappush(Q, [-X[p][1], X[p][0], X[p][1]])
                    x1 = X[p][0]
                    heapq.heappop(Q)
                    pop = heapq.heappop(Q)
                    y1 = -pop[0]
                    heapq.heappush(Q, pop)
                    ans = min(ans, (x1-x0) * (y1-y0))
print(ans)

Submission status: Accepted

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

X=sorted([i[0] for i in xy])
Y=sorted([i[1] for i in xy])

ans=[]
for i in range(N-1):
  lx=X[i]
  for j in range(i+1,N):
    rx=X[j]
    for k in range(N-1):
      dy=Y[k]
      for l in range(k+1,N):
        uy=Y[l]
        cnt=0
        for x,y in xy:
          if lx<=x and x<=rx and dy<=y and y<=uy:
            cnt+=1
        if cnt>=K:
          ans.append((rx-lx)*(uy-dy))
          
          
print(min(ans))

Submission status: Accepted

Solution code:
n,K=map(int,input().split())
xy=[]
x=[]
y=[]
for i in range(n):
    a,b=map(int,input().split())
    x.append(a)
    y.append(b)
    xy.append([a,b])
x.sort()
y.sort()
data=[[0]*(n+1) for i in range(n+1)]
for u in xy:
    a,b=u
    X=x.index(a)
    Y=y.index(b)
    data[X][Y]=1
for i in range(n):
    for j in range(1,n):
        data[i][n-1-j]+=data[i][n-j]
for i in range(1,n):
    for j in range(n):
        data[n-i-1][j]+=data[n-i][j]
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):
                if data[i][k]+data[j+1][l+1]-data[i][l+1]-data[j+1][k]>=K:
                    ans=min(ans,(x[j]-x[i])*(y[l]-y[k]))
print(ans)

Submission status: Accepted

Solution code:
import sys
import heapq
INF = 1e20
n, k = [int(i) for i in sys.stdin.readline().split()]
ls = []
for i in range(n):
    x, y = [int(i) for i in sys.stdin.readline().split()]
    ls.append((x, y))
ls.sort(key=lambda x:x[0])
x_ls, y_ls = zip(*ls)
best = INF

x_ls = sorted(list(x_ls))
y_ls = sorted(list(y_ls))
for left_ind in range(n - k + 1):
    left = x_ls[left_ind]
    for right_ind in range(left_ind + k - 1, n):
        right = x_ls[right_ind]
        for down_ind in range(n - k + 1):
            down = y_ls[down_ind]
            for up_ind in range(down_ind + k - 1, n):
                up = y_ls[up_ind]
                cnt = 0
                for i in range(n):
                    x, y = ls[i]
                    if left <= x <= right and up >= y >= down:
                        cnt += 1
                if cnt >= k:
                    best = min(best, (up - down) * (right - left))
print(max(1,best))

Submission status: Accepted

Solution code:
# 二次元累積和
# 写経
# https://ikatakos.com/pot/programming_algorithm/contest_history/atcoder/2017/1014_abc075

def solve():
    from collections import namedtuple
    from operator import attrgetter
    import sys

    input = sys.stdin.readline

    Coordinates = namedtuple('Coordinates', ('x', 'y'))

    n, k = map(int, input().split())

    e = []
    for _ in range(n):
        x, y = map(int, input().split())
        e.append(Coordinates(x=x, y=y))
    x_asc = tuple(sorted(e, key=attrgetter('x')))  # x昇順
    y_asc = tuple(sorted(e, key=attrgetter('y')))  # y昇順

    # print(x_asc)
    # print(y_asc)

    tbl = tuple([0] * (n + 1) for _ in range(n + 1))
    for yi, py in enumerate(y_asc, 1):
        for xi, px in enumerate(x_asc, 1):
            tbl[xi][yi] = tbl[xi - 1][yi] + tbl[xi][yi - 1] - tbl[xi - 1][yi - 1] + (1 if py == px else 0)

    ans = float('inf')

    for left in range(1, n - (k - 1) + 1):
        for top in range(1, n - (k - 1) + 1):
            for right in range(left + k - 1, n + 1):
                for bottom in range(top + k - 1, n + 1):
                    if tbl[right][bottom] - tbl[left - 1][bottom] - tbl[right][top - 1] + tbl[left - 1][top - 1] >= k:
                        ans = min(ans,
                                  (y_asc[bottom - 1].y - y_asc[top - 1].y) * (x_asc[right - 1].x - x_asc[left - 1].x))
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
# 二次元累積和
# 写経
# https://ikatakos.com/pot/programming_algorithm/contest_history/atcoder/2017/1014_abc075

from collections import namedtuple
from operator import attrgetter

Coordinates = namedtuple('Coordinates', ('ind', 'x', 'y'))

n, k = map(int, input().split())

e = []
for ind in range(n):
    x, y = map(int, input().split())
    e.append(Coordinates(ind=ind, x=x, y=y))
x_asc = sorted(e, key=attrgetter('x'))  # x昇順
y_asc = sorted(e, key=attrgetter('y'))  # y昇順

# print(x_asc)
# print(y_asc)

tbl = [[0] * (n + 1) for _ in range(n + 1)]
for yi, py in enumerate(y_asc, 1):
    for xi, px in enumerate(x_asc, 1):
        tbl[xi][yi] = tbl[xi - 1][yi] + tbl[xi][yi - 1] - tbl[xi - 1][yi - 1] + (1 if py == px else 0)

ans = float('inf')

for left in range(1, n - (k - 1) + 1):
    for top in range(1, n - (k - 1) + 1):
        for right in range(left + k - 1, n + 1):
            for bottom in range(top + k - 1, n + 1):
                if tbl[right][bottom] - tbl[left - 1][bottom] - tbl[right][top - 1] + tbl[left - 1][top - 1] >= k:
                    ans = min(ans, (y_asc[bottom - 1].y - y_asc[top - 1].y) * (x_asc[right - 1].x - x_asc[left - 1].x))
print(ans)

Submission status: Accepted

Solution code:
def solve():
    res = float('inf')
    for i in range(n):
        r_top = coordinates[i][1]
        for j in range(n):
            r_bottom = coordinates[j][1]
            if r_bottom < r_top:
                continue
            for k in range(n):
                c_left = coordinates[k][0]
                for l in range(n):
                    c_right = coordinates[l][0]
                    if c_right < c_left:
                        continue
                    cnt = 0
                    for c, r in coordinates:
                        # print(r_top, r, r_bottom, c_left, c, c_right)
                        if (r_top <= r <= r_bottom) and (c_left <= c <= c_right):
                            cnt += 1
                            if cnt >= need:
                                res = min(res, (r_bottom - r_top) * (c_right - c_left))
                                break

    return res


n, need = map(int, input().split())
coordinates = tuple(sorted(tuple(map(int, input().split())) for _ in range(n)))
# x,y昇順

# print(coordinates)

print(solve())

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
def inputs():return [int(x) for x in input().split()]
N,K = inputs()
xy = [inputs() for _ in range(N)]
#xy = sorted(xy,key=lambda x: x[1])
xy = sorted(xy,key=lambda x: x[0])
#print(xy)
ans = 10**20
for i in range(N-K+1):
  for j in range(i+K-1,N):
    #print(i,j)
    xy1 = xy[i:j+1]
    #print(xy1)
    xy1 = sorted(xy1,key=lambda x: x[1])
    mi = min(xy1[i+K-1][1]-xy1[i][1] for i in range(len(xy1)-K+1))
    ans = min(ans,(xy[j][0]-xy[i][0])*mi)
print(ans)

Submission status: Accepted

Solution code:
if __name__ == "__main__":
    INF = 40 ** 18 + 1
    N, K = map(int, input().split())
    Point = list()
    for i in range(N):
        Point.append(list(map(int, input().split())))

    # 四角形の頂点を２点選んでその中にK点含まれてて、面積が小さければ更新
    ans = INF
    # iは1点目のx, jは1点目のy、kは2点目のx, lは2点目のy
    for i in range(N):
        for j in range(N):
            for k in range(N):
                for l in range(N):
                    x0 = Point[i][0]
                    y0 = Point[j][1]
                    x1 = Point[k][0]
                    y1 = Point[l][1]
                    # 四角形作れない座標の組み合わせと、1点目 < 2点目の座標関係で無いならスルー
                    if x0 >= x1 or y0 >= y1:
                        continue
                    count = 0
                    for m in range(N):
                        x, y = Point[m][0], Point[m][1]
                        if x0 <= x <= x1 and y0 <= y <= y1:
                            count += 1
                        if count >= K:
                            area = (x1 - x0) * (y1 - y0)
                            if area < ans:
                                ans = area
                            break

    print(ans)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
P,X,Y=[],[],[]
for _ in range(n):
    x,y=map(int,input().split())
    P.append((x,y))
    X.append(x)
    Y.append(y)
ans=10**19
X.sort()
Y.sort()
for d in range(n-1):
    for u in range(d,n):
        for l in range(n-1):
            for r in range(l,n):
                D,U,L,R=X[d],X[u],Y[l],Y[r]
                cnt=0
                for i in P:
                    if D<=i[0]<=U and L<=i[1]<=R:
                        cnt+=1
                if cnt>=k:
                    ans=min(ans,(U-D)*(R-L))
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline
N, M = map(int, input().split())
P = []
for _ in range(N):
  P.append(list(map(int, input().split())))
X = sorted(set([p[0] for p in P]))
Y = sorted(set([p[1] for p in P]))

res = (X[-1] - X[0]) * (Y[-1] - Y[0])
cs = [[0] * (len(Y)) for _ in range(len(X))]

for i in range(len(X)):
  for j in range(len(Y)):
    for p in P:
      if X[0] <= p[0] <= X[i] and Y[0] <= p[1] <= Y[j]:
        cs[i][j] += 1
for l in range(len(X) - 1):
  for r in range(l + 1, len(X)):
    for d in range(len(Y) - 1):
      for u in range(d + 1, len(Y)):
        a = cs[r][u]
        if l > 0:
          a -= cs[l - 1][u]
        if d > 0:
          a -= cs[r][d - 1]
        if l > 0 and d > 0:
          a += cs[l - 1][d - 1]
        if a >= M:
          #print(X[l], X[r], Y[d], Y[u], abs(X[r] - X[l]) * abs(Y[u] - Y[d]), a, l, r, d, u)
          res = min(res, abs(X[r] - X[l]) * abs(Y[u] - Y[d]))
print(res)

Submission status: Accepted

Solution code:
import sys
I = lambda:[int(x) for x in sys.stdin.readline().split()]
N,K = I()
Z = [I() for _ in range(N)]
Z.sort()

INF = 10**20
ans = INF

for i in range(N):
    for j in range(i+K-1,N):
        l = sorted(t[1] for t in Z[i:j+1])
        ans_tmp = [(Z[j][0]-Z[i][0])*(v-u) for u,v in zip(l,l[K-1:])]
        ans = min(ans,*ans_tmp)
print(ans)

Submission status: Accepted

Solution code:
import sys
def LI(): return([int(x) for x in sys.stdin.readline().split()])

N,K = LI()
XY = [LI() for _ in range(N)]

X = []
Y = []
for x,y in XY:
    if not(x in X):
        X.append(x)
    if not(y in Y):
        Y.append(y)
        
X.sort()
Y.sort()
dic_XoYo = {}
dic_XcYo = {}
dic_XoYc = {}
dic_XcYc = {}
for x1 in X:
  for y1 in Y:
    key = x1*(10**10)+y1
    cnt_XoYo = 0
    cnt_XcYo = 0
    cnt_XoYc = 0
    cnt_XcYc = 0
    for x2,y2 in XY:
      if x2<=x1 and y2<=y1:
        cnt_XcYc += 1
      if x2<x1 and y2<=y1:
        cnt_XoYc += 1
      if x2<=x1 and y2<y1:
        cnt_XcYo += 1
      if x2<x1 and y2<y1:
        cnt_XoYo += 1
    dic_XcYc[key] = cnt_XcYc
    dic_XoYc[key] = cnt_XoYc
    dic_XcYo[key] = cnt_XcYo
    dic_XoYo[key] = cnt_XoYo

ans = []
for xl in range(len(X)-1):
  for xr in range(xl,len(X)):
    for yd in range(len(Y)-1):
      for yu in range(yd,len(Y)):
        cnt = dic_XcYc[X[xr]*(10**10)+Y[yu]]
        cnt -= dic_XcYo[X[xr]*(10**10)+Y[yd]]
        cnt -= dic_XoYc[X[xl]*(10**10)+Y[yu]]
        cnt += dic_XoYo[X[xl]*(10**10)+Y[yd]]
        if cnt>=K:
          ans.append((X[xr]-X[xl])*(Y[yu]-Y[yd]))
print(min(ans))

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
ary = [list(map(int,input().split())) for _ in range(N)]
a = sorted(ary)
ans = float("Inf")
for i in range(N-K+1):
    for j in range(i,N-K+1):
        lx = a[i][0]; rx = a[K+j-1][0]
        b = a[i:K+j]
        c = sorted(b,key=lambda x:(x[1]))
        for k in range(len(c)-K+1):
            by = c[k][1]; uy = c[k+K-1][1]
            ans = min(ans,(rx - lx) * (uy - by))
print(ans)