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 sys
from collections import *
import heapq
import math
import bisect
import copy
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

n,k=map(int,input().split())
xy=[list(map(int,input().split())) for i in range(n)]
xy.sort()
lst=[0]*n
lst2=[0]*n
for i in range(n):
    lst[i]=xy[i][0]
    lst2[i]=xy[i][1]
# print(lst)
# print(lst2)
per=list(combinations(lst2,2))
# print(per)
ans=float('inf')
for i in range(n-k+1):
    xl,xr=lst[i],lst[i+k-1]
    if xl==xr:
        continue
    for j in range(len(per)):
        yl,yr=min(per[j]),max(per[j])
        if yl==yr:
            continue
        cnt=0
        for l in range(n):
            x,y=xy[l]
            if xl<=x<=xr and yl<=y<=yr:
                cnt+=1
        if cnt>=k:
            ans=min(ans,(xr-xl)*(yr-yl))
print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby
    #from itertools import product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

    n,k = map(int, input().split())
    xy = [list(map(int, input().split())) for _ in range(n)]
    x = sorted(xy, key=lambda a: a[0])
    y = sorted(xy, key=lambda a: a[1])

    res = 10**20
    for l in range(n):
        for r in range(l+1, n):
            for b in range(n):
                for t in range(b+1, n):
                    cnt = 0
                    for vx, vy in xy:
                        if x[l][0] <= vx <= x[r][0] and y[b][1] <= vy <= y[t][1]:
                            cnt += 1
                        if cnt >= k:
                            res = min(res, (x[r][0]-x[l][0])*(y[t][1]-y[b][1]))
                            break
    print(res)

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby
    #from itertools import product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

    n,k = map(int, input().split())
    xy = [list(map(int, input().split())) for _ in range(n)]
    x = sorted(xy, key=lambda a: a[0])
    y = sorted(xy, key=lambda a: a[1])
    left, right, bottom, top = 0, n-1, 0, n-1

    for _ in range(n-k):
        l = (x[left+1][0]-x[left][0])*(y[top][1]-y[bottom][1])
        r = (x[right][0]-x[right-1][0])*(y[top][1]-y[bottom][1])
        b = (y[bottom+1][1]-y[bottom][1])*(x[right][0]-x[left][0])
        u = (y[top][1]-y[top-1][1])*(x[right][0]-x[left][0])
        best = max(l, r, b, u)
        if best == l:
            if x[left][1] == y[bottom][1]:
                bottom += 1
            if x[left][1] == y[top][1]:
                top -= 1
            left += 1
        elif best == r:
            if x[right][1] == y[bottom][1]:
                bottom += 1
            if x[right][1] == y[top][1]:
                top -= 1
            right -= 1
        elif best == b:
            if y[bottom][0] == x[left][0]:
                left += 1
            if y[bottom][0] == x[right][0]:
                right -= 1
            bottom += 1
        else:
            if y[top][0] == x[left][0]:
                left += 1
            if y[top][0] == x[right][0]:
                right -= 1
            top -= 1
    print((x[right][0]-x[left][0])*(y[top][1]-y[bottom][1]))

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby
    #from itertools import product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

    n,k = map(int, input().split())
    xy = [list(map(int, input().split())) for _ in range(n)]
    x = sorted(xy, key=lambda a: a[0])
    y = sorted(xy, key=lambda a: a[1])
    left, right, bottom, top = 0, n-1, 0, n-1

    for _ in range(n-k):
        l = (x[left+1][0]-x[left][0])*(y[top][1]-y[bottom][1])
        r = (x[right][0]-x[right-1][0])*(y[top][1]-y[bottom][1])
        b = (y[bottom+1][1]-y[bottom][1])*(x[right][0]-x[left][0])
        u = (y[top][1]-y[top-1][1])*(x[right][0]-x[left][0])
        best = max(l, r, b, u)
        if best == l:
            if x[left][1] == y[bottom][1]:
                bottom += 1
            if x[left][1] == y[top][1]:
                top -= 1
            left += 1
        elif best == r:
            if x[right][1] == y[bottom][1]:
                bottom += 1
            if x[right][1] == y[top][1]:
                top -= 1
            right -= 1
        elif best == b:
            if x[bottom][0] == y[left][0]:
                left += 1
            if x[bottom][0] == y[right][0]:
                right -= 1
            bottom += 1
        else:
            if x[top][0] == y[left][0]:
                left += 1
            if x[top][0] == y[right][0]:
                right -= 1
            top -= 1
    print((x[right][0]-x[left][0])*(y[top][1]-y[bottom][1]))

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby
    #from itertools import product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

    n,k = map(int, input().split())
    xy = [list(map(int, input().split())) for _ in range(n)]
    x = sorted(xy, key=lambda a: a[0])
    y = sorted(xy, key=lambda a: a[1])
    left, right, bottom, top = 0, n-1, 0, n-1

    for _ in range(n-k):
        l = (x[left+1][0]-x[left][0])*(y[top][1]-y[bottom][1])
        r = (x[right][0]-x[right-1][0])*(y[top][1]-y[bottom][1])
        b = (y[bottom+1][1]-y[bottom][1])*(x[right][0]-x[left][0])
        u = (y[top][1]-y[top-1][1])*(x[right][0]-x[left][0])
        best = max(l, r, b, u)
        if best == l:
            if x[left][1] == y[bottom][1]:
                bottom += 1
            if x[left][1] == y[top][1]:
                top -= 1
            left += 1
        elif best == r:
            if x[right][1] == y[bottom][1]:
                bottom += 1
            if x[right][1] == y[top][1]:
                top -= 1
            right -= 1
        elif best == bottom:
            if x[bottom][0] == y[left][0]:
                left += 1
            if x[bottom][0] == y[right][0]:
                right -= 1
            bottom += 1
        else:
            if x[top][0] == y[left][0]:
                left += 1
            if x[top][0] == y[right][0]:
                right -= 1
            top -= 1
    print((x[right][0]-x[left][0])*(y[top][1]-y[bottom][1]))

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#075_D
n, k = map(int, input().split())
xy = [tuple(map(int, input().split())) for _ in range(n)]
xy.sort()

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

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
x=[0]*n
y=[0]*n
for i in range(n):
  x[i],y[i]=map(int,input().split())
ans=4*(10**18)
for i in range(n):
  for j in range(n):
    for l in range(n):
      for m in range(n):
        minX=min(x[i],x[j],x[l],x[m])
        maxX=max(x[i],x[j],x[l],x[m])
        minY=min(y[i],y[j],y[l],y[m])
        maxY=max(y[i],y[j],y[l],y[m])
        if minX==maxX or minY==maxY:
          continue
        cnt=0
        for i in range(n):
          if minX<=x[i]<=maxX and minY<=y[i]<=maxY:
            cnt+=1
        if cnt>=k:
          ans=min(ans,(maxX-minX)*(maxY-minY))
print(ans)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
x=[0]*n
y=[0]*n
for i in range(n):
  x[i],y[i]=map(int,input().split())
ans=4*10**18
for i in range(n):
  for j in range(n):
    for l in range(n):
      for m in range(n):
        minX=min(x[i],x[j],x[l],x[m])
        maxX=max(x[i],x[j],x[l],x[m])
        minY=min(y[i],y[j],y[l],y[m])
        maxY=max(y[i],y[j],y[l],y[m])
        if minX==maxX or minY==maxY:
          continue
        cnt=0
        for i in range(n):
          if minX<=x[i]<=maxX and minY<=y[i]<=maxY:
            cnt+=1
        if cnt>=k:
          ans=min(ans,(maxX-minX)*(maxY-minY))
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline


def main():
    n, k = map(int, input().split())
    X, Y = [], []
    for _ in range(n):
        x, y = map(int, input().split())
        X.append(x)
        Y.append(y)
    x_min, x_max = min(X), max(X)
    y_min, y_max = min(Y), max(Y)
    res = abs(x_max - x_min) * abs(y_max - y_min)

    for x1 in range(n):
        for x2 in range(x1 + 1, n):
            for y1 in range(n):
                for y2 in range(y1 + 1, n):
                    lx, rx = X[x1], X[x2]
                    by, uy = Y[y1], Y[y2]
                    cnt = 0
                    for i in range(n):
                        if lx <= X[i] <= rx and by <= Y[i] <= uy:
                            cnt += 1
                    if cnt >= k:
                        res = min(res, (rx - lx) * (uy - by))
    print(res)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    n, k = map(int, input().split())
    X, Y = [], []
    for _ in range(n):
        x, y = map(int, input().split())
        X.append(x)
        Y.append(y)
    x_min, x_max = min(X), max(X)
    y_min, y_max = min(Y), max(Y)
    res = abs(x_max - x_min) * abs(y_max - y_min)

    for x1 in range(n):
        for x2 in range(n):
            for y1 in range(n):
                for y2 in range(n):
                    lx, rx = X[x1], X[x2]
                    by, uy = X[y1], X[y2]
                    cnt = 0
                    for i in range(n):
                        if lx <= X[i] <= rx and by <= Y[i] <= uy:
                            cnt += 1
                    if cnt >= k:
                        res = min(res, abs(rx - lx) * abs(uy - by))
    print(res)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
pos = sorted([tuple(map(int, input().split())) for _ in range(N)], key=lambda x: x[0])
ans = 10 ** 37
for x in range(N-K+1):
    max_y = (-1) * (10 ** 9 + 1)
    min_y = 10 ** 9 + 1
    for i in range(K):
        y = pos[x+i][1]
        max_y = max(max_y, y)
        min_y = min(min_y, y)
    min_area = (pos[x+K-1][0] - pos[x][0]) * (max_y - min_y)
    ans = min(ans, min_area)
print(ans)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
pos = sorted([tuple(map(int, input().split())) for _ in range(N)], key=lambda x: x[0])
ans = 10 ** 37
for i in range(N-K+1):
    max_y = (-1) * 10 ** 9 - 1
    min_y = 10 ** 9 + 1
    for j in range(K):
        y = pos[i+j][1]
        max_y = max(max_y, y)
        min_y = min(min_y, y)
    ans = min(ans, (pos[i+K-1][0] - pos[i][0]) * (max_y - min_y))
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions
from decimal import Decimal
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n,K = inpl()
a = [inpl() for _ in range(n)]
res = INF
for i in range(n-1):
    for j in range(i+1,n):
        l = a[i][0]
        r = a[j][0]
        b = [a[i],a[j]]
        cnt = 2
        for _ in range(n):
            if _ == i or _ == j:
                continue
            if l < a[_][0] < r:
                cnt += 1
                b += [a[_]]
        if cnt < K: continue
        b.sort(key=lambda x:x[1])
        for _ in range(cnt-K+1):
            u = max(x[1] for x in b[_:_+K])
            d = min(x[1] for x in b[_:_+K])
            res = min(res, (r-l)*(u-d))
print(res)

Submission status: Wrong Answer

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions
from decimal import Decimal
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n,K = inpl()
a = [inpl() for _ in range(n)]
res = INF
for i in range(n-1):
    for j in range(i+1,n):
        l = a[i][0]
        r = a[j][0]
        b = [a[i],a[j]]
        cnt = 2
        for _ in range(n):
            if _ == i or _ == j:
                continue
            if l < a[_][0] < r:
                cnt += 1
                b += [a[_]]
        if cnt < j: continue
        b.sort(key=lambda x:x[1])
        for _ in range(cnt-K+1):
            u = max(x[1] for x in b[_:_+K])
            d = min(x[1] for x in b[_:_+K])
            res = min(res, (r-l)*(u-d))
print(res)

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.buffer.readline
    N, K = (int(i) for i in input().split())
    XY = [[int(i) for i in input().split()] for j in range(N)]
    ans = 5*10**19
    XY.sort()
    for i in range(N-K+1):
        xs = [x for x, y in XY[i:i+K]]
        ys = [y for x, y in XY[i:i+K]]
        x = max(xs) - min(xs)
        y = max(ys) - min(ys)
        ans = min(ans, x*y)
    XY.sort(key=lambda p: p[1])
    for i in range(N-K+1):
        xs = [x for x, y in XY[i:i+K]]
        ys = [y for x, y in XY[i:i+K]]
        x = max(xs) - min(xs)
        y = max(ys) - min(ys)
        ans = min(ans, x*y)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
pos = sorted([tuple(map(int, input().split())) for _ in range(N)], key=lambda x: x[0])
ans = 10 ** 36 + 1
for i in range(N-K+1):
    max_y = (-1) * 10 ** 9 - 1
    min_y = 10 ** 9 + 1
    for j in range(K):
        y = pos[i+j][1]
        max_y = max(max_y, y)
        min_y = min(min_y, y)
    ans = min(ans, (pos[i+K-1][0] - pos[i][0]) * (max_y - min_y))
print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.buffer.readline
    N, K = (int(i) for i in input().split())
    XY = [[int(i) for i in input().split()] for j in range(N)]
    XY.sort()
    ans = 5*10**18
    for i in range(N-K+1):
        xs = [x for x, y in XY[i:i+K]]
        ys = [y for x, y in XY[i:i+K]]
        x = max(xs) - min(xs)
        y = max(ys) - min(ys)
        ans = min(ans, x*y)
    XY.sort(key=lambda p: p[1])
    for i in range(N-K+1):
        xs = [x for x, y in XY[i:i+K]]
        ys = [y for x, y in XY[i:i+K]]
        x = max(xs) - min(xs)
        y = max(ys) - min(ys)
        ans = min(ans, x*y)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.buffer.readline
    N, K = (int(i) for i in input().split())
    XY = [[int(i) for i in input().split()] for j in range(N)]
    XY.sort()
    ans = 5*10**18
    for i in range(N-K+1):
        x = XY[i+K-1][0] - XY[i][0]
        ys = [y for x, y in XY[i:i+K]]
        y = max(ys) - min(ys)
        ans = min(ans, x*y)
    from operator import itemgetter
    XY.sort(key=itemgetter(1))
    for i in range(N-K+1):
        y = XY[i+K-1][1] - XY[i][1]
        xs = [x for x, y in XY[i:i+K]]
        x = max(xs) - min(xs)
        ans = min(ans, x*y)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    N, K = (int(i) for i in input().split())
    XY = [[int(i) for i in input().split()] for j in range(N)]
    XY.sort()
    ans = 5*10**18
    for i in range(N-K+1):
        x = XY[i+K-1][0] - XY[i][0]
        ys = [y for x, y in XY[i:i+K]]
        y = max(ys) - min(ys)
        ans = min(ans, x*y)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions
from decimal import Decimal
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n,k = inpl()
a = [inpl() for _ in range(n)]
res = INF
for i in range(2):
    a.sort(key=lambda x:x[i])
    for j in range(n-k+1):
        r = max(x[0] for x in a[j:j+k])
        l = min(x[0] for x in a[j:j+k])
        u = max(x[1] for x in a[j:j+k])
        d = min(x[1] for x in a[j:j+k])
        res = min(res, (r-l)*(u-d))
print(res)

Submission status: Wrong Answer

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions
from decimal import Decimal
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n,k = inpl()
a = [inpl() for _ in range(n)]
xa = sum(x[0] for x in a)/n
ya = sum(x[1] for x in a)/n
# print(xa,ya)
for i,z in enumerate(a):
    x,y = z
    tmp = math.sqrt(abs(xa-x)**2 + abs(ya-y)**2)
    a[i] += [tmp]
a.sort(key=lambda x:x[2])
# print(a)
b = a[:k]
b.sort()
p = b[-1][0] - b[0][0]
b.sort(key=lambda x:x[1])
q = b[-1][1] - b[0][1]
print(p*q)

Submission status: Wrong Answer

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

ans = float('inf')
for i in range(N - 1):
    for j in range(i + K - 1, N):
        x = P[j][0] - P[i][0]
        if x == 0:
            continue

        Q = P[i: j + 1]
        Q.sort(key=lambda q: q[1])
        y = Q[-1][1] - Q[0][1]
        for k in range(0, len(Q) - K):
            for l in range(k + K - 1, len(Q)):
                ny = Q[l][1] - Q[k][1]
                if ny == 0:
                    continue
                y = min(y, ny)
        ans = min(ans, x * y)

print(ans)

Submission status: Wrong Answer

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

ans = float('inf')
for i in range(N - 1):
    for j in range(i + K - 1, N):
        x = P[j][0] - P[i][0]

        Q = P[i: j + 1]
        Q.sort(key=lambda q: q[1])
        y = Q[-1][1] - Q[0][1]
        for k in range(K, len(Q)):
            ny = Q[k][1] - Q[k - K][1]
            y = min(y, ny)
        ans = min(ans, x * y)

print(ans)

Submission status: Wrong Answer

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

for i in range(N - 1):
    for j in range(i + K - 1, N):
        x = P[j][0] - P[i][0]

        Q = P[i: j + 1]
        Q.sort(key=lambda x: x[1])
        y = Q[-1][1] - Q[0][1]
        for k in range(K, len(Q)):
            ny = Q[k - K][1] - Q[k][1]
            y = min(y, ny)

print(x * y)

Submission status: Wrong Answer

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

ans = float('inf')
for i in range(N - 1):
    for j in range(i + 1, N):
        (x1, y1), (x2, y2) = P[i], P[j]
        if x1 > x2:
            x1, x2 = x2, x1
        if y1 > y2:
            y1, y2 = y2, y1
        cnt = 0
        for k in range(i + 1, j):
            x3, y3 = P[k]
            if x1 <= x3 <= x2 and (y1 <= y3 <= y2):
                cnt += 1
        if cnt >= K - 2:
            ans = min(ans, abs((x2 - x1) * (y2 - y1)))

if N >= 3:
    for i in range(N - 2):
        for j in range(i + 1, N - 1):
            for k in range(j + 1, N):
                (xi, yi), (xj, yj), (xk, yk) = P[i], P[j], P[k]
                x1 = min([xi, xj, xk])
                x2 = max([xi, xj, xk])
                y1 = min(([yi, yj, yk]))
                y2 = max(([yi, yj, yk]))
                cnt = 0
                for l in range(i + 1, k):
                    x3, y3 = P[l]
                    if x1 <= x3 <= x2 and (y1 <= y3 <= y2):
                        cnt += 1
                if cnt >= K - 2:
                    ans = min(ans, abs((x2 - x1) * (y2 - y1)))

print(ans)

Submission status: Wrong Answer

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

ans=10**25
for i in range(0,N-K+1):
    W=X[i+K-1]-X[i]
    H=max(Y[i:i+K])-min(Y[i:i+K])
    test=W*H
    if ans>test:
        ans=test

print(ans)

Submission status: Wrong Answer

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


def init_min(init_min_val):
    #set_val
    for i in range(n):
        seg_min[i+num_min-1]=init_min_val[i]
    #built
    for i in range(num_min-2,-1,-1) :
        seg_min[i]=min(seg_min[2*i+1],seg_min[2*i+2])

def update_min(k,x):
    k += num_min-1
    seg_min[k] = x
    while k:
        k = (k-1)//2
        seg_min[k] = min(seg_min[k*2+1],seg_min[k*2+2])

def query_min(p,q):
    if q<=p:
        return ide_ele_min
    p += num_min-1
    q += num_min-2
    res=ide_ele_min
    while q-p>1:
        if p&1 == 0:
            res = min(res,seg_min[p])
        if q&1 == 1:
            res = min(res,seg_min[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = min(res,seg_min[p])
    else:
        res = min(min(res,seg_min[p]),seg_min[q])
    return res

#####単位元######
ide_ele_min = 10**10

#num_min:n以上の最小の2のべき乗
num_min =2**(n-1).bit_length()
seg_min=[ide_ele_min]*2*num_min

def init_max(init_max_val):
    #set_val
    for i in range(n):
        seg_max[i+num_max-1]=init_max_val[i]
    #built
    for i in range(num_max-2,-1,-1) :
        seg_max[i]=max(seg_max[2*i+1],seg_max[2*i+2])

def update_max(k,x):
    k += num_max-1
    seg_max[k] = x
    while k:
        k = (k-1)//2
        seg_max[k] = max(seg_max[k*2+1],seg_max[k*2+2])

def query_max(p,q):
    if q<=p:
        return ide_ele_max
    p += num_max-1
    q += num_max-2
    res=ide_ele_max
    while q-p>1:
        if p&1 == 0:
            res = max(res,seg_max[p])
        if q&1 == 1:
            res = max(res,seg_max[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = max(res,seg_max[p])
    else:
        res = max(max(res,seg_max[p]),seg_max[q])
    return res

#####単位元######
ide_ele_max = -10**10

#num_max:n以上の最小の2のべき乗
num_max =2**(n-1).bit_length()
seg_max=[ide_ele_max]*2*num_max

ans=10**20
init_min(Y)
init_max(Y)
for i in range(0,n-K+1):
    w=X[K-1+i]-X[i]
    h=query_max(i,K+i)-query_min(i,K+i)
    if ans>h*w:
        ans=h*w
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
n,k = map(int,input().split())
dots = []
for _ in range(n):
    x,y = map(int,input().split())
    dots.append((x,y))
res = float('inf')

for p in dots:
    for q,r in itertools.permutations(dots, 2):
        if q==p or r==p:
            continue
        x_mn, x_mx = min(p[0], q[0], r[0]), max(p[0], q[0], r[0])
        y_mn, y_mx = min(p[1], q[1], r[1]), max(p[1], q[1], r[1])
        cnt = 0
        for dot in dots:
            if x_mn<=dot[0]<=x_mx and y_mn<=dot[1]<=y_mx:
                cnt += 1
        if cnt >= k:
            res = min(res, (x_mx-x_mn)*(y_mx-y_mn))
print(res)

Submission status: Wrong Answer

Solution code:
import itertools
n,k = map(int,input().split())
dots = []
for _ in range(n):
    x,y = map(int,input().split())
    dots.append((x,y))
res = float('inf')

for p in dots:
    for q,r in itertools.permutations(dots, 2):
        if q==p or r==p:
            continue
        x_mn, x_mx = min(p[0], q[0]), max(p[0], q[0])
        y_mn, y_mx = min(p[1], r[1]), max(p[1], r[1])
        cnt = 0
        for dot in dots:
            if x_mn<=dot[0]<=x_mx and y_mn<=dot[1]<=y_mx:
                cnt += 1
        if cnt >= k:
            res = min(res, (x_mx-x_mn)*(y_mx-y_mn))
print(res)

Submission status: Wrong Answer

Solution code:
import itertools
n,k = map(int,input().split())
dots = []
for _ in range(n):
    x,y = map(int,input().split())
    dots.append((x,y))
res = float('inf')
for l,r in itertools.combinations(dots, 2):
    if l[0]==r[0] or l[1]==r[1]:
        continue
    x_mn = min(l[0], r[0])
    x_mx = max(l[0], r[0])
    y_mn = min(l[1], r[1])
    y_mx = max(l[1], r[1])
    cnt = 0
    for x,y in dots:
        if x_mn<=x<=x_mx and y_mn<=y<=y_mx:
            cnt += 1
    if cnt>=k:
        res = min(res, (x_mx-x_mn)*(y_mx-y_mn))
print(res)

Submission status: Wrong Answer

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

res = float('inf')
for v in itertools.combinations(dots, 4):
    x_max, x_min = 0, float('inf')
    y_max, y_min = 0, float('inf')
    for x,y in v:
        x_max = max(x_max, x)
        x_min = min(x_min, x)
        y_max = max(y_max, y)
        y_min = min(y_min, y)
    cnt = 0
    
    for x_, y_ in dots:
        if x_min<=x_<=x_max and y_min<=y_<=y_max:
            cnt += 1
    if k <= cnt:
        res = min(res, (x_max-x_min)*(y_max-y_min))
print(res)

Submission status: Wrong Answer

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

res = float('inf')
for v in itertools.combinations(dots, 4):
    x_max, x_min = 0, float('inf')
    y_max, y_min = 0, float('inf')
    for x,y in v:
        x_max = max(x_max, x)
        x_min = min(x_min, x)
        y_max = max(y_max, y)
        y_min = min(y_min, y)
    
    cnt = 4
    
    for x_, y_ in dots:
        if (x_, y_) not in v:
            if x_min<=x_<=x_max and y_min<=y_<=y_max:
                cnt += 1
    if k <= cnt:
        res = min(res, (x_max-x_min)*(y_max-y_min))
print(res)

Submission status: Wrong Answer

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

res = float('inf')
for v in itertools.combinations(dots, k):
    x_max, x_min = 0, float('inf')
    y_max, y_min = 0, float('inf')
    for x, y in v:
        x_max = max(x_max, x)
        x_min = min(x_min, x)
        y_max = max(y_max, y)
        y_min = min(y_min, y)
    res = min(res, (x_max-x_min)*(y_max-y_min))
print(res)

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):
    for j in range(i,n):
        xy_tmp = xy[i:j+1]
        if len(xy_tmp) >= k:
            l1 = xy_tmp[0][0]
            r1 = xy_tmp[-1][0]
            xy_tmp.sort(key = lambda x: x[1])
            ans = min(ans, (r1-l1) * (xy_tmp[-1][1] - xy_tmp[0][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):
    l = i
    r = i+k
    xy_tmp = xy[l:r]
    l1 = xy_tmp[0][0]
    r1 = xy_tmp[-1][0]
    xy_tmp.sort(key = lambda x: x[1])
    ans = min(ans, (r1-l1) * (xy_tmp[-1][1] - xy_tmp[0][1]))

print(ans)

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
l = [list(map(int,input().split())) for i in range(n)]
l.sort()
ans = float("INF")

for i in range(n-k+1):
    count = [(0,l[i][0],l[i][1])]
    for j in range(i+1,n):
        d = (l[j][0]-l[i][0])**2+(l[j][1]-l[i][1])**2
        count.append((d,l[j][0],l[j][1]))
    count.sort()
    wl = hl = 10**9
    wh = hh = -10**9
    for j in range(k):
        wl = min(wl,count[j][1])
        wh = max(wh,count[j][1])
        hl = min(hl,count[j][2])
        hh = max(hh,count[j][2])
    ans = min(ans,(hh-hl)*(wh-wl))
print(ans)

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
l = [list(map(int,input().split())) for i in range(n)]
l.sort()
ans = float("INF")

for i in range(n-k+1):
    hh = -10**9
    hl = 10**9
    for j in range(i,i+k):
        hh = max(hh,l[j][1])
        hl = min(hl,l[j][1])
    ans = min(ans,(hh-hl)*(l[i+k-1][0]-l[i][0]))
l.sort(key = lambda x: x[1])
for i in range(n-k+1):
    wh = -10**9
    wl = 10**9
    for j in range(i,i+k):
        wh = max(wh,l[j][0])
        wl = min(wl,l[j][0])
    ans = min(ans,(wh-wl)*(l[i+k-1][1]-l[i][1]))
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
INF = 10**20
MOD = 10**9 + 7
from bisect import insort_left

def main():
    n,k = map(int,input().split())
    XY = [tuple(map(int,input().split())) for _ in range(n)]  
    XY.sort(key = lambda x:x[0])
    
    ans = INF
    for l in range(n - k + 1):
        Y = [XY[i][1] for i in range(l,l + k - 1)]
        Y.sort()
        dif = -1
        for r in range(l + k - 1, n):
            dif += 1
            insort_left(Y,XY[r][1])
            w = Y[-1] - Y[0]
            for i in range(dif):
                w = min(w, Y[i + k - 1] - Y[i])
            ans = min(ans, w * (XY[r][0] - XY[l][0]))
    
    print(ans)   

if __name__=='__main__':
    main()