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:
import itertools

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

def get_dis_squ(point1, point2):
    return (point1[0] - point2[0])**2 + (point1[1] - point2[1])**2

min_area = 0
for point_t in points:
    distances = []
    for point in points:
        # same point is ignored
        if point_t == point:
            continue
        # cal distance:
        dis_squ = get_dis_squ(point_t, point)
        distances.append([point, dis_squ])
    # get near_points
    distances.sort(key=lambda x: x[1])
    in_squares = [point_dis[0] for point_dis in distances[:k-1]]
    in_squares.append(point_t)
    # cal area
    max_x = max(in_squares, key=lambda x: x[0])[0]
    min_x = min(in_squares, key=lambda x: x[0])[0]
    max_y = max(in_squares, key=lambda x: x[1])[1]
    min_y = min(in_squares, key=lambda x: x[1])[1]
    area = abs(max_x-min_x)*abs(max_y-min_y)
    if not min_area:
        min_area = area
    else:
        if area < min_area:
            min_area = area
print(min_area)

Submission status: Wrong Answer

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-1):
  x1,y1=xy[i]
  for j in range(i+1,n):
    x2,y2=xy[j]
    cnt=0
    for l in range(n):
      x3,y3=xy[l]
      if x1<=x3<=x2 and min(y1,y2)<=y3<=max(y1,y2):
        cnt+=1
    if cnt>=k:
      ans=min(ans,(x2-x1)*abs(y2-y1))
for i in range(n-2):
  x1,y1=xy[i]
  for j in range(i+1,n-1):
    x2,y2=xy[j]
    for l in range(j+1,n):
      x3,y3=xy[l]
      cnt=0
      for m in range(n):
        x4,y4=xy[m]
        ymax=max(y1,y2,y3)
        ymin=min(y1,y2,y3)
        if x1<=x4<=x3 and ymin<=y4<=ymax:
          cnt+=1
      if cnt>=k:
        ans=min(ans,(x3-x1)*(ymax-ymin))
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools

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

min_area = 0
for cs in itertools.permutations(points, r=2):
    in_square_count = 0
    cs_x = [c[0] for c in cs]
    cs_y = [c[1] for c in cs]
    # count points in square
    for point in points:
        if ((min(cs_x) <= point[0] <= max(cs_x)) 
            and (min(cs_y) <= point[1] <= max(cs_y))):
            in_square_count += 1
    # cal area
    if in_square_count >= k:
        area = abs(min(cs_x) - max(cs_x)) * abs(min(cs_y) - max(cs_y))
        if not min_area or area < min_area:
            min_area = area
print(min_area)

Submission status: Wrong Answer

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

x = [e for e, _ in xy]
y = [e for _, e in xy]

x.sort()
y.sort()

acc = [[0] * (N + 1) for _ in range(N + 1)]
for i, ex in enumerate(x, 1):
	for j, ey in enumerate(y, 1):
		cnt = 0
		for xx, yy in xy:
			if xx <= ex and yy <= ey:
				cnt += 1

		acc[i][j] = cnt

#print(*acc, sep="\n")

ans = float("inf")
for i in range(1, N + 1):
	for j in range(i + 1, N + 1):
		for k in range(1, N + 1):
			for l in range(k + 1, N + 1):
				cnt = acc[j][l] - acc[j][k-1] - acc[i-1][l] + acc[i-1][l-1]
				if cnt >= K:
					sq = (x[j-1] - x[i-1]) * (y[l-1] - y[k-1])
					ans = min(ans, sq)

print(ans)

Submission status: Wrong Answer

Solution code:
n, kosuu = 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 = sorted(X, reverse=True)
Y = sorted(Y, reverse=True)

s_min = 10**20
for i in range(n):
    for j in range(n):
        for k in range(n):
            for l in range(n):
                count = 0
                x_max = X[i]
                x_min = X[-1*(j+1)]
                if x_max <= x_min:
                    continue
                y_max = Y[k]
                y_min = Y[-1*(l+1)]
                if y_max <= y_min:
                    continue

                s = abs(x_max-x_min)*abs(y_max-y_min)
                count = 0

                for m in range(n):
                    x = XY[m][0]
                    y = XY[m][1]
                    if (x <= x_max and x >= x_min) and (y <= y_max and y >= y_min):
                        count += 1
                if count >= kosuu:
                    s_min = min(s, s)

print(s_min)

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def MI(N,num):
    if N<=0:
        return [[] for _ in range(num)]
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [LI() for _ in range(N)]
        return map(list, zip(*read_all))

#################

from bisect import bisect_left
from itertools import product,combinations

from operator import itemgetter
def index_sort(A):
    A_sort = sorted(enumerate(A),key=itemgetter(1))
    index = [a[0] for a in A_sort]
    sorted_A = [a[1] for a in A_sort]
    return index, sorted_A

N,K = LI()
x,y = MI(N,2)

index,_ = index_sort(x)
x2 = [x[i] for i in index]
y2 = [y[i] for i in index]

A = list(product(combinations(range(N),2),repeat=2))
ans = float('inf')
for a in A:
    xmin = min(x[a[0][0]],x[a[0][1]])
    xmax = max(x[a[0][0]],x[a[0][1]])
    ymin = min(y[a[1][0]],y[a[1][1]])
    ymax = max(y[a[1][0]],y[a[1][1]])
    S = (xmax-xmin)*(ymax-ymin)
    if S >= ans:
        continue
    l = bisect_left(x2,xmin)
    r = bisect_left(x2,xmax)
    num = 0
    for i in range(l,r+1):
        if ymin <= y[i] <= ymax:
            num += 1
    if num >= K:
        ans = S

print(ans)

Submission status: Wrong Answer

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

ans = float("inf")
for i in range(n):
    for j in range(i+1, n):
        for h in range(j+1, n):
            for g in range(h+1, n):
                x1 = min(xyl[i][0], xyl[j][0], xyl[h][0], xyl[g][0])
                x2 = max(xyl[i][0], xyl[j][0], xyl[h][0], xyl[g][0])
                y1 = min(xyl[i][1], xyl[j][1], xyl[h][1], xyl[g][0])
                y2 = max(xyl[i][1], xyl[j][1], xyl[h][1], xyl[g][0])
                cnt = 0
                for p in range(n):
                    if x1 <= xyl[p][0] <= x2 and  y1 <= xyl[p][1] <= y2:
                        cnt += 1
                if k <= cnt:
                    ans = min(ans, (x2-x1)*(y2-y1))

for i in range(n):
    for j in range(i+1, n):
        for h in range(j+1, n):
            x1 = min(xyl[i][0], xyl[j][0], xyl[h][0])
            x2 = max(xyl[i][0], xyl[j][0], xyl[h][0])
            y1 = min(xyl[i][1], xyl[j][1], xyl[h][1])
            y2 = max(xyl[i][1], xyl[j][1], xyl[h][1])
            cnt = 0
            for p in range(n):
                if x1 <= xyl[p][0] <= x2 and  y1 <= xyl[p][1] <= y2:
                    cnt += 1
            if k <= cnt:
                ans = min(ans, (x2-x1)*(y2-y1))

for i in range(n):
    for j in range(i+1, n):
        x1 = min(xyl[i][0], xyl[j][0])
        x2 = max(xyl[i][0], xyl[j][0])
        y1 = min(xyl[i][1], xyl[j][1])
        y2 = max(xyl[i][1], xyl[j][1])
        cnt = 0
        for p in range(n):
            if x1 <= xyl[p][0] <= x2 and  y1 <= xyl[p][1] <= y2:
                cnt += 1
        if k <= cnt:
            ans = min(ans, (x2-x1)*(y2-y1))



print(ans)

Submission status: Wrong Answer

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

ans = float("inf")
for i in range(n):
    for j in range(i+1, n):
        for h in range(j+1, n):
            x1 = min(xyl[i][0], xyl[j][0], xyl[h][0])
            x2 = max(xyl[i][0], xyl[j][0], xyl[h][0])
            y1 = min(xyl[i][1], xyl[j][1], xyl[h][1])
            y2 = max(xyl[i][1], xyl[j][1], xyl[h][1])
            cnt = 0
            for p in range(n):
                if x1 <= xyl[p][0] <= x2 and  y1 <= xyl[p][1] <= y2:
                    cnt += 1
            if k <= cnt:
                ans = min(ans, (x2-x1)*(y2-y1))

for i in range(n):
    for j in range(i+1, n):
        x1 = min(xyl[i][0], xyl[j][0])
        x2 = max(xyl[i][0], xyl[j][0])
        y1 = min(xyl[i][1], xyl[j][1])
        y2 = max(xyl[i][1], xyl[j][1])
        cnt = 0
        for p in range(n):
            if x1 <= xyl[p][0] <= x2 and  y1 <= xyl[p][1] <= y2:
                cnt += 1
        if k <= cnt:
            ans = min(ans, (x2-x1)*(y2-y1))

print(ans)

Submission status: Wrong Answer

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

ans = float("inf")
for i in range(n):
    for j in range(i+1, n):
        for h in range(j+1, n):
            x1 = min(xyl[i][0], xyl[j][0], xyl[h][0])
            x2 = max(xyl[i][0], xyl[j][0], xyl[h][0])
            y1 = min(xyl[i][1], xyl[j][1], xyl[h][1])
            y2 = max(xyl[i][1], xyl[j][1], xyl[h][1])
            cnt = 0
            for p in range(n):
                if x1 <= xyl[p][0] <= x2 and  y1 <= xyl[p][1] <= y2:
                    cnt += 1
            if k <= cnt:
                ans = min(ans, (x2-x1)*(y2-y1))

print(ans)

Submission status: Wrong Answer

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

ans = float("inf")
for i in range(n):
    for j in range(i+1, n):
        x1 = min(xyl[i][0], xyl[j][0])
        x2 = max(xyl[i][0], xyl[j][0])
        y1 = min(xyl[i][1], xyl[j][1])
        y2 = max(xyl[i][1], xyl[j][1])
        cnt = 0
        for p in range(n):
            if x1 <= xyl[p][0] <= x2 and  y1 <= xyl[p][1] <= y2:
                cnt += 1
        if k == cnt:
            ans = min(ans, (x2-x1)*(y2-y1))

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import itertools

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, K = lr()
XY = [lr() for _ in range(N)]
XY.sort()
answer = float('inf')
# 端の4点、まずはx軸の2点を選ぶ
for i, j in itertools.combinations(range(N), 2):
    xleft = XY[i][0]
    xright = XY[j][0]
    candidate = sorted(XY[i:j+1], key=lambda xy: xy[1])
    if len(candidate) < K:
        continue
    for s in range(len(candidate) - K + 1):
        yup = candidate[s+K-1][1]
        ylow = candidate[s][1]
    area = (xright - xleft) * (yup - ylow)
    if area < answer:
        answer = area

print(answer)
# 31

Submission status: Wrong Answer

Solution code:
import sys
import itertools

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, K = lr()
XY = [lr() for _ in range(N)]
XY.sort()
answer = float('inf')
# 端の4点、まずはx軸の2点を選ぶ
for i, j in itertools.combinations(range(N), 2):
    xleft = XY[i][0]
    xright = XY[j][0]
    if xright < xleft: xleft, xright = xright, xleft
    candidate = sorted(XY[i:j+1], key=lambda xy: xy[1])
    if len(candidate) < K:
        continue
    for s in range(len(candidate) - K + 1):
        yup = candidate[s+K-1][1]
        ylow = candidate[s][1]
    area = (xright - xleft) * (yup - ylow)
    if area < answer:
        answer = area

print(answer)
# 31

Submission status: Wrong Answer

Solution code:
import sys
import itertools

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, K = lr()
XY = [lr() for _ in range(N)]
answer = float('inf')
# 端の4点、まずはx軸の2点を選ぶ
for i, j in itertools.permutations(list(range(N)), 2):
    xleft = XY[i][0]
    xright = XY[j][0]
    if xright < xleft: xleft, xright = xright, xleft
    candidate = [(x, y) for x, y in XY if xleft <= x <= xright]
    if len(candidate) < K:
        continue
    candidate.sort(key=lambda z: z[1])
    for s in range(len(candidate) - K + 1):
        yup = candidate[s+K-1][1]
        ylow = candidate[s][1]
    area = (xright - xleft) * (yup - ylow)
    if area < answer:
        answer = area

print(answer)
# 31

Submission status: Wrong Answer

Solution code:
import sys
import itertools

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, K = lr()
XY = [lr() for _ in range(N)]
answer = float('inf')
# 端の4点、まずはx軸の2点を選ぶ
for i, j in itertools.product(list(range(N)), repeat=2):
    xleft = XY[i][0]
    xright = XY[j][0]
    if xright < xleft: xleft, xright = xright, xleft
    candidate = [(x, y) for x, y in XY if xleft <= x <= xright]
    if len(candidate) < K:
        continue
    candidate.sort(key=lambda z: z[1])
    for s in range(len(candidate) - K + 1):
        yup = candidate[s+K-1][1]
        ylow = candidate[s][1]
    area = (xright - xleft) * (yup - ylow)
    if area < answer:
        answer = area

print(answer)
# 31

Submission status: Wrong Answer

Solution code:
import sys
import itertools

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, K = lr()
XY = [lr() for _ in range(N)]
answer = float('inf')
# 端の4点、まずはx軸の2点を選ぶ
for i, j in itertools.product(list(range(N)), repeat=2):
    xleft = XY[i][0]
    xright = XY[j][0]
    candidate = [(x, y) for x, y in XY if xleft <= x <= xright]
    if len(candidate) < K:
        continue
    candidate.sort(key=lambda z: z[1])
    for s in range(len(candidate) - K + 1):
        yup = candidate[s+K-1][1]
        ylow = candidate[s][1]
    area = (xright - xleft) * (yup - ylow)
    if area < answer:
        answer = area

print(answer)
# 31

Submission status: Wrong Answer

Solution code:
n, k = [int(i) for i in input().split()]
x = []
y = []
for _ in range(n):
    a, b = [int(i) for i in input().split()]
    x.append(a)
    y.append(b)

ans = 10**20
for i1 in x:
    for i2 in y:
        for i3 in y:
            for i4 in y:
                l=0
                for j in range(n):
                    if i1 <= x[j] <= i2 and i3 <= y[j] <= i4:
                        l += 1
                if l == k:
                    ans = min(ans, abs((i1 - i2) * (i3 - i4)))
print(ans)

Submission status: Wrong Answer

Solution code:
import math
N, K = map(int, input().split())
xy = []
for _ in range(N):
    x, y = map(int, input().split())
    xy.append((x, y))
answer = float('inf')

for i in range(N):
    for j in range(i+1, N):
        count = 0
        x_small = min(xy[i][0], xy[j][0])
        x_large = max(xy[i][0], xy[j][0])
        y_small = min(xy[i][1], xy[j][1])
        y_large = max(xy[i][1], xy[j][1])
        S = (x_large - x_small) * (y_large - y_small)
        # print(xy[i], xy[j])
        # print(x_small,x_large,y_small,y_large)
        for k in range(N):
            if (x_small <= xy[k][0] and xy[k][0] <= x_large) and (y_small <= xy[k][1] and xy[k][1] <= y_large):
                count += 1
            # print('i={0}, j={1}, count={2}, S={3}'.format(i, j, count, S))
        if K <= count and answer >= S:
            answer = S

print(answer)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
x,y=[[0,0] for i in range(n)],[[0,0] for i in range(n)]
xy=[list(map(int,input().split())) for i in range(n)]
for i in range(n):
    x_sub,y_sub=xy[i]
    x[i][0]=x_sub
    x[i][1]=i
    y[i][0]=y_sub
    y[i][1]=i
x.sort()
y.sort()
ans=(10**18)*5
for i1 in range(n):
    i1_sub=n-i1
    for l1 in range(i1_sub,1,-1):
        for i2 in range(n):
            i2_sub=n-i2
            for l2 in range(i2_sub,1,-1):
                x_sub1=x[i1][0]
                x_sub2=x[i1+l1-1][0]
                y_sub1=y[i2][0]
                y_sub2=y[i2+l2-1][0]
                z=[0]*n
                for i in range(n):
                    if x_sub1<=xy[i][0]<=x_sub2 and y_sub1<=xy[i][1]<=y_sub2:
                        z[i]=1
                s=0
                for i in range(n):
                    s+=z[i]
                    if z[i]>=k:
                        ans=min((x_sub2-x_sub1)*(y_sub2-y_sub1),ans)
                        break
                else:
                    break
print(ans)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
x,y=[[0,0] for i in range(n)],[[0,0] for i in range(n)]
xy=[list(map(int,input().split())) for i in range(n)]
for i in range(n):
    x_sub,y_sub=xy[i]
    x[i][0]=x_sub
    x[i][1]=i
    y[i][0]=y_sub
    y[i][1]=i
x.sort()
y.sort()
w=[(i1,l1) for i1 in range(n) for l1 in range(n-i1,1,-1)]
v=[(i2,l2) for i2 in range(n) for l2 in range(n-i2,1,-1)]
#print(w)
#print(v)
ans=(10**18)*5
for w_sub in w:
    for v_sub in v:
        i1,l1=w_sub
        i2,l2=v_sub
        x_sub1=x[i1][0]
        x_sub2=x[i1+l1-1][0]
        y_sub1=y[i2][0]
        y_sub2=y[i2+l2-1][0]
        z=[0]*n
        for i in range(n):
            if x_sub1<=xy[i][0]<=x_sub2 and y_sub1<=xy[i][1]<=y_sub2:
                z[i]=1
        if sum(z)>=k:
            ans=min((x_sub2-x_sub1)*(y_sub2-y_sub1),ans)
        else:
            break
print(ans)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
x,y=[[0,0] for i in range(n)],[[0,0] for i in range(n)]
xy=[list(map(int,input().split())) for i in range(n)]
for i in range(n):
    x_sub,y_sub=xy[i]
    x[i][0]=x_sub
    x[i][1]=i
    y[i][0]=y_sub
    y[i][1]=i
x.sort()
y.sort()
ans=(10**18)*5
w=[[i1,l1] for i1 in range(n) for l1 in range(n-i1,1,-1)]
v=[[i2,l2] for i2 in range(n) for l2 in range(n-i2,1,-1)]
for w_sub in w:
    for v_sub in v:
        i1,l1=w_sub
        i2,l2=v_sub
        x_sub1=x[i1][0]
        x_sub2=x[i1+l1-1][0]
        y_sub1=y[i2][0]
        y_sub2=y[i2+l2-1][0]
        z=[0]*n
        for i in range(n):
            if x_sub1<=xy[i][0]<=x_sub2 and y_sub1<=xy[i][1]<=y_sub2:
                z[i]=1
        if sum(z)>=k:
            ans=min((x_sub2-x_sub1)*(y_sub2-y_sub1),ans)
        else:
            break
print(ans)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
x,y=[[0,0] for i in range(n)],[[0,0] for i in range(n)]
xy=[list(map(int,input().split())) for i in range(n)]
for i in range(n):
    x_sub,y_sub=xy[i]
    x[i][0]=x_sub
    x[i][1]=i
    y[i][0]=y_sub
    y[i][1]=i
x.sort(key=lambda z:z[0])
y.sort(key=lambda z:z[0])
ans=[]
for i1 in range(n):
    for l1 in range(n-i1,1,-1):
        for i2 in range(n):
            for l2 in range(n-i2,1,-1):
                if l1*l2<k:
                    break
                z=[0]*n
                for i in range(i1,i1+l1):
                    l=x[i][1]
                    z[l]=1
                for i in range(i2,i2+l2):
                    l=y[i][1]
                    z[l]=1
                if sum(z)>=k:
                    x_sub1,y_sub1=10**9+1,10**9+1
                    x_sub2,y_sub2=-10**9-1,-10**9-1
                    for i in range(n):
                        if z[i]==1:
                            x_sub1=min(xy[i][0],x_sub1)
                            x_sub2=max(xy[i][0],x_sub2)
                            y_sub1=min(xy[i][1],y_sub1)
                            y_sub2=max(xy[i][1],y_sub2)
                    ans.append((x_sub2-x_sub1)*(y_sub2-y_sub1))
                else:
                    break
print(min(ans))

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
x,y=[[0,0] for i in range(n)],[[0,0] for i in range(n)]
xy=[list(map(int,input().split())) for i in range(n)]
for i in range(n):
    x_sub,y_sub=xy[i]
    x[i][0]=x_sub
    x[i][1]=i
    y[i][0]=y_sub
    y[i][1]=i
x.sort(key=lambda z:z[0])
y.sort(key=lambda z:z[0])
ans=[]
for i1 in range(n):
    for l1 in range(n-i1,1,-1):
        for i2 in range(n):
            for l2 in range(n-i2,1,-1):
                if l1*l2<k:
                    break
                z=[0]*n
                for i in range(i1,i1+l1):
                    l=x[i][1]
                    z[l]=1
                for i in range(i2,i2+l2):
                    l=y[i][1]
                    z[l]=1
                if sum(z)>=k:
                    x_sub1,y_sub1=10**9+1,10**9+1
                    x_sub2,y_sub2=-10**9-1,-10**9-1
                    for i in range(n):
                        if z[i]==1:
                            x_sub1=min(xy[i][0],x_sub1)
                            x_sub2=max(xy[i][0],x_sub2)
                            y_sub1=min(xy[i][1],y_sub1)
                            y_sub2=max(xy[i][1],y_sub2)
                    ans.append((x_sub2-x_sub1)*(y_sub2-y_sub1))
                else:
                    break
print(max(ans))

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
x,y=[[0,0] for i in range(n)],[[0,0] for i in range(n)]
xy=[list(map(int,input().split())) for i in range(n)]
for i in range(n):
    x_sub,y_sub=xy[i]
    x[i][0]=x_sub
    x[i][1]=i
    y[i][0]=y_sub
    y[i][1]=i
x.sort(key=lambda z:z[0])
y.sort(key=lambda z:z[0])
ans=(10**18)*5
for i1 in range(n):
    for l1 in range(n-i1,1,-1):
        for i2 in range(n):
            for l2 in range(n-i2,1,-1):
                if l1*l2<k:
                    break
                z=[0]*n
                for i in range(i1,i1+l1):
                    l=x[i][1]
                    z[l]=1
                for i in range(i2,i2+l2):
                    l=y[i][1]
                    z[l]=1
                if sum(z)>=k:
                    x_sub1,y_sub1=10**9+1,10**9+1
                    x_sub2,y_sub2=-10**9-1,-10**9-1
                    for i in range(n):
                        if z[i]==1:
                            x_sub1=min(xy[i][0],x_sub1)
                            x_sub2=max(xy[i][0],x_sub2)
                            y_sub1=min(xy[i][1],y_sub1)
                            y_sub2=max(xy[i][1],y_sub2)
                    ans=min((x_sub2-x_sub1)*(y_sub2-y_sub1),ans)
                else:
                    break
print(ans)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
x,y=[[0,0] for i in range(n)],[[0,0] for i in range(n)]
xy=[list(map(int,input().split())) for i in range(n)]
for i in range(n):
    x_sub,y_sub=xy[i]
    x[i][0]=x_sub
    x[i][1]=i
    y[i][0]=y_sub
    y[i][1]=i
x.sort(key=lambda z:z[0])
y.sort(key=lambda z:z[0])
ans=(10**18)*5
for i1 in range(n):
    for l1 in range(n-i1,0,-1):
        for i2 in range(n):
            for l2 in range(n-i2,0,-1):
                z=[0]*n
                for i in range(i1,i1+l1):
                    l=x[i][1]
                    z[l]=1
                for i in range(i2,i2+l2):
                    l=y[i][1]
                    z[l]=1
                if sum(z)>=k:
                    x_sub1,y_sub1=10**9+1,10**9+1
                    x_sub2,y_sub2=-10**9-1,-10**9-1
                    for i in range(n):
                        if z[i]==1:
                            x_sub1=min(xy[i][0],x_sub1)
                            x_sub2=max(xy[i][0],x_sub2)
                            y_sub1=min(xy[i][1],y_sub1)
                            y_sub2=max(xy[i][1],y_sub2)
                    ans=min((x_sub2-x_sub1)*(y_sub2-y_sub1),ans)
print(ans)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
x,y=[[0,0] for i in range(n)],[[0,0] for i in range(n)]
xy=[list(map(int,input().split())) for i in range(n)]
for i in range(n):
    x_sub,y_sub=xy[i]
    x[i][0]=x_sub
    x[i][1]=i
    y[i][0]=y_sub
    y[i][1]=i
x.sort(key=lambda z:z[0])
y.sort(key=lambda z:z[0])
ans=(10**18)*5
for i1 in range(n):
    for l1 in range(n-i1,0,-1):
        for i2 in range(n):
            for l2 in range(n-i2,0,-1):
                z=[0]*n
                for i in range(i1,i1+l1):
                    l=x[i][1]
                    z[l]=1
                for i in range(i2,i2+l2):
                    l=y[i][1]
                    z[l]=1
                if sum(z)>=k:
                    x_sub1,y_sub1=10**9+1,10**9+1
                    x_sub2,y_sub2=-10**9-1,-10**9-1
                    for i in range(n):
                        if z[i]==1:
                            x_sub1=min(xy[i][0],x_sub1)
                            x_sub2=max(xy[i][0],x_sub2)
                            y_sub1=min(xy[i][1],y_sub1)
                            y_sub2=max(xy[i][1],y_sub2)
                    ans=min((x_sub2-x_sub1)*(y_sub2-y_sub1),ans)
                else:
                    break
print(ans)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
x,y=[[0,0] for i in range(n)],[[0,0] for i in range(n)]
xy=[list(map(int,input().split())) for i in range(n)]
for i in range(n):
    x_sub,y_sub=xy[i]
    x[i][0]=x_sub
    x[i][1]=i
    y[i][0]=y_sub
    y[i][1]=i
x.sort(key=lambda z:z[0])
y.sort(key=lambda z:z[0])
ans=(10**18)*5
for i1 in range(n):
    for l1 in range(n-i1,0,-1):
        for i2 in range(n):
            for l2 in range(n-i2,0,-1):
                if l1*l2<k:
                    break
                z=[0]*n
                for i in range(i1,i1+l1):
                    l=x[i][1]
                    z[l]=1
                for i in range(i2,i2+l2):
                    l=y[i][1]
                    z[l]=1
                if sum(z)>=k:
                    x_sub1,y_sub1=10**9+1,10**9+1
                    x_sub2,y_sub2=-10**9-1,-10**9-1
                    for i in range(n):
                        if z[i]==1:
                            x_sub1=min(xy[i][0],x_sub1)
                            x_sub2=max(xy[i][0],x_sub2)
                            y_sub1=min(xy[i][1],y_sub1)
                            y_sub2=max(xy[i][1],y_sub2)
                    ans=min((x_sub2-x_sub1)*(y_sub2-y_sub1),ans)
                else:
                    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()
#print("XY:", XY)

answer = []
for i in range(N):
  for k in range(K, N + 1):
    if i + k - 1 >= N:
      break
    dx = XY[i + k - 1][0] - XY[i][0]
    y_max = -1
    y_min = 10 ** 15
    for x, y in XY[i: i + k]:
      y_max = max(y_max, y)
      y_min = min(y_min, y)
    dy = y_max - y_min
    answer.append(dx * dy)

print(min(answer))

Submission status: Wrong Answer

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

XY.sort()
#print("XY:", XY)

answer = []
for i in range(N):
  if i + K - 1 == N:
    break
  dx = XY[i + K - 1][0] - XY[i][0]
  y_max = -1
  y_min = 10 ** 15
  for x, y in XY[i: i + K]:
    y_max = max(y_max, y)
    y_min = min(y_min, y)
  dy = y_max - y_min
  answer.append(dx * dy)

print(min(answer))

Submission status: Wrong Answer

Solution code:
import numpy as np
N,K=map(int,input().split())
xy=[list(map(int,input().split())) for _ in range(N)]
xy.sort()
#print(xy)
ans=float("inf")
for i in range(N-K+1):
    #ymax=np.max(xy[i:i+K],axis=1)
    #ymin=np.min(xy[i:i+K],axis=1)
    """print(i)
    print(xy[i:i+K][1])
    print(ymax,ymin)
    print(ymax)"""
    ymax=-float("inf")
    ymin=float("inf")
    for j in range(i,i+K):
        ymax=max(ymax,xy[j][1])
        ymin=min(ymin,xy[j][1])
    yl=ymax-ymin

    xmax=xy[i+K-1][0]
    xmin=xy[i][0]
    xl=xmax-xmin
    #print(xl,yl)
    ans=min(ans,xl*yl)
"""if N==K:
    ymax=-float("inf")
    ymin=float("inf")
    for j in range(N):
        ymax=max(ymax,xy[j][1])
        ymin=min(ymin,xy[j][1])
    yl=ymax-ymin

    xmax=xy[-1][0]
    xmin=xy[0][0]
    xl=xmax-xmin
    #print(xl,yl)
    ans=min(ans,xl*yl)"""
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
N,K=map(int,input().split())
xy=[list(map(int,input().split())) for _ in range(N)]
xy.sort()
#print(xy)
ans=float("inf")
for i in range(N-K):
    #ymax=np.max(xy[i:i+K],axis=1)
    #ymin=np.min(xy[i:i+K],axis=1)
    """print(i)
    print(xy[i:i+K][1])
    print(ymax,ymin)
    print(ymax)"""
    ymax=-float("inf")
    ymin=float("inf")
    for j in range(i,i+K):
        ymax=max(ymax,xy[j][1])
        ymin=min(ymin,xy[j][1])
    yl=ymax-ymin

    xmax=xy[i+K-1][0]
    xmin=xy[i][0]
    xl=xmax-xmin
    #print(xl,yl)
    ans=min(ans,xl*yl)
if N==K:
    ymax=-float("inf")
    ymin=float("inf")
    for j in range(N):
        ymax=max(ymax,xy[j][1])
        ymin=min(ymin,xy[j][1])
    yl=ymax-ymin

    xmax=xy[-1][0]
    xmin=xy[0][0]
    xl=xmax-xmin
    #print(xl,yl)
    ans=min(ans,xl*yl)
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()
#print(xy)
ans=float("inf")
for i in range(N-K):
    ymax=-float("inf")
    ymin=float("inf")
    for j in range(i,i+K):
        ymax=max(ymax,xy[j][1])
        ymin=min(ymin,xy[j][1])
    yl=ymax-ymin

    xmax=xy[i+K-1][0]
    xmin=xy[i][0]
    xl=xmax-xmin
    #print(xl,yl)
    ans=min(ans,xl*yl)
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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