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: Wrong Answer

Solution code:
# d
N,K = map(int, input().split())
xy = []
for _ in range(N):
    xy.append( tuple(map(int, input().split())) )
xy.sort(key=lambda x:x[0])
ans = float('inf')
for i in range(N-K+1):
    use = xy[i:i+K]
    use_x,use_y = list(zip(*use))
    area = abs(max(use_x)-min(use_x)) * abs(max(use_y)-min(use_y))
    ans = min(ans, area)
    
xy.sort(key=lambda x:x[1])
for i in range(N-K+1):
    use = xy[i:i+K]
    use_x,use_y = list(zip(*use))
    area = abs(max(use_x)-min(use_x)) * abs(max(use_y)-min(use_y))
    ans = min(ans, area)
print(ans)

Submission status: Wrong Answer

Solution code:
# d
N,K = map(int, input().split())
xy = []
for _ in range(N):
    xy.append( tuple(map(int, input().split())) )
xy.sort(key=lambda x:x[0])
ans = float('inf')
for i in range(N-K+1):
    use = xy[i:i+K]
    use_x,use_y = list(zip(*use))
    area = abs(max(use_x)-min(use_x)) * abs(max(use_y)-min(use_y))
    ans = min(ans, area)
print(ans)

Submission status: Wrong Answer

Solution code:
N,K = map(int, input().split())
xs,ys = [],[]
for _ in range(N):
    xi,yi = map(int, input().split())
    xs.append(xi)
    ys.append(yi)
ans = float('inf')
for i in range(N-K+1):
    use_x,use_y = xs[i:i+K],ys[i:i+K]
    area = abs(max(use_x)-min(use_x)) * abs(max(use_y)-min(use_y))
    ans = min(ans, area)
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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:
    i = bisect_left(X,x)
    j = 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: Wrong Answer

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:
    i = bisect_left(X,x)
    j = 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')
S = float('inf')
for b in range(1,N+1):
    for t in range(N-b+1):
        for r in range(1,N+1):
            for l in range(N-r+1):
                num = acc[b][r] - acc[b][l] - acc[t][r] + acc[t][l]
                if num < K: continue
                S = (Y[b-1] - Y[t]) * (X[r-1] - X[l])
                if S < ans:
                    ans = S

print(ans)

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
info = [list(map(int,input().split())) for i in range(N)]
X = sorted(info,key=lambda x:x[0])
Y = sorted(info,key=lambda x:x[1])
S = float('inf')
def get_column(l,c):
    min_ = l[0][c]; max_ = l[0][c]
    for i in range(len(l)):
        if l[i][c] < min_:
            min_ = l[i][c]
        if l[i][c] > max_:
            max_ = l[i][c]
    return (min_,max_)

for i in range(N-K+1):
    x_range = X[i:i+K]
    bottom,top = get_column(x_range,1)
    nS = (x_range[-1][0]-x_range[0][0])*(top-bottom)
    if nS < S:
        S = nS

for i in range(N-K+1):
    y_range = Y[i:i+K]
    bottom,top = get_column(y_range,0)
    nS = (y_range[-1][1]-y_range[0][1])*(top-bottom)
    if nS < S:
        S = nS
print(S)

Submission status: Wrong Answer

Solution code:
#075-D
n,k=map(int,input().split())
g=[]
for i in range(n):
    x,y=map(int,input().split())
    g.append([x,y])
g.sort()
ans=float("INF")
for i in range(n-k+1):
    for j in range(i+k-1,n):
        w=g[j][0]-g[i][0]
        y=[g[k][1] for k in range(i,j+1)]
        y.sort()
        h=y[-1]-y[0]
        ans=min(ans,w*h)
print(ans)

Submission status: Wrong Answer

Solution code:
#075-D
n,k=map(int,input().split())
g=[]
for i in range(n):
    x,y=map(int,input().split())
    g.append([x,y])
g.sort()
ans=float("INF")
for i in range(n-k+1):
    x=[g[k][0] for k in range(i,i+k)]
    y=[g[k][1] for k in range(i,i+k)]
    w=(x[-1]-x[0])*(max(y)-min(y))
    ans=(min(ans,w))
g.sort(key=lambda x:x[1])
for i in range(n-k+1):
    x=[g[k][0] for k in range(i,i+k)]
    y=[g[k][1] for k in range(i,i+k)]
    w=(y[-1]-y[0])*(max(x)-min(x))
    ans=(min(ans,w))
print(ans)

Submission status: Wrong Answer

Solution code:
#075-D
n,k=map(int,input().split())
g=[]
for i in range(n):
    x,y=map(int,input().split())
    g.append([x,y])
g.sort()
ans=float("INF")
for i in range(n-k+1):
    x=[g[k][0] for k in range(i,i+k)]
    y=[g[k][1] for k in range(i,i+k)]
    w=(x[-1]-x[0])*(max(y)-min(y))
    ans=(min(ans,w))
print(ans)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
z=sorted(list(map(int,input().split()))for _ in range(n))
a=10**30
for i,j in zip(range(n),range(k-1,n)):
    m,M=10**18,-10**18
    for(_,b)in z[i:j+1]:
        m=min(m,b)
        M=max(M,b)
    a=min(a,(M-m)*(z[j][0]-z[i][0]))
print(a)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
z=sorted(list(map(int,input().split()))for _ in range(n))
a=10**20
for i,j in zip(range(n),range(k-1,n)):
    m,M=10**18,-10**18
    for(_,b)in z[i:j+1]:
        m=min(m,b)
        M=max(M,b)
    a=min(a,(M-m)*(z[j][0]-z[i][0]))
print(a)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
X = []
Y = []
for _ in range(N):
    x, y = map(int, input().split())
    X.append(x)
    Y.append(y)
Xs = sorted(X)
Ys = sorted(Y)
ans = float('inf')
for left in range(N - 1):
    for right in range(left + 1, N):
        for down in range(N - 1):
            for up in range(down + 1, N):
                count = 0
                for i in range(N):
                    if Xs[left] <= X[i] <= Xs[right] and Ys[down] <= Y[i] <= Ys[up]:
                            count += 1
                if count >= K:
                    ans = min(ans, (X[right] - X[left]) * (Y[up] - Y[down]))
print(abs(ans))

Submission status: Wrong Answer

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(j,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: Wrong Answer

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][0]==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(j,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(1)

Submission status: Wrong Answer

Solution code:
inf = 10**20
def func(n, k, pos):
    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: Wrong Answer

Solution code:
inf = 10**20
def func(n, k, pos):
    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 = inf
        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: Wrong Answer

Solution code:
inf = 10**40
def func(n, k, pos):
    out = inf
    for i in range(n):
        # pos[i]を含む長方形を考える
        box = [pos[i] for _ in range(4)]
        used = [False for _ in range(n)]
        used[i] = True
        minS = inf
        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: Wrong Answer

Solution code:
inf = 10**20
def func(n, k, pos):
    out = inf
    for i in range(n):
        # pos[i]を含む長方形を考える
        box = [pos[i] for _ in range(4)]
        used = [False for _ in range(n)]
        used[i] = True
        minS = inf
        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: Wrong Answer

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

"""
参考：https://img.atcoder.jp/abc075/editorial.pdf
・自力ACしたのがO(N^4)でこれはO(N^5)の愚直解
・制約からして何とかなりそう(まじか？)だし、こっちのが実装全然軽いし実戦向きぽいね。
"""

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 x1 in X2:
    for y1 in Y2:
        for x2 in X2[x1+1:]:
            for y2 in Y2[y1+1:]:
                cnt = 0
                # 各頂点ループで範囲内にあるか1つずつ確認する
                for i in range(N):
                    if x1 <= X[i] <= x2 and y1 <= Y[i] <= y2:
                        cnt += 1
                if cnt >= K:
                    ans = min((x2 - x1) * (y2 - y1), ans)
print(ans)

Submission status: Wrong Answer

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(Y2)+1) for _ in range(len(X2)+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[i]-unzip_x[k+1]) * (unzip_y[j]-unzip_y[l+1]), ans)
print(ans)

Submission status: Wrong Answer

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(Y2)+1) for _ in range(len(X2)+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[i]-unzip_x[k+1]) * (unzip_y[j]-unzip_y[l+1]), ans)
print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    N, K = map(int, raw_input().split())
    Points = []
    for i in range(N):
        x, y = map(int, raw_input().split())
        Points.append([x, y])
    
    ans = float('inf')
    for u in range(N):
        for r in range(u, N):
            for d in range(r, N):
                for l in range(d, N):
                    x1, x2 = min(Points[l][0], Points[r][0]), max(Points[l][0], Points[r][0])
                    y1, y2 = min(Points[d][1], Points[u][1]), max(Points[d][1], Points[u][1])
                    tmp = 0
                    for x, y in Points:
                        if (x1 <= x <= x2) and (y1 <= y <= y2):
                            tmp += 1
                    if tmp >= K:
                        ans = min(ans,  (x2 - x1) * (y2 - y1))
    
    print(ans)

main()

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
xy = [tuple(map(int, input().split())) for i in range(n)]
ans = float("INF")
for x, y in xy:
    for w, _ in xy:
        for _, h in xy:
            count = 0
            for x_, y_ in xy:
                if min(x, w) <= x_ <= max(x, w) and min(y, h) <= y_ <= max(y, h):
                    count += 1
            if count >= k:
                ans = min(ans, abs(w - x) * abs(h - y))
print(ans)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
xy = [tuple(map(int, input().split())) for i in range(n)]
ans = float("INF")
for x, y in xy:
    for w, _ in xy:
        for h, _ in xy:
            count = 0
            for x_, y_ in xy:
                if min(x, w) <= x_ <= max(x, w) and min(y, h) <= y_ <= max(y, h):
                    count += 1
            if count >= k:
                ans = min(ans, abs(w - x) * abs(h - y))
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
N, K = [int(_) for _ in input().split()]
XY = [[int(_) for _ in input().split()] for _ in range(N)]
X, Y = sorted([x for x, y in XY]), sorted([y for x, y in XY])
ans = float('inf')
for x1, x2 in itertools.combinations(X, 2):
    for y1, y2 in itertools.combinations(Y, 2):
        k = sum([x1 <= X[i] <= x2 and y1 <= Y[i] <= y2 for i in range(N)])
        if k >= K:
            ans = min(ans, (x2 - x1) * (y2 - y1))
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
N, K = [int(_) for _ in input().split()]
X = [0] * N
Y = [0] * N
for i in range(N):
    X[i], Y[i] = [int(_) for _ in input().split()]
X.sort()
Y.sort()
ans = float('inf')
for x1, x2 in itertools.combinations(X, 2):
    x1, x2 = x2, x1
    for y1, y2 in itertools.combinations(Y, 2):
        y1, y2 = y2, y1
        k = sum([x1 <= X[i] <= x2 and y1 <= Y[i] <= y2 for i in range(N)])
        if k >= K:
            ans = min(ans, (x2 - x1) * (y2 - y1))
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import math
import sys
import bisect

N, K = [int(x) for x in input().split()]
X = [None] * N
Y = [None] * N
XY = [None] * N
M = [[0] * N for _ in range(N)]
M2 = [[0] * N for _ in range(N)]
M3 = [[0] * N for _ in range(N)]

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

X1 = sorted(list(set(X)))
Y1 = sorted(list(set(Y)))
for i in range(N):
    xIdx = bisect.bisect_left(X1, X[i])
    yIdx = bisect.bisect_left(Y1, Y[i])
    M[xIdx][yIdx] += 1

for i in range(0, N):
    M2[i][0] = M[i][0]
    for j in range(1, N):
        M2[i][j] = M2[i][j - 1] + M[i][j]

M3[0] = M2[0]
for i in range(1, N):
    for j in range(0, N):
        M3[i][j] = M3[i - 1][j] + M2[i][j]

ret = 100000**100000
for i1 in range(N):
    for j1 in range(N):
        for i2 in range(i1,N):
            for j2 in range(j1,N):
                p4cnt = M3[i2][j2]
                p1cnt = 0
                if i1-1>=0 and j1-1>=0:
                    p1cnt = M3[i1-1][j1-1]
                p2cnt = 0
                if i1-1 >= 0:
                    p2cnt = M3[i1-1][j2]
                p3cnt = 0
                if j1-1 >= 0:
                    p3cnt = M3[i2][j1-1]
                cnt = p4cnt - p2cnt - p3cnt + p1cnt

                if cnt >= K:
                    x1 = X1[j1]
                    x2 = X1[j2]
                    y1 = Y1[i1]
                    y2 = Y1[i2]
                    area = abs(x2-x1) * abs(y2-y1)
                    ret = min(ret, area)

print(ret)

Submission status: Wrong Answer

Solution code:
import math
import sys
import bisect

N, K = [int(x) for x in input().split()]
X = [None] * N
Y = [None] * N
XY = [None] * N
M = [[0] * N for _ in range(N)]
M2 = [[0] * N for _ in range(N)]
M3 = [[0] * N for _ in range(N)]

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

X1 = sorted(list(set(X)))
Y1 = sorted(list(set(Y)))
for i in range(N):
    xIdx = bisect.bisect_left(X1, X[i])
    yIdx = bisect.bisect_left(Y1, Y[i])
    M[xIdx][yIdx] += 1

for i in range(0, N):
    M2[i][0] = M[i][0]
    for j in range(1, N):
        M2[i][j] = M2[i][j - 1] + M[i][j]

M3[0] = M2[0]
for i in range(1, N):
    for j in range(0, N):
        M3[i][j] = M3[i - 1][j] + M2[i][j]

ret = 1000**10000
for i1 in range(N):
    for j1 in range(N):
        for i2 in range(i1,N):
            for j2 in range(j1,N):
                p4cnt = M3[i2][j2]
                p1cnt = 0
                if i1-1>=0 and j1-1>=0:
                    p1cnt = M3[i1-1][j1-1]
                p2cnt = 0
                if i1-1 >= 0 and j2 >= 0:
                    p2cnt = M3[i1-1][j2]
                p3cnt = 0
                if i2 >= 0 and j1-1 >= 0:
                    p3cnt = M3[i2][j1-1]
                cnt = p4cnt - p2cnt - p3cnt + p1cnt

                if cnt >= K:
                    x1 = X1[j1]
                    x2 = X1[j2]
                    y1 = Y1[i1]
                    y2 = Y1[i2]
                    area = (x2-x1) * (y2-y1)
                    ret = min(ret, area)

print(ret)

Submission status: Wrong Answer

Solution code:
import math
import sys
import bisect

N, K = [int(x) for x in input().split()]
X = [None] * N
Y = [None] * N
XY = [None] * N
M = [[0] * N for _ in range(N)]
M2 = [[0] * N for _ in range(N)]
M3 = [[0] * N for _ in range(N)]

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

X1 = sorted(list(set(X)))
Y1 = sorted(list(set(Y)))
for i in range(N):
    xIdx = bisect.bisect_left(X1, X[i])
    yIdx = bisect.bisect_left(Y1, Y[i])
    M[xIdx][yIdx] += 1

for i in range(0, N):
    M2[i][0] = M[i][0]
    for j in range(1, N):
        M2[i][j] = M2[i][j - 1] + M[i][j]

M3[0] = M2[0]
for i in range(1, N):
    for j in range(0, N):
        M3[i][j] = M3[i - 1][j] + M2[i][j]

ret = 10**1000
for i1 in range(N):
    for j1 in range(N):
        for i2 in range(i1,N):
            for j2 in range(j1,N):
                p4cnt = M3[i2][j2]
                p1cnt = 0
                if i1-1>=0 and j1-1>=0:
                    p1cnt = M3[i1-1][j1-1]
                p2cnt = 0
                if i1-1 >= 0 and j2 >= 0:
                    p2cnt = M3[i1-1][j2]
                p3cnt = 0
                if i2 >= 0 and j1-1 >= 0:
                    p3cnt = M3[i2][j1-1]
                cnt = p4cnt - p2cnt - p3cnt + p1cnt

                if cnt >= K:
                    x1 = X1[j1]
                    x2 = X1[j2]
                    y1 = Y1[i1]
                    y2 = Y1[i2]
                    area = (x2-x1) * (y2-y1)
                    ret = min(ret, area)

print(ret)

Submission status: Wrong Answer

Solution code:
import math
import sys
import bisect

N, K = [int(x) for x in input().split()]
X = [None] * N
Y = [None] * N
XY = [None] * N
M = [[0] * N for _ in range(N)]
M2 = [[0] * N for _ in range(N)]
M3 = [[0] * N for _ in range(N)]

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

X1 = sorted(X)
Y1 = sorted(Y)
for i in range(N):
    xIdx = bisect.bisect_left(X1, X[i])
    yIdx = bisect.bisect_left(Y1, Y[i])
    M[xIdx][yIdx] += 1

for i in range(0, N):
    M2[i][0] = M[i][0]
    for j in range(1, N):
        M2[i][j] = M2[i][j - 1] + M[i][j]

M3[0] = M2[0]
for i in range(1, N):
    for j in range(0, N):
        M3[i][j] = M3[i - 1][j] + M2[i][j]

ret = 10**1000
for i1 in range(N):
    for j1 in range(N):
        for i2 in range(i1,N):
            for j2 in range(j1,N):
                p4cnt = M3[i2][j2]
                p1cnt = 0
                if i1-1>=0 and j1-1>=0:
                    p1cnt = M3[i1-1][j1-1]
                p2cnt = 0
                if i1-1 >= 0 and j2 >= 0:
                    p2cnt = M3[i1-1][j2]
                p3cnt = 0
                if i2 >= 0 and j1-1 >= 0:
                    p3cnt = M3[i2][j1-1]
                cnt = p4cnt - p2cnt - p3cnt + p1cnt

                if cnt >= K:
                    x1 = X1[j1]
                    x2 = X1[j2]
                    y1 = Y1[i1]
                    y2 = Y1[i2]
                    area = (x2-x1) * (y2-y1)
                    ret = min(ret, area)

print(ret)

Submission status: Wrong Answer

Solution code:
N, K=map(int,input().strip().split(' '))
x=[]
y=[]
for i in range(N):
    xt,yt=map(int,input().strip().split(' '))
    x.append(xt)
    y.append(yt)
ans=10**20
x.sort()
y.sort()
for i in range(N):
    for j in range(i+1,N):
        xmin=x[i]
        xmax=x[j]
        for k in range(N):
            for l in range(k+1,N):
                ymin=y[k]
                ymax=y[l]
                A=(xmax-xmin)*(ymax-ymin)
                ct=0
                for m in range(N):
                    if xmin<=x[m] and x[m]<=xmax and ymin<=y[m] and y[m]<=ymax:
                        ct+=1
                if ct>=K:
                    ans=min(ans,A)
print(ans)