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
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
n,g = map(int,readline().split())
XY = []
for i in range(n):
    XY.append(list(map(int,readline().split())))
ans = 10**32

if g == 2:
    for i in range(n):
        for j in range(i+1,n):
            hidarisita = (min(XY[i][0],XY[j][0]),min(XY[i][1],XY[j][1]))
            migiue = (max(XY[i][0],XY[j][0]),max(XY[i][1],XY[j][1]))
        ans = min(ans,abs((migiue[0]-hidarisita[0])*(migiue[1]-hidarisita[1])))

elif g == 3:
    for i in range(n):
        for j in range(i+1,n):
            for k in range(j+1,n):
                hidarisita = (min(XY[i][0],XY[j][0],XY[k][0]),
                min(XY[i][1],XY[j][1],XY[k][1]))
                migiue = (max(XY[i][0],XY[j][0],XY[k][0]),
                max(XY[i][1],XY[j][1],XY[k][1]))
            ans = min(ans,abs((migiue[0]-hidarisita[0])*(migiue[1]-hidarisita[1])))
else:

    for i in range(n):
        for j in range(i+1,n):
            for k in range(j+1,n):
                for l in range(k+1,n):
                    hidarisita = (min(XY[i][0],XY[j][0],XY[k][0],XY[l][0]),
                    min(XY[i][1],XY[j][1],XY[k][1],XY[l][1]))
                    migiue = (max(XY[i][0],XY[j][0],XY[k][0],XY[l][0]),
                    max(XY[i][1],XY[j][1],XY[k][1],XY[l][1]))

                    res = 1
                    for m in range(n):
                        if hidarisita[0] <= XY[m][0] <= migiue[0] and \
                            hidarisita[1] <= XY[m][1] <= migiue[1]:
                            res += 1

                    if res >= g:
                        ans = min(ans,abs((migiue[0]-hidarisita[0])*(migiue[1]-hidarisita[1])))

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
n,g = map(int,readline().split())
XY = []
for i in range(n):
    XY.append(list(map(int,readline().split())))
ans = 10**32

if g == 2:
    for i in range(n):
        for j in range(i+1,n):
            hidarisita = (min(XY[i][0],XY[j][0]),min(XY[i][1],XY[j][1]))
            migiue = (max(XY[i][0],XY[j][0]),max(XY[i][1],XY[j][1]))
        ans = min(ans,abs((migiue[0]-hidarisita[0])*(migiue[1]-hidarisita[1])))

elif g == 3:
    for i in range(n):
        for j in range(i+1,n):
            for k in range(j+1,n):
                hidarisita = (min(XY[i][0],XY[j][0],XY[k][0]),
                min(XY[i][1],XY[j][1],XY[k][1]))
                migiue = (max(XY[i][0],XY[j][0],XY[k][0]),
                max(XY[i][1],XY[j][1],XY[k][1]))
            ans = min(ans,abs((migiue[0]-hidarisita[0])*(migiue[1]-hidarisita[1])))
else:

    for i in range(n):
        for j in range(i+1,n):
            for k in range(j+1,n):
                for l in range(k+1,n):
                    hidarisita = (min(XY[i][0],XY[j][0],XY[k][0],XY[l][0]),
                    min(XY[i][1],XY[j][1],XY[k][1],XY[l][1]))
                    migiue = (max(XY[i][0],XY[j][0],XY[k][0],XY[l][0]),
                    max(XY[i][1],XY[j][1],XY[k][1],XY[l][1]))

                    res = 1
                    for m in range(i+1,n):
                        if hidarisita[0] <= XY[m][0] <= migiue[0] and \
                            hidarisita[1] <= XY[m][1] <= migiue[1]:
                            res += 1

                    if res >= g:
                        ans = min(ans,abs((migiue[0]-hidarisita[0])*(migiue[1]-hidarisita[1])))

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
n,g = map(int,readline().split())
XY = []
for i in range(n):
    XY.append(list(map(int,readline().split())))
ans = 10**32

if g == 2:
    for i in range(n):
        for j in range(i+1,n):
            hidarisita = (min(XY[i][0],XY[j][0]),min(XY[i][1],XY[j][1]))
            migiue = (max(XY[i][0],XY[j][0]),max(XY[i][1],XY[j][1]))
        ans = min(ans,(migiue[0]-hidarisita[0])*(migiue[1]-hidarisita[1]))

elif g == 3:
    for i in range(n):
        for j in range(i+1,n):
            for k in range(j+1,n):
                hidarisita = (min(XY[i][0],XY[j][0],XY[k][0]),
                min(XY[i][1],XY[j][1],XY[k][1]))
                migiue = (max(XY[i][0],XY[j][0],XY[k][0]),
                max(XY[i][1],XY[j][1],XY[k][1]))
            ans = min(ans,(migiue[0]-hidarisita[0])*(migiue[1]-hidarisita[1]))
else:

    for i in range(n):
        for j in range(i+1,n):
            for k in range(j+1,n):
                for l in range(k+1,n):
                    hidarisita = (min(XY[i][0],XY[j][0],XY[k][0],XY[l][0]),
                    min(XY[i][1],XY[j][1],XY[k][1],XY[l][1]))
                    migiue = (max(XY[i][0],XY[j][0],XY[k][0],XY[l][0]),
                    max(XY[i][1],XY[j][1],XY[k][1],XY[l][1]))

                    res = 1
                    for m in range(i+1,n):
                        if hidarisita[0] <= XY[m][0] <= migiue[0] and \
                            hidarisita[1] <= XY[m][1] <= migiue[1]:
                            res += 1

                    if res >= g:
                        ans = min(ans,(migiue[0]-hidarisita[0])*(migiue[1]-hidarisita[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)]

x_index=set([])
y_index=set([])

for (x,y) in xy:
    x_index.add(x)
    y_index.add(y)
    
####座標圧縮

x_index=list(x_index)
y_index=list(y_index)

x_index.sort()
y_index.sort()

maze=[[0]*len(x_index) for _ in range(len(y_index)) ]

for (x,y) in xy:
    maze[y_index.index(y)][x_index.index(x)]=1

ans=10**15

for y1 in range(len(y_index)):
    for x1 in range(len(x_index)):
        for y2 in range(y1,len(y_index)):
            for x2 in range(x1,len(x_index)):
                tmp=0
                for (x,y) in xy:
                    if y1<=y_index.index(y) and y_index.index(y)<=y2:
                        if x1<=x_index.index(x) and x_index.index(x)<=x2:
                            tmp+=1
                if tmp==k:
                    menseki=(y_index[y2]-y_index[y1])*(x_index[x2]-x_index[x1])
                    ans=min(ans,menseki)

print(menseki)

Submission status: Wrong Answer

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

Px = sorted(P, key=lambda x: x[0])
Py = sorted(P, key=lambda x: x[1])

ans = float('inf')

for i in range(N-K+1):
    left = Px[i]
    right = Px[i+K-1]
    a1 = right[0] - left[0]
    a2 = []
    for j in range(K):
        a2.append(Px[j][1])
    a2 = max(a2) - min(a2)
    ans = min(ans, a1*a2)

for i in range(N-K+1):
    lower = Py[i]
    upper = Py[i+K-1]
    a1 = upper[1] - lower[1]
    a2 = []
    for j in range(K):
        a2.append(Py[j][0])
    a2 = max(a2) - min(a2)
    ans = min(ans, a1*a2)

print(ans)

Submission status: Wrong Answer

Solution code:
import sys

N, K = map(int, sys.stdin.readline().split())
points = []
for _ in range(N):
    x, y = map(int, sys.stdin.readline().split())
    points.append((x, y))

x_sorted = sorted(points)
y_sorted = sorted(points, key=lambda x: x[1])

ans = float("inf")
for i in range(N - K + 1):
    dx = x_sorted[i+K-1][0] - x_sorted[i][0]
    y_min = float("inf")
    y_max = -float("inf")
    for (x, y) in x_sorted[i:i+K]:
        y_min = min(y_min, y)
        y_max = max(y_max, y)
    ans = min(ans, dx * (y_max - y_min))

for i in range(N - K + 1):
    dy = y_sorted[i+K-1][1] - y_sorted[i][1]
    x_min = float("inf")
    x_max = -float("inf")
    for (x, y) in y_sorted[i:i+K]:
        x_min = min(x_min, x)
        x_max = max(x_max, x)
    ans = min(ans, (x_max - x_min) * dy)

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import heapq
import re
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from math import factorial, sqrt, ceil, gcd
from functools import lru_cache, reduce
from decimal import Decimal
from operator import mul

INF = 1 << 60
MOD = 1000000007
sys.setrecursionlimit(10 ** 7)


# UnionFind
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

# ダイクストラ
def dijkstra_heap(s, edge, n):
    #始点sから各頂点への最短距離
    d = [10**20] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

# 素因数分解
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

# 組合せnCr
def combinations_count(n, r):
    if n < r:
        return 0
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom

# 2数の最小公倍数
def lcm(x, y):
    return (x * y) // gcd(x, y)

# リストの要素の最小公倍数
def lcm_list(numbers):
    return reduce(lcm, numbers, 1)

# リストの要素の最大公約数
def gcd_list(numbers):
    return reduce(gcd, numbers)

# 素数判定
def is_prime(n):
    if n <= 1:
        return False
    p = 2
    while True:
        if p ** 2 > n:
            break
        if n % p == 0:
            return False
        p += 1
    return True


# limit以下の素数を列挙
def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []

    while True:
        prime = min(A)
        
        if prime > sqrt(limit):
            break
            
        P.append(prime)
            
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
            
    for a in A:
        P.append(a)
            
    return P

# 同じものを含む順列
def permutation_with_duplicates(L):

    if L == []:
        return [[]]

    else:
        ret = []

        # set（集合）型で重複を削除、ソート
        S = sorted(set(L))

        for i in S:

            data = L[:]
            data.remove(i)

            for j in permutation_with_duplicates(data):
                ret.append([i] + j)

        return ret

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]



# ここから書き始める
n, k = map(int, input().split())
x = [0 for i in range(n)]
y = [0 for i in range(n)]
for i in range(n):
    x[i], y[i] = map(int, input().split())

a = [[x[i], y[i]] for i in range(n)]

b = sorted(a, key=lambda x:(x[0], x[1]))
# c = sorted(a, key=lambda x:(x[1]))
ans = INF
for i in range(n):
    if i + k > n:
        break
    c = b[i:i+k]
    # print("c =", c)
    x_length = c[-1][0] - c[0][0]
    y_max = -INF
    y_min = INF
    for j in c:
        y_max = max(y_max, j[1])
        y_min = min(y_min, j[1])
    y_length = y_max - y_min
    # print("x_length =", x_length)
    # print("y_length =", y_length)
    ans = min(ans, x_length * y_length)
print(ans)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
xy = []
for _ in range(N):
    xy.append(tuple(map(int, input().split())))
xy.sort()
# print(xy)
ans = 10**20

for i in range(N):
    for j in range(i+K-1,N):
        s = sorted(xy[i:j+1], key=lambda x: x[1])
        ans = min(ans, (s[-1][1]-s[0][1]) * (xy[j][0]-xy[i][0]))

xy.sort(key=lambda x: x[1])
# print(xy)
for i in range(N):
    for j in range(i+K-1,N):
        s = sorted(xy[i:j+1])
        ans = min(ans, (s[-1][0]-s[0][0]) * (xy[j][1]-xy[i][1]))
print(ans)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
xy = []
for _ in range(N):
    xy.append(tuple(map(int, input().split())))
xy.sort()
#print(xy)
ans = 10**20

for i in range(N):
    for j in range(i+K-1,N):
        s = sorted(xy[i:j+1], key=lambda x: x[1])
        #print(i,j,s)
        ans = min(ans, abs(s[-1][1] - s[0][1])*abs(xy[j][0] - xy[i][0]))
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right
from itertools import accumulate

sys.setrecursionlimit(10**6)
INF = 10**12
m = 10**9 + 7

def main():
    N, K = map(int, input().split())
    xy = []
    for _ in range(N):
        xy.append(tuple(map(int, input().split())))
    xy.sort()
    ans = 10**20
    
    for i in range(N):
        for j in range(i+K-1,N):
            s = sorted(xy[i:j+1], key=lambda x: x[1])
            # print(i,j,s)
            ans = min(ans, (s[-1][1] - s[0][1])*(xy[j][0] - xy[i][0]))
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    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 = sorted(X)
    Y = sorted(Y)

    res = f_inf
    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__':
    resolve()

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    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.sort()
    Y.sort()

    res = f_inf
    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__':
    resolve()

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    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.sort()
    Y.sort()

    res = f_inf
    for x1 in range(n):
        for x2 in range(x1 + 1, n):
            for y1 in range(n):
                for y2 in range(y1 + 1, n):
                    x_left, x_right = X[x1], X[x2]
                    y_bottom, y_up = Y[y1], Y[y2]
                    cnt = 0
                    for i in range(n):
                        if x_left <= X[i] <= x_right and y_bottom <= Y[i] <= y_up:
                            cnt += 1
                    if cnt >= k:
                        res = min(res, (x_right - x_left) * (y_up - y_bottom))
    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    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.sort()
    Y.sort()

    res = f_inf
    for xi in range(n):
        x_left = X[xi]
        for xj in range(xi + 1, n):
            x_right = X[xj]
            for yi in range(n):
                y_bottom = Y[yi]
                for yj in range(yi + 1, n):
                    y_up = Y[yj]
                    cnt = 0
                    for i in range(n):
                        x, y = X[i], Y[i]
                        if x_left <= x <= x_right and y_bottom <= y <= y_up:
                            cnt += 1
                    if cnt >= k:
                        s = abs(x_right - x_left) * abs(y_up - y_bottom)
                        res = min(res, s)
    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, k = map(int, input().split())
    XY = [list(map(int, input().split())) for _ in range(n)]
    XY.sort()

    res = f_inf
    for i in range(n - (k - 1)):
        x1, y1 = XY[i]
        min_x = x1
        max_y, min_y = y1, y1
        for j in range(i + 1, i + k):
            x2, y2 = XY[j]
            max_x = x2
            max_y = max(max_y, y2)
            min_y = min(min_y, y2)
        s = abs(max_x - min_x) * abs(max_y - min_y)
        res = min(res, s)
    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Wrong Answer

Solution code:
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
#mod = 998244353
INF = 10**20
eps = 10**-7

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

P = [tuple(map(int,readline().split())) for i in range(N)]
P.sort(key=lambda x: x[0])

ans = INF

for i in range(N-K+1):
    xmin = P[i][0]
    xmax = P[i+K-1][0]
    plist = []
    for (x,y) in P:
        if xmin <= x <= xmax:
            plist.append(y)
    plist.sort()
    ylen = INF
    for j in range(len(plist)-K+1):
        ylen = min(ylen,plist[j+K-1]-plist[j])
    ans = min(ans,(xmax-xmin)*ylen)

for i in range(N):
    P[i] = (P[i][1],P[i][0])
P.sort(key=lambda x: x[0])

for i in range(N-K+1):
    xmin = P[i][0]
    xmax = P[i+K-1][0]
    plist = []
    for (x,y) in P:
        if xmin <= x <= xmax:
            plist.append(y)
    plist.sort()
    ylen = INF
    for j in range(len(plist)-K+1):
        ylen = min(ylen,plist[j+K-1]-plist[j])
    ans = min(ans,(xmax-xmin)*ylen)

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
#mod = 998244353
INF = 10**20
eps = 10**-7

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

P = [tuple(map(int,readline().split())) for i in range(N)]
P.sort(key=lambda x: x[0])

ans = INF

for i in range(N-K+1):
    xmin = P[i][0]
    xmax = P[i+K-1][0]
    plist = []
    for (x,y) in P:
        if xmin <= x <= xmax:
            plist.append(y)
    plist.sort()
    ylen = INF
    for j in range(len(plist)-K+1):
        ylen = min(ylen,plist[j+K-1]-plist[j])
    ans = min(ans,(xmax-xmin)*ylen)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
#mod = 998244353
INF = 10**20
eps = 10**-7

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

P = [tuple(map(int,readline().split())) for i in range(N)]
P.sort(key=lambda x: x[0])

ans = INF

for i in range(N-K+1):
    xmin = P[i][0]
    xmax = P[i+K-1][0]
    ymin = INF
    ymax = -INF
    for j in range(i,i+K):
        ymin = min(P[j][1],ymin)
        ymax = max(P[j][1],ymax)
    ans = min(ans,(xmax-xmin)*(ymax-ymin))
print(ans)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# hello worldと表示する
#float型を許すな
#numpyはpythonで
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, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

n,k=MI()
lis=[LI() for i in range(n)]
s=[]
for i in range(n):
    for j in range(n):
        for k in range(n):
            for l in range(n):
                xl=min(lis[i][0],lis[j][0])
                xu=max(lis[i][0],lis[j][0])
                yl=min(lis[k][1],lis[l][1])
                yu=max(lis[k][1],lis[l][1])
                count=0
                for m in range(n):
                    if xl<=lis[m][0]<=xu and yl<=lis[m][1]<=yu:
                        count+=1
                if count>=k:
                    s.append((xu-xl)*(yu-yl))
print(max(s))

Submission status: Wrong Answer

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

tate = []
yoko = []

for i,j in ab:
    tate.append(i)
    yoko.append(j)

ans = float('inf')

for i in range(n-k+1):
    #print(tate[i:i+k],yoko[i:i+k])
    square = (tate[i+k-1]-tate[i])*(max(yoko[i:i+k])-min(yoko[i:i+k]))
    ans = min(ans, square)
print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    n, k, *xy = map(int, open(0).read().split())
    *p, = zip(xy[::2], xy[1::2])
    p.sort(key=lambda a: (a[0], -a[1]))
    x, y = zip(*p)

    _x_ = sorted(list(set(x)))
    ans = 4 * 10 ** 18
    for _x in _x_:
        for x_ in _x_[1:]:
            w = x_ - _x
            c = 0
            _h_ = []
            for i, j in p:
                if _x <= i <= x_:
                    c += 1
                    _h_.append(j)

            if c >= k:
                _h_.sort()
                h = min(_h_[k - 1] - _h_[0], _h_[-1] - _h_[-k])
                ans = min(ans, h * w)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    n, k, *xy = map(int, open(0).read().split())
    *p, = zip(xy[::2], xy[1::2])
    p.sort(key=lambda a: (a[0], -a[1]))
    x, y = zip(*p)

    _x_ = sorted(list(set(x)))
    ans = 4 * 10 ** 18
    for _x in _x_:
        for x_ in _x_[1:]:
            w = x_ - _x
            c = 0
            _h_ = []
            for i, j in p:
                if _x <= i <= x_:
                    c += 1
                    _h_.append(j)
                else:
                    break

            if c >= k:
                _h_.sort()
                h = min(_h_[k - 1] - _h_[0], _h_[-1] - _h_[-k])
                ans = min(ans, h * w)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    n, k, *xy = map(int, open(0).read().split())
    *p, = zip(xy[::2], xy[1::2])
    p.sort(key=lambda a: (a[0], -a[1]))
    x, y = zip(*p)

    ans_ = 4 * 10 ** 18
    for i in range(n - k + 1):
        w = x[i + k - 1] - x[i]
        h = max(y[i:i + k]) - min(y[i:i + k])
        ans_ = min(ans_, h * w)

    p.sort(key=lambda a: (a[1], -a[0]))
    x, y = zip(*p)
    _ans = 4 * 10 ** 18
    for i in range(n - k + 1):
        w = y[i + k - 1] - y[i]
        h = max(x[i:i + k]) - min(x[i:i + k])
        _ans = min(_ans, h * w)

    ans = min(_ans, ans_)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    n, k, *xy = map(int, open(0).read().split())
    *p, = zip(xy[::2], xy[1::2])
    p.sort(key=lambda x: (x[0], -x[1]))
    x, y = zip(*p)

    ans = 4 * 10 ** 18
    for i in range(n - k + 1):
        w = x[i + k - 1] - x[i]
        h = max(y[i:i + k]) - min(y[i:i + k])
        ans = min(ans, h * w)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from itertools import combinations
    from operator import itemgetter
    n, k = map(int, readline().split())
    points = [list(map(int, readline().split())) for _ in range(n)]

    points.sort(key=itemgetter(0))
    for i in range(n):
        points[i].append(i)
    points.sort(key=itemgetter(1))
    for i in range(n):
        points[i].append(i)

    points.sort(key=itemgetter(2))

    ans = INF

    for first, last in combinations(range(n), 2):
        if (last - first + 1) < k:
            continue
        for p, q in combinations(range(first, last + 1), 2):
            p_num = points[p][3]
            q_num = points[q][3]
            if (abs(p_num - q_num) + 1) >= k:
                width = abs(points[last][0] - points[first][0])
                height = abs(points[p][1] - points[q][1])
                area = width * height
                ans = min(ans, area)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from itertools import permutations
    n, k = map(int, readline().split())
    points = [list(map(int, readline().split())) for _ in range(n)]
    points.sort()
    ans = INF

    for first in range(n - k + 1):
        last = first + k - 1
        width = points[last][0] - points[first][0]
        y_min, y_max = 10 ** 9 + 1, -(10 ** 9 + 1)
        for i in range(first, last + 1):
            y = points[i][1]
            y_min = min(y_min, y)
            y_max = max(y_max, y)
        height = y_max - y_min
        area = width * height
        ans = min(ans, area)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def resolve():
    N, K = list(map(int, input().split()))
    XY = [list(map(int, input().split()))+[True] for _ in range(N)]
    prev = 0
    centerx, centery = 0, 0
    while True:
        xmax, xmin, ymax, ymin = -float("inf"), float("inf"), -float("inf"), float("inf")
        edge_points = []
        points = 0
        for i, (x, y, flg) in enumerate(XY):
            if not flg:
                continue
            points += 1
            if xmax < x:
                edge_points.append(i)
                xmax = x
            if xmin > x:
                edge_points.append(i)
                xmin = x
            if ymax < y:
                edge_points.append(i)
                ymax = y
            if ymin > y:
                edge_points.append(i)
                ymin = y
        if points < K:
            print(prev)
            return
        prev = abs(xmax - xmin)*abs(ymax-ymin)
        centerx, centery = (xmax + xmin)/2, (ymax + ymin)/2
        faridx = None
        fardist = -float("inf")
        for idx in edge_points:
            x, y = XY[idx][0], XY[idx][1]
            dist = abs(x - centerx) + abs(y - centery)
            if fardist < dist:
                faridx = idx
                fardist = dist
        XY[faridx][2] = False




if '__main__' == __name__:
    resolve()

Submission status: Wrong Answer

Solution code:
from sys import stdin
def main():
    #入力
    readline=stdin.readline
    inf=10**20
    n,k=map(int,readline().split())
    co=[list(map(int,readline().split())) for _ in range(n)]
    
    co.sort()
    
    x_range=[]
    for i in range(n-1):
        for j in range(i+1,n):
            x_range.append((co[i][0],co[j][0]))

    co.sort(key=lambda x:x[1])
    ans=inf
    for x in x_range:
        x_min=x[0]
        x_max=x[1]
        y_min=0
        y_max=0
        cnt=0
        for i in range(n):
            if x_min<=co[i][0]<=x_max:
                if cnt==0:
                    y_min=co[i][1]
                    cnt+=1
                else:
                    y_max=co[i][1]
                    cnt+=1
            if cnt==k:
                break
        if cnt==k:
            ans=min(ans,(x_max-x_min)*(y_max-y_min))

    print(ans)

if __name__=="__main__":
    main()

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())

X = []
Y = []
Z = []

for i in range(N):
  x,y = map(int,input().split())
  X.append(x)
  Y.append(y)
  Z.append([x,y])
  
T = max(Y)
U = min(Y)
R = max(X)
L = min(X)
Y.sort()
X.sort()
ans = 10**10

for t in range(N):
  for u in range(N):
    for r in range(N):
      for l in range(N):
        T = Y[N-t-1]
        U = Y[u]
        R = X[N-r-1]
        L = X[l]
        cnt = 0
        for i in range(N):
          xi = Z[i][0]
          yi = Z[i][1]
          if xi >= L and xi <= R and yi >= U and yi <= T:
            cnt += 1
        if cnt >= K:
          M = int( (T-U) * (R-L) )
          ans = min(ans,M)
          
print(ans)