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())
P, X, Y = [], [], []
for i in range(N):
    x, y = map(int, input().split())
    P.append((x, y))
    X.append(x)
    Y.append(y)
X.sort()
Y.sort()

S = float("inf")
for i in range(N-1): #左辺の候補
    for k in range(N-1): #下辺
        for j in range(i+1, N): #右辺
            for l in range(k+1, N):
                Inside = 0
                for p in range(N):
                    if X[i] <= P[p][0] <= X[j] and Y[k] <= P[p][1] <= Y[l]:
                        Inside += 1
                if Inside >= K:
                    S = min(S, (X[j]-X[i]) * (Y[l]-Y[k]))
                    break
            if Inside >= K:
                break
print(S)

Submission status: Wrong Answer

Solution code:
def inpl(): return [int(i) for i in input().split()]
from collections import defaultdict

N, K = inpl()
inf = 10**9+1
x = [inf for _ in range(N+1)]
y = [inf for _ in range(N+1)]
H = defaultdict(lambda: 0)

for i in range(N):
    x[i], y[i] = inpl()
    H[(x[i],y[i])] = 1
    

x.sort()
y.sort()

for i in range(N-1):
    for j in range(N):
        H[(x[i+1],y[j])] = H[(x[i],y[j])] + H[(x[i+1],y[j])]

for j in range(N-1):
    for i in range(N):
        H[(x[i],y[j+1])] = H[(x[i],y[j])] + H[(x[i],y[j+1])]

for i in range(N+1):
    H[(x[i],inf)] = H[(inf,y[i])] = 0
H[(inf,inf)] = 0

ans = inf
for i in range(N):
    for j in range(N):
        for t in range(i):
            if i-t+1 < K:
                break
            for s in range(j):
                if j-s+1 < K:
                    break
                if H[(x[i],y[j])] - H[(x[t-1],y[j])] -\
                H[(x[i],y[s-1])] + H[(x[t-1],y[s-1])] != K:
                    continue
                ans = min(ans,(x[i]-x[t])*(y[j]-y[s]))
print(ans)

Submission status: Wrong Answer

Solution code:
def inpl(): return [int(i) for i in input().split()]

N, K = inpl()
xy = [inpl() for _ in range(N)]
xy = sorted(xy,key = lambda x: x[0])
H =[0 for _ in range(N-K+1)]

xyr = list(map(list, zip(*xy[0:K])))


maxx = max(xyr[0])
minx = min(xyr[0])
maxy = max(xyr[1])
miny = min(xyr[1])

ans = (maxy - miny)*(maxx - minx)

for i in range(N-K):
    xyr[0].remove(xy[i][0])
    xyr[1].remove(xy[i][1])
    xyr[0].append(xy[K+i][0])
    xyr[1].append(xy[K+i][1])
    maxx = max(xyr[0])
    minx = min(xyr[0])
    maxy = max(xyr[1])
    miny = min(xyr[1])
    ans = min(ans,(maxy - miny)*(maxx - minx))
    
xy = sorted(xy,key = lambda x: x[1])

xyr = list(map(list, zip(*xy[0:K])))

for i in range(N-K):
    xyr[0].remove(xy[i][0])
    xyr[1].remove(xy[i][1])
    xyr[0].append(xy[K+i][0])
    xyr[1].append(xy[K+i][1])
    maxx = max(xyr[0])
    minx = min(xyr[0])
    maxy = max(xyr[1])
    miny = min(xyr[1])
    ans = min(ans,(maxy - miny)*(maxx - minx))

print(ans)

Submission status: Wrong Answer

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

x = [0 for _ in range(n)]
y = [0 for _ in range(n)]
for i in range(n):
    x[i], y[i] = map(int, input().split())

min_x = min(x)
min_y = min(y)
for i in range(n):
    x[i] -= min_x
    y[i] -= min_y

sx = sorted(x)
sy = sorted(y)

if n == k:
    print(sx[n - 1] * sy[n - 1])
    exit()

d = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
for i in range(n):
    d[sx.index(x[i]) + 1][sy.index(y[i]) + 1] = 1

#for p in d: print(p)

for i in range(n + 1):
    for j in range(1, n + 1):
        d[i][j] += d[i][j - 1]

for i in range(n + 1):
    for j in range(1, n + 1):
        d[j][i] += d[j - 1][i]

sx = [0] + sx
sy = [0] + sy

a = 0
b = 1
ans = sx[n] * sy[n]
temp = 0
for p in range(n):
    for q in range(p + 1, n + 1):
        for a in range(n):
            for b in range(a + 1, n + 1):
                temp = d[q][b] - d[q][a] - d[p][b] + d[p][a]
                if temp >= k:
                    break
            if temp >= k:
                ans = min(ans, max(1, (sx[b] - sx[a + 1])) * max(1, (sy[q] - sy[p + 1])))

print(ans)

Submission status: Wrong Answer

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

x = [0 for _ in range(n)]
y = [0 for _ in range(n)]
for i in range(n):
    x[i], y[i] = map(int, input().split())

min_x = min(x)
min_y = min(y)
for i in range(n):
    x[i] -= min_x
    y[i] -= min_y

sx = sorted(x)
sy = sorted(y)

if n == k:
    print(sx[n - 1] * sy[n - 1])
    exit()

d = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
for i in range(n):
    d[sx.index(x[i]) + 1][sy.index(y[i]) + 1] = 1

#for p in d: print(p)

for i in range(n + 1):
    for j in range(1, n + 1):
        d[i][j] += d[i][j - 1]

for i in range(n + 1):
    for j in range(1, n + 1):
        d[j][i] += d[j - 1][i]

sx = [0] + sx
sy = [0] + sy

a = 0
b = 1
ans = sx[n] * sy[n]
temp = 0
for p in range(n):
    for q in range(p + 1, n + 1):
        for a in range(n):
            for b in range(a + 1, n + 1):
                temp = d[q][b] - d[q][a] - d[p][b] + d[p][a]
                if temp >= k:
                    break
            if temp >= k:
                ans = min(ans, (sx[b] - sx[a + 1]) * (sy[q] - sy[p + 1]))

print(ans)

Submission status: Wrong Answer

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

x = [0 for _ in range(n)]
y = [0 for _ in range(n)]
for i in range(n):
    x[i], y[i] = map(int, input().split())

min_x = min(x)
min_y = min(y)
for i in range(n):
    x[i] -= min_x
    y[i] -= min_y

sx = sorted(x)
sy = sorted(y)

if n == k:
    print(sx[n - 1] * sy[n - 1])
    exit()

d = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
for i in range(n):
    d[sx.index(x[i]) + 1][sy.index(y[i]) + 1] = 1

#for p in d: print(p)

for i in range(n + 1):
    for j in range(1, n + 1):
        d[i][j] += d[i][j - 1]

for i in range(n + 1):
    for j in range(1, n + 1):
        d[j][i] += d[j - 1][i]

sx = [0] + sx
sy = [0] + sy

a = 0
b = 1
ans = sx[n] * sy[n]
temp = 0
for p in range(n):
    for q in range(p + 1, n + 1):
        for a in range(n):
            for b in range(a + 1, n + 1):
                temp = d[q][b] - d[q][a] - d[p][b] + d[p][a]
                if temp >= k:
                    break
            if temp >= k:
                ans = min(ans, (sx[b] - sx[a]) * (sy[q] - sy[p]))

print(ans)

Submission status: Wrong Answer

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

x = [0 for _ in range(n)]
y = [0 for _ in range(n)]
for i in range(n):
    x[i], y[i] = map(int, input().split())

min_x = min(x)
min_y = min(y)
for i in range(n):
    x[i] -= min_x
    y[i] -= min_y

sx = sorted(x)
sy = sorted(y)

#print(x, sx)
#print(y, sy)

d = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
for i in range(n):
    d[sx.index(x[i]) + 1][sy.index(y[i]) + 1] = 1

for i in range(n + 1):
    for j in range(1, n + 1):
        d[i][j] += d[i][j - 1]

for i in range(n + 1):
    for j in range(1, n + 1):
        d[j][i] += d[j - 1][i]

#for p in d: print(p)
sx = [0] + sx
sy = [0] + sy

a = 0
b = 1
ans = sx[n] * sy[n]
temp = 0
for p in range(n):
    for q in range(p + 1, n + 1):
        for a in range(n):
            for b in range(a + 1, n + 1):
                temp = d[q][b] - d[q][a] - d[p][b] + d[p][a]
                if temp >= k:
                    break
            if temp >= k:
                #print(sx, sy)
                #print(a, b, p, q, sx[b], sx[a], sy[q], sy[p])
                ans = min(ans, (sx[b] - sx[a]) * (sy[q] - sy[p]))

print(ans)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
XY = [[] for i in range(N)]
Y = [0] * N
for i in range(N):
  x, y = map(int, input().split())
  XY[i] = [x, y]
  Y[i] = y
XY.sort()
ans = (XY[-1][0] - XY[0][0]) * (max(Y) - min(Y))
for s in range(N + 1 - K):
  for t in range(s + K - 1, N):
    x = XY[t][0] - XY[s][0]
    c = (XY[s][1] + XY[t][1]) / 2
    Y = sorted([[y, abs(y - c)] for x, y in XY[s + 1: t]], key=lambda a: a[1])[:K - 2]
    Y = [y for y, a in Y] + [XY[s][1], XY[t][1]]
    y = max(Y) - min(Y)
    ans = min(x * y, ans)
XY.sort(key=lambda xy: xy[1])
for s in range(N + 1 - K):
  for t in range(s + K - 1, N):
    y = XY[t][1] - XY[s][1]
    c = (XY[s][0] + XY[t][0]) / 2
    X = sorted([[x, abs(x - c)] for x, y in XY[s + 1: t]], key=lambda a: a[1])[:K - 2]
    X = [x for x, a in X] + [XY[s][0], XY[t][0]]
    x = max(X) - min(X)
    ans = min(x * y, ans)
print(ans)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
XY = [[] for i in range(N)]
Y = [0] * N
for i in range(N):
  x, y = map(int, input().split())
  XY[i] = [x, y]
  Y[i] = y
XY.sort(key=lambda xy: xy[0])
ans = (XY[-1][0] - XY[0][0]) * (max(Y) - min(Y))
for s in range(N + 1 - K):
  for t in range(s + K - 1, N):
    x = XY[t][0] - XY[s][0]
    c = (XY[s][1] + XY[t][1]) // 2
    Y = sorted([y for x, y in XY[s + 1: t]], key=lambda y: abs(y - c))[:K - 2] + [XY[s][1], XY[t][1]]
    y = max(Y) - min(Y)
    ans = min(x * y, ans)
XY.sort(key=lambda xy: xy[1])
for s in range(N + 1 - K):
  for t in range(s + K - 1, N):
    y = XY[t][1] - XY[s][1]
    c = (XY[s][0] + XY[t][0]) // 2
    X = sorted([x for x, y in XY[s + 1: t]], key=lambda x: abs(x - c))[:K - 2] + [XY[s][0], XY[t][0]]
    x = max(X) - min(X)
    ans = min(x * y, ans)
print(ans)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
XY = [[] for i in range(N)]
Y = [0] * N
for i in range(N):
  x, y = map(int, input().split())
  XY[i] = [x, y]
  Y[i] = y
XY.sort(key=lambda xy: xy[0])
ans = (XY[-1][0] - XY[0][0]) * (max(Y) - min(Y))
for s in range(N + 1 - K):
  for t in range(s + K - 1, N):
    x = XY[t][0] - XY[s][0]
    c = (XY[s][1] + XY[t][1]) / 2
    Y = sorted([y for x, y in XY[s + 1: t]], key=lambda y: abs(y - c))[:K - 2] + [XY[s][1], XY[t][1]]
    y = max(Y) - min(Y)
    ans = min(x * y, ans)
XY.sort(key=lambda xy: xy[1])
for s in range(N + 1 - K):
  for t in range(s + K - 1, N):
    y = XY[t][1] - XY[s][1]
    c = (XY[s][0] + XY[t][0]) / 2
    X = sorted([x for x, y in XY[s + 1: t]], key=lambda x: abs(x - c))[:K - 2] + [XY[s][0], XY[t][0]]
    x = max(X) - min(X)
    ans = min(x * y, ans)
print(ans)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
XY = [[] for i in range(N)]
Y = [0] * N
for i in range(N):
  x, y = map(int, input().split())
  XY[i] = [x, y]
  Y[i] = y
XY.sort()
ans = (XY[-1][0] - XY[0][0]) * (max(Y) - min(Y))
for s in range(N + 1 - K):
  for t in range(s + K - 1, N):
    x = XY[t][0] - XY[s][0]
    c = (XY[s][1] + XY[t][1]) / 2
    Y = sorted([y for x, y in XY[s + 1: t]], key=lambda y: abs(y - c))[:K - 2] + [XY[s][1], XY[t][1]]
    y = max(Y) - min(Y)
    ans = min(x * y, ans)
XY.sort(key=lambda xy: xy[1])
for s in range(N + 1 - K):
  for t in range(s + K - 1, N):
    y = XY[t][1] - XY[s][1]
    c = (XY[s][0] + XY[t][0]) / 2
    X = sorted([x for x, y in XY[s + 1: t]], key=lambda x: abs(x - c))[:K - 2] + [XY[s][0], XY[t][0]]
    x = max(X) - min(X)
    ans = min(x * y, ans)
print(ans)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
XY = [[] for i in range(N)]
Y = [0] * N
for i in range(N):
  x, y = map(int, input().split())
  XY[i] = [x, y]
  Y[i] = y
XY.sort()
ans = (XY[-1][0] - XY[0][0]) * (max(Y) - min(Y))
for s in range(N + 1 - K):
  for t in range(s + K - 1, N):
    x = XY[t][0] - XY[s][0]
    c = (XY[s][1] + XY[t][1]) / 2
    Y = sorted([y for x, y in XY[s + 1: t]], key=lambda y: abs(y - c))[:K - 2] + [XY[s][1], XY[t][1]]
    y = max(Y) - min(Y)
    ans = min(x * y, ans)
print(ans)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
XY = [[] for i in range(N)]
Y = [0] * N
for i in range(N):
  x, y = map(int, input().split())
  XY[i] = [x, y]
  Y[i] = y
XY.sort()
ans = (XY[-1][0] - XY[0][0]) * (max(Y) - min(Y))
for i in range(N + 1 - K):
  x = XY[i + K - 1][0] - XY[i][0]
  Y = [y for x, y in XY[i:i+K]]
  y = max(Y) - min(Y)
  ans = min(x * y, ans)
XY.sort(key=lambda xy: xy[1])
for i in range(N + 1 - K):
  y = XY[i + K - 1][1] - XY[i][1]
  X = [x for x, y in XY[i:i+K]]
  x = max(X) - min(X)
  ans = min(x * y, ans)
print(ans)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
XY = [[] for i in range(N)]
Y = [0] * N
for i in range(N):
  x, y = map(int, input().split())
  XY[i] = [x, y]
  Y[i] = y
XY.sort()
ans = (XY[-1][0] - XY[0][0]) * (max(Y) - min(Y))
for i in range(N + 1 - K):
  x = XY[i + K - 1][0] - XY[i][0]
  Y = [y for x, y in XY[i:i+K]]
  y = max(Y) - min(Y)
  ans = min(x * y, ans)
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import accumulate
import numpy as np
N,K=list(map(int,input().split()))
point=[]
x_set=set()
y_set=set()
p_dic={}

for i in range(N):
    x,y=list(map(int,input().split()))
    point.append((x,y))
    x_set.add(x)
    y_set.add(y)
x_arr=sorted(list(x_set))
y_arr=sorted(list(y_set))

x_dic={}
y_dic={}
for i,x in enumerate(x_arr):
    x_dic[x]=i
for i,y in enumerate(y_arr):
    y_dic[y]=i

square=[[0 for _ in range(len(x_arr)+1)] for _ in range(len(y_arr)+1)]
for p in point:
    j=x_dic[p[0]]
    i=y_dic[p[1]]
    square[i+1][j+1]+=1
square=np.array(square)

for i,line in enumerate(square):
    square[i]=list(accumulate(line))
for i,row in enumerate(square.T):
    square[:,i]=list(accumulate(row))

h=1
ans=float('inf')
W=len(square[0])
H=len(square)
for i in range(1,H):
    for j in range(i,H):
        for k in range(1,W): 
            num=square[j][k]-square[i-1][k]-square[j][h-1]+square[i-1][h-1]
            while num>=K:
                S=max(y_arr[j-1]-y_arr[i-1],1)*max(x_arr[k-1]-x_arr[h-1],1)
                ans=min(ans,S)
                h+=1
                num=square[j][k]-square[i-1][k]-square[j][h-1]+square[i-1][h-1]
print(int(ans))

Submission status: Wrong Answer

Solution code:
from itertools import accumulate
import numpy as np
N,K=list(map(int,input().split()))
point=[]
x_set=set()
y_set=set()
p_dic={}

for i in range(N):
    x,y=list(map(int,input().split()))
    point.append((x,y))
    x_set.add(x)
    y_set.add(y)
x_arr=sorted(list(x_set))
y_arr=sorted(list(y_set))

x_dic={}
y_dic={}
for i,x in enumerate(x_arr):
    x_dic[x]=i
for i,y in enumerate(y_arr):
    y_dic[y]=i

square=[[0 for _ in range(len(x_arr)+1)] for _ in range(len(y_arr)+1)]
for p in point:
    i=x_dic[p[0]]
    j=y_dic[p[1]]
    square[i+1][j+1]+=1
square=np.array(square)

for i,line in enumerate(square):
    square[i]=list(accumulate(line))
for i,row in enumerate(square.T):
    square[:,i]=list(accumulate(row))

h=1
ans=float('inf')
W=len(square[0])
H=len(square)
for i in range(1,H):
    for j in range(i,H):
        for k in range(1,W): 
            num=square[j][k]-square[i-1][k]-square[j][h-1]+square[i-1][h-1]
            while num>=K:
                S=max(y_arr[j-1]-y_arr[i-1],1)*max(x_arr[k-1]-x_arr[h-1],1)
                ans=min(ans,S)
                h+=1
                num=square[j][k]-square[i-1][k]-square[j][h-1]+square[i-1][h-1]
print(int(ans))

Submission status: Wrong Answer

Solution code:
n, k = [int(_) for _ in input().split()]
x, y = [], []
for _ in range(n):
    temp = [int(_) for _ in input().split()]
    x.append(temp[0])
    y.append(temp[1])
x.sort()
y.sort()

answer = 4 * 10**18
for i0 in range(n):
    for j0 in range(i0 + 1, n):
        xi = x[i0]
        xj = x[j0]
        for i1 in range(n):
            for j1 in range(i1 + 1, n):
                yi = y[i1]
                yj = y[j1]
                c = 0
                for l in range(n):
                    if xi <= x[l] and x[l] <= xj and yi <= y[l] and y[l] <= yj:
                        c += 1
                s = (xj - xi) * (yj - yi)
                if s <= answer and c >= k:
                    answer = s

print(answer)

Submission status: Wrong Answer

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

S = float("inf")
if K >= 3:
    for i in range(N-2):
        for j in range(i+1, N-1):
           for k in range(j+1, N):
               minX, maxX = min(P[i][0], P[j][0], P[k][0]), max(P[i][0], P[j][0], P[k][0])
               minY, maxY = min(P[i][1], P[j][1], P[k][1]), max(P[i][1], P[j][1], P[k][1])
               Inside = 3
               for a in range(N):
                   if a != i and a!=j and a!=k:
                       if minX < P[a][0] < maxX and minY < P[a][1] < maxY:
                           Inside += 1
               if Inside >= K:
                   S = min(S, (maxX-minX) * (maxY-minY))
    print(S)
elif K == 2:
    for i in range(N-1):
        for j in range(i+1, N):
            minX, maxX = min(P[i][0], P[j][0]), max(P[i][0], P[j][0])
            minY, maxY = min(P[i][1], P[j][1]), max(P[i][1], P[j][1])
            S = min(S, (maxX-minX) * (maxY-minY))
    print(S)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
X, Y = [], []
D = []
for i in range(N):
    x, y = map(int, input().split())
    X.append(x)
    Y.append(y)
    D.append((x, y))

X = sorted(X)
Y = sorted(Y)
num = float("inf")
for i in range(N - 1):
    for j in range(i + 1, N):
        for k in range(N - 1):
            for l in range(k + 1, N):
                tmp = 0
                for m in range(N):
                    if X[i] <= X[m] <= X[j] and Y[k] <= Y[m] <= Y[l]:
                        tmp += 1
                if tmp >= K:
                    num = min(num, (X[j] - X[i]) * (Y[l] - Y[k]))

print(num)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Oct 13 14:04:12 2018
ABC075D
@author: maezawa
"""

n, k = list(map(int, input().split()))
points = []
for i in range(n):
    point = list(map(int, input().split()))
    points.append(point)
    
xorder = sorted(points)
yorder = sorted(points, key=lambda x: x[1])

#print(xorder)
#print(yorder)

xmin = xorder[0][0]
xmax = xorder[-1][0]
ymin = yorder[0][0]
ymax = yorder[-1][0]

area = (xorder[-1][0]-xorder[0][0])*(yorder[-1][1]-yorder[0][1])

i = n
while i > k:
    # remove xmin
    if xorder[0] == yorder[0]:
        a0 = (xorder[-1][0]-xorder[1][0])*(yorder[-1][1]-yorder[1][1])
    elif xorder[0] == yorder[-1]:
        a0 = (xorder[-1][0]-xorder[1][0])*(yorder[-2][1]-yorder[0][1])
    else:
        a0 = (xorder[-1][0]-xorder[1][0])*(yorder[-1][1]-yorder[0][1])
        
    # remove xmax
    if xorder[-1] == yorder[0]:
        a1 = (xorder[-2][0]-xorder[0][0])*(yorder[-1][1]-yorder[1][1])
    elif xorder[-1] == yorder[-1]:
        a1 = (xorder[-2][0]-xorder[0][0])*(yorder[-2][1]-yorder[0][1])
    else:
        a1 = (xorder[-2][0]-xorder[0][0])*(yorder[-1][1]-yorder[0][1])
        
    # remove ymin
    if yorder[0] == xorder[0]:
        a2 = (yorder[-1][1]-yorder[1][1])*(xorder[-1][0]-xorder[1][0])
    elif yorder[0] == xorder[-1]:
        a2 = (yorder[-1][1]-yorder[1][1])*(xorder[-2][0]-xorder[0][0])
    else:
        a2 = (yorder[-1][1]-yorder[1][1])*(xorder[-1][0]-xorder[0][0])
        
    # remove ymax
    if yorder[-1] == xorder[0]:
        a3 = (yorder[-2][1]-yorder[0][1])*(xorder[-1][0]-xorder[1][0])
    elif xorder[-1] == yorder[-1]:
        a3 = (yorder[-2][1]-yorder[0][1])*(xorder[-2][0]-xorder[0][0])
    else:
        a3 = (yorder[-2][1]-yorder[0][1])*(xorder[-1][0]-xorder[0][0])

    if a0 <= a1 and a0 <= a2 and a0 <= a3:
        area = a0
        yorder.remove(xorder[0])
        xorder.pop(0)
    elif a1 <= a0 and a1 <= a2 and a1 <= a3:
        area = a1
        yorder.remove(xorder[-1])
        xorder.pop(-1)
    elif a2 <= a0 and a2 <= a1 and a2 <= a3:
        area = a2
        xorder.remove(yorder[0])
        yorder.pop(0)
    else:
        area = a3
        xorder.remove(yorder[-1])
        yorder.pop(-1)
    #print(xorder)
    #print(yorder)
    i -= 1
    
print(area)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

N,K = map(int,input().split())
src = [tuple(map(int,input().split())) for i in range(N)]

INF = float('inf')
x_cnt = defaultdict(lambda: 0)
x_ymax = defaultdict(lambda: -INF)
x_ymin = defaultdict(lambda: INF)
y_cnt = defaultdict(lambda: 0)
y_xmax = defaultdict(lambda: -INF)
y_xmin = defaultdict(lambda: INF)

for x,y in src:
    x_cnt[x] += 1
    x_ymax[x] = max(x_ymax[x], y)
    x_ymin[x] = min(x_ymin[x], y)
    y_cnt[y] += 1
    y_xmax[y] = max(y_xmax[y], x)
    y_xmin[y] = min(y_xmin[y], x)

ans = INF
sortedcnt = sorted(x_cnt.items())
cc = 0
for i,(x1,c1) in enumerate(sortedcnt):
    if N - cc < K: break
    cc += c1
    tmpc = 0
    tmpmax = -INF
    tmpmin = INF
    for j,(x2,c2) in enumerate(sortedcnt[i:]):
        tmpc += c2
        tmpmax = max(tmpmax, x_ymax[x2])
        tmpmin = min(tmpmin, x_ymin[x2])
        if tmpc >= K and x2 != x1 and tmpmax != tmpmin:
            tmp = (x2-x1) * (tmpmax-tmpmin)
            ans = min(ans, tmp)
            break

sortedcnt = sorted(y_cnt.items())
cc = 0
for i,(y1,c1) in enumerate(sortedcnt):
    if N - cc < K: break
    cc += c1
    tmpc = 0
    tmpmax = -INF
    tmpmin = INF
    for j,(y2,c2) in enumerate(sortedcnt[i:]):
        tmpc += c2
        tmpmax = max(tmpmax, y_xmax[y2])
        tmpmin = min(tmpmin, y_xmin[y2])
        if tmpc >= K and y2 != y1 and tmpmax != tmpmin:
            tmp = (y2-y1) * (tmpmax-tmpmin)
            ans = min(ans, tmp)
            break

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

N,K = map(int,input().split())
src = [tuple(map(int,input().split())) for i in range(N)]

INF = float('inf')
cnt = defaultdict(lambda: 0)
y_max = defaultdict(lambda: -INF)
y_min = defaultdict(lambda: INF)

for x,y in src:
    cnt[x] += 1
    y_max[x] = max(y_max[x], y)
    y_min[x] = min(y_min[x], y)

sortedcnt = sorted(cnt.items())
cc = 0
ans = INF
for i,(x1,c1) in enumerate(sortedcnt):
    if N - cc < K: break
    cc += c1
    tmpc = 0
    tmpmax = -INF
    tmpmin = INF
    for j,(x2,c2) in enumerate(sortedcnt[i:]):
        tmpc += c2
        tmpmax = max(tmpmax, y_max[x2])
        tmpmin = min(tmpmin, y_min[x2])
        if tmpc >= K and x2 != x1 and tmpmax != tmpmin:
            tmp = (x2-x1) * (tmpmax-tmpmin)
            ans = min(ans, tmp)
            break
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

N,K = map(int,input().split())
src = [tuple(map(int,input().split())) for i in range(N)]

INF = float('inf')
cnt = defaultdict(lambda: 0)
y_max = defaultdict(lambda: -INF)
y_min = defaultdict(lambda: INF)

for x,y in src:
    cnt[x] += 1
    y_max[x] = max(y_max[x], y)
    y_min[x] = min(y_min[x], y)

sortedcnt = sorted(cnt.items())
cc = 0
ans = INF
for i,(x1,c1) in enumerate(sortedcnt):
    if N - cc < K: break
    cc += c1
    tmpc = 0
    tmpmax = -INF
    tmpmin = INF
    for j,(x2,c2) in enumerate(sortedcnt[i:]):
        tmpc += c2
        tmpmax = max(tmpmax, y_max[x2])
        tmpmin = min(tmpmin, y_min[x2])
        if tmpc >= K:
            tmp = (x2-x1) * (tmpmax-tmpmin)
            ans = min(ans, tmp)
            break
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
stdin = sys.stdin

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

n,k = li()
xs = []
ys = []
points = []
for _ in range(n):
    x,y = li()
    xs.append(x)
    ys.append(y)
    points.append((x,y))
    
xs.sort()
ys.sort()

ans = 10**18
for xst in range(n):
    for xed in range(xst,n):
        for yst in range(n):
            for yed in range(yst, n):
                cnt = 0
                for px,py in points:
                    if xs[xst] <= px <= xs[xed] and ys[yst] <= py <= ys[yed]:
                        cnt += 1
                        
                if cnt >= k:
                    ans = min(ans, (xs[xed]-xs[xst])*(ys[yed]-ys[yst]))
                    
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
stdin = sys.stdin

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

n,k = li()
x = []
y = []
points = [tuple(li()) for _ in range(n)]
for i in range(n):
    x.append(points[i][0])
    y.append(points[i][1])
    
x.sort()
y.sort()

ans = (x[-1]-x[0]) * (y[-1]-y[0])
for xs in x[:-1]:
    for xt in x[xs+1:]:
        for ys in y[:-1]:
            for yt in y[ys+1:]:
                area = (xt-xs) * (yt-ys)
                inner = 0
                for xi,yi in points:
                    if xs<=xi<=xt and ys<=yi<=yt:
                        inner += 1
                        
                if inner >= k:
                    ans = min(ans,area)
                    
                    
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
stdin = sys.stdin

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

n,k = li()
x = []
y = []
points = [tuple(li()) for _ in range(n)]
for i in range(n):
    x.append(points[i][0])
    y.append(points[i][1])
    
x.sort()
y.sort()
points.sort()

ans = (x[-1]-x[0]) * (y[-1]-y[0])
for x_st in range(n-1):
    for x_ed in range(x_st+1,n):
        for y_st in range(n-1):
            for y_ed in range(y_st+1,n):

                inner = 0
                ys = [points[i][1] for i in range(y_st, y_ed+1)]
                area = (points[x_ed][0] - points[x_st][0]) * (max(ys) - min(ys))
                for xi,yi in points:
                    if points[x_st][0] <= xi <= points[x_ed][0] and points[y_st][1] <= yi <= points[y_ed][1]:
                        inner += 1
                        
                if inner >= k:
                    ans = min(ans,area)
                    
                    
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
stdin = sys.stdin

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

n,k = li()
x = []
y = []
points = [tuple(li()) for _ in range(n)]
for i in range(n):
    x.append(points[i][0])
    y.append(points[i][1])
    
x.sort()
y.sort()

ans = float("inf")
for x_st in x[:-1]:
    for x_ed in x[x_st+1:]:
        for y_st in y[:-1]:
            for y_ed in y[y_st+1:]:
                inner = 0
                area = (x_ed - x_st) * (y_ed - y_st)
                for xi,yi in points:
                    if x_st <= xi <= x_ed and y_st <= yi <= y_ed:
                        inner += 1
                        
                if inner >= k:
                    ans = min(ans,area)
                    
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
stdin = sys.stdin

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

n,k = li()
xy = []

xlist = []
ylist = []
for _ in range(n):
    xy.append((tuple(list(li()))))
    xlist.append(xy[-1][0])
    ylist.append(xy[-1][1])
   
    
# xをソート→yを考える
xy.sort()
xlist.sort()

ans = [0]*(n-k+1)
for i in range(n-k+1):
    ys = [xy[j][1] for j in range(i,i+k)]
    y = max(ys) - min(ys)
    ans[i] = (xlist[i+k-1] - xlist[i]) * y

xtoy = min(ans)

# xをソート→yを考える   
xy.sort(key=lambda x:x[1])
ylist.sort()

ans = [0]*(n-k+1)
for i in range(n-k+1):
    xs = [xy[j][0] for j in range(i,i+k)]
    x = max(xs) - min(xs)
    ans[i] = (ylist[i+k-1] - ylist[i]) * x

ytox = min(ans)

print(min(xtoy, ytox))

Submission status: Wrong Answer

Solution code:
import sys
stdin = sys.stdin

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

n,k = li()
xy = []
xs = []
for _ in range(n):
    xy.append((tuple(list(li()))))
    xs.append(xy[-1][0])
    
xy.sort()
xs.sort()

ans = [0]*(n-k+1)
for i in range(n-k+1):
    ys = [xy[j][1] for j in range(i,i+k)]
    y = max(ys) - min(ys)
    ans[i] = (xs[i+k-1] - xs[i]) * y
    
print(min(ans))

Submission status: Wrong Answer

Solution code:
from operator import itemgetter

import numpy as np

N, K = map(int, input().split())
xy = [[int(x) for x in input().split()] for _ in range(N)]


def min_area(xy):
    xy = np.array(xy)
    res = float('inf')
    for i in range(N - K + 1):
        max_x, max_y = xy[i:i + K].max(axis=0)
        min_x, min_y = xy[i:i + K].min(axis=0)
        dx = abs(max_x - min_x)
        dy = abs(max_y - min_y)
        res = min(res, dx * dy)
    return res


ans = min_area(sorted(xy, key=itemgetter(0)))
ans = min(ans, min_area(sorted(xy, key=itemgetter(0))[::-1]))
ans = min(ans, min_area(sorted(xy, key=itemgetter(1))))
ans = min(ans, min_area(sorted(xy, key=itemgetter(1))[::-1]))
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

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

xy = [[int(x) for x in input().split()] for _ in range(N)]
xy.sort()
xy = np.array(xy)

ans = float('inf')
for i in range(N - K + 1):
    max_x, max_y = xy[i:i + K].max(axis=0)
    min_x, min_y = xy[i:i + K].min(axis=0)
    dx = abs(max_x - min_x)
    dy = abs(max_y - min_y)
    ans = min(ans , dx * dy)
print(ans)