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:
#!/usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')
move = [(0, 1), (1, 1), (-1, 1), (0, -1), (1, -1), (-1, -1), (1, 0), (-1, 0)]
#A
def A():
    a, b, c = LI()
    if a == b:
        print(c)
    if b == c:
        print(a)
    if a == c:
        print(b)
    return

#B
def B():
    h, w = LI()
    s = SR(h)
    for y in range(h):
        for x in range(w):
            if s[y][x] == ".":
                b = 0
                for my, mx in move:
                    ym = my + y
                    xm = mx + x
                    if 0 <= ym < h and 0 <= xm < w:
                        if s[ym][xm] == "#":
                            b += 1
                s[y][x] = b
    for i in range(h):
        print("".join(map(str, s[i])))
    return

#C
def C():
    n, m = LI()
    edg = [[] for i in range(n)]
    ab = LIR_(m)
    for a,b in ab:
        edg[a].append(b)
        edg[b].append(a)
    ans = 0
    for a, b in ab:
        c = [True] * n
        ed = defaultdict(int)
        q = deque()
        q.append(0)
        c[0] = False
        ed[(a,b)] = True
        while q:
            now = q.pop()
            for e in edg[now]:
                if ed[(now,e)] or ed[(e,now)]:
                    continue
                ed[(now, e)] = True
                c[e] = False
                q.appendleft(e)
        if True in c:
            ans += 1
    print(ans)
    return

#D
def D():
    n, k = LI()
    xy = LIR(n)
    fullserch = itertools.combinations(range(n), 4)
    ans = inf
    for a, b, c, d in fullserch:
        minx = min(xy[a][0], xy[b][0], xy[c][0], xy[d][0])
        maxx = max(xy[a][0], xy[b][0], xy[c][0], xy[d][0])
        miny = min(xy[a][1], xy[b][1], xy[c][1], xy[d][1])
        maxy = max(xy[a][1], xy[b][1], xy[c][1], xy[d][1])
        b = 0
        for i in range(n):
            if minx <= xy[i][0] <= maxx and miny <= xy[i][1] <= maxy:
                b += 1

        if b >= k:
            ans = min(ans, (maxx - minx) * (maxy - miny))
    print(ans) 
    return

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

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')
move = [(0, 1), (1, 1), (-1, 1), (0, -1), (1, -1), (-1, -1), (1, 0), (-1, 0)]
#A
def A():
    a, b, c = LI()
    if a == b:
        print(c)
    if b == c:
        print(a)
    if a == c:
        print(b)
    return

#B
def B():
    h, w = LI()
    s = SR(h)
    for y in range(h):
        for x in range(w):
            if s[y][x] == ".":
                b = 0
                for my, mx in move:
                    ym = my + y
                    xm = mx + x
                    if 0 <= ym < h and 0 <= xm < w:
                        if s[ym][xm] == "#":
                            b += 1
                s[y][x] = b
    for i in range(h):
        print("".join(map(str, s[i])))
    return

#C
def C():
    n, m = LI()
    edg = [[] for i in range(n)]
    ab = LIR_(m)
    for a,b in ab:
        edg[a].append(b)
        edg[b].append(a)
    ans = 0
    for a, b in ab:
        c = [True] * n
        ed = defaultdict(int)
        q = deque()
        q.append(0)
        c[0] = False
        ed[(a,b)] = True
        while q:
            now = q.pop()
            for e in edg[now]:
                if ed[(now,e)] or ed[(e,now)]:
                    continue
                ed[(now, e)] = True
                c[e] = False
                q.appendleft(e)
        if True in c:
            ans += 1
    print(ans)
    return

#D
def D():
    n, k = LI()
    xy = LIR(n)
    fullserch = itertools.combinations_with_replacement(range(n), 3)
    ans = inf
    for a, b, c in fullserch:
        minx = min(xy[a][0], xy[b][0], xy[c][0])
        maxx = max(xy[a][0], xy[b][0], xy[c][0])
        miny = min(xy[a][1], xy[b][1], xy[c][1])
        maxy = max(xy[a][1], xy[b][1], xy[c][1])
        b = 0
        for i in range(n):
            if minx <= xy[i][0] <= maxx and miny <= xy[i][1] <= maxy:
                b += 1

        if b >= k:
            ans = min(ans, (maxx - minx) * (maxy - miny))
    print(ans) 
    return

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

Submission status: Wrong Answer

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

m = float('inf')
for i in range(N) :
    for j in range(i + 1, N) :
        for k in range(j + 1, N) :
            x, y = zip(xy[i], xy[j], xy[k])
            mx, Mx = min(x), max(x)
            my, My = min(y), max(y)
            
            counter = 0
            for l in range(N) :
                if mx <= xy[l][0] <= Mx and my <= xy[l][1] <= My :
                    counter += 1
            if counter >= K :
                m = min(m, (Mx-mx)*(My-my))
print(m)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
#ABC75 D

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))


n,K = LI()
xy = [LI() for _ in range(n)]
xy.sort(key = itemgetter(1))
ans = inf
for i in range(n)[::-1]:
    ux,uy = xy[i]
    for j in range(n):
        dx,dy = xy[j]
        if uy < dy:
            print(ans)
            quit()
        for k in range(n):
            rx,ry = xy[k]
            for l in range(n):
                lx,ly = xy[l]
                if rx < lx:
                    continue
                cnt = 0
                for m in range(n):
                    x,y = xy[m]
                    if lx <= x <= rx and dy <= y <= uy:
                        cnt += 1
                if cnt >= K:
                    S = (uy - dy)*(rx - lx)
                    ans = min(ans,S)
print(ans)

Submission status: Wrong Answer

Solution code:
from operator import itemgetter

N,K = map(int,input().split())
p = [list(map(int,input().split())) for i in range(N)]
px = sorted(p)
p.sort(key=itemgetter(1))
py = p
inf = float('inf')
ans = inf

for i in range(N):
    for j in range(i+1, N):
        x1 = px[i][0]
        x2 = px[j][0]
        for k in range(N):
            for l in range(k+1, N):
                y1 = py[k][1]
                y2 = py[l][1]
                count = 0
                for ii in px[i+1:j]:
                    if y1 < ii[1] < y2:
                        count += 1
                if count == K-2:
                    ans = min(ans, abs(x1-x2) * abs(y1-y2))
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()
XY_Y = sorted(XY, key = lambda x: x[1])

def count(x_min, x_max, y_min, y_max, i, j):
    OK = 0
    NG = 0
    a = j - i + 1 - K
    for m in range(i, j + 1):
        if y_min <= XY[m][1] <= y_max:
            OK += 1
        else:
            NG += 1
        if OK >= K:
            return True
        if NG > a:
            return False

ans = 10 ** 19
for i in range(N - 1):
    for j in range(i + K - 1, N):
        for k in range(N - 1):
            for l in range(i + K - 1, N):
                if count(XY[i][0], XY[j][0], XY_Y[k][1], XY_Y[l][1], i, j):
                    # print ('A')
                    ans = min(ans, (XY[j][0] - XY[i][0]) * (XY_Y[l][1] - XY_Y[k][1]))
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()
XY_Y = sorted(XY, key = lambda x: x[1])

def count(x_min, x_max, y_min, y_max, i, j):
    OK = 0
    NG = 0
    a = j - i + 1 - K
    for m in range(i, j + 1):
        if y_min <= XY[m][1] <= y_max:
            OK += 1
        else:
            NG += 1
        if OK >= K:
            return True
        if NG > a:
            return False


ans = 10 ** 20
for i in range(N - 1):
    for j in range(i + K - 1, N):
        for k in range(N - 1):
            for l in range(i + K - 1, N):
                if count(XY[i][0], XY[j][0], XY_Y[k][1], XY_Y[l][1], i, j):
                    # print ('A')
                    ans = min(ans, (XY[j][0] - XY[i][0]) * (XY_Y[l][1] - XY_Y[k][1]))
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()

ans = 10 ** 20
for i in range(N - K + 1):
    # print ('A')
    for j in range(i + K, N + 1):
        # print ('i, j = ', i, j)
        abs_x = XY[j - 1][0] - XY[i][0]
        abs_y = max(XY[i:j], key = lambda x: x[1])[1] - min(XY[i:j], key = lambda x: x[1])[1]
        # print (abs_x, abs_y)
        tmp = abs_x * abs_y
        ans = min(ans, tmp)

XY.sort(key = lambda x: x[1])
for i in range(N - K + 1):
    # print ('A')
    for j in range(i + K, N + 1):
        # print ('i, j = ', i, j)
        abs_y = XY[j - 1][1] - XY[i][1]
        abs_x = max(XY[i:j], key = lambda x: x[0])[0] - min(XY[i:j], key = lambda x: x[0])[0]
        # print (abs_x, abs_y)
        tmp = abs_x * abs_y
        ans = min(ans, tmp)


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()

ans = 10 ** 20
for i in range(N - K + 1):
    # print ('A')
    for j in range(i + K, N + 1):
        # print ('i, j = ', i, j)
        abs_x = XY[j - 1][0] - XY[i][0]
        abs_y = max(XY[i:j], key = lambda x: x[1])[1] - min(XY[i:j], key = lambda x: x[1])[1]
        # print (abs_x, abs_y)
        tmp = abs_x * abs_y
        ans = min(ans, tmp)

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()

ans = 10 ** 20
for i in range(N - K + 1):
    # print ('A')
    for j in range(i + K, N + 1):
        # print (i, j)
        abs_x = XY[j - 1][0] - XY[i][0]
        abs_y = max(XY[i:j + 1], key = lambda x: x[1])[1] - min(XY[i:j + 1], key = lambda x: x[1])[1]
        # print (abs_x, abs_y)
        tmp = abs_x * abs_y
        ans = min(ans, tmp)

print (ans)

Submission status: Wrong Answer

Solution code:
#D問題
N,K = map(int,input().split())
XY = []
for i in range(N):
    x,y = map(int,input().split())
    XY.append([x,y])
    
XY.sort()
X,Y = zip(*XY)

    
MIN = 10**20
for lx in range(N-K+1):
    for rx in range(K+lx-1,N):
        Ys = sorted(Y[lx:rx+1])
        for dy in range(len(Ys)-K+1):
            MIN = min(MIN,X[rx]-X[lx])*(Ys[dy+K-1]-Ys[dy])
            
print(MIN)

Submission status: Wrong Answer

Solution code:
#D問題
N,K = map(int,input().split())
XY = []
for i in range(N):
    x,y = map(int,input().split())
    XY.append([x,y])
    
XY.sort()
X,Y = zip(*XY)

    
MIN = float("inf")
for lx in range(N-K+1):
    for rx in range(K+lx-1,N):
        Ys = sorted(Y[lx:rx+1])
        for dy in range(len(Ys)-K+1):
            MIN = min(MIN,X[rx]-X[lx])*(Ys[dy+K-1]-Ys[dy])
            
print(MIN)

Submission status: Wrong Answer

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

    
MIN = float("inf")
for lx in range(N-K+1):
    for rx in range(K+lx-1,N):
        Ys = sorted(Y[lx:rx+1])
        for dy in range(len(Ys)-K+1):
            MIN = min(MIN,X[rx]-X[lx])*(Ys[dy+K-1]-Ys[dy])
            
print(MIN)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
XY = [list(map(int, input().split())) for _ in range(N)]
XY.sort()
r = 10**20
for xi0 in range(N - K + 1):
  for xi1 in range(K + xi0 - 1, N):
    x = XY[xi1][0] - XY[xi0][0]
    XY_ys = sorted(XY, key=lambda a: a[1])
    for yi0 in range(len(XY_ys) - K + 1):
      y = XY_ys[yi0 + K - 1][1] - XY_ys[yi0][1]
      r = min(r, x * y)
print(r)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
xy = [list(map(int, input().split())) for _ in range(N)]
zxy = []
S = float("inf")
for x, y in xy:
    zxy.append([x-y, x, y])
zxy.sort()

for i in range(N+1-K):
    x1, y1 = zxy[i][1], zxy[i][2]
    x2, y2 = zxy[i + K - 1][1], zxy[i + K - 1][2]
    S = min(S, abs(y2 - y1) * abs(x2 - x1))

print(S)

Submission status: Wrong Answer

Solution code:
N, K = map(int,input().split())
X = []
Y = []
table = []
for i in range(N):
    x, y = map(int, input().split())
    X.append(x)
    Y.append(y)
    table.append((x,y))
S = 5*10**18
for y0 in Y:
    for y1 in Y:
        if y0 == y1:
            continue
        for x0 in X:
            for x1 in X:
                if x0 == x1:
                    continue
                x0, x1 = max(x0,x1), min(x0,x1)
                y0, y1 = max(y0,y1), min(y0,y1)
                cnt = 0
                for x,y in table:
                    if x1 <= x <= x0 and y1 <= y <= y0:
                        cnt += 1
                if cnt >= K:
                    S = min(S, (x0-x1)*(y0-y1))


print(S)

Submission status: Wrong Answer

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

xPrime = sorted(table,key=lambda x:x[0])
yPrime = sorted(table,key=lambda x:x[1])


S = (xPrime[-1][0]-xPrime[0][0]) * (yPrime[-1][1]-yPrime[0][1])

for i in range(N-K):
    x0 = xPrime[0]
    x1 = xPrime[-1]
    y0 = yPrime[0]
    y1 = yPrime[-1]

    xCopy = xPrime.copy()
    yCopy = yPrime.copy()
    xCopy.remove(x0)
    yCopy.remove(x0)
    a = (xCopy[-1][0]-xCopy[0][0]) * (yCopy[-1][1]-yCopy[0][1])
    
    xCopy = xPrime.copy()
    yCopy = yPrime.copy()
    xCopy.remove(x1)
    yCopy.remove(x1)
    b = (xCopy[-1][0]-xCopy[0][0]) * (yCopy[-1][1]-yCopy[0][1])

    xCopy = xPrime.copy()
    yCopy = yPrime.copy()
    xCopy.remove(y0)
    yCopy.remove(y0)
    c = (xCopy[-1][0]-xCopy[0][0]) * (yCopy[-1][1]-yCopy[0][1])
    
    xCopy = xPrime.copy()
    yCopy = yPrime.copy()
    xCopy.remove(y1)
    yCopy.remove(y1)
    d = (xCopy[-1][0]-xCopy[0][0]) * (yCopy[-1][1]-yCopy[0][1])

    if min(a,b,c,d)==a:
        xPrime.remove(x0)
        yPrime.remove(x0)
        S = a
    elif min(a,b,c,d)==b:
        xPrime.remove(x1)
        yPrime.remove(x1)
        S = b
    elif min(a,b,c,d)==c:
        xPrime.remove(y0)
        yPrime.remove(y0)
        S = c
    elif min(a,b,c,d)==d:
        xPrime.remove(y1)
        yPrime.remove(y1)
        S = d
    
print(S)

Submission status: Wrong Answer

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

xPrime = sorted(table,key=lambda x:x[0])
yPrime = sorted(table,key=lambda x:x[1])


S = (xPrime[-1][0]-xPrime[0][0]) * (yPrime[-1][1]-yPrime[0][1])

for i in range(N-K):
    x0 = xPrime[0]
    x1 = xPrime[-1]
    y0 = yPrime[0]
    y1 = yPrime[-1]

    xCopy = xPrime.copy()
    yCopy = yPrime.copy()
    xCopy.remove(x0)
    yCopy.remove(x0)
    a = (xCopy[-1][0]-xCopy[0][0]) * (yCopy[-1][1]-yCopy[0][1])
    
    xCopy = xPrime.copy()
    yCopy = yPrime.copy()
    xCopy.remove(x1)
    yCopy.remove(x1)
    b = (xCopy[-1][0]-xCopy[0][0]) * (yCopy[-1][1]-yCopy[0][1])

    xCopy = xPrime.copy()
    yCopy = yPrime.copy()
    xCopy.remove(y0)
    yCopy.remove(y0)
    c = (xCopy[-1][0]-xCopy[0][0]) * (yCopy[-1][1]-yCopy[0][1])
    
    xCopy = xPrime.copy()
    yCopy = yPrime.copy()
    xCopy.remove(y1)
    yCopy.remove(y1)
    d = (xCopy[-1][0]-xCopy[0][0]) * (yCopy[-1][1]-yCopy[0][1])

    if min(a,b,c,d)==a:
        xPrime.remove(x0)
        yPrime.remove(x0)
    elif min(a,b,c,d)==b:
        xPrime.remove(x1)
        yPrime.remove(x1)
    elif min(a,b,c,d)==c:
        xPrime.remove(y0)
        yPrime.remove(y0)
    elif min(a,b,c,d)==d:
        xPrime.remove(y1)
        yPrime.remove(y1)
        
    
print(S)

Submission status: Wrong Answer

Solution code:
import math
import copy
from operator import mul
from functools import reduce
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
# 一次元累積和
from itertools import accumulate
from bisect import bisect_left, bisect_right

import re
# import numpy as np
# from scipy.misc import comb

# 再帰がやばいとき
# import sys
# sys.setrecursionlimit(10**9)

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W

# 四方向: 右, 下, 左, 上
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
 
def i_inpl(): return int(input())
def l_inpl(): return list(map(int, input().split()))
def line_inpl(x): return [i_inpl() for _ in range(x)]

INF = int(1e18)
MOD = int(1e9)+7 # 10^9 + 7

# field[H][W]
def create_grid(H, W, value = 0):
    return [[ value for _ in range(W)] for _ in range(H)]

########

def main():
    N, K = l_inpl()
    xy = []
    for _ in range(N):
        xi, yi = l_inpl()
        xy.append([xi, yi])

    ans = INF
    xy.sort()

    for l, (xl, yl) in list(enumerate(xy))[:N-K+1]:
        for r, (xr, yr) in list(enumerate(xy))[l+K-1:]:
            ys = sorted([ y for _, y in xy[l:r+1]]) 
            for yd, yu in zip(ys, ys[K-1:]):
                # if yd <= yl and yd <= yr and yl <= yu and yr <= yu:
                if yd <= yl and yr <= yu:
                    ans = min(ans, (xr-xl) * (yu - yd))
    
    print(ans)
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import math
import copy
from operator import mul
from functools import reduce
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
# 一次元累積和
from itertools import accumulate
from bisect import bisect_left, bisect_right

import re
# import numpy as np
# from scipy.misc import comb

# 再帰がやばいとき
# import sys
# sys.setrecursionlimit(10**9)

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W

# 四方向: 右, 下, 左, 上
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
 
def i_inpl(): return int(input())
def l_inpl(): return list(map(int, input().split()))
def line_inpl(x): return [i_inpl() for _ in range(x)]

INF = int(1e18)
MOD = int(1e9)+7 # 10^9 + 7

# field[H][W]
def create_grid(H, W, value = 0):
    return [[ value for _ in range(W)] for _ in range(H)]

########

def main():
    N, K = l_inpl()
    xy = []
    for _ in range(N):
        xi, yi = l_inpl()
        xy.append([xi, yi])

    ans = INF
    xy.sort()

    for l, (xl, yl) in list(enumerate(xy))[:N-K+1]:
        for r, (xr, yr) in list(enumerate(xy))[l+K-1:]:
            ys = sorted([ y for _, y in xy[l:r+1]]) 
            for yd, yu in zip(ys, ys[K-1:]):
                if yd <= yl and yd <= yr and yl <= yu and yr <= yu:
                    ans = min(ans, (xr-xl) * (yu - yd))
    
    print(ans)
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import math
import copy
from operator import mul
from functools import reduce
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
# 一次元累積和
from itertools import accumulate
from bisect import bisect_left, bisect_right

import re
# import numpy as np
# from scipy.misc import comb

# 再帰がやばいとき
# import sys
# sys.setrecursionlimit(10**9)

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W

# 四方向: 右, 下, 左, 上
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
 
def i_inpl(): return int(input())
def l_inpl(): return list(map(int, input().split()))
def line_inpl(x): return [i_inpl() for _ in range(x)]

INF = int(1e18)
MOD = int(1e9)+7 # 10^9 + 7

# field[H][W]
def create_grid(H, W, value = 0):
    return [[ value for _ in range(W)] for _ in range(H)]

########

def main():
    N, K = l_inpl()
    x, y = [], []
    for _ in range(N):
        xi, yi = l_inpl()
        x.append(xi)
        y.append(yi)

    ans = INF
    for xi in range(N):
        for xj in range(N):
            for yi in range(N):
                for yj in range(N):
                    x_l, x_r = x[xi], x[xj]
                    y_u, y_d = y[yi], y[yj]
                    if x_l < x_r and y_d < y_u and xi != xj and yi != yj:
                        cnt = 0
                        for i in range(N):
                            if x_l <= x[i] <= x_r and y_d <= y[i] <= y_u:
                                cnt += 1
                        if cnt >= K:
                            ans = min((x_r - x_l) * (y_u - y_d), ans)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import math
import copy
from operator import mul
from functools import reduce
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
# 一次元累積和
from itertools import accumulate
from bisect import bisect_left, bisect_right

import re
# import numpy as np
# from scipy.misc import comb

# 再帰がやばいとき
# import sys
# sys.setrecursionlimit(10**9)

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W

# 四方向: 右, 下, 左, 上
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
 
def i_inpl(): return int(input())
def l_inpl(): return list(map(int, input().split()))
def line_inpl(x): return [i_inpl() for _ in range(x)]

INF = int(1e18)
MOD = int(1e9)+7 # 10^9 + 7

# field[H][W]
def create_grid(H, W, value = 0):
    return [[ value for _ in range(W)] for _ in range(H)]

########

def main():
    N, K = l_inpl()
    x, y = [], []
    for _ in range(N):
        xi, yi = l_inpl()
        x.append(xi)
        y.append(yi)

    ans = INF
    for xi in range(N):
        for xj in range(N):
            for yi in range(N):
                for yj in range(N):
                    x_l, x_r = x[xi], x[xj]
                    y_u, y_d = y[yi], y[yj]
                    if x_l < x_r and y_d < y_u:
                        cnt = 0
                        for i in range(N):
                            if x_l <= x[i] <= x_r and y_d <= y[i] <= y_u:
                                cnt += 1
                        if cnt >= K:
                            ans = min((x_r - x_l) * (y_u - y_d), ans)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import math
import copy
from operator import mul
from functools import reduce
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
# 一次元累積和
from itertools import accumulate
from bisect import bisect_left, bisect_right

import re
# import numpy as np
# from scipy.misc import comb

# 再帰がやばいとき
# import sys
# sys.setrecursionlimit(10**9)

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W

# 四方向: 右, 下, 左, 上
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
 
def i_inpl(): return int(input())
def l_inpl(): return list(map(int, input().split()))
def line_inpl(x): return [i_inpl() for _ in range(x)]

INF = int(1e18)
MOD = int(1e9)+7 # 10^9 + 7

# field[H][W]
def create_grid(H, W, value = 0):
    return [[ value for _ in range(W)] for _ in range(H)]

########

def main():
    N, K = l_inpl()
    x, y = [], []
    for _ in range(N):
        xi, yi = l_inpl()
        x.append(xi)
        y.append(yi)

    ans = INF
    for xi in range(N):
        for xj in range(N):
            for yi in range(N):
                for yj in range(N):
                    x_l, x_r = x[xi], x[xj]
                    y_u, y_d = y[yi], y[yj]
                    if x_l < x_r and y_d < y_u:
                        cnt = 0
                        for i in range(N):
                            if x_l <= x[i] <= x_r and y_d <= y[i] <= y_u:
                                cnt += 1
                        if cnt >= K:
                            ans = (x_r - x_l) * (y_u - y_d)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
INF = float("inf")


def solve(N: int, K: int, x: "List[int]", y: "List[int]"):
    sx = sorted(x)
    sy = sorted(y)

    m = INF
    for i, x1 in enumerate(sx):
        for j, y1 in enumerate(sy):
            # 始点を固定
            for x2 in sx[i:]:
                for y2 in sy[j:]:
                    # 終点を固定
                    counter = 0
                    for xx, yy in zip(x, y):
                        if (x1 <= xx <= x2) and (y1 <= yy <= y2):
                            counter += 1
                    if counter >= K:
                        area = abs(y2-y1)*abs(x2-x1)
                        if area < m:
                            m = area
    print(area)
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    x = [int()] * (N)  # type: "List[int]"
    y = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        x[i] = int(next(tokens))
        y[i] = int(next(tokens))
    solve(N, K, x, y)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
INF = float("inf")


def solve(N: int, K: int, x: "List[int]", y: "List[int]"):
    sx = sorted(x)
    sy = sorted(y)
    ks = [[0]*N for _ in range(N)]

    m = INF
    for i, x1 in enumerate(sx):
        for j, y1 in enumerate(sy):
            # 始点を固定
            for x2 in sx[i+1:]:
                for y2 in sy[j+1:]:
                    # 終点を固定
                    counter = 0
                    for xx, yy in zip(x, y):
                        if (x1 <= xx <= x2) and (y1 <= yy <= y2):
                            counter += 1
                    if counter >= K:
                        area = (y2-y1)*(x2-x1)
                        if area < m:
                            m = area
    print(area)
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    x = [int()] * (N)  # type: "List[int]"
    y = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        x[i] = int(next(tokens))
        y[i] = int(next(tokens))
    solve(N, K, x, y)


if __name__ == '__main__':
    main()