Problem:


Score : 400 points

Problem Statement

We have N points in a two-dimensional plane.

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

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

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

Find the minimum possible area of such a rectangle.  

Constraints

2 \leq K \leq N \leq 50 

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

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

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

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

Input

Input is given from Standard Input in the following format:  

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

Output

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

Sample Input 1

4 4
1 4
3 3
6 2
8 1

Sample Output 1

21

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

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

Sample Input 2

4 2
0 0
1 1
2 2
3 3

Sample Output 2

1

Sample Input 3

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

Sample Output 3

3999999996000000001

Watch out for integer overflows.  



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


Sample output:
21

Submission status: Wrong Answer

Solution code:
import itertools
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
def main():
    N,K=mi()
    G = []
    maxX,maxY,minX,minY = -INF,-INF,INF,INF
    for i in range(N):
        x,y = mi()
        G.append((x,y))
        maxX=max(maxX,x)
        maxY=max(maxY,y)
        minX=max(minX,x)
        minY=max(minY,y)


    def c(downx,upx,downy,upy):
        return count(downx,upx,downy,upy) >= K
       

    def count(downx,upx,downy,upy):
        _count = 0
        for i in range(N):
            x,y = G[i]
            if downx<=x<=upx and downy<=y<=upy:
                _count += 1
        
        return _count

    

    ans = INF
    for v in itertools.combinations(G, 2):
        u = list(v)
        u.sort()
        (x1,y1),(x2,y2) = u

        new_ans = 0
        if y1 < y2:
            #p1を角, p2のx採用: x1<=x<=x2, y1<=y<= newy, y2 <= newy 
            l = y2
            r = maxY
            while r-l > 1:
                mid = (l+r)//2
                if c(x1,x2,y1,mid):
                    r = mid
                else:
                    l = mid
            
            newy = r
            if count(x1,x2,y1,newy) >= K:
                new_ans = min(ans,abs(x1-x2) * abs(y1-newy))
            
            # p2のy採用:  x1<=x<=newx, y1<=y<=y2 
            l = x2
            r = maxX
            while r-l > 1:
                mid = (l+r)//2
                if c(x1,mid,y1,y2):
                    r = mid
                else:
                    l = mid
            
            newx = r
            if count(x1,newx,y1,y2) >= K:
                new_ans = min(ans,abs(x1-newx) * abs(y1-y2))

            #p2を角, p1のx採用
            l = minY
            r = y1
            while r-l > 1:
                mid = (l+r)//2
                if c(x1,x2,mid,y2):
                    r = mid
                else:
                    l = mid
            
            newy = r
            if count(x1,x2,newy,y2) >= K:
                new_ans = min(ans,abs(x1-x2) * abs(y2-newy))
            
            # p2を角, y採用
            l = minX
            r = x2
            while r-l > 1:
                mid = (l+r)//2
                if c(mid,x2,y2,y1):
                    r = mid
                else:
                    l = mid
            
            newx = r
            if count(newx,x2,y2,y1) >= K:
                new_ans = min(ans,abs(x2-newx) * abs(y1-y2))

        if y1 >= y2:
            #p2のx採用: x1<=x<=x2, y2<=y<= newy, y2 <= newy 
            l = y1
            r = maxY
            while r-l > 1:
                mid = (l+r)//2
                if c(x1,x2,mid,y2):
                    r = mid
                else:
                    l = mid
            
            newy = r
            if count(x1,x2,newy,y2) >= K:
                new_ans = min(ans,abs(x1-x2) * abs(y2-newy))
            
            # p2のy採用:  x1<=x<=newx, y2<=y<=y1
            l = x2
            r = maxX
            while r-l > 1:
                mid = (l+r)//2
                if c(x1,mid,y2,y1):
                    r = mid
                else:
                    l = mid
            
            newx = r
            if count(x1,newx,y2,y1) >= K:
                new_ans = min(ans,abs(x1-newx) * abs(y1-y2))


            #p2を角, p1のx採用
            l = y1
            r = maxY
            while r-l > 1:
                mid = (l+r)//2
                if c(x1,x2,y2,mid):
                    r = mid
                else:
                    l = mid
            
            newy = r
            if count(x1,x2,y2,newy) >= K:
                new_ans = min(ans,abs(x1-x2) * abs(y2-newy))
            
            # p1のy採用
            l = minY
            r = x1
            while r-l > 1:
                mid = (l+r)//2
                if c(mid,x2,y1,y2):
                    r = mid
                else:
                    l = mid
            
            newx = r
            if count(newx,x2,y1,y2) >= K:
                new_ans = min(ans,abs(x2-newx) * abs(y1-y2))


        if new_ans > 0:
            ans = min(ans,new_ans)

        # print(ans)

        downy = min(y1,y2)
        upy = max(y1,y2)

        _count = 0
        for i in range(N):
            x,y = G[i]

            if x1<=x<=x2 and downy<=y<=upy:
                _count += 1
        
        if not _count >= K: continue
        ans = min(ans,abs(x1-x2) * abs(y1-y2))

    
    print(ans)

            



if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import itertools
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
def main():
    N,K=mi()
    G = []
    maxX,maxY,minX,minY = -INF,-INF,INF,INF
    for i in range(N):
        x,y = mi()
        G.append((x,y))
        maxX=max(maxX,x)
        maxY=max(maxY,y)
        minX=max(minX,x)
        minY=max(minY,y)


    def c(downx,upx,downy,upy):
        return count(downx,upx,downy,upy) >= K
       

    def count(downx,upx,downy,upy):
        _count = 0
        for i in range(N):
            x,y = G[i]
            if downx<=x<=upx and downy<=y<=upy:
                _count += 1
        
        return _count

    

    ans = INF
    for v in itertools.combinations(G, 2):
        u = list(v)
        u.sort()
        (x1,y1),(x2,y2) = u

        new_ans = 0
        if y1 < y2:
            #p1を角, p2のx採用: x1<=x<=x2, y1<=y<= newy, y2 <= newy 
            l = y2
            r = maxY
            while r-l > 1:
                mid = (l+r)//2
                if c(x1,x2,y1,mid):
                    r = mid
                else:
                    l = mid
            
            newy = r
            if count(x1,x2,y1,newy) >= K:
                new_ans = min(ans,abs(x1-x2) * abs(y1-newy))
            
            # p2のy採用:  x1<=x<=newx, y1<=y<=y2 
            l = x2
            r = maxX
            while r-l > 1:
                mid = (l+r)//2
                if c(x1,mid,y1,y2):
                    r = mid
                else:
                    l = mid
            
            newx = r
            if count(x1,newx,y1,y2) >= K:
                new_ans = min(ans,abs(x1-newx) * abs(y1-y2))

        if y1 >= y2:
            #p2のx採用: x1<=x<=x2, y2<=y<= newy, y2 <= newy 
            l = y1
            r = maxY
            while r-l > 1:
                mid = (l+r)//2
                if c(x1,x2,mid,y2):
                    r = mid
                else:
                    l = mid
            
            newy = r
            if count(x1,x2,newy,y2) >= K:
                new_ans = min(ans,abs(x1-x2) * abs(y1-newy))
            
            # p2のy採用:  x1<=x<=newx, y2<=y<=y1
            l = x2
            r = maxX
            while r-l > 1:
                mid = (l+r)//2
                if c(x1,mid,y2,y1):
                    r = mid
                else:
                    l = mid
            
            newx = r
            if count(x1,newx,y2,y1) >= K:
                new_ans = min(ans,abs(x1-newx) * abs(y1-y2))

        if new_ans > 0:
            ans = min(ans,new_ans)

        # print(ans)

        downy = min(y1,y2)
        upy = max(y1,y2)

        _count = 0
        for i in range(N):
            x,y = G[i]

            if x1<=x<=x2 and downy<=y<=upy:
                _count += 1
        
        if not _count >= K: continue
        ans = min(ans,abs(x1-x2) * abs(y1-y2))

    
    print(ans)

            



if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import itertools
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
def main():
    N,K=mi()
    G = []
    maxX,maxY,minX,minY = -INF,-INF,INF,INF
    for i in range(N):
        x,y = mi()
        G.append((x,y))
        maxX=max(maxX,x)
        maxY=max(maxY,y)
        minX=max(minX,x)
        minY=max(minY,y)


    def c(downx,upx,downy,upy):
        return count(downx,upx,downy,upy) >= K
       

    def count(downx,upx,downy,upy):
        _count = 0
        for i in range(N):
            x,y = G[i]
            if downx<=x<=upx and downy<=y<=upy:
                _count += 1
        
        return _count

    

    ans = INF
    for v in itertools.combinations(G, 2):
        u = list(v)
        u.sort()
        (x1,y1),(x2,y2) = u

        new_ans = 0
        if y1 < y2:
            #p1を角, p2のx採用: x1<=x<=x2, y1<=y<= newy, y2 <= newy 
            l = y2
            r = maxY
            while r-l > 1:
                mid = (l+r)//2
                if c(x1,x2,y1,mid):
                    r = mid
                else:
                    l = mid
            
            newy = r
            if count(x1,x2,y1,newy) >= K:
                new_ans = min(ans,abs(x1-x2) * abs(y1-newy))
            
            # p2のy採用:  x1<=x<=newx, y1<=y<=y2 
            l = x2
            r = maxX
            while r-l > 1:
                mid = (l+r)//2
                if c(x1,mid,y1,y2):
                    r = mid
                else:
                    l = mid
            
            newx = r
            if count(x1,newx,y1,y2) >= K:
                new_ans = min(ans,abs(x1-newx) * abs(y1-y2))

        if y1 >= y2:
            #p2のx採用: x1<=x<=x2, y2<=y<= newy, y2 <= newy 
            l = y1
            r = maxY
            while r-l > 1:
                mid = (l+r)//2
                if c(x1,x2,mid,y2):
                    r = mid
                else:
                    l = mid
            
            newy = r
            if count(x1,x2,newy,y2) >= K:
                new_ans = min(ans,abs(x1-x2) * abs(y1-newy))
            
            # p2のy採用:  x1<=x<=newx, y2<=y<=y1
            l = x2
            r = maxX
            while r-l > 1:
                mid = (l+r)//2
                if c(x1,mid,y2,y1):
                    r = mid
                else:
                    l = mid
            
            newx = r
            if count(x1,newx,y2,y1) >= K:
                new_ans = min(ans,abs(x1-newx) * abs(y1-y2))

        if new_ans > 0:
            ans = min(ans,new_ans)

        # print(ans)



        # downy = min(y1,y2)
        # upy = max(y1,y2)



        # count = 0
        # for i in range(N):
        #     x,y = G[i]

        #     if x1<=x<=x2 and downy<=y<=upy:
        #         count += 1
        
        # if not count >= K: continue
        # ans = min(ans,abs(x1-x2) * abs(y1-y2))

    
    print(ans)

            



if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import itertools
import numpy as np
N, K, *XY = [int(_) for _ in open(0).read().split()]
X = sorted(XY[::2])
Y = sorted(XY[1::2])
XY = np.array(XY, dtype=np.int64).reshape((N, 2)).T
ans = float('inf')
for x, y in zip(itertools.combinations(X, 2), itertools.combinations(Y, 2)):
    F = (x[0] <= XY[0]) * (XY[0] <= x[1]) * (y[0] <= XY[1]) * (XY[1] <= y[1])
    if sum(F) < K:
        continue
    ans = min(ans, (x[1] - x[0]) * (y[1] - y[0]))
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
import numpy as np
N, K, *XY = [int(_) for _ in open(0).read().split()]
X = sorted(XY[::2])
Y = sorted(XY[1::2])
XY = np.array(XY).reshape((N, 2))
ans = float('inf')
for xs, ys in zip(itertools.combinations(X, 2), itertools.combinations(Y, 2)):
    F = (xs[0] <= XY[:, 0]) * (XY[:, 0] <= xs[1]) * (ys[0] <= XY[:, 1]) * (XY[:, 1] <= ys[1])
    if sum(F) < K:
        continue
    ans = min(ans, (xs[1] - xs[0]) * (ys[1] - ys[0]))
print(ans)

Submission status: Wrong Answer

Solution code:
import math
N,K = map(int, input().split())
xy=sorted([list(map(int, input().split())) for i in range(N)])
S = math.inf
for j in range(N-K+1):
    for k in range(N-K-j+1):
        y = sorted(xy[j:j+K+k],key=lambda x:x[1])
        T = xy[j+K+k-1][0] - xy[j][0]
        S = min(S, T*(y[-1][1]-y[0][1]))
        # j <= x < j+K+k には、点が K+k つまり y方向の調整で k 個削減してよい
        for m in range(k):
            for n in range(m):
                S = min(S, T*(y[n-m-1][1]-y[n][1]))
print(S)

Submission status: Wrong Answer

Solution code:
import sys
from operator import itemgetter
input = sys.stdin.readline

def main():
  n, k = map(int, input().split())
  point = [[int(x) for x in input().split()] for _ in range(n)]
  point.sort()
  point = [[x[0], x[1], i] for i, x in enumerate(point)]
  point.sort(key=itemgetter(1))
  point = [[x[0], x[1], x[2], i] for i, x in enumerate(point)]
  
  count_sum = [[0]*(n+1) for _ in range(n+1)]
  for i in range(n):
    for j in range(n):
      count_sum[i+1][j+1] += count_sum[i+1][j]+count_sum[i][j+1]-count_sum[i][j]
      if point[i][2] == j:
        count_sum[i+1][j+1] += 1
  
  key_x = dict()
  key_y = dict()
  for i in range(n):
    a, b, c, d = point[i]
    key_x[a] = c+1
    key_y[b] = d+1

  ans = pow(10, 18)*4
  for a in range(n):
    for b in range(n):
      for c in range(n):
        for d in range(n):
          x, y = [point[a][0], point[b][0], point[c][0], point[d][0]], [point[a][1], point[b][1], point[c][1], point[d][1]]
          x1, x2, y1, y2 = min(x), max(x), min(y), max(y)
          i1, i2, j1, j2 = key_x[x1], key_x[x2], key_y[y1], key_y[y2]
          count = count_sum[i2][j2]-count_sum[i1-1][j2]-count_sum[i2][j1-1]+count_sum[i1-1][j1-1]
          if count < k:
            continue
          sub = (x2-x1)*(y2-y1)
          if ans > sub:
            ans = sub
  
  print(ans)
  
  
if __name__ == "__main__":
  main()

Submission status: Wrong Answer

Solution code:
import sys
from operator import itemgetter
input = sys.stdin.readline

def main():
  n, k = map(int, input().split())
  point = [[int(x) for x in input().split()] for _ in range(n)]
  point.sort()
  point = [[x[0], x[1], i] for i, x in enumerate(point)]
  point.sort(key=itemgetter(1))
  point = [[x[0], x[1], x[2], i] for i, x in enumerate(point)]
  
  count_sum = [[0]*(n+1) for _ in range(n+1)]
  for i in range(n):
    for j in range(n):
      count_sum[i+1][j+1] += count_sum[i+1][j]+count_sum[i][j+1]-count_sum[i][j]
      if point[i][2] == j:
        count_sum[i+1][j+1] += 1
  
  key_x = dict()
  key_y = dict()
  for i in range(n):
    a, b, c, d = point[i]
    key_x[a] = c+1
    key_y[b] = d+1

  ans = pow(10, 18)*4
  for a in range(n):
    for b in range(a+1):
      for c in range(b+1):
        for d in range(c+1):
          x, y = [point[a][0], point[b][0], point[c][0], point[d][0]], [point[a][1], point[b][1], point[c][1], point[d][1]]
          x1, x2, y1, y2 = min(x), max(x), min(y), max(y)
          i1, i2, j1, j2 = key_x[x1], key_x[x2], key_y[y1], key_y[y2]
          count = count_sum[i2][j2]-count_sum[i1-1][j2]-count_sum[i2][j1-1]+count_sum[i1-1][j1-1]
          if count < k:
            continue
          sub = (x2-x1)*(y2-y1)
          if ans > sub:
            ans = sub
  
  print(ans)
  
  
if __name__ == "__main__":
  main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

def main():
  n, k = map(int, input().split())
  point = [[int(x) for x in input().split()] for _ in range(n)]
  
  ans = pow(10, 18)*4
  for a in range(n):
    for b in range(a):
      for c in range(b):
        for d in range(c):
          x, y = [point[a][0], point[b][0], point[c][0], point[d][0]], [point[a][1], point[b][1], point[c][1], point[d][1]]
          x1, x2, y1, y2 = min(x), max(x), min(y), max(y)
          count = 0
          for e in range(n):
            if x1 <= point[e][0] <= x2 and y1 <= point[e][1] <= y2:
              count += 1
          if count < k:
            continue
          sub = (x2-x1)*(y2-y1)
          if ans > sub:
            ans = sub
  
  print(ans)
  
  
if __name__ == "__main__":
  main()

Submission status: Wrong Answer

Solution code:
import sys
from operator import itemgetter

n, k = map(int, input().split())
point = [[int(x) for x in input().split()] for _ in range(n)]

point.sort()

ans = 4*pow(10, 18)
judge = [[None]*n for _ in range(n)]
for i in range(n):
  sub = point[i][1]
  for j in range(i+1):
    if i == j:
      judge[i][j] = (sub, sub)
    else:
      judge[i][j] = (min(judge[i-1][j][0], sub), max(judge[i-1][j][1], sub))
    if i-j+1 >= k:
      res = (point[i][0]-point[j][0])*(judge[i][j][1]-judge[i][j][0])
      if ans > res:
        ans = res

        
point.sort(key=itemgetter(1))
judge = [[None]*n for _ in range(n)]
for i in range(n):
  sub = point[i][0]
  for j in range(i+1):
    if i == j:
      judge[i][j] = (sub, sub)
    else:
      judge[i][j] = (min(judge[i-1][j][0], sub), max(judge[i-1][j][1], sub))
    if i-j+1 >= k:
      res = (point[i][1]-point[j][1])*(judge[i][j][1]-judge[i][j][0])
      if ans > res:
        ans = res

print(1 if k == 1 else ans)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
point = [[int(x) for x in input().split()] for _ in range(n)]

point.sort()

ans = 4*pow(10, 18)
judge = [[None]*n for _ in range(n)]
for i in range(n):
  sub = point[i][1]
  for j in range(i+1):
    if i == j:
      judge[i][j] = (sub, sub)
    else:
      judge[i][j] = (min(judge[i-1][j][0], sub), max(judge[i-1][j][1], sub))
    if i-j+1 >= k:
      res = (point[i][0]-point[j][0])*(judge[i][j][1]-judge[i][j][0])
      if ans > res:
        ans = res

print(1 if k == 1 else ans)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
point = [[int(x) for x in input().split()] for _ in range(n)]

point.sort()

ans = 4*pow(10, 18)
judge = [[None]*n for _ in range(n)]
for i in range(n):
  sub = point[i][1]
  for j in range(i+1):
    if i == j:
      judge[i][j] = (sub, sub)
    else:
      judge[i][j] = (min(judge[i-1][j][0], sub), max(judge[i-1][j][1], sub))
    if i-j+1 >= k:
      res = (point[i][0]-point[j][0])*(judge[i][j][1]-judge[i][j][0])
      if ans > res:
        ans = res

print(ans)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
Points = [tuple(map(int, input().split())) for _ in range(N)]
Points.sort()
ans = float('inf')

for i in range(N):
    if i + K > N:
        break
    X = []
    Y = []
    for j in range(i, i + K):
        X.append(Points[j][0])
        Y.append(Points[j][1])
    a = (max(X) - min(X)) * (max(Y) - min(Y))
    for j in range(i + K, N):
        X.append(Points[j][0])
        Y.append(Points[j][1])
        Y.sort()
        x = (X[-1] - X[0]) * (Y[-1] - Y[1])
        y = (X[-1] - X[0]) * (Y[-2] - Y[0])
        if x > y:
            Y = Y[1:]
            if a >= y:
                a = y
            else:
                break
        else:
            Y = Y[:-1]
            if a >= x:
                a = x
            else:
                break
    ans = min(ans, a)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
readline=sys.stdin.readline
read=sys.stdin.read

def main():
    n,k=map(int,readline().split())
    ab=[list(map(int,l.split())) for l in read().splitlines()]
    
    ek=0
    while k>>ek:
        ek+=1

    cand=[]
    for i in range(ek):
        if k>>i&1:
            m=(k>>(i+1))<<(i+1)|((1<<i)-1)
            cand.append(sum([e[1] for e in ab if e[0]|m==m]))
    cand.append(sum([e[1] for e in ab if e[0]|k==k]))
    print(max(cand))

if __name__=='__main__':
  main()

Submission status: Wrong Answer

Solution code:
import sys
readline=sys.stdin.readline
read=sys.stdin.read

def main():
    n,k=map(int,readline().split())
    ab=[list(map(int,l.split())) for l in read().splitlines()]
    
    ek=0
    while k>>ek:
        ek+=1

    cand=[]
    for i in range(ek):
        if k>>i&1:
            m=(k>>(i+1))<<(i+1)|((1<<i)-1)
            cand.append(sum([e[1] for e in ab if e[0]|m==m]))
    cand.append(sum([e[1] for e in ab if e[0]|k==k]))
    print(max(cand))

if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

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


def resolve():
    n, k = map(int, input().split())
    X, Y = [], []
    XY = []
    for _ in range(n):
        x, y = map(int, input().split())
        X.append(x)
        Y.append(y)
        XY.append([x, y])
    X.sort()
    Y.sort()
    right = X[-1]
    up = Y[-1]
    res = f_inf
    for left in X:
        for bottom in Y:
            cnt = 0
            for x, y in XY:
                if left <= x <= right and bottom <= y <= up:
                    cnt += 1
            if cnt >= k:
                area = (right - left) * (up - bottom)
                res = min(res, area)
    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Wrong Answer

Solution code:
from itertools import combinations as comb
n, k = map(int, input().split())
xys = [list(map(int, input().split())) for _ in range(n)]

def count_in_rect(x1, y1, x2, y2):
    ret = 0
    for i in xys:
        this_x, this_y = i[0], i[1]
        if this_x == x1 or this_x == x2:
            ret += 1
        if (x1 < this_x < x2 or  x1 > this_x > x2) and (y1 < this_y < y2 or  y1 > this_y > y2):
            ret += 1
    return ret

def find_closek(x1, y1, x2, y2):
    bar = (y1 + y2) / 2
    ret = []
    for _ in range(k-2):
        tmp_dif = float('inf')
        tmp_x = ""
        tmp_y = ""
        for i in xys:
            this_x, this_y = i[0], i[1]
            if this_x == x1 or this_x == x2:
                continue
            if (x1 < this_x < x2 or  x1 > this_x > x2) and abs(bar-this_y) < tmp_dif and ((this_x,this_y) not in ret):
                tmp_dif = abs(bar-this_y)
                tmp_x = this_x
                tmp_y = this_y
        if not tmp_x == "":
            ret.append((tmp_x,tmp_y))
    return ret

res = float('inf')
perms = list(range(n))
for p in comb(perms, 2):
    #print()
    #print(p)
    x1, y1 = xys[p[0]]
    x2, y2 = xys[p[1]]
    if count_in_rect(x1, y1, x2, y2) >= k:
        if abs(x1-x2) == 0:
            res = min(res, abs(y1 - y2))
        elif abs(y1-y2) == 0:
            res = min(res,abs(x1-x2))
        else:
            res = min(res,abs(x1-x2)*abs(y1-y2))
    else:
        ret = find_closek(x1, y1, x2, y2)
        if len(ret) < k-2:
            continue
        else:
            high = -float('inf')
            low = float('inf')
            for i in ret + [(x1, y1), (x2, y2)]:
                high = max(high,i[1])
                low = min(low, i[1])
            res = min(res,abs(x1-x2)*(high-low))
    #print(res)
print(res)

Submission status: Wrong Answer

Solution code:
from itertools import combinations as comb
n, k = map(int, input().split())
xys = [list(map(int, input().split())) for _ in range(n)]

def count_in_rect(x1, y1, x2, y2):
    ret = 0
    for i in xys:
        this_x, this_y = i[0], i[1]
        if this_x == x1 or this_x == x2:
            ret += 1
        if (x1 < this_x < x2 or  x1 > this_x > x2) and (y1 < this_y < y2 or  y1 > this_y > y2):
            ret += 1
    return ret

def find_closek(x1, y1, x2, y2):
    bar = (y1 + y2) / 2
    ret = []
    for _ in range(k-2):
        tmp_dif = float('inf')
        tmp_x = ""
        tmp_y = ""
        for i in xys:
            this_x, this_y = i[0], i[1]
            if this_x == x1 or this_x == x2:
                continue
            if (x1 < this_x < x2 or  x1 > this_x > x2) and abs(bar-this_y) < tmp_dif and ((this_x,this_y) not in ret):
                tmp_dif = abs(bar-this_y)
                tmp_x = this_x
                tmp_y = this_y
        if not tmp_x == "":
            ret.append((tmp_x,tmp_y))
    return ret

res = float('inf')
perms = list(range(n))
for p in comb(perms, 2):
    x1, y1 = xys[p[0]]
    x2, y2 = xys[p[1]]
    if count_in_rect(x1, y1, x2, y2) >= k:
        res = min(res,abs(x1-x2)*abs(y1-y2))
    else:
        ret = find_closek(x1, y1, x2, y2)
        if len(ret) < k-2:
            continue
        else:
            high = -float('inf')
            low = float('inf')
            for i in ret + [(x1, y1), (x2, y2)]:
                high = max(high,i[1])
                low = min(low, i[1])
            res = min(res,abs(x1-x2)*(high-low))
print(res)

Submission status: Wrong Answer

Solution code:
from itertools import combinations as comb
n, k = map(int, input().split())
xys = [list(map(int, input().split())) for _ in range(n)]

def count_in_rect(x1, y1, x2, y2):
    ret = 0
    for i in xys:
        this_x, this_y = i[0], i[1]
        if this_x == x1 or this_x == x2:
            ret += 1
        if (x1 < this_x < x2 or  x1 > this_x > x2) and (y1 < this_y < y2 or  y1 > this_y > y2):
            ret += 1
    return ret

def find_closek(x1, y1, x2, y2):
    bar = (y1 + y2) / 2
    ret = []
    for _ in range(k):
        tmp_dif = float('inf')
        tmp_x = ""
        tmp_y = ""
        for i in xys:
            this_x, this_y = i[0], i[1]
            if this_x == x1 or this_x == x2:
                continue
            if (x1 < this_x < x2 or  x1 > this_x > x2) and abs(bar-this_y) < tmp_dif and ((this_x,this_y) not in ret):
                tmp_dif = abs(bar-this_y)
                tmp_x = this_x
                tmp_y = this_y
        if not tmp_x == "":
            ret.append((tmp_x,tmp_y))
    return ret

res = float('inf')
perms = list(range(n))
for p in comb(perms, 2):
    x1, y1 = xys[p[0]]
    x2, y2 = xys[p[1]]
    if count_in_rect(x1, y1, x2, y2) >= k:
        res = min(res,abs(x1-x2)*abs(y1-y2))
    else:
        ret = find_closek(x1, y1, x2, y2)
        if len(ret) < k-2:
            continue
        else:
            high = -float('inf')
            low = float('inf')
            for i in ret + [(x1, y1), (x2, y2)]:
                high = max(high,i[1])
                low = min(low, i[1])
            res = min(res,abs(x1-x2)*(high-low))
print(res)

Submission status: Wrong Answer

Solution code:
import sys
from itertools import accumulate
def input(): return sys.stdin.readline().strip()

def main():
    N, K = map(int, input().split())
    points = []
    X = set()
    Y = set()
    for _ in range(N):
        x, y = map(int, input().split())
        points.append((x, y))
        X.add(x)
        Y.add(y)
    X = list(X)
    Y = list(Y)
    X.sort()
    Y.sort()

    mapX = {} # mapX[x] = (点のx座標が小さい方から何番目か)
    mapY = {} # mapY[y] = (点のy座標が小さい方から何番目か)
    for i, x in enumerate(X): mapX[x] = i + 1
    for i, y in enumerate(Y): mapY[y] = i + 1

    # 圧縮後の座標平面に対してグリッドを張るので、そのサイズを求めておく
    h, w = len(mapX), len(mapY)
    grid = [[0] * (w + 1) for _ in range(h + 1)]
    for x, y in points:
        grid[mapY[y]][mapX[x]] = 1
    sum_grid = [list(accumulate(grid[y])) for y in range(h + 1)]
    for y in range(1, h + 1):
        for x in range(1, w + 1):
            sum_grid[y][x] += sum_grid[y - 1][x]
    print("sum_grid")
    for y in range(h + 1):
        print(sum_grid[y])

    ans = 10**20
    for sx in range(1, w + 1):
        for sy in range(1, h + 1):
            for ex in range(sx, w + 1):
                for ey in range(sy, h + 1):
                    cnt = sum_grid[ey][ex] - sum_grid[ey][sx-1] - sum_grid[sy-1][ex] + sum_grid[sy-1][sx-1]
                    if cnt < K: continue
                    area = (X[ex - 1] - X[sx - 1]) * (Y[ey - 1] - Y[sy - 1])
                    ans = min(ans, area)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

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

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

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

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

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

print(ans)