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:
#!/usr/bin/env python3
import sys
INF = float("inf")


def solve(N: int, K: int, x: "List[int]", y: "List[int]"):
    sx = sorted(x)
    sy = sorted(y)

    m = INF
    for i, x1 in enumerate(sx):
        for x2 in sx[i:]:
            for j, y1 in enumerate(sy):
                for y2 in sy[j:]:
                    counter = 0
                    for xx, yy in zip(x, y):
                        if (x1 <= xx <= x2) and (y1 <= yy <= y2):
                            counter += 1
                    if counter >= K:
                        area = (y2-y1)*(x2-x1)
                        if m > area:
                            m = area
    print(area)
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    x = [int()] * (N)  # type: "List[int]"
    y = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        x[i] = int(next(tokens))
        y[i] = int(next(tokens))
    solve(N, K, x, y)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    N,K = map(int,input().split())
    XY = [list(map(int,input().split())) for _ in [0]*N]
    iX = [0]*N
    iY = [0]*N
    for i,xy in enumerate(XY):
        x,y = xy
        iX[i] = x
        iY[i] = y
    iX.sort()
    iY.sort()
    X = {x:i for i,x in enumerate(iX)}
    Y = {y:i for i,y in enumerate(iY)}

    c = [[0]*(N+1) for i in [0]*(N+1)]
    for x,y in XY:
        c[Y[y]+1][X[x]+1] = 1

    for i in range(N):
        ci1 = c[i+1]
        for j in range(N):
            ci1[j+1] += ci1[j]
    for i in range(N):
        ci1 = c[i+1]
        ci = c[i]
        ci1 = [ci1j+cij for ci1j,cij in zip(ci1,ci)]

    ans = 10**20
    for u in range(N):
        for d in range(u+K-1,N):
            l = 0
            r = K-1
            dY = iY[d]-iY[u]
            cd = c[d+1]
            cu = c[u]
            while r<N:
                if cd[r+1]+cu[l]-cu[r+1]-cd[l] >=K:
                    ans = min(ans, (iX[r] - iX[l])*dY)
                    l+=1
                else:r+=1

    print(ans)
main()

Submission status: Wrong Answer

Solution code:
def main():
    N,K = map(int,input().split())
    XY = [list(map(int,input().split())) for _ in [0]*N]
    iX = [0]*N
    iY = [0]*N
    for i,xy in enumerate(XY):
        x,y = xy
        iX[i] = x
        iY[i] = y
    iX.sort()
    iY.sort()
    X = {x:i for i,x in enumerate(iX)}
    Y = {y:i for i,y in enumerate(iY)}

    c = [[0]*(N+1) for i in [0]*(N+1)]
    for x,y in XY:
        c[Y[y]+1][X[x]+1] = 1

    for i in range(N):
        ci1 = c[i+1]
        for j,ci1j in enumerate(ci1[:-1]):
            ci1[j+1] += ci1j
    for i in range(N):
        ci1 = c[i+1]
        ci = c[i]
        for j,cij in enumerate(ci[1:],1):
            ci1[j] += cij

    ans = 10**20
    for u in range(N):
        for d in range(u+K-1,N):
            l = 0
            r = K-1
            dY = iY[d]-iY[u]
            cd = c[d+1]
            cu = c[u]
            while r<N:
                if cd[r+1]+cu[l]-cu[r+1]-cd[l] >=K:
                    ans = min(ans, (iX[r] - iX[l])*dY)
                    l+=1
                else:r+=1

    print(ans)
main()

Submission status: Wrong Answer

Solution code:
def main():
    N,K = map(int,input().split())
    XY = [list(map(int,input().split())) for _ in [0]*N]
    
    iX = sorted(x for x,y in XY)
    iY = sorted(y for x,y in XY)
    X = {x:i for i,x in enumerate(iX)}
    Y = {y:i for i,y in enumerate(iY)}

    c = [[0]*(N+1) for i in [0]*(N+1)]
    for x,y in XY:
        c[Y[y]+1][X[x]+1] = 1

    for i in range(N):
        ci1 = c[i+1]
        for j in range(N):
            ci1[j+1] += ci1[j]
    for i in range(N):
        ci1 = c[i+1]
        ci = c[i]
        for j in range(N):
            ci1[j+1] += ci[j+1]

    ans = 10**20
    for u in range(N):
        for d in range(u+K,N):
            l = 0
            r = 0
            dY = iY[d]-iY[u]
            cd = c[d+1]
            cu = c[u]
            while r<N:
                if cd[r+1]+cu[l]-cu[r+1]-cd[l] >=K:
                    ans = min(ans, (iX[r] - iX[l])*dY)
                    l+=1
                else:r+=1

    print(ans)
main()

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
XY = [list(map(int,input().split())) for _ in [0]*N]

iX = sorted(x for x,y in XY)
iY = sorted(y for x,y in XY)
X = {x:i for i,x in enumerate(iX)}
Y = {y:i for i,y in enumerate(iY)}

c = [[0]*(N+1) for i in [0]*(N+1)]
for x,y in XY:
    c[Y[y]+1][X[x]+1] = 1

for i in range(N):
    ci1 = c[i+1]
    for j in range(N):
        ci1[j+1] += ci1[j]
for i in range(N):
    ci1 = c[i+1]
    ci = c[i]
    for j in range(N):
        ci1[j+1] += ci[j+1]

ans = 10**20
for u in range(N):
    for d in range(u+K,N):
        l = 0
        r = 1
        dY = iY[d]-iY[u]
        cd = c[d+1]
        cu = c[u]
        while r<N:
            if cd[r+1]+cu[l]-cu[r+1]-cd[l] >=K:
                ans = min(ans, (iX[r] - iX[l])*dY)
                l+=1
            else:r+=1

print(ans)

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
XY = [list(map(int,input().split())) for _ in [0]*N]

iX = sorted(x for x,y in XY)
iY = sorted(y for x,y in XY)
X = {x:i for i,x in enumerate(iX)}
Y = {y:i for i,y in enumerate(iY)}

c = [[0]*(N+1) for i in [0]*(N+1)]
for x,y in XY:
    c[Y[y]+1][X[x]+1] = 1

for i in range(N):
    ci1 = c[i+1]
    for j in range(N):
        ci1[j+1] += ci1[j]
for i in range(N):
    ci1 = c[i+1]
    ci = c[i]
    for j in range(N):
        ci1[j+1] += ci[j+1]

ans = 10**20
for u in range(N):
    for d in range(u+K+1,N):
        l = 0
        r = 1
        dY = iY[d]-iY[u]
        cd = c[d+1]
        cu = c[u]
        while r<N:
            if cd[r+1]+cu[l]-cu[r+1]-cd[l] >=K:
                ans = min(ans, (iX[r] - iX[l])*dY)
                l+=1
            else:r+=1

print(ans)

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
XY = [list(map(int,input().split())) for _ in [0]*N]

iX = sorted(x for x,y in XY)
iY = sorted(y for x,y in XY)
X = {x:i for i,x in enumerate(iX)}
Y = {y:i for i,y in enumerate(iY)}

c = [[0]*(N+1) for i in [0]*(N+1)]
for x,y in XY:
    c[Y[y]+1][X[x]+1] = 1

for i in range(N):
    ci1 = c[i+1]
    for j in range(N):
        ci1[j+1] += ci1[j]
for i in range(N):
    ci1 = c[i+1]
    ci = c[i]
    for j in range(N):
        ci1[j+1] += ci[j+1]

ans = 10**20
for u in range(N):
    for d in range(min(u+K,N-1),N):
        l = 0
        r = min(K,N-1)
        dY = iY[d]-iY[u]
        cd = c[d+1]
        cu = c[u]
        while r<N:
            if cd[r+1]+cu[l]-cu[r+1]-cd[l] >=K:
                ans = min(ans, (iX[r] - iX[l])*dY)
                l+=1
            else:r+=1

print(ans)

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
XY = [list(map(int,input().split())) for _ in [0]*N]

iX = sorted(x for x,y in XY)
iY = sorted(y for x,y in XY)
X = {x:i for i,x in enumerate(iX)}
Y = {y:i for i,y in enumerate(iY)}

c = [[0]*(N+1) for i in [0]*(N+1)]
for x,y in XY:
    c[Y[y]+1][X[x]+1] = 1

for i in range(N):
    ci1 = c[i+1]
    for j in range(N):
        ci1[j+1] += ci1[j]
for i in range(N):
    ci1 = c[i+1]
    ci = c[i]
    for j in range(N):
        ci1[j+1] += ci[j+1]

ans = 10**20
for u in range(N):
    for d in range(min(u+K+1,N-1),N):
        l = 0
        r = min(K+1,N-1)
        dY = iY[d]-iY[u]
        cd = c[d+1]
        cu = c[u]
        while r<N:
            if cd[r+1]+cu[l]-cu[r+1]-cd[l] >=K:
                ans = min(ans, (iX[r] - iX[l])*dY)
                l+=1
            else:r+=1

print(ans)

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
XY = [list(map(int,input().split())) for _ in [0]*N]

iX = sorted(x for x,y in XY)
iY = sorted(y for x,y in XY)
X = {x:i for i,x in enumerate(iX)}
Y = {y:i for i,y in enumerate(iY)}

c = [[0]*(N+1) for i in [0]*(N+1)]
for x,y in XY:
    c[Y[y]+1][X[x]+1] = 1

for i in range(N):
    ci1 = c[i+1]
    for j in range(N):
        ci1[j+1] += ci1[j]
for i in range(N):
    ci1 = c[i+1]
    ci = c[i]
    for j in range(N):
        ci1[j+1] += ci[j+1]

ans = 10**20
for u in range(N):
    for d in range(u+K+1,N):
        l = 0
        r = K+1
        dY = iY[d]-iY[u]
        cd = c[d+1]
        cu = c[u]
        while r<N:
            if cd[r+1]+cu[l]-cu[r+1]-cd[l] >=K:
                ans = min(ans, (iX[r] - iX[l])*dY)
                l+=1
            else:r+=1

print(ans)

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
XY = [list(map(int,input().split())) for _ in [0]*N]

iX = sorted(x for x,y in XY)
iY = sorted(y for x,y in XY)
X = {x:i for i,x in enumerate(iX)}
Y = {y:i for i,y in enumerate(iY)}

c = [[0]*(N+1) for i in [0]*(N+1)]
for x,y in XY:
    c[Y[y]+1][X[x]+1] = 1

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

ans = 10**20
for l in range(N):
    for r in range(l+1,N):
        u = 0
        d = 1
        dX = iX[r] - iX[l]
        while d<N:
            if c[d+1][r+1]+c[u][l]-c[u][r+1]-c[d+1][l] >=K:
                ans = min(ans, dX*(iY[d]-iY[u]))
                u+=1
            else:d+=1

print(ans)

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
x = []
y = []
l = []
for i in range(N):
    xx,yy = map(int,input().split())
    x.append(xx)
    y.append(yy)
    l.append((xx,yy))

import itertools
ans = float("inf")

for xx in itertools.combinations(x,2):
    for i in range(N):
        if x[i] == xx[0]:
            xai = i
        if x[i] == xx[1]:
            xbi = i

    if x[xai] > x[xbi]:
        continue

    for yy in itertools.combinations(y,2):
        for i in range(N):
            if y[i] == yy[0]:
                yai = i
            if y[i] == yy[1]:
                ybi = i

        if y[yai] > y[ybi]:
            continue

        num = 0
        for i in range(N):
            if l[i][0] >= x[xai] and l[i][0] <= x[xbi] and l[i][1] >= y[yai] and l[i][1] <= y[ybi]:
                num += 1

        if K > num:
            continue

        ans = min(ans , abs(xx[0] - xx[1])*abs(yy[0] - yy[1]))
print(ans)

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
x = []
y = []
l = []
for i in range(N):
    xx,yy = map(int,input().split())
    x.append(xx)
    y.append(yy)
    l.append((xx,yy))

import itertools
ans = float("inf")

for xx in itertools.combinations(x,2):
    for i in range(N):
        if x[i] == xx[0]:
            xai = i
        if x[i] == xx[1]:
            xbi = i

    if x[xai] > x[xbi]:
        continue

    if abs(x[xai] - x[xbi]) + 1 < K:
        continue

    for yy in itertools.combinations(y,2):
        for i in range(N):
            if y[i] == yy[0]:
                yai = i
            if y[i] == yy[1]:
                ybi = i

        if y[yai] > y[ybi]:
            continue

        if abs(y[yai] - y[ybi]) + 1 < K:
            continue

        num = 0
        for i in range(N):
            if l[i][0] >= x[xai] and l[i][0] <= x[xbi] and l[i][1] >= y[yai] and l[i][1] <= y[ybi]:
                num += 1

        if K > num:
            continue

        ans = min(ans , abs(xx[0] - xx[1])*abs(yy[0] - yy[1]))
print(ans)

Submission status: Wrong Answer

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

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

import itertools
ans = float("inf")

for xx in itertools.combinations(x,2):
    for i in range(N):
        if x[i] == xx[0]:
            xai = i
        if x[i] == xx[1]:
            xbi = i
    xnum = abs(xai - xbi) + 1
    if K > xnum :
        continue


    for yy in itertools.combinations(y,2):
        for i in range(N):
            if y[i] == yy[0]:
                yai = i
            if y[i] == yy[1]:
                ybi = i

        ynum = abs(yai - ybi) + 1
        if K > ynum:
            continue

        ans = min(ans , abs(xx[0] - xx[1])*abs(yy[0] - yy[1]))
print(ans)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
xy=[]
yx=[]
for i in range(n):
    tmp=[int(j) for j in input().split()]
    xy.append(tmp)
    yx.append([tmp[1],tmp[0]])

ans=10**100
from operator import itemgetter
xy.sort(key=itemgetter(1)) 
xy.sort(key=itemgetter(0)) 
yx.sort(key=itemgetter(1)) 
yx.sort(key=itemgetter(0)) 

for i in range(n-k+1):
    l=xy[i:i+k]
    wx,wn,hx,hn=0,10**10,0,10*10
    for i,j in l:
        wx=max(wx,i)
        wn=min(wn,i)
        hx=max(hx,j)
        hn=min(hn,j)
    ans=min(ans,(wx-wn)*(hx-hn))


for i in range(n-k+1):
    l=yx[i:i+k]
    wx,wn,hx,hn=0,10**10,0,10*10
    for i,j in l:
        wx=max(wx,i)
        wn=min(wn,i)
        hx=max(hx,j)
        hn=min(hn,j)
    ans=min(ans,(wx-wn)*(hx-hn))

print(ans)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
xy = [list(map(int, input().split())) for i in range(N)]
ans = 10**20
xy.sort()
for l in range(N-K+1):
    for r in range(l+K, N+1):
        y = sorted(xy, key = lambda v: v[1])
        for i in range(r-l-K+1):
            sq = (xy[r-1][0] - xy[l][0]) * (y[i+K-1][1] - y[i][1])
            ans = min(ans, sq)
print(ans)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
xy = [list(map(int, input().split())) for i in range(N)]
ans = 10**20
xy.sort()
for l in range(N-K+1):
    r = l + K
    yu, yb = max(xy[l:r], key = lambda z : z[1])[1], min(xy[l:r], key = lambda z : z[1])[1]
    sq = (xy[r-1][0] - xy[l][0]) * (yu - yb)
    ans = min(ans, sq)
xy.sort(key = lambda z : z[1])
for b in range(N-K+1):
    u = b + K
    xr, xl = max(xy[b:u])[0], min(xy[b:u])[0]
    sq = (xr - xl) * (xy[u-1][1] - xy[b][1])
    ans = min(ans, sq)
print(ans)

Submission status: Wrong Answer

Solution code:
def solve(n, k):
    ps = []
    for _ in range(n):
        px, py = map(int, input().split())
        ps.append((px, py))
    ps.sort()
    min_area = float('inf')
    for i in range(n-k+1):
        r_x = ps[i][0]
        l_x = ps[i+k-1][0]
        b_y = min(j[1] for j in ps[i:i+k])
        t_y = max(j[1] for j in ps[i:i+k])
        diff_x = abs(l_x-r_x)
        diff_y = abs(t_y-b_y)
        min_area = min(min_area, diff_x*diff_y)
    return min_area


if __name__ == '__main__':
    n, k = map(int, input().split())
    print(solve(n, k))

Submission status: Wrong Answer

Solution code:
from itertools import combinations

N, K = map(int, input().split())
coord = sorted([tuple(map(int, input().split())) for _ in range(N)])
ans = float('inf')
for left, right in combinations(range(N), 2):
    n_points = right - left + 1
    if n_points < K: continue
    width = coord[right][0] - coord[left][0]
    temp = [y for _, y in coord[left: right+1]]
    height = max(temp) - min(temp)
    ans = min(ans, width*height)
print(ans)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
coord = [tuple(map(int, input().split())) for _ in range(N)]
sorted_x = sorted(coord, key=lambda x:x[0])
sorted_y = sorted(coord, key=lambda x:x[1])
ans1 = float('inf')
for i in range(N - K+1):
    width = sorted_x[i+K-1][0] - sorted_x[i][0]
    temp = [y for _, y in coord[i: i+K]]
    height = max(temp) - min(temp)
ans2 = float('inf')
for i in range(N - K+1):
    height = sorted_y[i+K-1][1] - sorted_y[i][1]
    temp = [x for x, _ in coord[i: i+K]]
    width = max(temp) - min(temp)
    ans2 = min(ans2, width*height)
print(min(ans1, ans2))

Submission status: Wrong Answer

Solution code:
n,c=map(int,input().split())
pos=[list(map(int,input().split())) for _ in range(n)]
if c==2:
  ans=10**20
  for i in range(n):
    x1,y1=pos[i]
    for j in range(i+1,n):
      x2,y2=pos[j]
      w=abs(x1-x2)
      h=abs(y1-y2)
      ans=min(ans,w*h)
  print(ans)
elif c==3:
  ans=10**20
  for i in range(n):
    x1,y1=pos[i]
    for j in range(i+1,n):
      x2,y2=pos[j]
      for k in range(j+1,n):
        x3,y3=pos[k]
        rx1,rx2=min(x1,x2,x3),max(x1,x2,x3)
        ry1,ry2=min(y1,y2,y3),max(y1,y2,y3)
        cnt=0
        for l in range(n):
          if rx1<=pos[l][0]<=rx2 and ry1<=pos[l][1]<=ry2:
            cnt+=1
        if cnt>=c:
          w=abs(rx1-rx2)
          h=abs(ry1-ry2)
          ans=min(ans,w*h)
  print(ans)
else:
  xpos=[]
  ypos=[]
  for i in range(n):
    xpos.append(pos[i][0])
    ypos.append(pos[i][1])
  xpos=sorted(xpos)
  ypos=sorted(ypos)
  dic={}
  for x in xpos:
    for y in ypos:
      cnt=0
      for tx,ty in pos:
        if tx<=x and ty<=y:
          cnt+=1
        if tx==x and ty==y:
          cnt-=1
      dic[(x,y)]=cnt
  ans=10**20
  for i in range(n):
    x1,y1=pos[i]
    for j in range(i+1,n):
      x2,y2=pos[j]
      for k in range(j+1,n):
        x3,y3=pos[k]
        for l in range(k+1,n):
          x4,y4=pos[l]
          rx1,rx2=min(x1,x2,x3,x4),max(x1,x2,x3,x4)
          ry1,ry2=min(y1,y2,y3,y4),max(y1,y2,y3,y4)
          cnt=dic[(rx2,ry2)]-dic[(rx1,ry2)]-dic[(rx1,ry2)]+dic[(rx1,ry1)]
          if cnt>=c:
            w=abs(rx1-rx2)
            h=abs(ry1-ry2)
            ans=min(ans,w*h)
  print(ans)

Submission status: Wrong Answer

Solution code:
n,c=map(int,input().split())
pos=[list(map(int,input().split())) for _ in range(n)]
if c==2:
  ans=10**20
  for i in range(n):
    x1,y1=pos[i]
    for j in range(i+1,n):
      x2,y2=pos[j]
      w=abs(x1-x2)
      h=abs(y1-y2)
      ans=min(ans,w*h)
  print(ans)
elif c==3:
  ans=10**20
  for i in range(n):
    x1,y1=pos[i]
    for j in range(i+1,n):
      x2,y2=pos[j]
      for k in range(j+1,n):
        x3,y3=pos[k]
        rx1,rx2=min(x1,x2,x3),max(x1,x2,x3)
        ry1,ry2=min(y1,y2,y3),max(y1,y2,y3)
        cnt=0
        for l in range(n):
          if rx1<=pos[l][0]<=rx2 and ry1<=pos[l][1]<=ry2:
            cnt+=1
        if cnt>=c:
          w=abs(rx1-rx2)
          h=abs(ry1-ry2)
          ans=min(ans,w*h)
  print(ans)
else:
  ans=10**20
  for i in range(n):
    x1,y1=pos[i]
    for j in range(i+1,n):
      x2,y2=pos[j]
      for k in range(j+1,n):
        x3,y3=pos[k]
        for l in range(k+1,n):
          x4,y4=pos[l]
          rx1,rx2=min(x1,x2,x3,x4),max(x1,x2,x3,y4)
          ry1,ry2=min(y1,y2,y3,y4),max(y1,y2,y3,y4)
          cnt=0
          for m in range(n):
            if rx1<=pos[m][0]<=rx2 and ry1<=pos[m][1]<=ry2:
              cnt+=1
          if cnt>=c:
            w=abs(rx1-rx2)
            h=abs(ry1-ry2)
            ans=min(ans,w*h)
  print(ans)

Submission status: Wrong Answer

Solution code:
n,c=map(int,input().split())
pos=[list(map(int,input().split())) for _ in range(n)]
if c==2:
  ans=10**20
  for i in range(n):
    x1,y1=pos[i]
    for j in range(i+1,n):
      x2,y2=pos[j]
      w=abs(x1-x2)
      h=abs(y1-y2)
      ans=min(ans,w*h)
  print(ans)
elif c==3:
  ans=10**20
  for i in range(n):
    x1,y1=pos[i]
    for j in range(i+1,n):
      x2,y2=pos[j]
      for k in range(j+1,n):
        x3,y3=pos[k]
        rx1,rx2=min(x1,x2,x3),max(x1,x2,x3)
        ry1,ry2=min(y1,y2,y3),max(y1,y2,y3)
        cnt=0
        for l in range(n):
          if rx1<=pos[l][0]<=rx2 and ry1<=pos[l][1]<=ry2:
            cnt+=1
        if cnt>=c:
          w=abs(rx1-rx2)
          h=abs(ry1-ry2)
          ans=min(ans,w*h)
  print(ans)
else:
  ans=10**20
  for i in range(n):
    x1,y1=pos[i]
    for j in range(i+1,n):
      x2,y2=pos[j]
      for k in range(j+1,n):
        x3,y3=pos[k]
        for l in range(k+1,n):
          x4,y4=pos[l]
          rx1,rx2=min(x1,x2,x3,x4),max(x1,x2,x3,y4)
          ry1,ry2=min(y1,y2,y3,y4),max(y1,y2,y3,y4)
          cnt=0
          for l in range(n):
            if rx1<=pos[l][0]<=rx2 and ry1<=pos[l][1]<=ry2:
              cnt+=1
          if cnt>=c:
            w=abs(rx1-rx2)
            h=abs(ry1-ry2)
            ans=min(ans,w*h)
  print(ans)

Submission status: Wrong Answer

Solution code:
n,c=map(int,input().split())
pos=[list(map(int,input().split())) for _ in range(n)]
if c==2:
  ans=10**20
  for i in range(n):
    x1,y1=pos[i]
    for j in range(i+1,n):
      x2,y2=pos[j]
      w=abs(x1-x2)
      h=abs(y1-y2)
      ans=min(ans,w*h)
  print(ans)
else:
  ans=10**20
  for i in range(n):
    x1,y1=pos[i]
    for j in range(i+1,n):
      x2,y2=pos[j]
      for k in range(j+1,n):
        x3,y3=pos[k]
        rx1,rx2=min(x1,x2,x3),max(x1,x2,x3)
        ry1,ry2=min(y1,y2,y3),max(y1,y2,y3)
        cnt=3
        for l in range(n):
          if l==i or l==j or l==k:
            continue
          if rx1<=pos[l][0]<=rx2 and ry1<=pos[l][1]<=ry2:
            cnt+=1
        if cnt>=c:
          w=abs(rx1-rx2)
          h=abs(ry1-ry2)
          ans=min(ans,w*h)
  print(ans)

Submission status: Wrong Answer

Solution code:
n,c=map(int,input().split())
pos=[list(map(int,input().split())) for _ in range(n)]
if c==2:
  ans=10**20
  for i in range(n):
    x1,y1=pos[i]
    for j in range(i+1,n):
      x2,y2=pos[j]
      w=abs(x1-x2)
      h=abs(y1-y2)
      ans=min(ans,w*h)
  print(ans)
else:
  ans=10**20
  for i in range(n):
    x1,y1=pos[i]
    for j in range(i+1,n):
      x2,y2=pos[j]
      rx1,rx2=min(x1,x2),max(x1,x2)
      ry1,ry2=min(y1,y2),max(y1,y2)
      cnt=2
      for k in range(n):
        if k==i or k==j:
          continue
        if rx1<=pos[k][0]<=rx2 and ry1<=pos[k][1]<=ry2:
          cnt+=1
      if cnt>=c:
        w=abs(x1-x2)
        h=abs(y1-y2)
        ans=min(ans,w*h)
  for i in range(n):
    x1,y1=pos[i]
    for j in range(i+1,n):
      x2,y2=pos[j]
      rx1,rx2=min(x1,x2),max(x1,x2)
      ry1,ry2=min(y1,y2),max(y1,y2)
      for k in range(j+1,n):
        x3,y3=pos[k]
        rx1,rx2=min(rx1,x3),max(rx2,x3)
        ry1,ry2=min(ry1,y3),max(ry2,y3)
        cnt=3
        for l in range(n):
          if l==i or l==j or l==k:
            continue
          if rx1<=pos[l][0]<=rx2 and ry1<=pos[l][1]<=ry2:
            cnt+=1
        if cnt>=c:
          w=abs(rx1-rx2)
          h=abs(ry1-ry2)
          ans=min(ans,w*h)
  print(ans)

Submission status: Wrong Answer

Solution code:
n,c=map(int,input().split())
pos=[list(map(int,input().split())) for _ in range(n)]
if c==2:
  ans=10**20
  for i in range(n):
    x1,y1=pos[i]
    for j in range(i+1,n):
      x2,y2=pos[j]
      w=abs(x1-x2)
      h=abs(y1-y2)
      ans=min(ans,w*h)
  print(ans)
else:
  ans=10**20
  for i in range(n):
    x1,y1=pos[i]
    for j in range(i+1,n):
      x2,y2=pos[j]
      rx1,rx2=min(x1,x2),max(x1,x2)
      ry1,ry2=min(y1,y2),max(y1,y2)
      for k in range(j+1,n):
        x3,y3=pos[k]
        rx1,rx2=min(rx1,x3),max(rx2,x3)
        ry1,ry2=min(ry1,y3),max(ry2,y3)
        cnt=3
        for l in range(n):
          if l==i or l==j or l==k:
            continue
          if rx1<=pos[l][0]<=rx2 and ry1<=pos[l][1]<=ry2:
            cnt+=1
        if cnt>=c:
          w=abs(rx1-rx2)
          h=abs(ry1-ry2)
          ans=min(ans,w*h)
  print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import combinations


def main():
    N, K = map(int, input().split())
    C = []
    for _ in range(N):
        x, y = map(int, input().split())
        C.append((x, y))
    ans = float('INF')
    for ll in list(combinations(C, K)):
        lx = float('INF')
        rx = 0
        ty = 0
        dy = float('INF')
        for x, y in ll:
            lx = min(lx, x)
            rx = max(rx, x)
            ty = max(ty, y)
            dy = min(dy, y)
        ans = min(ans, abs(rx - lx) * abs(ty - dy))
    print(ans)


main()

Submission status: Wrong Answer

Solution code:
import itertools
from functools import lru_cache

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

XY = [[int(x) for x in input().split()] for _ in range(N)]
XY.sort()
X,Y = zip(*XY)

@lru_cache(None)
def cnt(x,y):
  c = 0
  for x1,y1 in XY:
    if x1 > x:
      break
    if y1 <= y:
      c += 1
  return c

min_area = 5*10**18

for x1,x2 in itertools.combinations(X,2):
  for y1,y2 in itertools.combinations(Y,2):
    area = (x2-x1) * (y2-y1)
    if area > min_area:
      continue
    
    c = cnt(x2,y2) - cnt(x2,y1-1) - cnt(x1-1,y2) + cnt(x1-1,y1-1)
    if c < K:
      continue
      
    min_area = area
    
print(min_area)

Submission status: Wrong Answer

Solution code:
import sys
import itertools

N,K=map(int, sys.stdin.readline().split())
XY=[ map(int, sys.stdin.readline().split()) for _ in range(N) ]

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

L=list( itertools.combinations( range(N), 2) )


ans=float("inf")
for v1, v2 in L:	#v1, v2 ==> Vertex(chouten)
	x1=XY[v1][0]
	y1=XY[v1][1]
	x2=XY[v2][0]
	y2=XY[v2][1]
	if y2<y1: y1,y2=y2,y1

	cnt=2
	for i in range(v1+1,v2):
		y=XY[i][1]
		if y1<=y<=y2:
			cnt+=1

	menseki=abs(x1-x2)*abs(y1-y2)

	if K<=cnt:
		ans=min(ans, menseki)

print ans

Submission status: Wrong Answer

Solution code:
#from numpy import*
#from scipy import*
from collections import* #defaultdict Counter deque appendleft
from fractions import gcd
from functools import* #reduce
from itertools import* #permutations("AB",repeat=2) combinations("AB",2) product("AB",2) groupby
from operator import mul
from bisect import* #bisect_left bisect_right
from heapq import* #heapify heappop heappushpop
from math import factorial,pi
from copy import deepcopy
import sys
#input=sys.stdin.readline  #危険！基本オフにしろ！
sys.setrecursionlimit(10**6)



def main():
    n,k=map(int,input().split())
    grid=[list(map(int,input().split()))for i in range(n)]
    ans=[]
    dx=sorted(grid,key=lambda x:x[0])
    for i in range(n-k+1):
        v=dx[i:i+k]
        y=set(t for s,t in v)
        #print(v)
        ans.append((v[-1][0]-v[0][0])*(max(y)-min(y)) )
    dy=sorted(grid,key=lambda x:x[1])
    for i in range(n-k+1):
        v=dy[i:i+k]
        x=set(s for s,t in v)
        ans.append((v[-1][1]-v[0][1])*(max(x)-min(x)) )
    print(max(ans))
    
    
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#from numpy import*
#from scipy import*
from collections import* #defaultdict Counter deque appendleft
from fractions import gcd
from functools import* #reduce
from itertools import* #permutations("AB",repeat=2) combinations("AB",2) product("AB",2) groupby
from operator import mul
from bisect import* #bisect_left bisect_right
from heapq import* #heapify heappop heappushpop
from math import factorial,pi
from copy import deepcopy
import sys
#input=sys.stdin.readline  #危険！基本オフにしろ！
sys.setrecursionlimit(10**6)



def main():
    n,k=map(int,input().split())
    grid=[list(map(int,input().split()))for i in range(n)]
    ans=[]
    dx=sorted(grid,key=lambda x:x[0])
    for i in range(n-k+1):
        v=dx[i:i+k]
        y=set(t for s,t in v)
        #print(v)
        ans.append((v[-1][0]-v[0][0])*(max(y)-min(y)) )
    #dy=sorted(grid,key=lambda x:x[1])
    #for i in range(n-k+1):
    #    v=dy[i:i+k]
    #    x=set(s for s,t in v)
    #    ans.append((v[-1][1]-v[0][1])*(max(x)-min(x)) )
    print(max(ans))
    
    
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#from numpy import*
#from scipy import*
from collections import* #defaultdict Counter deque appendleft
from fractions import gcd
from functools import* #reduce
from itertools import* #permutations("AB",repeat=2) combinations("AB",2) product("AB",2) groupby
from operator import mul
from bisect import* #bisect_left bisect_right
from heapq import* #heapify heappop heappushpop
from math import factorial
from copy import deepcopy
import sys
from scipy.sparse.csgraph import floyd_warshall

#input=sys.stdin.readline  #危険！基本オフにしろ！
sys.setrecursionlimit(10**6)


def main():
    n,k=map(int,input().split())
    points=[list(map(int,input().split()))for i in range(n)]
    print(points)
    ans=[]
    for s,t in [zip(*i) for i in combinations(points,2)]:
        print(s,t)
        minx=min(s)
        maxx=max(s)
        miny=min(t)
        maxy=max(t)
#        print(minx,miny,maxx,maxy)
        if sum(minx<=g<=maxx or miny<=h<=maxy for g,h in points)>=k:
            ans.append(abs((minx-maxx)*(miny-maxy)))
            print(abs((minx-maxx)*(miny-maxy)))
    print(min(ans))
        
        
        

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

X = []
Y = []
Z = []
for i in range(N):
    x,y = list(map(int,input().split()))
    X.append(x)
    Y.append(y)
    Z.append([x,y])

X.sort()
Y.sort()

min_rec=0

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):
                count=0
                for n in range(N):
                    if Z[n][0]>=X[i] and Z[n][0]<=X[j] and Z[n][1]>=Y[k] and Z[n][1]<=Y[l]:
                        count+=1
                if count==K:
                    min_rec = min(min_rec,(X[j]-X[i])*(Y[l]-Y[k]))

print(min_rec)

Submission status: Wrong Answer

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

X = []
Y = []
Z = []
for i in range(N):
    x,y = list(map(int,input().split()))
    X.append(x)
    Y.append(y)
    Z.append([x,y])

X.sort()
Y.sort()

max_rec=0

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):
                count=0
                for n in range(N):
                    if Z[n][0]>=X[i] and Z[n][0]<=X[j] and Z[n][1]>=Y[k] and Z[n][1]<=Y[l]:
                        count+=1
                if count==K:
                    max_rec = max(max_rec,(X[j]-X[i])*(Y[l]-Y[k]))

print(max_rec)

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
xy=[]
X=[]
Y=[]
for i in range(N):
    x,y=map(int,input().split())
    xy.append([x,y])
xy.sort()
X=[i[0] for i in xy]
Y=[i[1] for i in xy]
ans=10**30
for i in range(K,N+1):
    for j in range(N+1-i):
        X_=X[j:j+i]
        Y_=Y[j:j+i]
        a=max(X_)-min(X_)
        b=max(Y_)-min(Y_)
        ans=min(ans,a*b)
print(ans)