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())
A=[]
B=[]
for i in range(N):
  a=[int(x) for x in input().split()]
  A.append(a)
  B.append([a[1],a[0]])
A.sort()
B.sort()

ans=[float('inf') for x in range(N)]
ansY=[float('inf') for x in range(N)]

for i in range(N-K+1):
  X=abs(A[i+K-1][0]-A[i][0])
  maY=-10000000000
  miY=float('inf')
  for j in range(i,i+K):
    maY=max(maY,A[j][1])
    miY=min(miY,A[j][1])
  ans[i]=X*(abs(maY-miY))
for i in range(N-K+1):
  Y=abs(B[i+K-1][0]-B[i][0])
  maX=-10000000000
  miX=float('inf')
  for j in range(i,i+K):
    maX=max(maX,B[j][1])
    miX=min(miX,B[j][1])
  ansY[i]=Y*(abs(maX-miX))

print(min(min(ans),min(ansY)))

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
A=[]
B=[]
for i in range(N):
  a=[int(x) for x in input().split()]
  A.append(a)
  B.append([a[1],a[0]])
A.sort()
B.sort()

ans=[float('inf') for x in range(N)]
ansY=[float('inf') for x in range(N)]

for i in range(N-K+1):
  X=abs(A[i+K-1][0]-A[i][0])
  maY=-10000000000
  miY=float('inf')
  for j in range(i,i+K):
    maY=max(maY,A[j][1])
    miY=min(miY,A[j][1])
  ans[i]=X*(abs(maY-miY))
for i in range(N-K+1):
  Y=abs(A[i+K-1][0]-A[i][0])
  maX=-10000000000
  miX=float('inf')
  for j in range(i,i+K):
    maX=max(maX,B[j][1])
    miX=min(miX,B[j][1])
  ansY[i]=Y*(abs(maX-miX))

print(min(min(ans),min(ansY)))

Submission status: Wrong Answer

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


ans=[float('inf') for x in range(N)]

for i in range(N-K+1):
  X=abs(A[i+K-1][0]-A[i][0])
  maY=-10000000000
  miY=float('inf')
  for j in range(i,i+K):
    maY=max(maY,A[j][1])
    miY=min(miY,A[j][1])
  ans[i]=X*(abs(maY-miY))

print(min(ans))

Submission status: Wrong Answer

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

ans=[float('inf') for x in range(N)]

for i in range(N-K+1):
  X=abs(A[i+K-1][0]-A[i][0])
  maY=0
  miY=float('inf')
  for j in range(i,i+K):
    maY=max(maY,A[j][1])
    miY=min(miY,A[j][1])
  ans[i]=X*(abs(maY-miY))

print(min(ans))

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
x=[0 for i in range(N)]
y=[0 for i in range(N)]
p=[0 for i in range(N)]
q=[0 for i in range(N)]
for i in range(N):
    x[i],y[i]=map(int,input().split())
    p[i],q[i]=x[i],y[i]
p.sort()
q.sort()
S=[[0 for i in range(N)]for i in range(N)]
R=abs((p[N-1]-p[0])*(q[N-1]-q[0]))
for n in range(N):
    for i in range(N):
        for j in range(N):
            if x[n]<=p[i] and y[n]<=q[j]:
                S[i][j]+=1
for a in range(N):
    for b in range(N):
        for c in range(a,N):
            for d in range(b,N):
                if (S[c][d]+S[a][b]-S[c][b]-S[d][a])>=K:
                    if abs((p[c]-p[a])*(q[d]-q[b]))<R:
                        R=abs(p[c]-p[a])*abs(q[d]-q[b])
print(R)

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
x=[0 for i in range(N)]
y=[0 for i in range(N)]
p=[0 for i in range(N)]
q=[0 for i in range(N)]
for i in range(N):
    x[i],y[i]=map(int,input().split())
    p[i],q[i]=x[i],y[i]
p.sort()
q.sort()
S=[[0 for i in range(N)]for i in range(N)]
R=abs((p[N-1]-p[0])*(q[N-1]-q[0]))
for n in range(N):
    for i in range(N):
        for j in range(N):
            if x[n]<=p[i] and y[n]<=q[j]:
                S[i][j]+=1
for a in range(N):
    for b in range(N):
        for c in range(a,N):
            for d in range(b,N):
                if (S[c][d]+S[a][b]-S[c][b]-S[d][a]+1)>=K:
                    if abs((p[c]-p[a])*(q[d]-q[b]))<R:
                        R=abs(p[c]-p[a])*abs(q[d]-q[b])
print(R)

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
x=[0 for i in range(N)]
y=[0 for i in range(N)]
p=[0 for i in range(N)]
q=[0 for i in range(N)]
for i in range(N):
    x[i],y[i]=map(int,input().split())
    p[i],q[i]=x[i],y[i]
p.sort()
q.sort()
S=[[0 for i in range(N)]for i in range(N)]
R=abs((p[N-1]-p[0])*(q[N-1]-q[0]))
for n in range(N):
    for i in range(N):
        for j in range(N):
            if x[n]<=p[i] and y[n]<=q[j]:
                S[i][j]+=1
for a in range(N-1):
    for b in range(N-1):
        for c in range(a+1,N):
            for d in range(b+1,N):
                if (S[c][d]+S[a][b]-S[c][b]-S[d][a]+1)>=K:
                    if abs((p[c]-p[a])*(q[d]-q[b]))<R:
                        R=abs(p[c]-p[a])*abs(q[d]-q[b])
print(R)

Submission status: Wrong Answer

Solution code:
import numpy
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())
s = list(numpy.argsort(numpy.array(x)))
R = 4*10**18
for i in range(N-K+1):
    P = x[s[i+K-1]]-x[s[i]]
    D = [y[s[i]] for i in range(i,i+K)]
    Q = max(D)-min(D)
    if R>P*Q:
        R=P*Q
print(R)

Submission status: Wrong Answer

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

cums = [[0 for j in range(N + 1)] for i in range(N + 1)]
for i in range(N):
    for j in range(N):
        Xc, Yc = XY[i][0], YX[j][0]
        cnt = 0
        for x, y in XY:
            if (x <= Xc) & (y <= Yc):
                cnt += 1
        cums[i+1][j+1] = cnt

ans = float('inf')

for i in range(N-1):
    for j in range(i+1, N):
        for k in range(N-1):
            for l in range(k+1, N):
                if cums[l+1][j+1] - cums[l+1][i] - cums[k][j+1] + cums[k][i] >= K:
                        ans = min(ans, (XY[j][0]-XY[i][0]) * (YX[l][0]-YX[k][0]))

print(ans)

Submission status: Wrong Answer

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

cums = [[0 for j in range(N + 1)] for i in range(N + 1)]
for i in range(N):
    for j in range(N):
        Xc, Yc = XY[i][0], YX[j][0]
        cnt = 0
        for x, y in XY:
            if (x <= Xc) & (y <= Yc):
                cnt += 1
        cums[i+1][j+1] = cnt

ans = float('inf')

for i in range(N-1):
    for j in range(i+1, N):
        for k in range(N-1):
            for l in range(k+1, N):
                if (XY[i][0] > XY[i][0]) or (YX[k][0] > XY[l][0]):
                    continue
                if cums[l+1][j+1] - cums[l+1][i] - cums[k][j+1] + cums[k][i] >= K:
                        ans = min(ans, (XY[j][0]-XY[i][0]) * (YX[l][0]-YX[k][0]))

print(ans)

Submission status: Wrong Answer

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

cums = [[0 for j in range(N + 1)] for i in range(N + 1)]
for i in range(N):
    for j in range(N):
        Xc, Yc = XY[i][0], YX[j][0]
        cnt = 0
        for x, y in XY:
            if (x <= Xc) & (y <= Yc):
                cnt += 1
        cums[i+1][j+1] = cnt

ans = float('inf')

for i in range(N):
    for j in range(N):
        for k in range(N):
            for l in range(N):
                if cums[l+1][j+1] - cums[l+1][i] - cums[k][j+1] + cums[k][i] >= K:
                        ans = min(ans, (XY[j][0]-XY[i][0]) * (YX[l][0]-YX[k][0]))

print(ans)

Submission status: Wrong Answer

Solution code:


def main():
    N, K = map(int, input().split())
    x, y = zip(*(
        map(int, input().split())
        for _ in range(N)
    ))

    f(N, K, x, y)


def f(N, K, x, y):
    """
    制約
    * 2≦K≦N≦50
    * −10^9≦xi,yi≦10^9 (1≦i≦N)
    * xi≠xj (1≦i<j≦N)
    * yi≠yj (1≦i<j≦N)
    * 入力値はすべて整数である。(21:50 追記)

    長方形の内部にN点のうち
    K個以上の点を含みつつ、
    それぞれの辺がX軸かY軸に平行な長方形を考えます。
    →最小の面積

    制約より、
    xyの範囲を全探索はTLE
    点は重ならないかつ、50以下
    →点の座標から求めれば間に合いそう

    例題1より、
    全ての点を含む場合、
    abs(x_max-x_min) * abs(y_max-y_min)
    => 追記:
        これを分かったのに図示しなかったため、
        点が角ではなく辺上にのることに気づかず…
        点同士の組合せになってしまった(座標同士の組合せと気づけたはず)

    例題2より
    １つの場合1、ただし1*1の長方形より最大4点含む
    →この例の場合、4点から2点以上で面積1

    (x_2nd-x_min)*(y_max-y_min)
    →x_maxを除いた点が含まれる
    →50*50では済まない

    y
    ↑
    |*...
    |.*..
    |...*
    |*...
    ------→x
    (0,0)
    (0,4)
    (1,3)
    (3,1)

    各点を結んだときの面積の個数：O(N*N)
    面積求めたあとの点が含まれる個数の計算量: O(N)
    => O(N^3) => 50^3 => 1.25 * 10^5 => OK
      点を必ず含む場所からの面積
      => そこからでなくてよい, むしろ広くなる

    => 
    """
    ans = abs(max(x) - min(x)) * abs(max(y) - min(y))
    if K == N:
        print(ans)
        return

    def r(x, y, x_start=0, y_start=0):
        for xi in range(x_start, N):
            for yi in range(y_start, N):
                yield x[xi], y[yi], xi, yi

    # for x1, y1 in zip(x, y):
    #     for x2, y2 in zip(x, y):
    # for x1, y1 in r(x, y):
    #     for x2, y2 in r(x, y):
    x = sorted(x)
    y = sorted(y)
    for min_x, min_y, xi, yi in r(x, y):
        for max_x, max_y, _, _ in r(x, y, x_start=xi+1, y_start=yi+1):

            # s = abs(x1-x2) * abs(y1-y2)
            # if s == 0:
            #     continue

            # min_x = min(x1, x2)
            # max_x = max(x1, x2)
            # min_y = min(y1, y2)
            # max_y = max(y1, y2)

            contains_count = 0
            for x3, y3 in zip(x, y):
                if min_x <= x3 <= max_x and min_y <= y3 <= max_y:
                    contains_count += 1
            if contains_count >= K:
                s = (max_x - min_x) * (max_y - min_y)
                ans = min(ans, s)

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
import math
import collections
import itertools
import array
import inspect
import copy

# Set max recursion limit
sys.setrecursionlimit(10000)

# Debug output
def chkprint(*args):
    names = {id(v):k for k,v in inspect.currentframe().f_back.f_locals.items()}
    print(', '.join(names.get(id(arg),'???')+' = '+repr(arg) for arg in args))

# Binary converter
def to_bin(x):
    return bin(x)[2:]

# Set 2 dimension list
def dim2input(N):
    li = []
    for _ in range(N):
        li.append(input().split())
    return li

# --------------------------------------------

dp = None

def calc_rect_area(P):
    left = 10**10
    right = -(10**10)
    upper = -(10**10)
    lower = 10**10

    for p in P:
        left = min(p[0], left)
        right = max(p[0], right)
        upper = max(p[1], upper)
        lower = min(p[1], lower)

    area = (right - left) * (upper - lower)

    return area

def main():
    N, K = list(map(int, input().split()))
    P = []
    for _ in range(N):
        P.append(list(map(int, input().split())))

    P_original = copy.deepcopy(P)

    # Y座標->X座標の順に点をソートする
    P.sort(key=lambda x:x[1])
    P.sort(key=lambda x:x[0])

    idx = 0
    limit = len(P) - K
    min_area = 10**100
    while idx <= limit:
        min_area = min(
            calc_rect_area(P[idx:idx+K]),
            min_area
        )
        idx += 1

    P = P_original

    P.sort(key=lambda x:x[0])
    P.sort(key=lambda x:x[1])

    idx = 0
    while idx <= limit:
        min_area = min(
            calc_rect_area(P[idx:idx+K]),
            min_area
        )
        idx += 1

    print(min_area)

main()

Submission status: Wrong Answer

Solution code:
import sys
import math
import collections
import itertools
import array
import inspect

# Set max recursion limit
sys.setrecursionlimit(10000)

# Debug output
def chkprint(*args):
    names = {id(v):k for k,v in inspect.currentframe().f_back.f_locals.items()}
    print(', '.join(names.get(id(arg),'???')+' = '+repr(arg) for arg in args))

# Binary converter
def to_bin(x):
    return bin(x)[2:]

# Set 2 dimension list
def dim2input(N):
    li = []
    for _ in range(N):
        li.append(input().split())
    return li

# --------------------------------------------

dp = None

def calc_rect_area(P):
    left = 10**10
    right = -(10**10)
    upper = -(10**10)
    lower = 10**10

    for p in P:
        left = min(p[0], left)
        right = max(p[0], right)
        upper = max(p[1], upper)
        lower = min(p[1], lower)

    area = (right - left) * (upper - lower)

    return area

def main():
    N, K = list(map(int, input().split()))
    P = []
    for _ in range(N):
        P.append(list(map(int, input().split())))

    # Y座標->X座標の順に点をソートする
    P.sort(key=lambda x:x[1])
    P.sort(key=lambda x:x[0])

    idx = 0
    limit = len(P) - K
    min_area = 10**100
    while idx <= limit:
        min_area = min(
            calc_rect_area(P[idx:idx+K]),
            min_area
        )
        idx += 1

    print(min_area)

main()

Submission status: Wrong Answer

Solution code:
from itertools import combinations as comb
import numpy as np
N, K = map(int, input().split())
ans = 10 ** 18 + 1
choice = min(K, 4)
ps = np.array([list(map(int, input().split())) for i in range(N)])
for idxs in comb(range(N), choice):
	rep_ps = ps[idxs, :]
	x_max = rep_ps[:, 0].max()
	y_max = rep_ps[:, 1].max()
	x_min = rep_ps[:, 0].min()
	y_min = rep_ps[:, 1].min()
	in_num = sum((ps[:, 0] <= x_max) & (ps[:, 0] >= x_min) & (ps[:, 1] <= y_max) & (ps[:, 1] >= y_min))
	area = (x_max - x_min) * (y_max - y_min)
	if K <= in_num and area < ans:
		ans = area
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import combinations as comb
import numpy as np
N, K = map(int, input().split())
ans = 10 ** 18 + 1
choice = min(K, 4)
ps = np.array([list(map(int, input().split())) for i in range(N)])
for idxs in comb(range(N), choice):
	rep_ps = ps[idxs, :]
	x_max = rep_ps[:, 0].max()
	y_max = rep_ps[:, 1].max()
	x_min = rep_ps[:, 0].min()
	y_min = rep_ps[:, 1].min()
	in_num = sum((ps[:, 0] <= x_max) & (ps[:, 0] >= x_min) & (ps[:, 1] <= y_max) & (ps[:, 1] >= y_min))
	area = (x_max - x_min) * (y_max - y_min)
	if K <= in_num and area < ans:
		ans = area
print(area)

Submission status: Wrong Answer

Solution code:
from itertools import combinations as comb
import numpy as np
N, K = map(int, input().split())
ans = 10 ** 18 + 1
choice = min(K, 4)
ps = np.array([list(map(int, input().split())) for i in range(N)])
for idxs in comb(range(N), choice):
	rep_ps = ps[idxs, :]
	x_max = rep_ps[:, 0].max()
	y_max = rep_ps[:, 1].max()
	x_min = rep_ps[:, 0].min()
	y_min = rep_ps[:, 1].min()
	in_num = sum((ps[:, 0] <= x_max) & (ps[:, 0] >= x_min) & (ps[:, 1] <= y_max) & (ps[:, 1] >= y_min))
	area = (y_max - y_min) * (x_max - x_min)
	if K >= in_num and area < ans:
		ans = area
print(area)

Submission status: Wrong Answer

Solution code:
n, k = list(map(int, input().split()))
xy = [tuple(map(int, input().split())) for i in range(n)]

import heapq


class Rect:
    def __init__(self, xy):
        self.xy = set(xy)

    def excluded(self, p):
        return Rect((q for q in self.xy if q != p))


    def __lt__(self, other):
        return self.get_score() < other.get_score()

    def __len__(self):
        return len(self.xy)

    def get_x_max(self):
        return max(self.xy, key=lambda t: t[0])

    def get_x_min(self):
        return min(self.xy, key=lambda t: t[0])

    def get_y_max(self):
        return max(self.xy, key=lambda t: t[1])

    def get_y_min(self):
        return min(self.xy, key=lambda t: t[1])

    def get_score(self):
        return (self.get_x_max()[0] - self.get_x_min()[0]) * (self.get_y_max()[1] - self.get_y_min()[1])

    def __str__(self):
        return str(self.xy)



heap = []
r = Rect(xy)
score = r.get_score()

while len(r) > k:
    s = r.excluded(r.get_x_max())
    t = r.excluded(r.get_x_min())
    u = r.excluded(r.get_y_max())
    v = r.excluded(r.get_y_min())
    heapq.heappush(heap, s)
    heapq.heappush(heap, t)
    heapq.heappush(heap, u)
    heapq.heappush(heap, v)
    r = heapq.heappop(heap)

print(r.get_score())

Submission status: Wrong Answer

Solution code:

n, k = map(int, input().split())

xs, ys = [], []

for _ in range(n):
    x, y = map(int, input().split())
    xs.append(x)
    ys.append(y)


res = int(1 << 80)

def contains(x, y, x1, y1, x2, y2):
    if x < x1 or x2 < x:
        return False
    if y < y1 or y2 < y:
        return False
    return True

xs = sorted(xs)
ys = sorted(ys)

for i0 in range(n):
    for i1 in range(i0 + 1, n):
        for j0 in range(n):
            for j1 in range(j0 + 1, n):
                cnt = 0
                for kk in range(n):
                    if contains(xs[kk], ys[kk], xs[i0], ys[j0], xs[i1], ys[i1]):
                        cnt += 1
                if cnt >= k:
                    res = min(res, (ys[i1] - ys[i0]) * (xs[i1] - xs[i0]))


print(res)

Submission status: Wrong Answer

Solution code:

n, k = map(int, input().split())

xs, ys = [], []

for _ in range(n):
    x, y = map(int, input().split())
    xs.append(x)
    ys.append(y)


res = int(1 << 80)

def contains(x, y, x1, y1, x2, y2):
    if x < x1 or x2 < x:
        return False
    if y < y1 or y2 < y:
        return False
    return True

for i in range(n):
    for x2 in xs:
        for y2 in ys:
            x1, y1 = xs[i], ys[i]
            if x1 > x2: x1, x2 = x2, x1
            if y1 > y2: y1, y2 = y2, y1
            cnt = 0
            for kk in range(n):
                if contains(xs[kk], ys[kk], x1, y1, x2, y2):
                    cnt += 1
            if cnt >= k:
                res = min(res, (x2 - x1) * (y2 - y1))

print(res)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
from itertools import product, combinations
from operator import itemgetter
def inpl(): return tuple(map(int, input().split()))

N, K = inpl()
X = []
Y = []
Px = []
Py = []

for i in range(N):
    x, y = inpl()
    X.append(x)
    Y.append(y)
    Px.append((x, i))
    Py.append((y, i))

X = sorted(X)
Y = sorted(Y)

dX = {x:i for i, x in enumerate(X)}
dY = {y:i for i, y in enumerate(Y)}
Px = sorted(Px)
Py = sorted(Py)

get = itemgetter(1)
res = 5 * 10**18

for (l, r), (d, u) in product(combinations(X, 2), combinations(Y, 2)):
    if res < (r-l)*(u-d):
        continue
    if (dX[r] - dX[l] < K-1) or (dY[u] - dY[d] < K-1):
        continue

    sx = set(map(get, Px[dX[l]:dX[r]+1]))
    sy = set(map(get, Py[dY[d]:dY[u]+1]))
    if len(sx.intersection(sy)) >= K:
        res = min(res, (r-l)*(u-d))

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
X, Y, XY = [], [], []
for i in range(N):
  x, y = map(int,input().split())
  X += [x]
  Y += [y]
  XY += [[x,y]]
  
ans = float("inf")

for x1 in range(N):
  for x2 in range(x1,N):
    for y1 in range(N):
      for y2 in range(y1, N):
        boxed = 0
        for i in range(N):
          if (X[x1] - X[i])*(X[x2]-X[i])<=0 and (Y[y1] - Y[i])*(Y[y2]-Y[i])<=0:
            boxed+= 1
        if boxed >= K: ans = min(ans,abs(X[x1]-X[x2])*abs(Y[x1]-Y[x2]))
print(ans)

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
X, Y, XY = [], [], []
for i in range(N):
  x, y = map(int,input().split())
  X += [x]
  Y += [y]
  XY += [[x,y]]
  
ans = float("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):
        boxed = 0
        for i in range(N):
          if (X[x1] - X[i])*(X[x2]-X[i])<=0 and (Y[y1] - Y[i])*(Y[y2]-Y[i])<=0:
            boxed+= 1
        if boxed >= K: ans = min(ans,abs(X[x1]-X[x2])*abs(Y[x1]-Y[x2]))
print(ans)

Submission status: Wrong Answer

Solution code:
N, K = map(int, raw_input().split())
x = [map(int, raw_input().split()) for i in range(N)]
ans = 10**30
for i in range(N):
    for j in range(i+1, N):
        x0, y0 = x[i]
        x1, y1 = x[j]
        x_min, x_max = min(x0, x1), max(x0, x1)
        y_min, y_max = min(y0, y1), max(y0, y1)
        cnt = 0
        for k in range(N):
            x2, y2 = x[k]
            if (x_min <= x2 <= x_max) and (y_min <= y2 <= y_max):
                cnt += 1
        if cnt >= K:
            S = (x_max - x_min) * (y_max - y_min)
            ans = min(S, ans)
print ans

Submission status: Wrong Answer

Solution code:
# x or y で sortしてK個見る
n, k = map(int,input().split())

point = []
for i in range(n):
    point.append(list(map(int, input().split())))
point.sort()

ans_prob = []
for i in range(n - k + 1):
    xmin = point[i][0]
    xmax = point[i + k - 1][0]
    ymax = max([point[j][1] for j in range(i, i+k)])
    ymin = min([point[j][1] for j in range(i, i+k)])
    ans_prob.append((xmax - xmin)*(ymax - ymin))
ans_prob.sort()
print(ans_prob[0])

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
https://beta.atcoder.jp/contests/abc075/tasks/abc075_d

"""
import sys
from sys import stdin
from statistics import mean
from math import sqrt
input = stdin.readline


def solve(points, N, K):
    x_arr = [p[0] for p in points]
    y_arr = [p[1] for p in points]
    x_arr.sort()
    y_arr.sort()

    ans = (x_arr[-1] - x_arr[0]) * (y_arr[-1] - y_arr[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
                    lx = x_arr[xi]
                    rx = x_arr[xj]
                    by = y_arr[yi]
                    uy = y_arr[yj]

                    for i in range(N):
                        if lx <= x_arr[i] <= rx and by <= y_arr[i] <= uy:
                            num += 1
                    if num >= K:
                        ans = min(ans, ((rx - lx) * (uy - by)))
    return ans



def main(args):
    N, K = map(int, input().split())
    points = []
    for _ in range(N):
        points.append([int(x) for x in input().split()])

    result = solve(points, N, K)
    print(result)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
https://beta.atcoder.jp/contests/abc075/tasks/abc075_d

"""
import sys
from sys import stdin
from statistics import mean
from math import sqrt
input = stdin.readline


def solve(points, N, K):
    to_remove = N - K

    while to_remove:
        sx = [p[0] for p in points]
        sy = [p[1] for p in points]
        cx = mean(sx)
        cy = mean(sy)

        dist = [0] * len(points)
        for i, p in enumerate(points):
            dist[i] = sqrt((cx - p[0])**2 + (cy - p[1])**2)

        i = dist.index(max(dist))
        points.pop(i)
        to_remove -= 1

    points.sort()
    lx = points[0][0]
    rx = points[-1][0]
    points.sort(key=lambda p: p[1])
    by = points[0][1]
    uy = points[-1][1]

    return (rx - lx) * (uy - by)



def main(args):
    N, K = map(int, input().split())
    points = []
    for _ in range(N):
        points.append([int(x) for x in input().split()])

    result = solve(points, N, K)
    print(result)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
https://beta.atcoder.jp/contests/abc075/tasks/abc075_d

"""
import sys
from sys import stdin
input = stdin.readline


def solve(points, N, K):
    x_points = points[:]
    x_points.sort()
    y_points = points[:]
    y_points.sort(key=lambda x: x[1])

    ans = (x_points[-1][0] - x_points[0][0]) * (y_points[-1][1] - y_points[0][1])
    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_points[xi][0]
                    rx = x_points[xj][0]
                    by = y_points[yi][1]
                    uy = y_points[yj][1]

                    for i in range(N):
                        if lx <= x_points[i][0] <= rx and by <= y_points[i][1] <= uy:
                            num += 1
                    if num >= K:
                        ans = min(ans, (rx - lx) * (uy - by))
    return ans


def main(args):
    N, K = map(int, input().split())
    points = []
    for _ in range(N):
        points.append([int(x) for x in input().split()])

    result = solve(points, N, K)
    print(result)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Wrong Answer

Solution code:
N,K = [int(_) for _ in input().split()]
arealist = []
xlist = []
ylist = []
xylist =[]
count = 0
count2 = 0
count3 = 0
#print(N,K)
for i in range(N):
    xylist.append(list(int(k) for k in input().split()))
for i in range(N):
    xlist.append(xylist[i][0])
    ylist.append(xylist[i][1])
xsorted = sorted(xlist)
ysorted = sorted(ylist)
#print(xlist,ylist)
for i in range(N-1):
    #print("i={}".format(i))
    xw = xsorted[i]
    count = 1
    temp = []
    temp.append(xsorted[i])
    for j in range(i+1,N):
        #print("j={}".format(j))
        xe = xsorted[j]
        temp.append(xsorted[j])
        count += 1
        #print(count)
        if count < K:
            #print("hi")
            continue
        for k in range(N-1):
            ys = ysorted[k]
            if k >= 1:
                if xlist[ylist.index(ysorted[k-1])] in temp:
                    count -= 1
                    count3 +=1
            #print("k={}".format(k))
            if count < K:
                count += count3
                count3 = 0
                break
            for l in range(N-k-1):
                #print("l={}".format(l))
                yn = ysorted[N-l-1]
                if l >= 1:
                    if xlist[ylist.index(ysorted[N-l])] in temp:
                        count -= 1
                        count2 += 1
                    #print(count)
                if count >= K:
                    #print(xw,xe)
                    #print(ys,yn)
                    arealist.append((xe-xw)*(yn-ys))

                if count<K:
                    count += count2
                    count2 = 0
                    break
#print(arealist)
print(sorted(arealist)[0])

Submission status: Wrong Answer

Solution code:
N,K = [int(i) for i in input().split()]
arealist = []
xlist = []
ylist = []
xylist =[]
count = 0
for i in range(N):
    xylist.append(list(int(k) for k in input().split()))
for i in range(N):
    xlist.append(xylist[i][0])
    ylist.append(xylist[i][1])
xsorted = sorted(xlist)
ysorted = sorted(ylist)
#print(xlist,ylist)
for i in range(N-1):
    count = 1
    temp = []
    temp.append(xsorted[i])
    for j in range(i+1,N):
        temp.append(xsorted[j])
        count += 1
        if count < K:
            #print(j)
            continue
        for k in range(N-1):
            if count < K:
                count +=1
                break
            for l in range(k+1,N):
                xw = xsorted[i]
                xe = xsorted[j]
                ys = ysorted[k]
                yn = ysorted[N-l]
                if count >= K:
                    #print(xw,xe)
                    arealist.append((xe-xw)*(yn-ys))
                if xlist[ylist.index(yn)] in temp:
                    count -= 1
                if count<K:
                    break
#print(arealist)
print(sorted(arealist)[0])

Submission status: Wrong Answer

Solution code:
N,K = [int(i) for i in input().split()]
arealist = []
xlist = []
ylist = []
xylist =[]
count = 0
for i in range(N):
    xylist.append(list(int(k) for k in input().split()))
for i in range(N):
    xlist.append(xylist[i][0])
    ylist.append(xylist[i][1])
xsorted = sorted(xlist)
ysorted = sorted(ylist)
#print(xlist,ylist)
for i in range(N-1):
    count = 1
    temp = []
    temp.append(xsorted[i])
    for j in range(i+1,N):
        temp.append(xsorted[j])
        count += 1
        if count < K:
            #print(j)
            continue
        for k in range(N-1):
            if count < K:
                count +=1
                break
            for l in range(k+1,N):
                xw = xsorted[i]
                xe = xsorted[j]
                ys = ysorted[k]
                yn = ysorted[N-l]
                if count >= K:
                    print(xw,xe)
                    arealist.append((xe-xw)*(yn-ys))
                if xlist[ylist.index(yn)] in temp:
                    count -= 1
                if count<K:
                    break
#print(arealist)
print(sorted(arealist)[0])

Submission status: Wrong Answer

Solution code:
N,K = [int(i) for i in input().split()]
arealist = []
xlist = []
ylist = []
xylist =[]
count = 0
for i in range(N):
    xylist.append(list(int(k) for k in input().split()))
for i in range(N):
    xlist.append(xylist[i][0])
    ylist.append(xylist[i][1])
xsorted = sorted(xlist)
ysorted = sorted(ylist)
#print(xlist,ylist)
for i in range(N-1):
    count = 1
    temp = []
    temp.append(xsorted[i])
    for j in range(i+1,N):
        temp.append(xsorted[j])
        count += 1
        if count < K:
            continue
        for k in range(N-1):
            if count < K:
                count +=1
                break
            for l in range(k+1,N):
                xw = xsorted[i]
                xe = xsorted[j]
                ys = ysorted[k]
                yn = ysorted[N-l]
                if count >= K:
                    arealist.append((xe-xw)*(yn-ys))
                if xlist[ylist.index(yn)] in temp:
                    count -= 1
                if count<K:
                    break
print(sorted(arealist)[0])

Submission status: Wrong Answer

Solution code:
N,K = [int(i) for i in input().split()]
arealist = []
xlist = []
ylist = []
xylist =[]
count = 0
for i in range(N):
    xylist.append(list(int(k) for k in input().split()))
for i in range(N):
    xlist.append(xylist[i][0])
    ylist.append(xylist[i][1])
xsorted = sorted(xlist)
ysorted = sorted(ylist)
#print(xlist,ylist)
for i in range(N-1):
    count = 1
    temp = []
    temp.append(xsorted[i])
    for j in range(i+1,N):
        temp.append(xsorted[j])
        count += 1
        if count < K:
            continue
        for k in range(N-1):
            if count < K:
                break
            for l in range(k+1,N):
                xw = xsorted[i]
                xe = xsorted[j]
                ys = ysorted[k]
                yn = ysorted[N-l]
                if count >= K:
                    arealist.append((xe-xw)*(yn-ys))
                if xlist[ylist.index(yn)] in temp:
                    count -= 1
                if count<K:
                    break
print(sorted(arealist)[0])