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:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())

N,K = inpl()
xys = []
xx = set()
yy = set()
for i in range(N):
    x,y = inpl()
    xys.append([x,y])
    xx.add(x)
    yy.add(y)

ans = INF
for x1 in xx:
    for x2 in xx:
        for y1 in yy:
            for y2 in yy:
                x1,x2 = min(x1,x2),max(x1,x2)
                y1,y2 = min(y1,y2),max(y1,y2)
                tmp = 0
                for x,y in xys:
                    if x1 <= x <= x2 and y1 <= y <= y2:
                        tmp += 1
                if K <= tmp:
                    ans = min(ans,(x2-x1)*(y2-y1))

print(ans)

Submission status: Wrong Answer

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

xs, ys = tuple(zip(*xy))
cmpx = sorted(xs)
cmpy = sorted(ys)

x2cmp = dict((x, i) for i,x in enumerate(cmpx))
y2cmp = dict((x, i) for i,x in enumerate(cmpy))

sm = [[0] * (N + 1) for _ in range(N + 1)]
for x, y in xy:
    sm[x2cmp[x]][y2cmp[y]] = 1

for i in range(N):
    for j in range(N):
        sm[i][j] += sm[i][j - 1]
for j in range(N):
    for i in range(N):
        sm[i][j] += sm[i - 1][j]

ans = float('inf')
for x1 in range(N):
    for y1 in range(N):
        for x2 in range(x1 + 1, N):
            for y2 in range(y1 + 1, N):
                k = sm[y2][x2] - sm[y2][x1 - 1] - sm[y1 - 1][x2] + sm[y1 - 1][x1 - 1]
                if k == K:
                    area = abs((cmpx[x2] - cmpx[x1]) * (cmpy[y2] - cmpy[y1]))
                    ans = min(ans, area)

print(ans)

Submission status: Wrong Answer

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

inf = float('inf')
dp = [[[inf, inf, inf, -inf, -inf] for _ in range(K + 1)] for _ in range(N + 1)]
for i, (x, y) in enumerate(xy, 1):
    pdp = dp[i - 1]
    for k in range(2, min(i, K) + 1):
        if k == 2:
            area = inf
            dp_k = None
            for a in xy[:i-1]:
                min_x = min(a[0], x)
                min_y = min(a[1], y)
                max_x = max(a[0], x)
                max_y = max(a[1], y)
                cand = (max_x - min_x) * (max_y - min_y)
                if cand < area:
                    area = cand
                    dp_k = [cand, min_x, min_y, max_x, max_y]
            if area < pdp[k][0]:
                dp[i][k] = dp_k
            else:
                dp[i][k] = pdp[k]
        else:
            area_a, min_x, min_y, max_x, max_y = pdp[k - 1]
            min_x = min(min_x, x)
            min_y = min(min_y, y)
            max_x = max(max_x, x)
            max_y = max(max_y, y)
            area_a = (max_x - min_x) * (max_y - min_y)
            area_b = pdp[k][0]
            if area_a < area_b:
                dp[i][k] = [area_a, min_x, min_y, max_x, max_y]
            else:
                dp[i][k] = pdp[k]
print(dp[N][K][0])

Submission status: Wrong Answer

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

inf = float('inf')
dp = [[[inf, inf, inf, -inf, -inf] for _ in range(K + 2)] for _ in range(N + 1)]
for i, (x, y) in enumerate(xy, 1):
    pdp = dp[i - 1]
    for k in range(1, min(i, K) + 1):
        area_a, min_x, min_y, max_x, max_y = pdp[k - 1]
        min_x = min(min_x, x)
        min_y = min(min_y, y)
        max_x = max(max_x, x)
        max_y = max(max_y, y)
        area_a = (max_x - min_x) * (max_y - min_y)
        area_b = pdp[k][0]
        if area_a < area_b:
            dp[i][k] = [area_a, min_x, min_y, max_x, max_y]
        else:
            dp[i][k] = pdp[k]
print(dp[N][K][0])

Submission status: Wrong Answer

Solution code:
"""
D - Axis-Parallel Rectangle
各点を頂点とする長方形じゃだめなの？
解説どおり、各点と平行な線を引いて解いた
"""

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

points_x = []
points_y = []
for n in range(N):
    line = input().split()
    points_x.append(int(line[0]))
    points_y.append(int(line[1]))

points_x.sort()
points_y.sort()

all_min = (points_x[N-1] - points_x[0]) * (points_y[N-1] - points_y[0])
for xi in range(N):
    for xj in range(xi+1, N):
        for yi in range(N):
            for yj in range(yi+1, N):
                
                inner_point = 0
                left_x = points_x[xi]
                right_x = points_x[xj]
                left_y = points_y[yi]
                right_y = points_y[yj]
                
                for i in range(N):
                    if (left_x <= points_x[i]
                    and points_x[i] <= right_x
                    and left_y <= points_y[i]
                    and points_y[i] <= right_y):

                        inner_point += 1
                
                if inner_point >= K:
                    all_min = min(all_min, (right_x - left_x) * (right_y - left_y))

print(all_min)

Submission status: Wrong Answer

Solution code:
"""
D - Axis-Parallel Rectangle
各点を頂点とする長方形じゃだめなの？
解説どおり、各点と平行な線を引いて解いた
"""

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

points_x = []
points_y = []
for n in range(N):
    line = input().split()
    points_x.append(int(line[0]))
    points_y.append(int(line[1]))

print(points_x)
print(points_y)

points_x.sort()
points_y.sort()

all_min = (points_x[N-1] - points_x[0]) * (points_y[N-1] - points_y[0])
for xi in range(N):
    for xj in range(xi+1, N):
        for yi in range(N):
            for yj in range(yi+1, N):
                
                inner_point = 0
                left_x = points_x[xi]
                right_x = points_x[xj]
                left_y = points_y[yi]
                right_y = points_y[yj]
                
                for i in range(N):
                    if (left_x <= points_x[i]
                    and points_x[i] <= right_x
                    and left_y <= points_y[i]
                    and points_y[i] <= right_y):

                        inner_point += 1
                
                if inner_point >= K:
                    all_min = min(all_min, (right_x - left_x) * (right_y - left_y))

print(all_min)

Submission status: Wrong Answer

Solution code:
from itertools import product as pd
f=lambda x,y:(x,y) if x<y else (y,x) 
n,k=map(int,input().split())
o=[tuple(map(int,input().split())) for _ in range(n)]

v=1e9
for (a,b,c,d) in pd(range(n),repeat=4):
  lx,rx=f(o[a][0],o[b][0])
  dy,uy=f(o[c][1],o[d][1])
  if lx==rx or dy==uy:continue
  cnt=sum(1 for i in range(n) if lx<=o[i][0]<=rx and dy<=o[i][1]<=uy)
  if cnt==k:
    v=min(v,(rx-lx)*(uy-dy))
print(v)

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
a = []
for i in range(n):
    li = list(map(int,input().split()))
    a.append(li)
a.sort()
x = []
y = []
for i in range(n):
    x.append(a[i][0])
    y.append(a[i][1])

ass = [] #kotae kouho


for i in range(n-k+1):
    xx = x[i+k-1]-x[i]
    mi = min(y[:k+i:])
    ma = max(y[:k+i:])
    
    ass.append(xx*(ma-mi))
    
print(min(ass))

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
x = []
for i in range(n):
    x1,y1=[int(i) for i in input().split()]
    x.append([x1,y1])
x = sorted(x)
ans = []
for i in range(k):
  ans.append(x[i])
xmin = ans[0][0]
xmax = ans[-1][0]
ans2 = sorted(ans,key = lambda x:x[1])
ymin = ans2[0][1]
ymax = ans2[-1][1]
kota = (xmax-xmin) * (ymax-ymin)
for i in range(k,n):
  xmin = ans[0][0]
  xmax = ans[-1][0]
  ans2 = sorted(ans,key = lambda x:x[1])
  ymin = ans2[0][1]
  ymax = ans2[-1][1]
  kota1 = (xmax-xmin) * (ymax-ymin)
  
  ans.append(x[i])
  a = ans.pop(0)
  xmin = ans[0][0]
  xmax = ans[-1][0]
  ans2 = sorted(ans,key = lambda x:x[1])
  ymin = ans2[0][1]
  ymax = ans2[-1][1]
  kota2 = (xmax-xmin) * (ymax-ymin)
  
  ans.append(a)
  ans = sorted(ans,key = lambda x:x[1])
  b = ans.pop()
  ymin = ans[0][1]
  ymax = ans[-1][1]
  ans = sorted(ans)
  xmin = ans[0][0]
  xmax = ans[-1][0]
  kota3 = (xmax-xmin) * (ymax-ymin)
  
  ans.append(b)
  ans = sorted(ans,key = lambda x:x[1])
  c = ans.pop(0)
  ymin = ans[0][1]
  ymax = ans[-1][1]
  ans = sorted(ans)
  xmin = ans[0][0]
  xmax = ans[-1][0]
  kota4 = (xmax-xmin) * (ymax-ymin)
  
  ans.append(c)
  ti = min(kota1,kota2,kota3,kota4)
  if ti == kota2:
    ans = sorted(ans)
    ans.pop(0)
  elif (ti == kota3 and kota3 == kota4):
    ans = sorted(ans,key = lambda x:x[1])
    if ans[0][0] > ans[-1][0]:
      ans.pop()
    else:
      ans.pop(0)
  elif ti == kota3:
    ans = sorted(ans,key = lambda x:x[1])
    ans.pop()
  elif ti == kota4:
    ans = sorted(ans,key = lambda x:x[1])
    ans.pop(0)
  else:
    ans = sorted(ans)
    ans.pop()
    
  kota = min(kota,ti)
print(kota)

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
x = []
for i in range(n):
    x1,y1=[int(i) for i in input().split()]
    x.append([x1,y1])
x = sorted(x)
ans = []
for i in range(k):
  ans.append(x[i])
xmin = ans[0][0]
xmax = ans[-1][0]
ans2 = sorted(ans,key = lambda x:x[1])
ymin = ans2[0][1]
ymax = ans2[-1][1]
kota = (xmax-xmin) * (ymax-ymin)
for i in range(k,n):
  xmin = ans[0][0]
  xmax = ans[-1][0]
  ans2 = sorted(ans,key = lambda x:x[1])
  ymin = ans2[0][1]
  ymax = ans2[-1][1]
  kota1 = (xmax-xmin) * (ymax-ymin)
  
  ans.append(x[i])
  a = ans.pop(0)
  xmin = ans[0][0]
  xmax = ans[-1][0]
  ans2 = sorted(ans,key = lambda x:x[1])
  ymin = ans2[0][1]
  ymax = ans2[-1][1]
  kota2 = (xmax-xmin) * (ymax-ymin)
  
  ans.append(a)
  ans = sorted(ans,key = lambda x:x[1])
  b = ans.pop()
  ymin = ans[0][1]
  ymax = ans[-1][1]
  ans = sorted(ans)
  xmin = ans[0][0]
  xmax = ans[-1][0]
  kota3 = (xmax-xmin) * (ymax-ymin)
  
  ans.append(b)
  ans = sorted(ans,key = lambda x:x[1])
  c = ans.pop(0)
  ymin = ans[0][1]
  ymax = ans[-1][1]
  ans = sorted(ans)
  xmin = ans[0][0]
  xmax = ans[-1][0]
  kota4 = (xmax-xmin) * (ymax-ymin)
  
  ans.append(c)
  ti = min(kota1,kota2,kota3,kota4)
  if ti == kota2:
    ans = sorted(ans)
    ans.pop(0)
  elif kota3 == kota4:
    ans = sorted(ans,key = lambda x:x[1])
    if ans[0][0] > ans[-1][0]:
      ans.pop()
    else:
      ans.pop(0)
  elif ti == kota3:
    ans = sorted(ans,key = lambda x:x[1])
    ans.pop()
  elif ti == kota4:
    ans = sorted(ans,key = lambda x:x[1])
    ans.pop(0)
  else:
    ans = sorted(ans)
    ans.pop()
    
  kota = min(kota,ti)
print(kota)

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
x = []
for i in range(n):
    x1,y1=[int(i) for i in input().split()]
    x.append([x1,y1])
x = sorted(x)
ans = []
for i in range(k):
  ans.append(x[i])
xmin = ans[0][0]
xmax = ans[-1][0]
ans2 = sorted(ans,key = lambda x:x[1])
ymin = ans2[0][1]
ymax = ans2[-1][1]
kota = (xmax-xmin) * (ymax-ymin)
for i in range(k,n):
  ans.append(x[i])
  ans = sorted(ans,key = lambda x:x[1])
  if ans[1][1] - ans[0][1] > ans[-2][1] - ans[-1][1]:
    ans.pop(0)
    ymin = ans[0][1]
    ymax = ans[-1][1]
    ans = sorted(ans)
    xmin = ans[0][0]
    xmax = ans[-1][0]
    kota = min((xmax-xmin) * (ymax-ymin),kota)
  elif ans[1][1] - ans[0][1] == ans[-2][1] - ans[-1][1]:
    if ans[0][0] > ans[-1][0]:
      ans.pop(-1)
    else:
      ans.pop(0)
    ymin = ans[0][1]
    ymax = ans[-1][1]
    ans = sorted(ans)
    xmin = ans[0][0]
    xmax = ans[-1][0]
    kota = min((xmax-xmin) * (ymax-ymin),kota)
  else:
    ans.pop(-1)
    ymin = ans[0][1]
    ymax = ans[-1][1]
    ans = sorted(ans)
    xmin = ans[0][0]
    xmax = ans[-1][0]
    kota = min((xmax-xmin) * (ymax-ymin),kota)
ans = []
x = sorted(x,key = lambda x:-x[0])
for i in range(k):
  ans.append(x[i])
xmax = ans[0][0]
xmin = ans[-1][0]
ans2 = sorted(ans,key = lambda x:x[1])
ymin = ans2[0][1]
ymax = ans2[-1][1]
kota = min((xmax-xmin) * (ymax-ymin),kota)
for i in range(k,n):
  ans.append(x[i])
  ans = sorted(ans,key = lambda x:x[1])
  if ans[1][1] - ans[0][1] > ans[-2][1] - ans[-1][1]:
    ans.pop(0)
    ymin = ans[0][1]
    ymax = ans[-1][1]
    ans = sorted(ans,key = lambda x:-x[0])
    xmax = ans[0][0]
    xmin = ans[-1][0]
    kota = min((xmax-xmin) * (ymax-ymin),kota)
  elif ans[1][1] - ans[0][1] == ans[-2][1] - ans[-1][1]:
    if ans[0][0] > ans[-1][0]:
      ans.pop(-1)
    else:
      ans.pop(0)
    ymin = ans[0][1]
    ymax = ans[-1][1]
    ans = sorted(ans,key = lambda x:-x[0])
    xmax = ans[0][0]
    xmin = ans[-1][0]
    kota = min((xmax-xmin) * (ymax-ymin),kota)
  else:
    ans.pop(-1)
    ymin = ans[0][1]
    ymax = ans[-1][1]
    ans = sorted(ans,key = lambda x:-x[0])
    xmax = ans[0][0]
    xmin = ans[-1][0]
    kota = min((xmax-xmin) * (ymax-ymin),kota)
print(kota)

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
x = []
for i in range(n):
    x1,y1=[int(i) for i in input().split()]
    x.append([x1,y1])
x = sorted(x)
ans = []
for i in range(k):
  ans.append(x[i])
xmin = ans[0][0]
xmax = ans[-1][0]
ans2 = sorted(ans,key = lambda x:x[1])
ymin = ans2[0][1]
ymax = ans2[-1][1]
kota = (xmax-xmin) * (ymax-ymin)
for i in range(k,n):
  ans.append(x[i])
  ans = sorted(ans,key = lambda x:x[1])
  if ans[1][1] - ans[0][1] > ans[-2][1] - ans[-1][1]:
    ans.pop(0)
    ymin = ans[0][1]
    ymax = ans[-1][1]
    ans = sorted(ans)
    xmin = ans[0][0]
    xmax = ans[-1][0]
    kota = min((xmax-xmin) * (ymax-ymin),kota)
  elif ans[1][1] - ans[0][1] == ans[-2][1] - ans[-1][1]:
    if ans[0][0] > ans[-1][0]:
      ans.pop(-1)
    else:
      ans.pop(0)
    ymin = ans[0][1]
    ymax = ans[-1][1]
    ans = sorted(ans)
    xmin = ans[0][0]
    xmax = ans[-1][0]
    kota = min((xmax-xmin) * (ymax-ymin),kota)
  else:
    ans.pop(-1)
    ymin = ans[0][1]
    ymax = ans[-1][1]
    ans = sorted(ans)
    xmin = ans[0][0]
    xmax = ans[-1][0]
    kota = min((xmax-xmin) * (ymax-ymin),kota)
print(kota)

Submission status: Wrong Answer

Solution code:
from itertools import combinations
N,K=map(int,input().split())
px = [0 for _ in range(N)]
py = [0 for _ in range(N)]
for i in range(N):
  px[i],py[i] = list(map(int,input().split()))
a=10**20
for i0,i1 in combinations(range(N), 2):
  px0,px1 = min(px[i0],px[i1]),max(px[i0],px[i1])
  py0,py1 = min(py[i0],py[i1]),max(py[i0],py[i1])
  dx,dy = px1-px0,py1-py0
  if a < dx*dy: continue
  cnt = 0
  for i in range(N):
    if px0<=px[i] and px[i]<=px1 and py0<=py[i] and py[i]<=py1:
      cnt += 1
  if K <= cnt and dx*dy < a: a = dx*dy
print(a)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, K, XY):
    X = sorted(map(lambda x: x[0], XY))
    RX = reversed(X)
    Y = sorted(map(lambda x: x[1], XY))
    RY = reversed(Y)

    ans = sys.maxsize
    for lx in X:
        for rx in RX:
            if lx > rx:
                break
            for by in Y:
                for ty in RY:
                    if by > ty:
                        break

                    k = 0
                    for x, y in XY:
                        if lx <= x <= rx and by <= y <= ty:
                            k += 1
                    if k >= K:
                        ans = min(ans, (rx-lx)*(ty-by))
                    else:
                        break

    return ans


def main():
    N, K = read_int_n()
    XY = [read_int_n() for _ in range(N)]

    print(slv(N, K, XY))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

arr = []

for i in range(n):
	arr.append(map(int,raw_input().split()))

ans = float("inf")

for i in range(n):
	for j in range(i+1,n):
		count = 0
		minx = min(arr[i][0],arr[j][0])
		maxx = max(arr[i][0],arr[j][0])
		miny = min(arr[i][1],arr[j][1])
		maxy = max(arr[i][1],arr[j][1])
		
		for s in range(n):
			x = arr[s][0]
			y = arr[s][1]
			if minx <= x and x <= maxx and  miny <= y and y <= maxy:
				count += 1

		if count >= k:
			area = abs(arr[i][0] - arr[j][0]) * abs(arr[i][1] - arr[j][1])
			ans = min(ans,area)

print ans

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, K, XY):
    XY.sort(key=lambda x: x[1], reverse=True)
    XY.sort(key=lambda x: x[0])

    ans = sys.maxsize
    for i in range(N-K+1):
        XY_ = XY[i:i+K]
        xl = min(XY_, key=lambda x: x[0])[0]
        xr = max(XY_, key=lambda x: x[0])[0]
        yb = min(XY_, key=lambda x: x[1])[1]
        yt = max(XY_, key=lambda x: x[1])[1]
        ans = (xr-xl)*(yt-yb)

    return ans


def main():
    N, K = read_int_n()
    XY = [read_int_n() for _ in range(N)]

    print(slv(N, K, XY))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, K, XY):
    XY.sort(key=lambda x: x[1])
    XY.sort(key=lambda x: x[0])

    ans = sys.maxsize
    for i in range(N-K+1):
        XY_ = XY[i:i+K]
        xl = min(XY_, key=lambda x: x[0])[0]
        xr = max(XY_, key=lambda x: x[0])[0]
        yb = min(XY_, key=lambda x: x[1])[1]
        yt = max(XY_, key=lambda x: x[1])[1]
        ans = (xr-xl)*(yt-yb)

    return ans


def main():
    N, K = read_int_n()
    XY = [read_int_n() for _ in range(N)]

    print(slv(N, K, XY))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
inps = input().split(" ")
points = [[]]
for i in range(0, int(inps[0])):
    curr = input().split(" ")
    curr[0] = int(curr[0])
    curr[1] = int(curr[1])
    points.append(curr)
# print(points)
mini = 100000000000000000000

def checkIfInside(recX1, recY1, recX2, recY2, x, y):
    return (((x >= recX1 and x <= recX2) or (x >= recX2 and x <= recX1))  and 
      ((y >= recY1 and y <= recY2) or (y >= recY2 and y <= recY1)))

for i in  range(1, len(points)):
    for j in  range(1, len(points)):
        for k in  range(1, len(points)):
            if i != j and i != k and j != k:
                recX1 = points[i][0]
                recY1 = points[i][1]
                recX2, recY2 = 0, 0
                if points[j][0] >= points[k][0]:
                    if points[j][0] >= recX1:
                        recX2 = points[j][0]
                    else:
                        recX2 = points[k][0]
                else:
                    if points[k][0] >= recX1:
                        recX2 = points[k][0]
                    else:
                        recX2 = points[j][0]
                if points[j][1] <= points[k][1]:
                    if points[j][1] <= recY1:
                        recY2 = points[j][1]
                    else:
                        recY2 = points[k][1]
                else:
                    if points[k][1] >= recY1:
                        recY2 = points[k][1]
                    else:
                        recY2 = points[j][1]
                countA, countB = 0, 0
                for s in range(1, len(points)):
                    if checkIfInside(recX1, recY1, recX2, recY2, points[s][0], points[s][1]):
                        countA += 1
                    if checkIfInside(recX1, recY1, points[j][0], points[j][1], points[s][0], points[s][1]):
                        countB += 1
                # print(str(recX1) + " " + str(recY1) + " " + str(recX2) + " " + str(recY2))
                if countA >= int(inps[1]):
                    mini = min(mini, abs(recX2-recX1)*abs(recY2-recY1))
                if countB >= int(inps[1]):
                    mini = min(mini, abs(points[j][0]-recX1)*abs(points[j][1]-recY1))

print(mini)

Submission status: Wrong Answer

Solution code:
nk=input().split()
n=int(nk[0])
k=int(nk[1])
xlist=[]
ylist=[]
ans=99999999999999999999999999999999999999
points=0
for t in range(n):
	xy=input().split()
	xlist.append(int(xy[0]))
	ylist.append(int(xy[1]))
for i in range(len(xlist)):
	for j in range(len(xlist)):
		points=0
		for m in range(len(xlist)):
			if ((xlist[m]>=xlist[i] and xlist[m]<=xlist[j]) or (xlist[m]<=xlist[i] and xlist[m]>=xlist[j]))and ((ylist[m]>=ylist[i] and ylist[m]<=ylist[j]) or (ylist[m]<=ylist[i] and ylist[m]>=ylist[j])):
				points=points+1
		if points>=k:
			ans=min(ans,(abs(xlist[i]-xlist[j]))*(abs(ylist[i]-ylist[j])))
print(ans)

Submission status: Wrong Answer

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

x_list = []
y_list = []
for _ in range(N):
    x, y = map(int, input().split())
    x_list.append(x)
    y_list.append(y)

x_list.sort()
y_list.sort()

min_area = float('inf')

for xi in range(N):
    for xj in range(xi + 1, N):
        for yi in range(N):
            for yj in range(yi + 1, N):
                num = 0
                lx = x_list[xi]
                rx = x_list[xj]
                by = y_list[yi]
                uy = y_list[yj]

                for i in range(N):
                    if lx <= x_list[i] <= rx and by <= y_list[i] <= uy:
                        num += 1
                if num >= K:
                    min_area = min(min_area, (rx - lx) * (uy - by))
print(min_area)

Submission status: Wrong Answer

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

x_list = []
y_list = []
for _ in range(N):
    x, y = map(int, input().split())
    x_list.append(x)
    y_list.append(y)

x_list.sort()
y_list.sort()

x_c_sum = []
for i in range(K - 1, len(x_list), K - 1):
    x_c_sum.append(abs(x_list[i] - x_list[i - (K - 1)]))

y_c_sum = []
for i in range(K - 1, len(y_list), K - 1):
    y_c_sum.append(abs(y_list[i] - y_list[i - (K - 1)]))

min_area = float('inf')
for i in range(len(x_c_sum)):
    min_area = min(min_area, x_c_sum[i] * y_c_sum[i])
print(min_area)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

N, K = map(int, input().split())
P = [tuple(map(int, input().split())) for _ in range(N)]
answers = {}

for s in P:
    for t in P:
        for r in P:
            for u in P:
                xs = [s[0], t[0], r[0], u[0]]
                ys = [s[1], t[1], r[1], u[1]]
                size = abs(max(xs) - min(xs)) * abs(max(ys) - min(ys))
                num_point = 0
                for v in P:
                    if min(xs) <= v[0] <= max(xs) and min(ys) <= v[1] <= max(ys):
                        num_point += 1
                if num_point >= K:
                    answers[num_point] = size
for k, v in sorted(answers.items()):
    print(v)
    break

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

N, K = map(int, input().split())
P = [tuple(map(int, input().split())) for _ in range(N)]
answers = {}

for s in P:
    for t in P:
        for r in P:
            for u in P:
                xs = [s[0], t[0], r[0], u[0]]
                ys = [s[1], t[1], r[1], u[1]]
                xs.sort(reverse=True)
                ys.sort(reverse=True)
                size = abs(abs(xs[0]) - abs(xs[-1])) * abs(abs(ys[0]) - abs(ys[-1]))
                num_point = 0
                for v in P:
                    if xs[-1] <= v[0] <= xs[0] and ys[-1] <= v[1] <= ys[0]:
                        num_point += 1
                if num_point >= K:
                    answers[num_point] = size
for k, v in sorted(answers.items()):
    print(v)
    break

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

N, K = map(int, input().split())
P = [tuple(map(int, input().split())) for _ in range(N)]
answers = {}

for s in P:
    for t in P:
        for r in P:
            for u in P:
                xs = [s[0], t[0], r[0], u[0]]
                ys = [s[1], t[1], r[1], u[1]]
                xs.sort(reverse=True)
                ys.sort(reverse=True)
                size = abs(xs[0] - xs[-1]) * abs(ys[0] - ys[-1])
                num_point = 0
                for v in P:
                    if xs[-1] <= v[0] <= xs[0] and ys[-1] <= v[1] <= ys[0]:
                        num_point += 1
                if num_point >= K:
                    answers[num_point] = size
for k, v in sorted(answers.items()):
    print(v)
    break

Submission status: Wrong Answer

Solution code:
def d_axis_parallel_rectangle(N, K, P):
    x_array, y_array = [], []  # 点のx,y座標
    for x, y in P:
        x_array.append(x)
        y_array.append(y)

    x_array = sorted(x_array)
    y_array = sorted(y_array)

    # すべての点を内部に含む、最大の面積を持つ矩形が初期値
    ans = (x_array[N - 1] - x_array[0]) * (y_array[N - 1] - y_array[0])

    # 全探索
    for xi in range(N):
        for xj in range(xi + 1, N):
            for yi in range(N):
                for yj in range(yi + 1, N):
                    num = 0
                    left = x_array[xi]
                    right = x_array[xj]
                    bottom = y_array[yi]
                    top = y_array[yj]

                    for i in range(N):
                        if left <= x_array[i] and x_array[i] <= right and bottom <= y_array[i] and y_array[i] <= top:
                            num += 1
                            if num == K:
                                ans = min(ans, (right - left) * (top - bottom))
                                break
    return ans

N,K = [int(i) for i in input().split()]
P = [[int(i) for i in input().split()] for j in range(N)]
print(d_axis_parallel_rectangle(N, K, P))

Submission status: Wrong Answer

Solution code:
def d_axis_parallel_rectangle(N, K, P):
    x_array, y_array = [], []  # 点のx,y座標
    for X, Y in P:
        x_array.append(X)
        y_array.append(Y)

    x_array = sorted(x_array)
    y_array = sorted(y_array)

    # すべての点を内部に含む、最大の面積を持つ矩形が初期値
    ans = (x_array[N - 1] - x_array[0]) * (y_array[N - 1] - y_array[0])

    # 全探索
    for xi in range(0, N, 1):
        for xj in range(xi + 1, N, 1):
            for yi in range(0, N, 1):
                for yj in range(yi + 1, N, 1):
                    num = 0
                    left = x_array[xi]
                    right = x_array[xj]
                    bottom = y_array[yi]
                    upper = y_array[yj]

                    for x,y in zip(x_array,y_array):
                        if(left <= x <= right and bottom <= y <= upper):
                            num += 1
                    if num >= K:
                        ans = min(ans, (right - left) * (upper - bottom))
    return ans

N,K = [int(i) for i in input().split()]
P = [[int(i) for i in input().split()] for j in range(N)]
print(d_axis_parallel_rectangle(N, K, P))

Submission status: Wrong Answer

Solution code:
import math
INF = 10000000000000000000000000000000000
N, K = map(int, input().split())
points = []
to_search_x = []
to_search_y = []
for i in range(N):
    xi, yi = map(int, input().split())
    points.append([xi, yi])
    to_search_x.append(xi)
    to_search_y.append(yi)

to_search_x.sort()
to_search_y.sort()

def is_between(x1, x2, x):
    if x >= x1 and x <= x2:
        return True
    elif x <= x1 and x >= x2:
        return True
    else:
        return False

def count(x1, x2, y1, y2):
    num = 0
    for i in range(N):
        if is_between(x1, x2, points[i][0]) and is_between(y1, y2, points[i][1]):
            num += 1
    return num

ans = INF
for i in range(N):
    for j in range(N):
        if count(to_search_x[i], to_search_x[j], to_search_y[i], to_search_y[j]) >= K:
            ans = min(ans, abs((to_search_x[i]-to_search_x[j])*(to_search_y[i]-to_search_y[j])))

print(ans)