Problem:


Score : 400 points

Problem Statement

We have N points in a two-dimensional plane.

The coordinates of the i-th point (1 \leq i \leq N) are (x_i,y_i).

Let us consider a rectangle whose sides are parallel to the coordinate axes that contains K or more of the N points in its interior.

Here, points on the sides of the rectangle are considered to be in the interior.

Find the minimum possible area of such a rectangle.  

Constraints

2 \leq K \leq N \leq 50 

-10^9 \leq x_i,y_i \leq 10^9 (1 \leq i \leq N) 

x_i≠x_j (1 \leq i<j \leq N) 

y_i≠y_j (1 \leq i<j \leq N) 

All input values are integers. (Added at 21:50 JST)  

Input

Input is given from Standard Input in the following format:  

N K  
x_1 y_1
:  
x_{N} y_{N}

Output

Print the minimum possible area of a rectangle that satisfies the condition.  

Sample Input 1

4 4
1 4
3 3
6 2
8 1

Sample Output 1

21

One rectangle that satisfies the condition with the minimum possible area has the following vertices: (1,1), (8,1), (1,4) and (8,4).

Its area is (8-1) × (4-1) = 21.  

Sample Input 2

4 2
0 0
1 1
2 2
3 3

Sample Output 2

1

Sample Input 3

4 3
-1000000000 -1000000000
1000000000 1000000000
-999999999 999999999
999999999 -999999999

Sample Output 3

3999999996000000001

Watch out for integer overflows.  



Sample input:
4 4
1 4
3 3
6 2
8 1


Sample output:
21

Submission status: Wrong Answer

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


def check(pa, pb):
    xa, ya = pa
    xb, yb = pb
    if xa > xb:
        xa, xb = xb, xa
    if ya > yb:
        ya, yb = yb, ya

    res = points[:]
    res = filter(lambda p: p[0] >= xa and p[0] <= xb and p[1] >= ya and p[1] <= yb, res)
    
    return list(res)

ans = int(9e20)
for a in range(N-1):
    for b in range(a+1, N):
        pa = points[a]
        pb = points[b]
        poss = check(pa, pb)
        if len(poss) >= K:
            tmp = abs(pa[0] - pb[0]) * abs(pa[1] - pb[1])
            ans = min(ans, tmp)
print(ans)

Submission status: Wrong Answer

Solution code:
N, K = map(int, raw_input().split())
ps = []
for i in xrange(N):
  ps.append(map(int, raw_input().split()))

xsorted = zip(*sorted(ps, key=lambda p: p[0]))[0]
ysorted = zip(*sorted(ps, key=lambda p: p[1]))[1]

ans = float('inf')
for i in xrange(N):
  bottom = ysorted[i]
  for j in xrange(i+K-1, N):
    top = ysorted[j]
    answered = False
    for k in xrange(N):
      right = xsorted[k]
      for l in xrange(k+K-1, N):
        left = xsorted[l]
        c = 0
        for a in xrange(N):
          if right <= ps[a][0] <= left and bottom <= ps[a][1] <= top:
            c += 1
            if c >= K: break
        else:
          continue
        area = (left - right) * (top - bottom)
        if area < ans:
          ans = area
        break
      else:
        continue
      answered = True
    if answered:
      break

print ans

Submission status: Wrong Answer

Solution code:
import numpy as np

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

points = np.empty((N, 2), dtype='int64')

for i in range(N):
    points[i] = list(map(int, input().split()))
    
xSortedPoints = points[points[:,0].argsort(),:]

for i in range(N-K+1):
    maxY = np.max(xSortedPoints[i:i+K, 1])
    minY =  np.min(xSortedPoints[i:i+K, 1])
    
    currentSquare = (xSortedPoints[i+K-1, 0] - xSortedPoints[i, 0])*(maxY-minY)
    
    if i == 0:
        minSquare = currentSquare
    elif minSquare > currentSquare:
        minSquare = currentSquare

print(int(minSquare))

# 4 3
# -1000000000 -1000000000
# 1000000000 1000000000
# -999999999 999999999
# 999999999 -999999999

Submission status: Wrong Answer

Solution code:
N, K = map(int, raw_input().split())
ps = []
for i in xrange(N):
  ps.append(map(int, raw_input().split()))

xsorted = zip(*sorted(ps, key=lambda p: p[0]))[0]
ysorted = zip(*sorted(ps, key=lambda p: p[1]))[1]

ans = float('inf')
for i in xrange(N):
  bottom = ysorted[i]
  for j in xrange(i+K-1, N):
    top = ysorted[j]
    for k in xrange(N):
      right = xsorted[k]
      for l in xrange(k+K-1, N):
        left = xsorted[l]
        c = 0
        for a in xrange(N):
          if right <= ps[a][0] <= left and bottom <= ps[a][1] <= top:
            c += 1
            if c >= K: break
        else:
          continue
        area = (left - right) * (top - bottom)
        if area < ans:
          ans = area
        break
      else:
        continue
      break
    else:
      continue
    break

print ans

Submission status: Wrong Answer

Solution code:


def menseki(S):
    sx=[ss[0] for ss in S]
    sy=[ss[1] for ss in S]

    zahyominmax=[min(sx),max(sx),min(sy),max(sy)]
    return (zahyominmax[1]-zahyominmax[0])*(zahyominmax[3]-zahyominmax[2])



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



N,K=spaceinput()

x=[]
for i in range(N):
    x.append(spaceinput())

x=sorted(x,key=lambda s:s[0])

S=x[:K]

sx=[ss[0] for ss in S]
sy=[ss[1] for ss in S]

zahyominmax=[min(sx),max(sx),min(sy),max(sy)]
minmenseki=(zahyominmax[1]-zahyominmax[0])*(zahyominmax[3]-zahyominmax[2])


for i in range(K,len(x)):

    #print(S)
    a=x[i]
    S.append(a)

    #minmenseki=menseki
    kmin=len(S)-1
    for k in range(len(S)):
        bb=S[:k]
        bb.extend(S[k+1:])
        s=menseki(bb)
        if s<minmenseki:
            minmenseki=s
            kmin=k

    del S[kmin]


print(minmenseki)

Submission status: Wrong Answer

Solution code:


def menseki(S):
    sx=[ss[0] for ss in S]
    sy=[ss[1] for ss in S]

    zahyominmax=[min(sx),max(sx),min(sy),max(sy)]
    return (zahyominmax[1]-zahyominmax[0])*(zahyominmax[3]-zahyominmax[2])



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



N,K=spaceinput()

x=[]
for i in range(N):
    x.append(spaceinput())

x=sorted(x,key=lambda s:s[0])

S=x[:K]

sx=[ss[0] for ss in S]
sy=[ss[1] for ss in S]

zahyominmax=[min(sx),max(sx),min(sy),max(sy)]
minmenseki=(zahyominmax[1]-zahyominmax[0])*(zahyominmax[3]-zahyominmax[2])


for i in range(K,len(x)):

    #print(S)
    a=x[i]
    S.append(a)

    #minmenseki=menseki
    for k in range(len(S)):
        bb=S[:k]
        bb.extend(S[k+1:])
        s=menseki(bb)
        if s<minmenseki:
            minmenseki=s
            kmin=k


    #menseki=minmenseki
    del S[k]


print(minmenseki)

Submission status: Wrong Answer

Solution code:
import numpy as np

n,k = input().split()
n = int(n)
k = int(k)
xy_list = []
for i in range(n):
    x,y = input().split()
    x = int(x)
    y = int(y)
    xy_list.append([x,y])
    
ar = np.array(xy_list)

def menseki_all(ar):
    max_x = ar[:,0].max()
    min_x = ar[:,0].min()
    max_y = ar[:,1].max()
    min_y = ar[:,1].min()
    return (max_x-min_x)*(max_y-min_y)

k_ar = np.ones(len(ar),dtype=bool)
while k_ar.sum() > k:
    max_x_idx = np.argmax(ar[:,0])
    min_x_idx = np.argmin(ar[:,0])
    max_y_idx = np.argmax(ar[:,1])
    min_y_idx = np.argmin(ar[:,1])
    
    max_min_xy_idx = [max_x_idx,min_x_idx,max_y_idx,min_y_idx]
    menseki_list = []
    
    for i in max_min_xy_idx:
        tmp_k_ar = k_ar.copy()
        tmp_k_ar[i] = False
        menseki_list.append(menseki_all(ar[tmp_k_ar]))
    
    ar_menseki = np.array(menseki_list)
    delete_idx = max_min_xy_idx[ar_menseki.argmin()]
    
    ar = np.delete(ar,delete_idx,0)
    k_ar = np.ones(len(ar),dtype=bool)

print(menseki_all(ar))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import copy

n, k = [int(i) for i in input().split()]
num_list_x = [[int(i) for i in input().split()] for _ in range(n)]
num_list_x.sort()
curr_square = 0

for pos in range(n - k + 1):
    distance_x = num_list_x[pos + k - 1][0] - num_list_x[pos][0]
    num_list_y = copy.deepcopy(num_list_x[pos:pos+k])
    num_list_y.sort(key=lambda number: number[1])
    distance_y = num_list_y[-1][1] - num_list_y[0][1]
    curr_square = max(curr_square, distance_x * distance_y)
print(curr_square)

Submission status: Wrong Answer

Solution code:
from sys import stdin
n,k = map(int,stdin.readline().split())
a = []
for i in xrange(n):
 a.append(map(int,stdin.readline().split()))
def solve(i,j,u,v):
 cnt = 0
 minx = min(a[i][0],a[j][0])
 maxx =  max(a[i][0],a[j][0])
 miny = min(a[i][1],a[j][1])
 maxy = max(a[i][1],a[j][1])
 
 minx1 = min(a[u][0],a[v][0])
 maxx1 =  max(a[u][0],a[v][0])
 miny1 = min(a[u][1],a[v][1])
 maxy1 = max(a[u][1],a[v][1])
 
 minx = min(minx,minx1)
 miny = min(miny,miny1)
 maxx = max(maxx,maxx1)
 maxy = max(maxy,maxy1)
 #print "solving",i,j,u,v,minx,maxx,miny,maxy
 for m in xrange(n):
  if a[m][0]>=minx and a[m][0]<=maxx and a[m][1]>=miny and a[m][1]<=maxy:
   cnt+=1
 #print "has",cnt
 if cnt>=k:
  return (maxx-minx)*(maxy-miny)
 return 10**100
ans = 10**50
for i in xrange(n):
 for j in xrange(n):
  for u in xrange(n):
   ans = min(ans,solve(i,j,u,i))
print ans

Submission status: Wrong Answer

Solution code:
from sys import stdin
n,k = map(int,stdin.readline().split())
a = []
for i in xrange(n):
 a.append(map(int,stdin.readline().split()))
def solve(i,j,u,v):
 cnt = 0
 minx = min(a[i][0],a[j][0])
 maxx =  max(a[i][0],a[j][0])
 miny = min(a[i][1],a[j][1])
 maxy = max(a[i][1],a[j][1])
 
 minx1 = min(a[u][0],a[v][0])
 maxx1 =  max(a[u][0],a[v][0])
 miny1 = min(a[u][1],a[v][1])
 maxy1 = max(a[u][1],a[v][1])
 
 minx = min(minx,minx1)
 miny = min(miny,miny1)
 maxx = max(maxx,maxx1)
 maxy = max(maxy,maxy1)
 #print "solving",i,j,minx,maxx,miny,maxy
 for m in xrange(n):
  if a[m][0]>=minx and a[m][0]<=maxx and a[m][1]>=miny and a[m][1]<=maxy:
   cnt+=1
 #print "has",cnt
 if cnt>=k:
  return (maxx-minx)*(maxy-miny)
 return 10**100
ans = 10**50
for i in xrange(n):
 for j in xrange(i+1,n):
  for u in xrange(j+1,n):
   for v in xrange(u+1,n):
    ans = min(ans,solve(i,j,u,v))
print ans

Submission status: Wrong Answer

Solution code:


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



N,K=spaceinput()

x=[]
for i in range(N):
    x.append(spaceinput())

x=sorted(x,key=lambda s:s[0])

S=x[:K]

sx=[ss[0] for ss in S]
sy=[ss[1] for ss in S]

zahyominmax=[min(sx),max(sx),min(sy),max(sy)]
menseki=(zahyominmax[1]-zahyominmax[0])*(zahyominmax[3]-zahyominmax[2])


for i in range(K,len(x)):
    a=x[i]
    nzahyominmax=zahyominmax[:]
    nzahyominmax[1]=a[0]

    if nzahyominmax[2]>a[1]:
        nzahyominmax[2]=a[1]

    if nzahyominmax[3]<a[1]:
        nzahyominmax[3]=a[1]


    news=(zahyominmax[1]-zahyominmax[0])*(zahyominmax[3]-zahyominmax[2])

    if menseki>news:
        menseki=news


print(menseki)

Submission status: Wrong Answer

Solution code:
from sys import stdin
n,k = map(int,stdin.readline().split())
a = []
for i in xrange(n):
 a.append(map(int,stdin.readline().split()))
def solve(i,j,a,n):
 cnt = 0
 minx = min(a[i][0],a[j][0])
 maxx =  max(a[i][0],a[j][0])
 miny = min(a[i][1],a[j][1])
 maxy = max(a[i][1],a[j][1])
 #print "solving",i,j,minx,maxx,miny,maxy
 for m in xrange(n):
  if a[m][0]>=minx and a[m][0]<=maxx and a[m][1]>=miny and a[m][1]<=maxy:
   cnt+=1
 #print "has",cnt
 if cnt>=k:
  return (maxx-minx)*(maxy-miny)
 return 10**100
ans = 10**50
for i in xrange(n):
 for j in xrange(i+1,n):
  ans = min(ans,solve(i,j,a,n))
print ans

Submission status: Wrong Answer

Solution code:
def i1():
 return int(input())
def i2():
 return [int(i) for i in input().split()]
[n,k]=i2()
x=[]
y=[]
for i in range(n):
 z=i2()
 x.append(z[0])
 y.append(z[1])
x.sort()
y.sort()
a=float("inf")
for i in range(n):
 for j in range(i,n):
  for kk in range(n):
    for l in range(kk,n):
      if min(j-i+1,l-kk+1)==k:
       a=min(a,(x[j]-x[i])*(y[l]-y[kk]))  
print(a)

Submission status: Time Limit Exceeded

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

ans = float("inf")
for i in S:
    for j in S:
        for k in T:
            for l in T:
                c = 0
                for x, y in A:
                    if i <= x <= j:
                        if k <= y <= l:
                            c += 1
                if c >= K:
                    ans = min(ans, (j - i)*(l - k))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
xv, yv = [], []
xy = []
for _ in range(n):
    x, y = map(int, input().split())
    xv.append(x)
    yv.append(y)
    xy.append((x, y))

xv = sorted(xv)
yv = sorted(yv)
ans = (xv[n-1] - xv[0]) * (yv[n-1] - yv[0])
for l in range(n):
    lx = xv[l]
    for r in range(l+1, n):
        rx = xv[r]
        for b in range(n):
            by = yv[b]
            for t in range(b+1, n):
                ty = yv[t]
                cnt = 0
                for x, y in xy:
                    if lx <= x <= rx and by <= y <= ty:
                        cnt += 1
                if cnt >= k:
                    ans = min(ans, (rx - lx)*(ty - by))
print(ans)

Submission status: Time Limit Exceeded

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

P = [[int(_) for _ in input().split()] for n in range(N)]

X = []
Y = []
for n in range(N):
    x, y = P[n]
    X.append(x)
    Y.append(y)
X.sort()
Y.sort()

ans = 10 ** 20
for xi in range(N):
    for xj in range(xi+1, N):
        for yi in range(N):
            for yj in range(yi+1, N):
                x1, y1 = X[xi], Y[yi]
                x2, y2 = X[xj], Y[yj]
                c = 0
                for v in range(N):
                    x, y = P[v]
                    if x1 <= x <= x2 and y1 <= y <= y2:
                        c += 1
                if c >= K:
                    ans = min(ans, (x2-x1) * (y2-y1))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def TUPLE(): return tuple(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

N, K = MAP()
xy = [LIST() for _ in range(N)]
x, y = zip(*xy)

x = sorted(x)
y = sorted(y)

ans = INF
for ax, bx in combinations(x, 2):
	for ay, by in combinations(y, 2):
		cnt = 0
		for cx, cy in xy:
			if ax <= cx <= bx and ay <= cy <= by:
				cnt += 1
		if K <= cnt:
			ans = min(ans, (bx-ax)*(by-ay))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def TUPLE(): return tuple(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

N, K = MAP()
xy = [LIST() for _ in range(N)]

ans = INF
for (ax, ay), (bx, by) in combinations(xy, 2):
	edge_left = min(ax, bx)
	edge_right = max(ax, bx)
	edge_top = max(ay, by)
	edge_bottom = min(ay, by)
	cnt = 0
	for cx, cy in xy:
		if cx == ax or cx == bx:
			continue
		elif edge_left <= cx <= edge_right and edge_bottom <= cy <= edge_top:
			cnt += 1
	if K <= cnt+2:
		ans = min((edge_right-edge_left)*(edge_top-edge_bottom), ans)

for (ax, ay), (bx, by), (cx, cy) in combinations(xy, 3):
	edge_left = min(ax, bx, cx)
	edge_right = max(ax, bx, cx)
	edge_top = max(ay, by, cy)
	edge_bottom = min(ay, by, cy)
	cnt = 0
	for dx, dy in xy:
		if dx == ax or dx == bx or dx == cx:
			continue
		elif edge_left <= dx <= edge_right and edge_bottom <= dy <= edge_top:
			cnt += 1
	if K <= cnt+3:
		ans = min((edge_right-edge_left)*(edge_top-edge_bottom), ans)

for (ax, ay), (bx, by), (cx, cy), (dx, dy) in combinations(xy, 4):
	edge_left = min(ax, bx, cx, dx)
	edge_right = max(ax, bx, cx, dx)
	edge_top = max(ay, by, cy, dy)
	edge_bottom = min(ay, by, cy, dy)
	cnt = 0
	for ex, ey in xy:
		if ex == ax or ex == bx or ex == cx or ex == dx:
			continue
		elif edge_left <= ex <= edge_right and edge_bottom <= ey <= edge_top:
			cnt += 1
	if K <= cnt+4:
		ans = min((edge_right-edge_left)*(edge_top-edge_bottom), ans)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations, product
from functools import reduce
import bisect as bs
from collections import namedtuple

Area = namedtuple('Area', ['xinf', 'xsup', 'yinf', 'ysup'])

def tuple_int(iterable):
    return tuple(map(int, iterable.split()))

def insert_xy(line):
    x, y = map(int, line.split())
    X.insert(bs.bisect_left(X,x), x)
    Y.insert(bs.bisect_left(Y,y), y)
    return X, Y

def S_with_K_plots(X, Y, K):
    result = []
    for x, y in product(combinations(X,2), combinations(Y,2)):
        area = Area(xinf=min(x),xsup=max(x),yinf=min(y),ysup=max(y))
        S = (area.xsup-area.xinf)*(area.ysup-area.yinf)
        if count_plots(area) == K:
            result.append(S)
    return result

def count_plots(area):
    is_in_the_area = lambda x: is_in_area(x, area)
    return sum(map(is_in_the_area, plots))

def is_in_area(plot, area):
    between = lambda a, b, c:True if b <= a <= c else False
    x, y = plot
    x1, x2, y1, y2 = area
    if between(x, x1, x2) and between(y, y1, y2):
        return 1
    else:
        return 0

if __name__ == '__main__':
    with open(0) as f:
        N, K = map(int, f.readline().split())
        data = f.readlines()
    plots = list(map(tuple_int, data))
    X, Y = [], []
    for x, y in plots:
        X.append(x); Y.append(y)
    print(min(S_with_K_plots(X, Y, K)))

Submission status: Time Limit Exceeded

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

dot=[]
xxx=[]
yyy=[]

ans=float('inf')

for i in range(n):
  x,y=map(int,input().split())
  dot.append([x,y])
  xxx.append(x)
  yyy.append(y)

for sx in xxx:
  for sy in yyy:
    for gx in xxx:
      for gy in yyy:
        if sx==gx or sy==gy:
          continue
        cnt=0
        for lst in dot:
          if sx<=lst[0]<=gx or gx<=lst[0]<=sx:
            if sy<=lst[1]<=gy or gy<=lst[1]<=sy:
              cnt+=1
      
        if cnt>=k:
          ans=min(ans,abs(sx-gx)*abs(sy-gy))


print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
nodes=[]
for i in range(N):
  x,y=map(int,input().split())
  nodes.append((x,y))
import math
ans=math.inf
count=0
for i in range(N):
  for j in range(N):
    for k in range(N):
      for l in range(N):
        count=0
        for m in range(N):
          if nodes[i][0]<=nodes[m][0]<=nodes[j][0] and nodes[k][1]<=nodes[m][1]<=nodes[l][1]:
            count+=1
        if count>=K:
          ans=min(ans,(nodes[j][0]-nodes[i][0])*(nodes[l][1]-nodes[k][1]))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def abc075_d():
    n, k = map(int, input().split())
    P = []
    xarr = []
    yarr = []
    for _ in range(n):
        x, y = (int(x) for x in input().split())
        P.append((x, y))
        xarr.append(x)
        yarr.append(y)
    xarr.sort()
    yarr.sort()

    def count_inside(xi, xj, yi, yj)->int:
        res = 0
        for x, y in P:
            if xi <= x and x <= xj and yi <= y and y <= yj:
                res += 1
        return res

    ans = 5*10**18
    for s, xi in enumerate(xarr):
        for xj in xarr[s+1:]:
            for t, yi in enumerate(yarr):
                for yj in yarr[t+1:]:
                    if count_inside(xi, xj, yi, yj) >= k:
                        area = (xj - xi) * (yj - yi)
                        ans = min(ans, area)
    print(ans)

if __name__ == '__main__':
    abc075_d()

Submission status: Time Limit Exceeded

Solution code:
def abc075_d():
    n, k = map(int, input().split())
    P = []
    xarr = []
    yarr = []
    for _ in range(n):
        x, y = (int(x) for x in input().split())
        P.append((x, y))
        xarr.append(x)
        yarr.append(y)
    xarr.sort()
    yarr.sort()

    def count_inside(xi, xj, yi, yj)->int:
        res = 0
        for x, y in P:
            if xarr[xi] <= x and x <= xarr[xj] and yarr[yi] <= y and y <= yarr[yj]:
                res += 1
        return res

    ans = 5*10**18
    for xi in range(n-1):
        for xj in range(xi+1, n):
            for yi in range(n-1):
                for yj in range(yi+1, n):
                    if count_inside(xi, xj, yi, yj) >= k:
                        area = (xarr[xj] - xarr[xi]) * (yarr[yj] - yarr[yi])
                        ans = min(ans, area)
    print(ans)

if __name__ == '__main__':
    abc075_d()

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
x=[0]*n
y=[0]*n
for i in range(n):
  x[i],y[i]=map(int,input().split())
ans=10**19
for i in range(n):
  for j in range(n):
    for k in range(n):
      for l in range(n):
        xl=min(x[i],x[j],x[k],x[l])
        xr=max(x[i],x[j],x[k],x[l])
        yl=min(y[i],y[j],y[k],y[l])
        yh=max(y[i],y[j],y[k],y[l])
        cnt=0
        for c in range(n):
          cnt+=xl<=x[c]<=xr and yl<=y[c]<=yh
        if cnt>=m:ans=min(ans,(xr-xl)*(yh-yl))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections, itertools, sys
import numpy as np
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def S(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()

def resolve():
    N, K = LI()
    xy = [LI() for _ in range(N)]

    # x, y全ての重複あり組み合わせに対して含まれる点の個数を算出する

    x_cnt = collections.Counter([i[0] for i in xy])
    x_coordinate = np.array(list((x_cnt.keys())))
    x_coordinate.sort()
    len_x_c = len(x_coordinate)
    y_cnt = collections.Counter([i[1] for i in xy])
    y_coordinate = np.array(list(y_cnt.keys()))
    y_coordinate.sort()
    len_y_c = len(y_coordinate)

    ans = INF
    for k in range(len_x_c - 1):
        xl = x_coordinate[k]
        for l in range(k + 1, len_y_c):
            xh = x_coordinate[l]
            # 4番目の辺の探索は、個数条件を満たしたら終了していよい
            for i in range(len_y_c - 1):
                yl = y_coordinate[i]
                for j in range(i + 1, len_y_c):
                    yh = y_coordinate[j]
                    cnt = len([(i, j) for i, j in xy if xl <= i <= xh and yl <= j <= yh])
                    if cnt >= K:
                        ans = min((xh - xl) * (yh - yl), ans)
                        break

    print(ans)

if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

Solution code:
import collections, itertools, sys
import numpy as np
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def S(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()

def resolve():
    N, K = LI()
    xy = [LI() for _ in range(N)]

    # x, y全ての重複あり組み合わせに対して含まれる点の個数を算出する

    x_cnt = collections.Counter([i[0] for i in xy])
    x_coordinate = np.array(list((x_cnt.keys())))
    x_coordinate.sort()
    # len_x_c = len(x_coordinate)
    y_cnt = collections.Counter([i[1] for i in xy])
    y_coordinate = np.array(list(y_cnt.keys()))
    y_coordinate.sort()
    len_y_c = len(y_coordinate)

    ans = INF
    for xl, xh in itertools.combinations(x_coordinate, 2):
        # 4番目の辺の探索は、個数条件を満たしたら終了していよい
        for i in range(len_y_c - 1):
            yl = y_coordinate[i]
            for j in range(i + 1, len_y_c):
                yh = y_coordinate[j]
                cnt = len([(i, j) for i, j in xy if xl <= i <= xh and yl <= j <= yh])
                if cnt >= K:
                    ans = min((xh - xl) * (yh - yl), ans)
                    break

    print(ans)

if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

Solution code:
import collections, itertools, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def S(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()

def resolve():
    N, K = LI()
    xy = [LI() for _ in range(N)]

    # x, y全ての重複あり組み合わせに対して含まれる点の個数を算出する

    x_cnt = collections.Counter([i[0] for i in xy])
    x_coordinate = list(x_cnt.keys())
    x_coordinate.sort()
    # len_x_c = len(x_coordinate)
    y_cnt = collections.Counter([i[1] for i in xy])
    y_coordinate = list(y_cnt.keys())
    y_coordinate.sort()
    len_y_c = len(y_coordinate)

    ans = INF
    for xl, xh in itertools.combinations(x_coordinate, 2):
        # 4番目の辺の探索は、個数条件を満たしたら終了していよい
        for i in range(len_y_c - 1):
            yl = y_coordinate[i]
            for j in range(i + 1, len_y_c):
                yh = y_coordinate[j]
                cnt = len([(i, j) for i, j in xy if xl <= i <= xh and yl <= j <= yh])
                if cnt >= K:
                    ans = min((xh - xl) * (yh - yl), ans)
                    break

    print(ans)

if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

Solution code:
import collections, itertools, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def S(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()

def resolve():
    N, K = LI()
    xy = [LI() for _ in range(N)]

    # x, y全ての重複あり組み合わせに対して含まれる点の個数を算出する

    x_cnt = collections.Counter([i[0] for i in xy])
    x_coordinate = list(x_cnt.keys())
    x_coordinate.sort()
    y_cnt = collections.Counter([i[1] for i in xy])
    y_coordinate = list(y_cnt.keys())
    y_coordinate.sort()

    ans = INF
    for x0, x1 in itertools.combinations_with_replacement(x_coordinate, 2):
        for y0, y1 in itertools.combinations_with_replacement(y_coordinate, 2):
            cnt = len([(i, j) for i, j in xy if x0 <= i <= x1 and y0 <= j <= y1])
            if cnt >= K:
                ans = min((x1 - x0) * (y1 - y0), ans)

    print(ans)

if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys, itertools, collections
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def S(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()

def resolve():
    N, K = LI()
    xy = [LI() for _ in range(N)]

    # x, y全ての重複あり組み合わせに対して含まれる点の個数を算出する

    x_cnt = collections.Counter([i[0] for i in xy])
    x_coordinate = list(x_cnt.keys())
    x_coordinate.sort()
    y_cnt = collections.Counter([i[1] for i in xy])
    y_coordinate = list(y_cnt.keys())
    y_coordinate.sort()

    ans = INF
    for x0, x1 in itertools.combinations_with_replacement(x_coordinate, 2):
        for y0, y1 in itertools.combinations_with_replacement(y_coordinate, 2):
            cnt = len([(i, j) for i, j in xy if x0 <= i <= x1 and y0 <= j <= y1])
            if cnt >= K:
                ans = min((x1 - x0) * (y1 - y0), ans)

    print(ans)

if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
N, K = map(int, input().split())
P = [list(map(int, input().split())) for _ in range(N)]
ans = 1<<62
for t in combinations(P, min(4, K)):
    xs, ys = zip(*t)
    xmin = min(xs)
    xmax = max(xs)
    ymin = min(ys)
    ymax = max(ys)
    area = (xmax-xmin) * (ymax-ymin)
    if ans < area:
        continue
    k = 0
    for x, y in P:
        if xmin <= x <= xmax and ymin <= y <= ymax:
            k += 1
    if k >= K:
        ans = area
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, K = (int(x) for x in input().split())
Plot = [tuple(int(x) for x in input().split()) for _ in range(N)]
X = [p[0] for p in Plot]
Y = [p[1] for p in Plot]
X.sort()
Y.sort()
#全2点間で長方形の辺を作り、その内内部点がK個のものだけ面積を比較する。
ans = 10e20
from itertools import combinations
for x1, x2 in combinations(X, 2):
    for y1, y2 in combinations(Y, 2):
        cnt = sum(x1 <= x <= x2 and y1 <= y <= y2 for x,y in Plot)
        if cnt == K:
            S = (x2-x1)*(y2-y1)
            ans = min(ans, S)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, K = (int(x) for x in input().split())
Plot = [tuple(int(x) for x in input().split()) for _ in range(N)]
X = [p[0] for p in Plot]
Y = [p[1] for p in Plot]
X.sort()
Y.sort()
#全2点間で長方形の辺を作り、その内内部点がK個のものだけ面積を比較する。
ans = 10e20
from itertools import combinations
for x1, x2 in combinations(X, 2):
    for y1, y2 in combinations(Y, 2):
        S = (x2-x1)*(y2-y1)
        cnt = sum(x1 <= p[0] <= x2 and y1 <= p[1] <= y2 for p in Plot)
        if cnt == K and S != 0:
            ans = min(ans, S)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, K = (int(x) for x in input().split())
Plot = [tuple(int(x) for x in input().split()) for _ in range(N)]
X = [p[0] for p in Plot]
Y = [p[1] for p in Plot]
X.sort()
Y.sort()
#全2点間で長方形の辺を作り、その内内部点がK個のものだけ面積を比較する。
ans = 10e20
from itertools import combinations
for x1, x2 in combinations(X, 2):
    for y1, y2 in combinations(Y, 2):
        S = (x2-x1)*(y2-y1)
        cnt = 0
        for p in Plot:
            if x1 <= p[0] <= x2 and y1 <= p[1] <= y2:
                cnt += 1
        if cnt == K and S != 0:
            ans = min(ans, S)
print(ans)