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:
def axis_parallel_rectangle(N: int, K: int, xy: list)->int:
    # 1. 座標圧縮
    sorted_x = sorted(v[0] for v in xy)
    sorted_y = sorted(v[1] for v in xy)

    XY = [(sorted_x.index(v[0]), sorted_y.index(v[1])) for v in xy]
    # 2. 圧縮された座標上で点の個数に関して累積和をとる。
    S = [[0] * (N+1) for _ in range(N+1)]
    for x, y in XY:
        S[x+1][y+1] = 1

    for x in range(N+1):
        for y in range(N):
            S[x][y+1] += S[x][y]

    for y in range(N+1):
        for x in range(N):
            S[x+1][y] += S[x][y]

    # 3. x 座標から二つを選ぶ。
    min_area = float('inf')
    for x1 in range(N):
        for x2 in range(x1+1, N):
            for y1 in range(N):
                for y2 in range(y1+1, N):
                    count = S[x2+1][y2+1]-S[x2+1][y1]-S[x1][y2+1]+S[x1][y1]
                    if count < K:
                        continue
                    xmin, xmax = sorted_x[x1], sorted_x[x2]
                    ymin, ymax = sorted_y[y1], sorted_y[y2]
                    min_area = min(min_area, (xmax-xmin)*(ymax-ymin))
    # これで O(N^3) = O(10^5) くらい ?
    return min_area


if __name__ == "__main__":
    N = 0
    N, K = map(int, input().split())
    xy = [tuple(map(int, input().split())) for _ in range(N)]
    ans = axis_parallel_rectangle(N, K, xy)
    print(ans)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
p = [tuple(map(int, input().split())) for _ in range(n)]
xlist = []
ylist = []
for x, y in p:
    xlist.append(x)
    ylist.append(y)
xlist.sort()
ylist.sort()
cum = [[0 for _ in range(n+1)] for _ in range(n+1)]
for i in range(n):
    for j in range(n):
        cum[i+1][j+1] = cum[i+1][j] + cum[i][j+1] - cum[i][j] + ((xlist[i], ylist[j]) in p)
minarea = 10 ** 20
for l in range(n-1):
    for r in range(l+2, n+1):
        for u in range(n-1):
            for d in range(u+2, n+1):
                point = cum[r][d] - cum[l][d] - cum[r][u] + cum[l][u]
                if point == k:
                    minarea = min(minarea, (xlist[r-1] - xlist[l]) * (ylist[d-1] - ylist[u]))
print(minarea)

Submission status: Accepted

Solution code:
import sys
from collections import deque
import copy
 
from math import *
 
def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline
 
def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N, K] =  [long(input_raw[0]), long(input_raw[1])]
    x_list = [0 for i in range(N)]
    y_list = [0 for i in range(N)]
    point_set = set([])
    for i in range(N):
        input_raw = read_func().strip().split()
        [x, y] =  [long(input_raw[0]), long(input_raw[1])]
        x_list[i] = x
        y_list[i] = y
        point_set.add((x, y))
    h = {}
    gx = {}
    gy = {}
    for x in x_list:
        for y in y_list:
            num = 0
            num_gx = 0
            num_gy = 0
            for i in range(N):
                if x <= x_list[i] and y <= y_list[i]:
                    num += 1
                if x == x_list[i] and y <= y_list[i]:
                    num_gx += 1
                if y == y_list[i] and x <= x_list[i]:
                    num_gy += 1
            h[(x, y)] = num
            gx[(x, y)] = num_gx
            gy[(y, x)] = num_gy
##    for point in point_set:
##        for y in y_list: #count x point num of more y
##            if (point[0], y) not in gx:
##                gx[(point[0], y)] = 0
##            if point[1] >= y:
##                gx[(point[0], y)] += 1L
##
##    for point in point_set:
##        for x in x_list: #count y point num of more x
##            if (point[1], x) not in gy:
##                gy[(point[1], x)] = 0
##            if point[0] >= x:
##                gy[(point[1], x)] += 1L
 
 
    min_S = long(sys.maxint) * long(sys.maxint)
    for i in range(N):
        for j in range(i + 1, N):
            for m in range(N):
                for n in range(m + 1, N):
                    x1 = min(x_list[i], x_list[j])
                    x2 = max(x_list[i], x_list[j])
                    y1 = min(y_list[m], y_list[n])
                    y2 = max(y_list[m], y_list[n])
                    in_num =  (h[(x1, y1)] - h[(x2, y1)] - h[(x1, y2)] + h[(x2, y2)] +
                                gx[(x2, y1)] - gx[(x2, y2)] + gy[(y2, x1)] - gy[(y2, x2)] +
                                  (1 if (x2, y2) in point_set else 0))
##                    in_num = 0
##                    for k in range(N):
##                        xk = x_list[k]
##                        yk = y_list[k]
##                        if (xk <= max(x1, x2) and xk >= min(x1, x2) and
##                            yk <= max(y1, y2) and yk >= min(y1, y2)):
##                                in_num += 1
##                        if in_num >= K:
##                            break
                    if in_num >= K:
                        S= abs(x1 - x2) * abs(y1 - y2)
                        if S < min_S:
                            min_S = S
    print min_S
 
 
 
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

def solve(N, K, XYs):
    ans = 10 ** 19 + 1

    XYs.sort(key=lambda x: x[0])
    for i in range(N):
        for j in range(i+K-1, N):
            narrowedXY = XYs[i:j+1]
            narrowedXY.sort(key=lambda x: x[1])
            for y1 in range(len(narrowedXY)):
                for y2 in range(y1+K, len(narrowedXY)+1):
                    min_x = XYs[i][0]
                    max_x = XYs[j][0]
                    ys = [xy[1] for xy in narrowedXY[y1:y2]]
                    max_y = max(ys)
                    min_y = min(ys)
                    ans = min(ans, abs(max_x - min_x) * abs(max_y - min_y))

    return ans

if __name__ == "__main__":
    N, K = tuple(map(int, input().split(" ")))
    XYs = [tuple(map(int, input().split(" "))) for _ in range(N)]
    print(solve(N, K, XYs))

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A
def A():
    return

#B
def B():
    return

#C
def C():
    def bfs(a,b):
        bfs_map = [1 for i in range(n)]
        bfs_map[0] = 0
        q = deque()
        q.append(0)
        s = 1
        while q:
            x = q.pop()
            for y in v[x]:
                if [x,y] != [a,b] and [x,y] != [b,a]:
                    if bfs_map[y]:
                        bfs_map[y] = 0
                        q.append(y)
                        s += 1
        return s
    n,m = LI()
    v = [deque() for i in range(n)]
    l = deque()
    for i in range(m):
        a,b = LI()
        a -= 1
        b -= 1
        v[a].append(b)
        v[b].append(a)
        l.append([a,b])
    ans = 0
    for a,b in l:
        s = bfs(a,b)
        if s < n:
            ans += 1
    print(ans)
#D
def D():
    n,k = LI()
    v = [None for i in range(n)]
    for i in range(n):
        v[i] = LI()
        v[i] = [[None,None]]+[v[i]]
    v.sort(key = lambda x:x[1][1])
    for i in range(n):
        v[i][0][1] = i
    v.sort(key = lambda x:x[1][0])
    for i in range(n):
        v[i][0][0] = i
    po = [[None for i in range(n)] for j in range(n)]
    h = [None for i in range(n)]
    w = [None for i in range(n)]
    for i in range(n):
        po[v[i][0][0]][v[i][0][1]] = v[i][1]
        h[v[i][0][0]] = v[i][1][0]
        w[v[i][0][1]] = v[i][1][1]
    re = [[[[0 for x in range(n)] for y in range(n)] for t in range(n)] for s in range(n)]
    ans = float("inf")
    for s in range(n):
        for t in range(n):
            for y in range(s,n):
                for x in range(t,n):
                    if x == t:
                        re[s][t][y][x] = re[s][t][y-1][x]
                    else:
                        re[s][t][y][x] = max(0,re[s][t][y][x-1]+re[s][t][y-1][x]-re[s][t][y-1][x-1])
                    if po[y][x] != None:
                        re[s][t][y][x] += 1
                    if re[s][t][y][x] >= k:
                        ans = min(ans,(h[y]-h[s])*(w[x]-w[t]))
    print(ans)
#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == "__main__":
    D()

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
XY=[list(map(int,input().split())) for _ in range(n)]
XY.sort()
ans=float('inf')
for i in range(n):
    for j in range(i+1,n):
        x=XY[j][0]-XY[i][0]
        T=sorted(Z[1] for Z in XY[i:j+1])
        for u,v in zip(T,T[k-1:]):
            ans=min(ans,x*(v-u))
print(ans)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
lst = [list(map(int, input().split())) for i in range(n)]

answer = 10**100
sortx = sorted(lst, key = lambda x: x[0])
for a, pt1 in enumerate(sortx[:n-k+1]):
    for b, pt2 in enumerate(sortx[a+k-1:]):
        #print(a,b)
        sorty = sorted(sortx[a:a+k+b], key = lambda x: x[1])
        sorty_len = len(sorty)
        for c, pt3 in enumerate(sorty[:sorty_len-k+1]):
            #print(len(sorty), c, k)
            pt4 = sorty[c+k-1]
            #print(pt1, pt2, pt3, pt4)
            if pt3[1] <= pt1[1] and pt3[1] <= pt2[1] and pt4[1] >= pt1[1] and pt4[1] >= pt2[1]:
                answer = min(answer, (pt2[0] - pt1[0]) * (pt4[1] - pt3[1]))
print(answer)

Submission status: Accepted

Solution code:
#https://atcoder.jp/contests/abc075/submissions/2242350
N,K=map(int,input().split())

points=[tuple(map(int,input().split())) for i in range(N)]
answer=10**19
sortx=sorted(points)
numberx = list(enumerate(sortx))

#n-k+1以降を左の頂点とすると点の数が明らかに足りない
for left,(x1,y1) in numberx[:N-K+1]:
  #left+K-1以降を右の頂点にしないと間に足りる点の数が入ってない
  for right,(x2,y2) in numberx[left+K-1:]:
    dx=x2-x1
    #left-rightの間でyについてsort
    sorty=sorted(y for x,y in sortx[left:right+1])
    #K個点を入れた状態で面積を求める
    for y3,y4 in zip(sorty,sorty[K-1:]):
      if y3<=y1 and y3<=y2 and y4>=y1 and y4>=y2:
        answer=min(answer,dx*(y4-y3))
         
print(answer)

Submission status: Accepted

Solution code:
N,K = map(int, input().split())
xy = []
for _ in range(N):
    xy.append( tuple(map(int, input().split())) )
xs,ys = map(list, zip(*xy))
xs.sort()
ys.sort()
grid = [[0]*(N+1) for _ in range(N+1)] # compressed coordinate
# 座標圧縮
# 圧縮するときに1-indexにしとくと矩形領域の計算が楽になる
for x,y in xy:
    i = xs.index(x)
    j = ys.index(y)
    grid[j+1][i+1] = 1
    
# print(grid)

# 2次元累積和
for h in range(N+1):
    for w in range(1,N+1):
        grid[h][w] += grid[h][w-1]
for w in range(N+1):
    for h in range(1,N+1):
        grid[h][w] += grid[h-1][w]

#print(grid)
ans = float('inf')
for l in range(N):
    for r in range(l+1,N):
        for b in range(N):
            for t in range(b+1,N):
                cnt = grid[t+1][r+1] - grid[b][r+1] - grid[t+1][l] \
                      + grid[b][l]
                xl,xr = xs[l],xs[r]
                yb,yt = ys[b],ys[t]
                if cnt>=K:
                    ans = min(ans, (xr-xl)*(yt-yb))
print(ans)

Submission status: Accepted

Solution code:
def acc2(grid):
    H = len(grid); W = len(grid[0])
    for i in range(H):
        for j in range(W-1):
            grid[i][j+1] += grid[i][j]
    for j in range(W):
        for i in range(H-1):
            grid[i+1][j] += grid[i][j]
    ngrid = [[0]*(W+1)]
    for i in range(H):
        line = [0] + grid[i]
        ngrid.append(line)
    return ngrid

from bisect import bisect_left
N,K = map(int,input().split())
X = []; Y = []; info = []
for i in range(N):
    x,y = map(int,input().split())
    X.append(x); Y.append(y); info.append([x,y])
X.sort(); Y.sort()

acc = [[0]*(N) for i in range(N)]
for x, y in info:
    j = bisect_left(X,x)
    i = bisect_left(Y,y)
    acc[i][j] += 1

acc = acc2(acc)

ans = float('inf')
for t in range(N-1):
    for b in range(t+1,N):
        for l in range(N-1):
            for r in range(l+1,N):
                num = acc[b+1][r+1] - acc[b+1][l] - acc[t][r+1] + acc[t][l]
                if num < K: continue
                S = (Y[b] - Y[t]) * (X[r] - X[l])
                if S < ans:
                    ans = S

print(ans)

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
X = []; Y = []; info = []
for i in range(N):
    x,y = map(int,input().split())
    X.append(x); Y.append(y); info.append([x,y])
X.sort(); Y.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):
                cnt = 0
                for x, y in info:
                    if X[i] <= x <= X[j] and Y[k] <= y <= Y[l]:
                        cnt += 1
                if cnt < K:
                    continue
                S = (Y[l]-Y[k])*(X[j]-X[i])
                if S < ans:
                    ans = S
print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left
N,K = map(int,input().split())
X = []; Y = []; info = []
for i in range(N):
    x,y = map(int,input().split())
    X.append(x); Y.append(y); info.append([x,y])
X.sort(); Y.sort()

acc = [[0]*(N+1) for i in range(N+1)]
for x, y in info:
    j = bisect_left(X,x)
    i = bisect_left(Y,y)
    acc[i+1][j+1] += 1

for i in range(N+1):
    for j in range(1,N):
        acc[i][j+1] += acc[i][j]

for j in range(N+1):
    for i in range(1,N):
        acc[i+1][j] += acc[i][j]

ans = float('inf')
for t in range(N-1):
    for b in range(t+1,N):
        for l in range(N-1):
            for r in range(l+1,N):
                num = acc[b+1][r+1] - acc[b+1][l] - acc[t][r+1] + acc[t][l]
                if num < K: continue
                S = (Y[b] - Y[t]) * (X[r] - X[l])
                if S < ans:
                    ans = S

print(ans)

def debug():
    for line in acc:
        print(line)

Submission status: Accepted

Solution code:
from itertools import product
from operator import itemgetter
N, K = 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.sort()
Y.sort()
XY.sort(key=itemgetter(1))

ans = 10 ** 19
for l, r, t in product(X, X, Y):
    if l > r:
        continue
    cnt = -K
    for x, y in XY:
        if y < t:
            continue
        if l <= x <= r:
            cnt += 1
            if cnt >= 0:
                area = (r - l) * (y - t)
                if area < ans:
                    ans = area
                break

print(ans)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
z=[tuple(map(int,input().split()))for _ in range(n)]
x=[i for i,_ in z]
y=[j for _,j in z]
x.sort()
y.sort()
a=10**20
for i,l in enumerate(x):
    for r in x[i+1:]:
        for v,d in enumerate(y):
            for u in y[v+1:]:
                if sum([1for i,j in z if l<=i<=r and d<=j<=u])>=k:
                    a=min(a,(r-l)*(u-d))
print(a)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
z=[list(map(int,input().split()))for _ in range(n)]
x=[]
y=[]
for i,j in z:
    x.append(i)
    y.append(j)
x.sort()
y.sort()
a=10**20
for i,l in enumerate(x):
    for r in x[i+1:]:
        for v,d in enumerate(y):
            for u in y[v+1:]:
                if sum([1for i,j in z if l<=i<=r and d<=j<=u])>=k:
                    a=min(a,(r-l)*(u-d))
print(a)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
z=[tuple(map(int,input().split()))for _ in range(N)]
x=[i for i,_ in z]
y=[j for _,j in z]
x.sort()
y.sort()
a=10**20
for i in range(N):
    for j in range(i+1,N):
        for k in range(N):
            for l in range(k+1,N):
                l,r,d,u=x[i],x[j],y[k],y[l]
                if sum([1for v,w in z if l<=v<=r and d<=w<=u])>=K:
                    a=min(a,(r-l)*(u-d))
print(a)

Submission status: Accepted

Solution code:
I=lambda:list(map(int,input().split()))
n,k=I()
z=[I()for _ in[0]*n]
z.sort()
a=10**20
for i in range(n):
 for j in range(i+k-1,n):l=sorted(t[1]for t in z[i:j+1]);a=min(a,*[(z[j][0]-z[i][0])*(v-u)for u,v in zip(l,l[k-1:])])
print(a)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
z=[list(map(int,input().split()))for _ in range(n)]
z.sort()
a=10**20
for i in range(n):
    for j in range(i+1,n):
        x=z[j][0]-z[i][0]
        l=sorted(t[1]for t in z[i:j+1])
        for u,v in zip(l,l[k-1:]):
            a=min(a,x*(v-u))
print(a)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
D=[]
X=[]
Y=[]
 
for i in range(N):
    x,y=map(int,input().split())
    D.append([x,y])
    X.append(x)
    Y.append(y)
    
X.sort()
Y.sort()
ans=10**20
for a in range(len(X)):
    for b in range(len(X)-a):
        for c in range(len(Y)):
            for d in range(len(Y)-c):
                cnt=0
                for e in range(N):
                    if X[a]<=D[e][0]<=X[len(X)-1-b] and Y[c]<=D[e][1]<=Y[len(Y)-1-d]:
                        cnt+=1
                if cnt>=K and ans>abs(X[a]-X[len(X)-1-b])*abs(Y[c]-Y[len(Y)-1-d]):
                    ans=abs(X[a]-X[len(X)-1-b])*abs(Y[c]-Y[len(Y)-1-d])
print(ans)

Submission status: Accepted

Solution code:
n,k_num = map(int,input().split())
info =[list(map(int,input().split())) for i in range(n)]
li_x = []
li_y = []

for i in range(n):
 # if info[i][0] not in li_x:
    li_x.append(info[i][0])
 # if info[i][1] not in li_y:
    li_y.append(info[i][1])

li_x = sorted(li_x)
li_y = sorted(li_y)

bunpu = [[0]*n for i in range(n)]
for i in range(n):
  for j in range(n):
    if info[i][0]==li_x[j]:
      zahyo_x=j
      break
  for k in range(n):
    if info[i][1]==li_y[k]:
      zahyo_y=k
      break
  bunpu[zahyo_x][zahyo_y]=1

ruiseki = [[0]*n for i in range(n)]


for i in range(0,n):
  for j in range(0,n):
    ruiseki[i][j] = bunpu[i][j]
#横方向(j)の累積
for i in range(n):
  for j in range(1,n):
    ruiseki[i][j] = ruiseki[i][j-1] + ruiseki[i][j]
#縦方向(i)の累積
for j in range(n):
  for i in range(1,n):
    ruiseki[i][j] = ruiseki[i-1][j] + ruiseki[i][j]

#print(bunpu)
#print(ruiseki)

ans = float("inf")

for i in range(len(li_x)):
  for j in range(i,len(li_x)):
    for k in range(len(li_y)):
      for l in range(k,len(li_y)):
        count = ruiseki[j][l]
        if 0<=k-1:
          count -= ruiseki[j][k-1]
        if 0<=i-1:
          count -= ruiseki[i-1][l]
        if 0<=k-1 and 0<=i-1:
          count += ruiseki[i-1][k-1]      
        if count ==k_num:
          ans = min(ans,(li_x[j]-li_x[i])*(li_y[l]-li_y[k]))
print(ans)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
p = [list(map(int, input().split())) for _ in range(N)]
x = sorted(list(zip(*p))[0])
y = sorted(list(zip(*p))[1])
dic_x = {v: i + 1 for i, v in enumerate(x)}
dic_y = {v: i + 1 for i, v in enumerate(y)}
cum_sum = [[0] * (N + 1) for _ in range(N + 1)]
for i, j in p:
    cum_sum[dic_y[j]][dic_x[i]] = 1

for i in range(1, N + 1):
    for j in range(N):
        cum_sum[i][j + 1] += cum_sum[i][j]

for i in range(1, N + 1):
    for j in range(N):
        cum_sum[j + 1][i] += cum_sum[j][i]

ans = 10 ** 20
for l in range(N):
    for r in range(l + 1, N):
        for d in range(N):
            for u in range(d + 1, N):
                z = cum_sum[u + 1][r + 1] - cum_sum[d][r + 1] \
                     - cum_sum[u + 1][l] + cum_sum[d][l]
                if z >= K:
                    ans = min(ans, (x[r] - x[l]) * (y[u] - y[d]))
print(ans)

Submission status: Accepted

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

x,y = [],[]
xx,yy = [],[]

for i in range(n):
    X,Y = map(int,input().split())

    x.append(X)
    xx.append(X)
    y.append(Y)
    yy.append(Y)



xx.sort()
yy.sort()
ans = 10**20

for i in range(n):
    for j in range(i):
        lx,rx = xx[j],xx[i]

        num = [0 for _ in range(n+1)]

        for k in range(n):
            if lx <= x[k] <= rx:
                num[yy.index(y[k])+1] += 1

        for k in range(n):
            num[k+1] += num[k]


        for k in range(n):
            for l in range(k):
                by,ty = yy[l],yy[k]

                if num[k+1] - num[l] >= K:
                    ans = min(ans,(rx-lx)*(ty-by))



print(ans)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
points = []
xMin = yMin = 10 ** 10
xMax = yMax = -10 ** 10
xKeys = set((-10 ** 10, 10 ** 10))
yKeys = set((-10 ** 10, 10 ** 10))
for _ in range(n):
    x, y = map(int, input().split())
    xMin = min(xMin, x)
    xMax = max(xMax, x)
    yMin = min(yMin, y)
    yMax = max(yMax, y)
    xKeys.add(x)
    yKeys.add(y)
    points.append((x, y))

xKeyToI = {}
xIToKey = {}
for i, key in enumerate(sorted(list(xKeys))):
    xKeyToI[key] = i
    xIToKey[i] = key

yKeyToI = {}
yIToKey = {}
for i, key in enumerate(sorted(list(yKeys))):
    yKeyToI[key] = i
    yIToKey[i] = key

xLen = len(xKeyToI)
yLen = len(yKeyToI)

mp = [[0] * (xLen + 2) for _ in range(yLen + 2)]
for x, y in points:
    ix, iy = xKeyToI[x], yKeyToI[y]
    mp[iy][ix] += 1


for y in range(1, yLen + 1):
    for x in range(xLen + 1):
        mp[y][x + 1] += mp[y][x]
        mp[y][x] += mp[y - 1][x]

ans = 10 ** 20
for py in range(1, yLen):
    for px in range(1, xLen):
        for h in range(yLen - py):
            for w in range(xLen - px):
                score = mp[py + h][px + w] - mp[py - 1][px + w] -\
                        mp[py + h][px - 1] + mp[py - 1][px - 1]
                if score >= k:
                    ans = min(ans, (xIToKey[px + w] - xIToKey[px]) * (yIToKey[py + h] - yIToKey[py])) 

print(ans)

Submission status: Accepted

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

XY.sort(key=itemgetter(0))
x, y = list(zip(*XY))

ans = 10**19
for l in range(N):
    for r in range(l, N):
        n = bisect.bisect_right(x, x[r]) - bisect.bisect_left(x, x[l])
        if n >= K:
            dx = x[r]-x[l]
            tmp = sorted(y[l:r+1])
            for i in range(n-K+1):
                dy = tmp[i+K-1] - tmp[i]
                ans = min(ans, dx*dy)
print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations
N, K = (list)(map(int, input().split()))
pos_x = []
pos_y = []

for _ in range(N):
    a, b = map(int, input().split())
    pos_x.append(a)
    pos_y.append(b)


def count_point(x, y):
    ret = 0
    x_min = min(x)
    x_max = max(x)
    y_min = min(y)
    y_max = max(y)
    for i in range(N):
        if x_min <= pos_x[i] <= x_max and y_min <= pos_y[i] <= y_max:
            ret += 1
    return ret


def calc_area(x, y):
    ret = (x[1]-x[0])*(y[1]-y[0])
    return (abs)(ret)


set_x = set(pos_x)
set_y = set(pos_y)


area = float('inf')
for cand_x in combinations(set_x, 2):
    for cand_y in combinations(set_y, 2):
        if count_point(cand_x, cand_y) == K:
            area = min(area, calc_area(cand_x, cand_y))
print(area)

Submission status: Accepted

Solution code:
inf = 10 ** 20


def func(n, _k, pos):
    x = [pos[i][0] for i in range(len(pos))]
    y = [pos[i][1] for i in range(len(pos))]
    x.sort()
    y.sort()
    imos = [[0 for _ in range(n)] for _ in range(n)]
    for i in range(n):
        for j in range(n):
            for k in range(n):
                if pos[i][0] == x[j] and pos[i][1] == y[k]:
                    imos[j][k] += 1
    for i in range(n):
        for j in range(1, n):
            imos[i][j] += imos[i][j - 1]
    for i in range(1, n):
        for j in range(n):
            imos[i][j] += imos[i - 1][j]
    # for i in reversed(range(len(imos))):
        # print(imos[i])

    def getImos(_right, _left, _upper, _bottom):
        _sum = imos[_right][_upper]
        if _bottom > 0:
            _sum -= imos[_right][_bottom - 1]
        if _left > 0:
            _sum -= imos[_left - 1][_upper]
        if _bottom > 0 and _left > 0:
            _sum += imos[_left - 1][_bottom - 1]
        return _sum

    _min = inf
    for left in range(len(x) - 1):
        for right in range(left + 1, len(x)):
            for bottom in range(len(y) - 1):
                for upper in range(bottom + 1, len(y)):
                    """
                    print("{} {} {} {} :{}poi s:{}".format(right, left, bottom, upper,
                                                        getImos(right, left, upper, bottom),
                                                        (x[right] - x[left]) * (y[upper] - y[bottom])))
                    """
                    if getImos(right, left, upper, bottom) >= _k:
                        _min = min(_min, (x[right] - x[left]) * (y[upper] - y[bottom]))
                        # print("s:{}".format((x[right] - x[left]) * (y[upper] - y[bottom])))
    return _min
    """
    out = inf
    for i in range(n):
        # pos[i]を含む長方形を考える
        box = [[pos[i][0], pos[i][1]] for _ in range(4)]
        used = [False for _ in range(n)]
        used[i] = True
        minS = 0
        for _k in range(k-1):
            minS = inf
            using = -1
            for j in range(n):
                if not used[j]:
                    s = (max(box[1][0], pos[j][0]) - min(box[0][0], pos[j][0])) \
                        * (max(box[1][1], pos[j][1]) - min(box[2][1], pos[j][1]))
                    if s < minS:
                        minS = s
                        using = j
            used[using] = True
            right = max(box[1][0], pos[using][0])
            left = min(box[0][0], pos[using][0])
            upper = max(box[1][1], pos[using][1])
            botom = min(box[2][1], pos[using][1])
            box = [[left, upper], [right, upper], [right, botom], [left, botom]]
            # print("i:{} _k:{} minS:{} box:{}".format(i, _k, minS, box))
        # if minS != math.inf:
            # print(minS)
        out = min(out, minS)
    return out
    """


n, k = [int(i) for i in input().split()]
pos = [[0, 0] for _ in range(n)]
for i in range(n):
    pos[i] = [int(i) for i in input().split()]
print(func(n, k, pos))
"""
print("21 vs " + str(func(4, 4, [[1, 4], [3, 3], [6, 2], [8, 1]])))
print("1 vs " + str(func(4, 2, [[0, 0], [1, 1], [2, 2], [3, 3]])))
print("3999999996000000001 vs " + str(func(4, 3, [[-1000000000, -1000000000], [1000000000, 1000000000],
                                                  [-999999999, 999999999], [999999999, -999999999]])))
"""
# print("print(\"\"+str(func({}, {}, {})))".format(n, k, pos))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

"""
参考：https://img.atcoder.jp/abc075/editorial.pdf
・自力ACしたのがO(N^4)でこれはO(N^5)の愚直解
・制約からして何とかなりそうだし、こっちのが実装全然軽いし実戦向きぽいね。
　→O(N^5)=50^5=3億1250万はpypyでも無理だったわ。
・添字見づらくなったけど定数倍改善。多分半分で約1憶5000万かと。
"""

N, K = map(int, input().split())

X, Y = [0]*N, [0]*N
for i in range(N):
    X[i], Y[i] = map(int, input().split())

X2 = sorted(set(X))
Y2 = sorted(set(Y))

ans = float('inf')
# 可能性のある全長方形ループ
for i in range(len(X2)):
    for j in range(len(Y2)):
        for k in range(i+1, len(X2)):
            for l in range(j+1, len(Y2)):
                cnt = 0
                # 各頂点ループで範囲内にあるか1つずつ確認する
                for m in range(N):
                    if X2[i] <= X[m] <= X2[k] and Y2[j] <= Y[m] <= Y2[l]:
                        cnt += 1
                if cnt >= K:
                    ans = min((X2[k] - X2[i]) * (Y2[l] - Y2[j]), ans)
print(ans)

Submission status: Accepted

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

xy.sort()
ans = float("inf")
for i in range(N):
    for j in range(i + 1, N):
        x = xy[j][0] - xy[i][0]
        y_list = [xy[1] for xy in xy[i:j + 1]]
        y_list.sort()
        for k in range(len(y_list)-K+1):
            y = y_list[k + K -1] - y_list[k]
            tmp = x * y
            if ans > tmp:
                ans = tmp

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

"""
・座標圧縮
・2次元累積和
"""

N, K = map(int, input().split())

X, Y = [0]*N, [0]*N
for i in range(N):
    X[i], Y[i] = map(int, input().split())

# 座標圧縮
zip_x, zip_y, unzip_x, unzip_y = {}, {}, {}, {}
X2 = sorted(set(X))
Y2 = sorted(set(Y))
# この後の処理のために添字は1-indexedにする
for i in range(len(X2)):
    zip_x[X2[i]] = i+1
    unzip_x[i+1] = X2[i]
for i in range(len(Y2)):
    zip_y[Y2[i]] = i+1
    unzip_y[i+1] = Y2[i]

# 圧縮した座標に点を割り当て(グリッドは累積和用に一回り大きく作る)
grid = [[0] * (len(X2)+1) for _ in range(len(Y2)+1)]
for i in range(N):
    grid[zip_y[Y[i]]][zip_x[X[i]]] += 1

# 2次元累積和
for i in range(len(Y2)+1):
    for j in range(1, len(X2)+1):
        grid[i][j] += grid[i][j-1]
for i in range(1, len(Y2)+1):
    for j in range(len(X2)+1):
        grid[i][j] += grid[i-1][j]

ans = float('inf')
for i in range(1, len(Y2)+1):
    for j in range(1, len(X2)+1):
        # 終点がK以上あれば始点を動かし始める
        if grid[i][j] >= K:
            for k in range(i):
                for l in range(j):
                    # 部分累積和を出して、点がK以上あるか確認
                    if grid[i][j] - grid[i][l] - grid[k][j] + grid[k][l] >= K:
                        # 長方形の面積を出して最小を保持
                        ans = min((unzip_x[j]-unzip_x[l+1]) * (unzip_y[i]-unzip_y[k+1]), ans)
print(ans)

Submission status: Accepted

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

import numpy as np
xy = np.zeros((n, 2), dtype=int)

for i in range(n):
	buf = input().split()
	xy[i][0] = int(buf[0])
	xy[i][1] = int(buf[1])

index = np.argsort(xy.T[0])
xysort = xy[index]

area = -1
for i in range(n-k+1):#nankotoruka
	num = k+i
	for j in range(n-(k+i)+1):
		y = np.sort(xysort[j: j+(k+i)].T[1])
		w = xysort[j+k+i-1][0] - xysort[j][0]
		hmin = y[k-1]-y[0]
		for p in range(i+1):
			if(y[p+k-1]-y[p] < hmin):
				hmin = y[p+k-1]-y[p]
		if(area == -1):
			area = w*hmin
		elif(w*hmin < area):
			area = w*hmin
			
print(area)