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:
n,k = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n)]
"""
n=5
k=4
ab = [[-1, 4], [6, 0], [-3, 2], [8, -1],[4,5]]
"""
ab_0 = sorted(ab,key=lambda x: x[0])
inf = float("INF")
res = inf
for i in range(n-k+1):
    yy = [l[1] for l in ab_0[i:i+k]]
    maxy = max(yy)
    miny = min(yy)    
    temp = abs((ab_0[i+k-1][0] - ab_0[i][0]) * (maxy-miny))
    res = min(res,temp)
    
ab_1 = sorted(ab,key=lambda x: x[1])

for j in range(n-k+1):
    xx = [m[0] for m in ab_1[j:j+k]]
    maxx = max(xx)
    minx = min(xx)
    temp = abs((maxx- minx) * (ab_1[j+k-1][1] - ab_1[j][1]))
    res = min(res,temp)
print(res)

Submission status: Wrong Answer

Solution code:
n,k = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n)]
"""
n=5
k=4
ab = [[-1, 4], [6, 0], [-3, 2], [8, -1],[4,5]]
"""
ab_0 = sorted(ab,key=lambda x: x[0])
inf = float("inf")
res = inf
for i in range(n-k+1):
    yy = [l[1] for l in ab_0[i:i+k]]
    maxy = max(yy)
    miny = min(yy)    
    temp = abs((ab_0[i+k-1][0] - ab_0[i][0]) * (maxy-miny))
    res = min(res,temp)
    
ab_1 = sorted(ab,key=lambda x: x[1])

for j in range(n-k+1):
    xx = [l[0] for l in ab_1[j:j+k]]
    maxx = max(xx)
    minx = min(xx)
    temp = abs((maxx- minx) * (ab_1[j+k-1][1] - ab_1[j][1]))
    res = min(res,temp)
print(res)

Submission status: Wrong Answer

Solution code:
n,k = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n)]
"""
n=5
k=4
ab = [[-1, 4], [6, 0], [-3, 2], [8, -1],[4,5]]
"""
ab_0 = sorted(ab)
inf = float("inf")
res = inf
for i in range(n-k+1):
    yy = [l[1] for l in ab_0[i:i+k]]
    maxy = max(yy)
    miny = min(yy)    
    temp = abs((ab_0[i+k-1][0] - ab_0[i][0]) * (maxy-miny))
    res = min(res,temp)
    
ab_1 = sorted(ab,key=lambda x: x[1])

for j in range(n-k+1):
    xx = [l[0] for l in ab_1[j:j+k]]
    maxx = max(xx)
    minx = min(xx)
    temp = abs((maxx- minx) * (ab_1[j+k-1][1] - ab_1[j][1]))
    res = min(res,temp)
print(res)

Submission status: Wrong Answer

Solution code:
n,k = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n)]
"""
n=4
k=3
ab = [[-1, 4], [6, 0], [-3, 2], [8, -1]]
"""
ab_0 = sorted(ab)
inf = float("inf")
res = inf
for i in range(n-k+1):
    yy = [l[1] for l in ab_0[i:i+k]]
    maxy = max(yy)
    miny = min(yy)    
    temp = abs(ab_0[i+k-1][0] - ab_0[i][0]) * abs(maxy-miny)
    res = min(res,temp)
    
ab_1 = sorted(ab,key=lambda x: x[1])

for j in range(n-k+1):
    xx = [l[0] for l in ab_1[j:j+k]]
    maxx = max(xx)
    minx = min(xx)
    temp = abs(maxx- minx) * abs(ab_1[j+k-1][1] - ab_1[j][1])
    res = min(res,temp)
print(res)

Submission status: Wrong Answer

Solution code:
n,k = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n)]
"""
n=4
k=3
ab = [[1, 4], [6, 2], [3, 3], [8, 1]]
ab = [[-1, 4], [6, 2], [-3, 3], [8, -1]]
"""
ab_0 = sorted(ab)
inf = float("inf")
res = inf
for i in range(n-k+1):
    yy = [l[1] for l in ab_0[i:i+k]]
    maxy = max(yy)
    miny = min(yy)    
    temp = abs(ab_0[i+k-1][0] - ab_0[i][0]) * abs(maxy-miny)
    res = min(res,temp)
    
ab_1 = sorted(ab,key=lambda x: x[1])

for j in range(n-k+1):
    xx = [l[0] for l in ab_1[i:i+k]]
    maxx = max(xx)
    minx = min(xx)
    temp = abs(maxx- minx) * abs(ab_1[j+k-1][1] - ab_1[j][1])
    res = min(res,temp)

print(res)

Submission status: Wrong Answer

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

ab_0 = sorted(ab)
res = 10**9
for i in range(n-k+1):
    temp = abs(ab_0[i+k-1][0] - ab_0[i][0]) * abs(ab_0[i+k-1][1] - ab_0[i][1])
    res = min(res,temp)
    
ab_1 = sorted(ab,key=lambda x: x[1])

for j in range(n-k+1):
    temp = abs(ab_1[j+k-1][0] - ab_1[j][0]) * abs(ab_1[j+k-1][1] - ab_1[j][1])
    res = min(res,temp)

print(res)

Submission status: Wrong Answer

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

ab_0 = sorted(ab)
res = 10**9
for i in range(n-k+1):
    temp = abs(ab_0[i+k-1][0] - ab_0[i][0]) * abs(ab_0[i+k-1][1] - ab_0[i][1])
    res = min(res,temp)
    
ab_1 = sorted(ab,key=lambda x: x[1])

for j in range(n-k+1):
    temp = abs(ab_1[j+k-1][0] - ab_1[j][0]) * abs(ab_1[j+k-1][1] - ab_1[j][1])
    res = min(res,temp)

print(res)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
xy = [list(map(int, input().split())) for i in range(N)]
xy.sort()
ans = float('inf')
for i in range(N):
  temp = xy[i:i+K].copy()
  if len(temp) < K:
    break
  y = [t[1] for t in temp]
  y.sort()
  ans = min(ans, (temp[-1][0]-temp[0][0])*(y[-1]-y[0]))

xy.sort(key=lambda x:x[1])
for i in range(N):
  temp = xy[i:i+K]
  if len(temp) < K:
    break
  x = [t[0] for t in temp]
  x.sort()
  ans = min(ans, (temp[-1][1]-temp[0][1])*(x[-1]-x[0]))

print(ans)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
xy = [list(map(int, input().split())) for i in range(N)]
xy.sort()
ans = float('inf')
for i in range(N):
  temp = xy[i:i+K].copy()
  if len(temp) < K:
    break
  y = [t[1] for t in temp]
  y.sort()
  ans = min(ans, (temp[-1][0]-temp[0][0])*(y[-1]-y[0]))

print(ans)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
XY = []
for i in range(n):
    x, y = map(int, input().split())
    XY.append((x, y))
XY.sort()

ans = float('inf')
for i in range(n-k+1):
    for j in range(i+k-1, n):
        X = XY[j][0]-XY[i][0]
        ymin = float('inf')
        ymax = -float('inf')
        for l in range(i, j+1):
            x, y = XY[l]
            if y <=  ymin:
                ymin = y
            if y >= ymax:
                ymax = y
        #print(ymin, ymax)
        Y = ymax-ymin
        ans = min(ans, X*Y)
print(ans)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
XY = []
for i in range(n):
    x, y = map(int, input().split())
    XY.append((x, y))
XY.sort()

ans = float('inf')
for i in range(n-k+1):
    X = XY[i+k-1][0]-XY[i][0]
    ymin = float('inf')
    ymax = -float('inf')
    for j in range(i, i+k):
        x, y = XY[j]
        if y <=  ymin:
            ymin = y
        if y >= ymax:
            ymax = y
    Y = ymax-ymin
    ans = min(ans, X*Y)

print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import combinations

N, K = map(int,input().split())
points = []
X = []
Y = []

for _ in range(N):
    x, y = map(int,input().split())
    points.append((x, y))
    X.append(x)
    Y.append(y)

X.sort()
Y.sort()

ans = 10 ** 8

for x1, x2 in combinations(X, 2):
    for y1, y2 in combinations(Y, 2):
        cnt = 0
        for point in points:
            if x1 <= point[0] <= x2 and y1 <= point[1] <= y2:
                cnt += 1
        if cnt >= K:
            ans = min(ans, (x2 - x1) * (y2 - y1))

print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    N, K = list(map(int, input().split(' ')))
    points = [list(map(int, input().split(' '))) for _ in range(N)]
    points.sort(key=lambda p: p[1])
    ans = 10**19
    for n in range(N):
        bottom = points[n][1]
        target_points = points[n:].copy()
        target_points.sort(key=lambda p: p[0])
        for left in range(N - n):
            right = left + K - 1
            if right >= N - n:
                break
            width = target_points[right][0] - target_points[left][0]
            top = max([p[1] for p in target_points[left:(right+1)]])
            ans = min([ans, width * (top - bottom)])
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    N, K = list(map(int, input().split(' ')))
    points = [list(map(int, input().split(' '))) for _ in range(N)]
    points.sort(key=lambda p: p[1])
    ans = 10**19
    for n in range(N):
        bottom = points[n][1]
        target_points = points[n:].copy()
        target_points.sort(key=lambda p: p[0])
        for left in range(N - n):
            right = left + K - 1
            if right >= N - n:
                break
            width = target_points[right][0] - target_points[left][0]
            top = max([p[1] for p in target_points])
            ans = min([ans, width * (top - bottom)])
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n,K=map(int,input().split())
xy=[]
x=[]
y=[]
for _ in range(n):
	X,Y=map(int,input().split())
	x.append(X+10**9)
	y.append(Y+10**9)
	xy.append((X+10**9,Y+10**9))
x.sort();y.sort();xy.sort()
num=[[0]*(n+1)for _ in range(n+1)]
for xx in xy:
	for i in range(n):
		if x[i]==xx[0]:
			break
	for j in range(n):
		if y[j]==xx[1]:
			break
	num[i+1][j+1]+=1
for i in range(n):
	for j in range(n):
		num[i+1][j+1]+=num[i+1][j]
for i in range(n):
	for j in range(n):
		num[i+1][j+1]+=num[i][j+1]
ans=10**20
for i in range(n):
	for j in range(n):
		for k in range(i+1,n+1):
			for l in range(j+1,n+1):
				if num[k][l]-num[i][l]-num[k][j]+num[i][j]>=K:
					r=(x[l-1]-x[j])*(y[k-1]-y[i])
					ans=min(ans,r)
print(ans)

Submission status: Wrong Answer

Solution code:
def solve():
    global ans
    for i in range(n - k + 1):
        ma, mi = f[i][1], f[i][1]
        for j in range(i, i + k):
            ma = max(ma, f[j][1])
            mi = min(mi, f[j][1])
        ans = min(ans, (f[k + i - 1][0] - f[i][0]) * (ma - mi))
    return

n, k = map(int, input().split())
f = [list(map(int, input().split())) for _ in range(n)]
f.sort()
ans = pow(10, 19)
solve()
for i in range(n):
    f[i][0], f[i][1] = f[i][1], f[i][0]
f.sort()
solve()
print(ans)

Submission status: Wrong Answer

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

node.sort()
mia = float("INF")
for i in range(N-K+1):
    y = [i[1] for i in node[i:i+K]]
    a = abs(node[i][0] - node[i+K-1][0])*abs(max(y) - min(y))
    if a < mia:
        mia = a

node.sort(key = lambda x:x[1])
for i in range(N-K+1):
    x = [i[0] for i in node[i:i+K]]
    a = abs(node[i][1] - node[i+K-1][1])*abs(max(x) - min(x))
    if a < mia:
        mia = a

print(mia)

Submission status: Wrong Answer

Solution code:
n,K = map(int,input().split())
xy = [[int(i) for i in input().split()] for j in range(n)]

ans = 10**20

for i in range(n):
    for j in range(i+1,n):
        if K == 2:
            ans = min(ans,abs(xy[i][0]-xy[j][0])*abs(xy[i][1]-xy[j][1]))
        for k in range(j+1,n):
            max_x = 0
            min_x = 0
            max_y = 0
            min_y = 0
            if K == 2:
                break
            max_x = max(xy[i][0],xy[j][0],xy[k][0])
            min_x = min(xy[i][0],xy[j][0],xy[k][0])
            max_y = max(xy[i][1],xy[j][1],xy[k][1])
            min_y = min(xy[i][1],xy[j][1],xy[k][1])
            if K == 3:
                #max_x = max(xy[i][0],xy[j][0],xy[k][0])
                #min_x = min(xy[i][0],xy[j][0],xy[k][0])
                #max_y = max(xy[i][1],xy[j][1],xy[k][1])
                #min_y = min(xy[i][1],xy[j][1],xy[k][1])
                ans = min(ans,abs(max_x-min_x)*abs(max_y-min_y))
            for l in range(k+1,n):
                if K == 2 or K == 3:
                    break
                cnt = 0
                max_x = max(max_x,xy[l][0])
                min_x = min(min_x,xy[l][0])
                max_y = max(max_y,xy[l][1])
                min_y = min(min_y,xy[l][1])
                for m in range(n):
                    if xy[m][0] >= min_x and xy[m][0] <= max_x\
                       and xy[m][1] >= min_y and xy[m][1] <= max_y:
                           cnt += 1
                if cnt >= K:
                    #print(cnt,K)
                    ans = min(ans,(max_x-min_x)*(max_y-min_y))
                
print(ans)

Submission status: Wrong Answer

Solution code:
n,K = map(int,input().split())
xy = [[int(i) for i in input().split()] for j in range(n)]

ans = 10**20

for i in range(n):
    for j in range(i+1,n):
        if K == 2:
            ans = min(ans,abs(xy[i][0]-xy[j][0])*abs(xy[i][1]-xy[j][1]))
        for k in range(j+1,n):
            if K == 2:
                break
            max_x = max(xy[i][0],xy[j][0],xy[k][0])
            min_x = min(xy[i][0],xy[j][0],xy[k][0])
            max_y = max(xy[i][1],xy[j][1],xy[k][1])
            min_y = min(xy[i][1],xy[j][1],xy[k][1])
            if K == 3:
                #max_x = max(xy[i][0],xy[j][0],xy[k][0])
                #min_x = min(xy[i][0],xy[j][0],xy[k][0])
                #max_y = max(xy[i][1],xy[j][1],xy[k][1])
                #min_y = min(xy[i][1],xy[j][1],xy[k][1])
                ans = min(ans,abs(max_x-min_x)*abs(max_y-min_y))
            for l in range(k+1,n):
                if K == 2 or K == 3:
                    break
                cnt = 0
                max_x = max(max_x,xy[l][0])
                min_x = min(min_x,xy[l][0])
                max_y = max(max_y,xy[l][1])
                min_y = min(min_y,xy[l][1])
                for m in range(n):
                    if xy[m][0] >= min_x and xy[m][0] <= max_x\
                       and xy[m][1] >= min_y and xy[m][1] <= max_y:
                           cnt += 1
                if cnt >= K:
                    #print(cnt,K)
                    ans = min(ans,(max_x-min_x)*(max_y-min_y))
                
print(ans)

Submission status: Wrong Answer

Solution code:
n,K = map(int,input().split())
xy = [[int(i) for i in input().split()] for j in range(n)]

ans = 10**20

for i in range(n):
    for j in range(i+1,n):
        if K == 2:
            ans = min(ans,abs(xy[i][0]-xy[j][0])*abs(xy[i][1]-xy[j][1]))
        for k in range(j+1,n):
            max_x = max(xy[i][0],xy[j][0],xy[k][0])
            min_x = min(xy[i][0],xy[j][0],xy[k][0])
            max_y = max(xy[i][1],xy[j][1],xy[k][1])
            min_y = min(xy[i][1],xy[j][1],xy[k][1])
            if K == 3:
                #max_x = max(xy[i][0],xy[j][0],xy[k][0])
                #min_x = min(xy[i][0],xy[j][0],xy[k][0])
                #max_y = max(xy[i][1],xy[j][1],xy[k][1])
                #min_y = min(xy[i][1],xy[j][1],xy[k][1])
                ans = min(ans,abs(max_x-min_x)*abs(max_y-min_y))
            for l in range(k+1,n):
                cnt = 0
                max_x = max(max_x,xy[l][0])
                min_x = min(min_x,xy[l][0])
                max_y = max(max_y,xy[l][1])
                min_y = min(min_y,xy[l][1])
                for m in range(n):
                    if xy[m][0] >= min_x and xy[m][0] <= max_x\
                       and xy[m][1] >= min_y and xy[m][1] <= max_y:
                           cnt += 1
                if cnt >= K:
                    #print(cnt,K)
                    ans = min(ans,(max_x-min_x)*(max_y-min_y))
                
print(ans)

Submission status: Wrong Answer

Solution code:
n,K = map(int,input().split())
xy = [[int(i) for i in input().split()] for j in range(n)]

ans = 10**20

for i in range(n):
    for j in range(i+1,n):
        if K == 2:
            ans = min(ans,abs(xy[i][0]-xy[j][0])*abs(xy[i][1]-xy[j][1]))
        for k in range(j+1,n):
            if K == 3:
                max_x = max(xy[i][0],xy[j][0],xy[k][0])
                min_x = min(xy[i][0],xy[j][0],xy[k][0])
                max_y = max(xy[i][1],xy[j][1],xy[k][1])
                min_y = min(xy[i][1],xy[j][1],xy[k][1])
                ans = min(ans,abs(max_x-min_x)*abs(max_y-min_y))
            for l in range(k+1,n):
                cnt = 0
                max_x = xy[i][0]#max(xy[i][0],xy[j][0],xy[k][0],xy[l][0])
                min_x = xy[i][0]#min(xy[i][0],xy[j][0],xy[k][0],xy[l][0])
                max_y = xy[i][0]#max(xy[i][1],xy[j][1],xy[k][1],xy[l][1])
                min_y = xy[i][0]#min(xy[i][1],xy[j][1],xy[k][1],xy[l][1])
                for m in range(n):
                    if xy[m][0] >= min_x and xy[m][0] <= max_x\
                       and xy[m][1] >= min_y and xy[m][1] <= max_y:
                           cnt += 1
                if cnt >= K:
                    #print(cnt,K)
                    ans = min(ans,(max_x-min_x)*(max_y-min_y))
                
print(ans)

Submission status: Wrong Answer

Solution code:
n,K = map(int,input().split())
xy = [[int(i) for i in input().split()] for j in range(n)]

ans = 10**20

for i in range(n):
    for j in range(i+1,n):
        if K == 2:
            ans = min(ans,abs(xy[i][0]-xy[j][0])*abs(xy[i][1]-xy[j][1]))
        for k in range(j+1,n):
            if K == 3:
                max_x = max(xy[i][0],xy[j][0],xy[k][0])
                min_x = min(xy[i][0],xy[j][0],xy[k][0])
                max_y = max(xy[i][1],xy[j][1],xy[k][1])
                min_y = min(xy[i][1],xy[j][1],xy[k][1])
                ans = min(ans,abs(max_x-min_x)*abs(max_y-min_y))
            for l in range(k+1,n):
                cnt = 0
                max_x = max(xy[i][0],xy[j][0],xy[k][0],xy[l][0])
                min_x = min(xy[i][0],xy[j][0],xy[k][0],xy[l][0])
                max_y = max(xy[i][1],xy[j][1],xy[k][1],xy[l][1])
                min_y = min(xy[i][1],xy[j][1],xy[k][1],xy[l][1])
                for m in range(n):
                    if xy[m][0] >= min_x and xy[m][0] <= max_x\
                       and xy[m][1] >= min_y and xy[m][1] <= max_y:
                           cnt += 1
            if cnt >= K:
                #print(cnt,K)
                ans = min(ans,(max_x-min_x)*(max_y-min_y))
                
print(ans)

Submission status: Wrong Answer

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

XY.sort(key=lambda x: x[0])

ans = float("INF")
for i in range(N):
    for j in range(i+K-1, N):
        W = XY[j][0] - XY[i][0]
        Y = [XY[x][1] for x in range(i, j+1)]
        Y.sort()
        for k in range(len(Y)-K-1):
            H = Y[k+K-1] - Y[k]
            ans = min(ans, W*H)

print(ans)

Submission status: Wrong Answer

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

XY.sort(key=lambda x: x[0])

ans = float("INF")
for i in range(N):
    for j in range(i+K-1, N):
        W = XY[j][0] - XY[i][0]
        Y = [XY[x][1] for x in range(i, j+1)]
        Y.sort()
        for k in range(len(Y)-K-1):
            H = Y[k+K] - Y[k]
            ans = min(ans, W*H)

print(ans)

Submission status: Wrong Answer

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

XY.sort(key=lambda x: x[0])

ans = float("INF")
for i in range(N):
    for j in range(i+K-1, N):
        W = XY[j][0] - XY[i][0]
        Y = [XY[x][1] for x in range(i, j+1)]
        Y.sort()
        for k in range(len(Y)):
            for l in range(i+K-1, len(Y)):
                H = Y[l] - Y[k]
                ans = min(ans, W*H)

print(ans)

Submission status: Wrong Answer

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

XY.sort(key=lambda x: x[0])

ans = float("INF")
for i in range(N):
    for j in range(i+K-1, N):
        W = XY[j][0] - XY[i][0]
        Y = [XY[x][1] for x in range(i, j+1)]
        Y.sort()
        for l, k in zip(Y, Y[K-1:]):
                H = k - l
                ans = min(ans, W*H)
                print(ans)

print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
from itertools import combinations,product
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    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())
    unique_x,unique_y=list(sorted(list(set(x)))),list(sorted(list(set(y))))
    d_x={z:i for i,z in enumerate(unique_x)}
    d_y={z:i for i,z in enumerate(unique_y)}
    xx=[d_x[z] for z in x]
    yy=[d_y[z] for z in y]
    c=[[0]*N for _ in range(N)]
    for i,j in zip(xx,yy):
        c[i][j]+=1
    s=[[0]*(N+1) for _ in range(N+1)]
    for i in range(N):
        for j in range(N):
            s[i+1][j+1]+=s[i][j+1]+s[i+1][j]-s[i][j]+c[i][j]
    xx.sort()
    yy.sort()
    ans=INF*10
    for (x0,x1),(y0,y1) in product(combinations(xx,2),combinations(yy,2)):
        if s[y1+1][x1+1]-s[y1+1][x0]-s[y0][x1+1]+s[y0][x0]>=K:
            ans=min(ans,abs(unique_y[y1]-unique_y[y0])*abs(unique_x[x1]-unique_x[x0]))
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
from itertools import combinations,product
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    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())
    unique_x,unique_y=list(sorted(list(set(x)))),list(sorted(list(set(y))))
    d_x={z:i for i,z in enumerate(unique_x)}
    d_y={z:i for i,z in enumerate(unique_y)}
    xx=[d_x[z] for z in x]
    yy=[d_y[z] for z in y]
    c=[[0]*N for _ in range(N)]
    for i,j in zip(xx,yy):
        c[i][j]+=1
    s=[[0]*(N+1) for _ in range(N+1)]
    for i in range(N):
        for j in range(N):
            s[i+1][j+1]+=s[i][j+1]+s[i+1][j]-s[i][j]+c[i][j]
    xx.sort()
    yy.sort()
    ans=INF*10
    for (x0,x1),(y0,y1) in product(combinations(xx,2),combinations(yy,2)):
        if s[y1+1][x1+1]-s[y1+1][x0]-s[y0][x1+1]+s[y0][x0]>=K:
            ans=min(ans,(unique_y[y1]-unique_y[y0])*(unique_x[x1]-unique_x[x0]))
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
from itertools import combinations,product
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    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())
    unique_x,unique_y=list(sorted(list(set(x)))),list(sorted(list(set(y))))
    d_x={z:i for i,z in enumerate(unique_x)}
    d_y={z:i for i,z in enumerate(unique_y)}
    xx=[d_x[z] for z in x]
    yy=[d_y[z] for z in y]
    c=[[0]*len(unique_x) for _ in range(len(unique_y))]
    for i,j in zip(xx,yy):
        c[i][j]+=1
    s=[[0]*(len(unique_x)+1) for _ in range(len(unique_y)+1)]
    for i in range(len(unique_y)):
        for j in range(len(unique_x)):
            s[i+1][j+1]+=s[i][j+1]+s[i+1][j]-s[i][j]+c[i][j]
    xx.sort()
    yy.sort()
    ans=INF*10
    for (x0,x1),(y0,y1) in product(combinations(xx,2),combinations(yy,2)):
        if s[y1+1][x1+1]-s[y1+1][x0]-s[y0][x1+1]+s[y0][x0]>=K:
            ans=min(ans,(unique_y[y1]-unique_y[y0])*(unique_x[x1]-unique_x[x0]))
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

n, k = map(int, readline().split())
xy = []
xx = []
yy = []
for _ in range(n):
    x, y = map(int, readline().split())
    xx.append(x)
    yy.append(y)
    xy.append((x, y))
xx.sort()
yy.sort()
ans = float('inf')
for i, ix in enumerate(xx):
    for jx in xx[i + 1:]:
        v = jx - ix
        for j, iy in enumerate(yy):
            for jy in yy[j + 1:]:
                cnt = 0
                v *= (jy - iy)
                for x, y in xy:
                    cnt += 1 if ix <= x <= jx and iy <= y <= jy else 0
                    if cnt >= k:
                        if ans > v:
                            ans = v
                        break
print(ans)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
XY = [list(map(int, input().split())) for _ in range(n)]
XY.sort(key=lambda x: x[0])
XY = [xy + [x] for x, xy in enumerate(XY)]
XY.sort(key=lambda x: x[1])
XY = [xy + [y] for y, xy in enumerate(XY)]

gr = [[0] * n for _ in range(n)]
for _, _, i, j in XY:
  gr[i][j] = 1

rui = [[0] * (n + 1) for _ in range(n + 1)]
for i in range(n):
  for j in range(n):
    rui[i + 1][j + 1] = rui[i + 1][j] + rui[i][j + 1] - rui[i][j] + gr[i][j]

# XYの2点,3点,4点を総当たり
ans = 10 ** 21
for i in range(n - 1):
  for j in range(i + 1, n):
    x = [XY[m][0] for m in [i, j]]
    y = [XY[m][1] for m in [i, j]]
    ii = [XY[m][2] + 1 for m in [i, j]]
    jj = [XY[m][3] + 1 for m in [i, j]]
    innerPoints = rui[max(ii)][max(jj)] \
                + rui[min(ii)][min(jj)] \
                - rui[min(ii)][max(jj)] \
                - rui[max(ii)][min(jj)]
    if innerPoints >= k:
      area = (max(x) - min(x)) * (max(y) - min(y)) 
      if area < ans:
        ans = area

if n > 2:
  for i in range(n - 2):
    for j in range(i + 1, n - 1):
      for k in range(j + 1, n):
        x = [XY[m][0] for m in [i, j, k]]
        y = [XY[m][1] for m in [i, j, k]]
        ii = [XY[m][2] + 1 for m in [i, j, k]]
        jj = [XY[m][3] + 1 for m in [i, j, k]]
        innerPoints = rui[max(ii)][max(jj)] \
                    + rui[min(ii)][min(jj)] \
                    - rui[min(ii)][max(jj)] \
                    - rui[max(ii)][min(jj)]
        if innerPoints >= k:
          area = (max(x) - min(x)) * (max(y) - min(y)) 
          if area < ans:
            ans = area

if n > 3:
  for i in range(n - 3):
    for j in range(i + 1, n - 2):
      for k in range(j + 1, n - 1):
        for l in range(k + 1, n):
          x = [XY[m][0] for m in [i, j, k, l]]
          y = [XY[m][1] for m in [i, j, k, l]]
          ii = [XY[m][2] + 1 for m in [i, j, k, l]]
          jj = [XY[m][3] + 1 for m in [i, j, k, l]]
          innerPoints = rui[max(ii)][max(jj)] \
                      + rui[min(ii)][min(jj)] \
                      - rui[min(ii)][max(jj)] \
                      - rui[max(ii)][min(jj)]
          if innerPoints >= k:
            area = (max(x) - min(x)) * (max(y) - min(y)) 
            if area < ans:
              ans = area

print(ans)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
XY = [list(map(int, input().split())) for _ in range(n)]
XY.sort(key=lambda x: x[0])
XY = [xy + [x] for x, xy in enumerate(XY)]
XY.sort(key=lambda x: x[1])
XY = [xy + [y] for y, xy in enumerate(XY)]

gr = [[0] * n for _ in range(n)]
for _, _, i, j in XY:
  gr[i][j] = 1

rui = [[0] * (n + 1) for _ in range(n + 1)]
for i in range(n):
  for j in range(n):
    rui[i + 1][j + 1] = rui[i + 1][j] + rui[i][j + 1] - rui[i][j] + gr[i][j]

# XYの2点,3点,4点を総当たり
ans = 10 ** 19
for i in range(n - 1):
  for j in range(i + 1, n):
    x = [XY[i][0] for i in range(2)]
    y = [XY[i][1] for i in range(2)]
    ii = [XY[i][2] for i in range(2)]
    jj = [XY[i][3] for i in range(2)]
    innerPoints = rui[max(ii)+1][max(jj)+1] \
                + rui[min(ii)][min(jj)] \
                - rui[min(ii)][max(jj)] \
                - rui[max(ii)][min(jj)]
    if innerPoints >= k:
      area = (max(x) - min(x)) * (max(y) - min(y)) 
      if area < ans:
        ans = area

if n > 2:
  for i in range(n - 2):
    for j in range(i + 1, n - 1):
      for k in range(j + 1, n):
        x = [XY[i][0] for i in range(3)]
        y = [XY[i][1] for i in range(3)]
        ii = [XY[i][2] for i in range(3)]
        jj = [XY[i][3] for i in range(3)]
        innerPoints = rui[max(ii)+1][max(jj)+1] \
                    + rui[min(ii)][min(jj)] \
                    - rui[min(ii)][max(jj)] \
                    - rui[max(ii)][min(jj)]
        if innerPoints >= k:
          area = (max(x) - min(x)) * (max(y) - min(y)) 
          if area < ans:
            ans = area

if n > 3:
  for i in range(n - 3):
    for j in range(i + 1, n - 2):
      for k in range(j + 1, n - 1):
        for l in range(k + 1, n):
          x = [XY[i][0] for i in range(4)]
          y = [XY[i][1] for i in range(4)]
          ii = [XY[i][2] for i in range(4)]
          jj = [XY[i][3] for i in range(4)]
          innerPoints = rui[max(ii)+1][max(jj)+1] \
                      + rui[min(ii)][min(jj)] \
                      - rui[min(ii)][max(jj)] \
                      - rui[max(ii)][min(jj)]
          if innerPoints >= k:
            area = (max(x) - min(x)) * (max(y) - min(y)) 
            if area < ans:
              ans = area

print(ans)