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: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
#ABC75 D

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))


n,K = LI()
xy = [LI() for _ in range(n)]
xy.sort(key = itemgetter(1),reverse = True)
ans = inf
for i in range(n):
    ux,uy = xy[i]
    for j in range(i+1,n):
        dx,dy = xy[j]
        for k in range(n):
            rx,ry = xy[k]
            for l in range(n):
                lx,ly = xy[l]
                if rx < lx:
                    continue
                cnt = 0
                for m in range(n):
                    x,y = xy[m]
                    if lx <= x <= rx and dy <= y <= uy:
                        cnt += 1
                if cnt >= K:
                    S = (uy - dy)*(rx - lx)
                    ans = min(ans,S)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
#ABC75 D

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))


n,K = LI()
xy = [LI() for _ in range(n)]
xy.sort(key = itemgetter(1))
xy.sort(key = itemgetter(0))
ans = inf
for i in range(n):
    ux,uy = xy[i]
    for j in range(n):
        dx,dy = xy[j]
        if uy < dy:
            continue
        for k in range(n):
            rx,ry = xy[k]
            for l in range(n):
                lx,ly = xy[l]
                if rx < lx:
                    continue
                cnt = 0
                for m in range(n):
                    x,y = xy[m]
                    if lx <= x <= rx and dy <= y <= uy:
                        cnt += 1
                if cnt >= K:
                    S = (uy - dy)*(rx - lx)
                    ans = min(ans,S)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
#ABC75 D

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))


n,K = LI()
xy = [LI() for _ in range(n)]
ans = inf
for i in range(n):
    ux,uy = xy[i]
    for j in range(n):
        dx,dy = xy[j]
        if uy < dy:
            continue
        for k in range(n):
            rx,ry = xy[k]
            for l in range(n):
                lx,ly = xy[l]
                if rx < lx:
                    continue
                cnt = 0
                for m in range(n):
                    x,y = xy[m]
                    if lx <= x <= rx and dy <= y <= uy:
                        cnt += 1
                if cnt >= K:
                    S = (uy - dy)*(rx - lx)
                    ans = min(ans,S)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
#ABC75 D

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))


n,K = LI()
xy = [LI() for _ in range(n)]
ans = inf
for i in range(n):
    ux,uy = xy[i]
    for j in range(n):
        dx,dy = xy[j]
        for k in range(n):
            rx,ry = xy[k]
            for l in range(n):
                lx,ly = xy[l]
                if uy <= dy and rx <= lx:
                    continue
                cnt = 0
                for m in range(n):
                    x,y = xy[m]
                    if lx <= x <= rx and dy <= y <= uy:
                        cnt += 1
                if cnt >= K:
                    S = (uy - dy)*(rx - lx)
                    ans = min(ans,S)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
#ABC75 D

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))


n,k = LI()
xy = [LI() for _ in range(n)]
ans = inf
for u in range(n):
    for d in range(n):
        for r in range(n):
            for l in range(n):
                cnt = 0
                if xy[u][1] < xy[d][1] or xy[r][0] < xy[l][0]:
                    continue
                for i in range(n):
                    x,y = xy[i]
                    if xy[l][0] <= x <= xy[r][0]  and xy[d][1] <= y <= xy[u][1]:
                        cnt += 1
                if cnt >= k:
                    S = (xy[u][1] - xy[d][1])*(xy[r][0] - xy[l][0])
                    ans = min(ans,S)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
#ABC75 D

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))


n,k = LI()
xy = [LI() for _ in range(n)]
ans = inf
for u in range(n):
    for d in range(n):
        for r in range(n):
            for l in range(n):
                cnt = 0
                for i in range(n):
                    x,y = xy[i]
                    if xy[l][0] <= x <= xy[r][0]  and xy[d][1] <= y <= xy[u][1]:
                        cnt += 1
                if cnt >= k:
                    S = (xy[u][1] - xy[d][1])*(xy[r][0] - xy[l][0])
                    ans = min(ans,S)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    N, K = map(int, input().split())
    XY = [tuple(map(int, input().split())) for _ in range(N)]
    XY.sort()
    XY = tuple(XY)

    def count(x_min, x_max, y_min, y_max, i, j):
        OK = 0
        # NG = 0
        for m, n in XY[i:j + 1]:
            if y_min <= n <= y_max:
                OK += 1
        if OK >= K:
            return True
        return False

    ans = 10 ** 20
    for i, val_i in enumerate(XY[:N - 1]):
        a = val_i[0]
        for j in range(i + K - 1, N):
            b = XY[j][0]
            e = b - a
            # print (e, i, j)
            for k, c in XY:
                # c = k[1]
                for l, d in XY:
                    # d = l[1]
                    if c < d:
                        if count(a, b, c, d, i, j):
                            # print ('A')
                            ans = min(ans, e * (d - c))
    print (ans)
    return

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    N, K = map(int, input().split())
    XY = [tuple(map(int, input().split())) for _ in range(N)]
    XY.sort()
    XY = tuple(XY)

    def count(x_min, x_max, y_min, y_max, i, j):
        OK = 0
        # NG = 0
        for m in XY[i:j + 1]:
            if y_min <= m[1] <= y_max:
                OK += 1
        if OK >= K:
            return True
        return False

    ans = 10 ** 20
    for i, val_i in enumerate(XY[:N - 1]):
        a = val_i[0]
        for j in range(i + K - 1, N):
            b = XY[j][0]
            e = b - a
            # print (e, i, j)
            for k in XY:
                c = k[1]
                for l in XY:
                    d = l[1]
                    if c < d:
                        if count(a, b, c, d, i, j):
                            # print ('A')
                            ans = min(ans, e * (d - c))
    print (ans)
    return

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    N, K = map(int, input().split())
    XY = [tuple(map(int, input().split())) for _ in range(N)]
    XY.sort()
    XY = tuple(XY)

    def count(x_min, x_max, y_min, y_max, i, j):
        OK = 0
        # NG = 0
        a = j - i + 1 - K
        for m in XY[i:j + 1]:
            if y_min <= m[1] <= y_max:
                OK += 1
        if OK >= K:
            return True
        return False

    ans = 10 ** 20
    for i, val_i in enumerate(XY[:N - 1]):
        a = val_i[0]
        for j, val_j in enumerate(XY[i + K - 1:N]):
            b = val_j[0]
            e = b - a
            # print (e, i, j)
            for k in XY:
                c = k[1]
                for l in XY:
                    d = l[1]
                    if c < d:
                        if count(a, b, c, d, i, j + i + K - 1):
                            # print ('A')
                            ans = min(ans, e * (d - c))
    print (ans)
    return

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    N, K = map(int, input().split())
    XY = [tuple(map(int, input().split())) for _ in range(N)]
    XY.sort()
    XY = tuple(XY)

    def count(x_min, x_max, y_min, y_max, i, j):
        OK = 0
        # NG = 0
        a = j - i + 1 - K
        for m in XY[i:j + 1]:
            if y_min <= m[1] <= y_max:
                OK += 1
        if OK >= K:
            return True
        return False

    ans = 10 ** 20
    for i, val_i in enumerate(XY[:N - 1]):
        a = val_i[0]
        for j, val_j in enumerate(XY[i + K - 1:N]):
            b = val_j[0]
            e = b - a
            # print (e, i, j)
            for k in range(N):
                c = XY[k][1]
                for l in range(N):
                    d = XY[l][1]
                    if c < d:
                        if count(a, b, c, d, i, j + i + K - 1):
                            # print ('A')
                            ans = min(ans, e * (d - c))
    print (ans)
    return

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    N, K = map(int, input().split())
    XY = [tuple(map(int, input().split())) for _ in range(N)]
    XY.sort()
    XY = tuple(XY)

    def count(x_min, x_max, y_min, y_max, i, j):
        OK = 0
        # NG = 0
        a = j - i + 1 - K
        for m in XY[i:j + 1]:
            if y_min <= m[1] <= y_max:
                OK += 1
        if OK >= K:
            return True
        return False

    ans = 10 ** 20
    for i, val in enumerate(XY[:N - 1]):
        a = val[0]
        for j in range(i + K - 1, N):
            b = XY[j][0]
            e = b - a
            for k in range(N):
                c = XY[k][1]
                for l in range(N):
                    d = XY[l][1]
                    if c < d:
                        if count(a, b, c, d, i, j):
                            # print ('A')
                            ans = min(ans, e * (d - c))
    print (ans)
    return

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    N, K = map(int, input().split())
    XY = [tuple(map(int, input().split())) for _ in range(N)]
    XY.sort()
    XY = tuple(XY)

    def count(x_min, x_max, y_min, y_max, i, j):
        OK = 0
        # NG = 0
        a = j - i + 1 - K
        for m in XY[i:j + 1]:
            if y_min <= m[1] <= y_max:
                OK += 1
        if OK >= K:
            return True
        return False

    ans = 10 ** 20
    for i in range(N - 1):
        a = XY[i][0]
        for j in range(i + K - 1, N):
            b = XY[j][0]
            e = b - a
            for k in range(N):
                c = XY[k][1]
                for l in range(N):
                    d = XY[l][1]
                    if c < d:
                        if count(a, b, c, d, i, j):
                            # print ('A')
                            ans = min(ans, e * (d - c))
    print (ans)
    return

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    N, K = map(int, input().split())
    XY = [tuple(map(int, input().split())) for _ in range(N)]
    XY.sort()
    XY = tuple(XY)

    def count(x_min, x_max, y_min, y_max, i, j):
        OK = 0
        # NG = 0
        a = j - i + 1 - K
        for m in range(i, j + 1):
            if y_min <= XY[m][1] <= y_max:
                OK += 1
            # else:
            #     NG += 1
            # if OK >= K:
            #     return True
            # if NG > a:
            #     return False
        if OK >= K:
            return True
        return False

    ans = 10 ** 20
    for i in range(N - 1):
        a = XY[i][0]
        for j in range(i + K - 1, N):
            b = XY[j][0]
            e = b - a
            for k in range(N):
                c = XY[k][1]
                for l in range(N):
                    d = XY[l][1]
                    if c < d:
                        if count(a, b, c, d, i, j):
                            # print ('A')
                            ans = min(ans, e * (d - c))
    print (ans)
    return

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    N, K = map(int, input().split())
    XY = [tuple(map(int, input().split())) for _ in range(N)]
    XY.sort()
    XY = tuple(XY)

    def count(x_min, x_max, y_min, y_max, i, j):
        OK = 0
        # NG = 0
        a = j - i + 1 - K
        for m in range(i, j + 1):
            if y_min <= XY[m][1] <= y_max:
                OK += 1
            # else:
            #     NG += 1
            # if OK >= K:
            #     return True
            # if NG > a:
            #     return False
        if OK >= K:
            return True
        return False

    ans = 10 ** 20
    for i in range(N - 1):
        a = XY[i][0]
        for j in range(i + K - 1, N):
            b = XY[j][0]
            for k in range(N):
                c = XY[k][1]
                for l in range(N):
                    d = XY[l][1]
                    if c < d:
                        if count(a, b, c, d, i, j):
                            # print ('A')
                            ans = min(ans, (b - a) * (d - c))
    print (ans)
    return

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    N, K = map(int, input().split())
    XY = [tuple(map(int, input().split())) for _ in range(N)]
    XY.sort()
    XY = tuple(XY)

    def count(x_min, x_max, y_min, y_max, i, j):
        OK = 0
        NG = 0
        a = j - i + 1 - K
        for m in range(i, j + 1):
            if y_min <= XY[m][1] <= y_max:
                OK += 1
            else:
                NG += 1
            if OK >= K:
                return True
            if NG > a:
                return False

    ans = 10 ** 20
    for i in range(N - 1):
        a = XY[i][0]
        for j in range(i + K - 1, N):
            b = XY[j][0]
            for k in range(N):
                c = XY[k][1]
                for l in range(N):
                    d = XY[l][1]
                    if c < d:
                        if count(a, b, c, d, i, j):
                            # print ('A')
                            ans = min(ans, (b - a) * (d - c))
    print (ans)
    return

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    N, K = map(int, input().split())
    XY = [tuple(map(int, input().split())) for _ in range(N)]
    # XY = [list(map(int, input().split())) for _ in range(N)]
    XY.sort()
    XY = tuple(XY)

    def count(x_min, x_max, y_min, y_max, i, j):
        OK = 0
        NG = 0
        a = j - i + 1 - K
        for m in range(i, j + 1):
            if y_min <= XY[m][1] <= y_max:
                OK += 1
            else:
                NG += 1
            if OK >= K:
                return True
            if NG > a:
                return False

    ans = 10 ** 20
    for i in range(N - 1):
        a = XY[i][0]
        for j in range(i + K - 1, N):
            b = XY[j][0]
            for k in range(N):
                c = XY[k][1]
                for l in range(N):
                    d = XY[l][1]
                    if c < d:
                        if count(a, b, c, d, i, j):
                            # print ('A')
                            ans = min(ans, (a - b) * (c - d))
    print (ans)
    return

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    N, K = map(int, input().split())
    XY = [tuple(map(int, input().split())) for _ in range(N)]
    # XY = [list(map(int, input().split())) for _ in range(N)]
    XY.sort()
    XY = tuple(XY)

    def count(x_min, x_max, y_min, y_max, i, j):
        OK = 0
        NG = 0
        a = j - i + 1 - K
        for m in range(i, j + 1):
            if y_min <= XY[m][1] <= y_max:
                OK += 1
            else:
                NG += 1
            if OK >= K:
                return True
            if NG > a:
                return False

    ans = 10 ** 20
    for i in range(N - 1):
        for j in range(i + K - 1, N):
            for k in range(N):
                for l in range(N):
                    if XY[k][1] < XY[l][1]:
                        if count(XY[i][0], XY[j][0], XY[k][1], XY[l][1], i, j):
                            # print ('A')
                            ans = min(ans, (XY[j][0] - XY[i][0]) * (XY[l][1] - XY[k][1]))
    print (ans)
    return

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    N, K = map(int, input().split())
    XY = [tuple(map(int, input().split())) for _ in range(N)]
    # XY = [list(map(int, input().split())) for _ in range(N)]
    XY.sort()

    def count(x_min, x_max, y_min, y_max, i, j):
        OK = 0
        NG = 0
        a = j - i + 1 - K
        for m in range(i, j + 1):
            if y_min <= XY[m][1] <= y_max:
                OK += 1
            else:
                NG += 1
            if OK >= K:
                return True
            if NG > a:
                return False

    ans = 10 ** 20
    for i in range(N - 1):
        for j in range(i + K - 1, N):
            for k in range(N):
                for l in range(N):
                    if XY[k][1] < XY[l][1]:
                        if count(XY[i][0], XY[j][0], XY[k][1], XY[l][1], i, j):
                            # print ('A')
                            ans = min(ans, (XY[j][0] - XY[i][0]) * (XY[l][1] - XY[k][1]))
    print (ans)
    return

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():

    N, K = map(int, input().split())
    XY = [list(map(int, input().split())) for _ in range(N)]
    XY.sort()

    def count(x_min, x_max, y_min, y_max, i, j):
        OK = 0
        NG = 0
        a = j - i + 1 - K
        for m in range(i, j + 1):
            if y_min <= XY[m][1] <= y_max:
                OK += 1
            else:
                NG += 1
            if OK >= K:
                return True
            if NG > a:
                return False

    ans = 10 ** 20
    for i in range(N - 1):
        for j in range(i + K - 1, N):
            for k in range(N):
                for l in range(N):
                    if XY[k][1] < XY[l][1]:
                        if count(XY[i][0], XY[j][0], XY[k][1], XY[l][1], i, j):
                            # print ('A')
                            ans = min(ans, (XY[j][0] - XY[i][0]) * (XY[l][1] - XY[k][1]))
    print (ans)
    return

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

def count(x_min, x_max, y_min, y_max, i, j):
    OK = 0
    NG = 0
    a = j - i + 1 - K
    for m in range(i, j + 1):
        if y_min <= XY[m][1] <= y_max:
            OK += 1
        else:
            NG += 1
        if OK >= K:
            return True
        if NG > a:
            return False


ans = 10 ** 20
for i in range(N - 1):
    for j in range(i + K - 1, N):
        for k in range(N):
            for l in range(N):
                if XY[k][1] < XY[l][1]:
                    if count(XY[i][0], XY[j][0], XY[k][1], XY[l][1], i, j):
                        # print ('A')
                        ans = min(ans, (XY[j][0] - XY[i][0]) * (XY[l][1] - XY[k][1]))
print (ans)

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
XY = [list(map(int, input().split())) for _ in range(N)]
XY.sort()
XY_Y = sorted(XY, key = lambda x: x[1])

def count(x_min, x_max, y_min, y_max, i, j):
    OK = 0
    NG = 0
    a = j - i + 1 - K
    for m in range(i, j + 1):
        if y_min <= XY[m][1] <= y_max:
            OK += 1
        else:
            NG += 1
        if OK >= K:
            return True
        if NG > a:
            return False


ans = 10 ** 20
for i in range(N - 1):
    for j in range(i + K - 1, N):
        for k in range(N):
            for l in range(N):
                if XY[k][1] < XY[l][1]:
                    if count(XY[i][0], XY[j][0], XY[k][1], XY[l][1], i, j):
                        # print ('A')
                        ans = min(ans, (XY[j][0] - XY[i][0]) * (XY[l][1] - XY[k][1]))
print (ans)

Submission status: Time Limit Exceeded

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

def count(x_min, x_max, y_min, y_max, i, j):
    OK = 0
    NG = 0
    a = j - i + 1 - K
    for m in range(i, j + 1):
        if x_min <= XY[m][0] <= x_max and y_min <= XY[m][1] <= y_max:
            OK += 1
        else:
            NG += 1
        if OK >= K:
            return True
        if NG > a:
            return False


ans = 10 ** 20
for i in range(N - 1):
    for j in range(i + 1, N):
        for k in range(N):
            for l in range(N):
                if XY[k][1] < XY[l][1] and j - i + 1 >= K:
                    if count(XY[i][0], XY[j][0], XY[k][1], XY[l][1], i, j):
                        # print ('A')
                        ans = min(ans, (XY[j][0] - XY[i][0]) * (XY[l][1] - XY[k][1]))
print (ans)

Submission status: Time Limit Exceeded

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

def count(x_min, x_max, y_min, y_max, i, j):
    cnt = 0
    for m in range(i, j + 1):
        if x_min <= XY[m][0] <= x_max and y_min <= XY[m][1] <= y_max:
            cnt += 1
    return cnt

ans = 10 ** 20
for i in range(N - 1):
    for j in range(i + 1, N):
        for k in range(N):
            for l in range(N):
                if XY[k][1] < XY[l][1] and j - i + 1 >= K:
                    if count(XY[i][0], XY[j][0], XY[k][1], XY[l][1], i, j) >= K:
                        # print ('A')
                        ans = min(ans, (XY[j][0] - XY[i][0]) * (XY[l][1] - XY[k][1]))
print (ans)

Submission status: Time Limit Exceeded

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

def count(x_min, x_max, y_min, y_max, i, j):
    cnt = 0
    for m in range(i, j + 1):
        if x_min <= XY[m][0] <= x_max and y_min <= XY[m][1] <= y_max:
            cnt += 1
    return cnt

ans = 10 ** 20
for i in range(N - 1):
    for j in range(i + 1, N):
        for k in range(N):
            for l in range(N):
                if XY[k][1] < XY[l][1]:
                    if count(XY[i][0], XY[j][0], XY[k][1], XY[l][1], i, j) >= K:
                        # print ('A')
                        ans = min(ans, (XY[j][0] - XY[i][0]) * (XY[l][1] - XY[k][1]))
print (ans)

Submission status: Time Limit Exceeded

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

def count(x_min, x_max, y_min, y_max):
    cnt = 0
    for i in range(N):
        if x_min <= XY[i][0] <= x_max and y_min <= XY[i][1] <= y_max:
            cnt += 1
    return cnt

ans = 10 ** 20
for i in range(N - 1):
    for j in range(i + 1, N):
        for k in range(N):
            for l in range(N):
                if XY[k][1] < XY[l][1]:
                    if count(XY[i][0], XY[j][0], XY[k][1], XY[l][1]) >= K:
                        # print ('A')
                        ans = min(ans, (XY[j][0] - XY[i][0]) * (XY[l][1] - XY[k][1]))
print (ans)

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
X = [0] * N
Y = [0] * N
for i in range(N):
    x, y = map(int, input().split())
    X[i] = x
    Y[i] = y

def count(x_min, x_max, y_min, y_max):
    cnt = 0
    for i in range(N):
        if x_min <= X[i] <= x_max and y_min <= Y[i] <= y_max:
            cnt += 1
    return cnt

ans = 10 ** 20
for i in range(N):
    for j in range(N):
        for k in range(N):
            for l in range(N):
                # print ('i, j , k, l = ', i, j, k, l)
                if X[i] < X[j] and Y[k] < Y[l]:
                    if count(X[i], X[j], Y[k], Y[l]) >= K:
                        # print ('A')
                        ans = min(ans, (X[j] - X[i]) * (Y[l] - Y[k]))
print (ans)

Submission status: Time Limit Exceeded

Solution code:
#D問題
N,K = map(int,input().split())
XY = [list(map(int,input().split())) for i in range(N)]

inf = float("inf")
MIN = inf
for i in range(N):
    for j in range(N):
        lx = min(XY[i][0],XY[j][0])
        rx = max(XY[i][0],XY[j][0])
        for k in range(N):
            for l in range(N):
                dy = min(XY[k][1],XY[l][1])
                uy = max(XY[k][1],XY[l][1])
                count = 0
                for m in range(N):
                    x = XY[m][0]
                    y = XY[m][1]
                    if (x >= lx and x <= rx) and (y >= dy and y <= uy):
                        count+=1
                if count >= K:
                    xx = rx-lx
                    yy = uy-dy
                    MIN = min(MIN,xx*yy)
                    
print(MIN)

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
XY = [list(map(int, input().split())) for _ in range(N)]
X, Y = zip(*XY)
X_s = sorted(X)
Y_s = sorted(Y)

r = 10**20
for xi0 in range(N):
  for xi1 in range(xi0, N):
    for yi0 in range(N):
      for yi1 in range(yi0, N):
        x0 = X_s[xi0]
        x1 = X_s[xi1]
        y0 = Y_s[yi0]
        y1 = Y_s[yi1]
        c = 0
        for x, y in XY:
          if x0 <= x <=x1 and y0 <= y <= y1:
            c += 1
        if c >= K:
          r = min(r, (x1 - x0) * (y1 - y0))
print(r)

Submission status: Time Limit Exceeded

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

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


ans = float('inf')

for lx, _ in XY:
    for rx, _ in XY:
        if lx > rx:
            continue
        for _, dy in XY:
            for _, uy in XY:
                if dy > uy:
                    continue
                count = 0
                for x,y in XY:
                    if lx <= x <= rx and dy <= y <= uy:
                        count += 1
                if count >= K:
                    ans = min(ans,(rx-lx)*(uy-dy))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int,input().split())
XY = list(list(map(int,input().split()))for i in range(N))

ans = float('inf')

for lx, _ in XY:
    for rx, _ in XY:
        if lx > rx:
            continue
        for _, dy in XY:
            for _, uy in XY:
                if dy > uy:
                    continue
                count = 0
                for x,y in XY:
                    if lx <= x <= rx and dy <= y <= uy:
                        count += 1
                if count >= K:
                    ans = min(ans,(rx-lx)*(uy-dy))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int,input().split())
XY = list(list(map(int,input().split()))for i in range(N))

ans = float('inf')

for lx, _ in XY:
    for rx, _ in XY:
        if lx < rx:
            for _, dy in XY:
                for _, uy in XY:
                    if dy < uy:
                        count = 0
                        for x,y in XY:
                            if lx <= x <= rx and dy <= y <= uy:
                                count += 1
                        if count >= K:
                            ans = min(ans,(rx-lx)*(uy-dy))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int,input().split())
XY = list(list(map(int,input().split()))for i in range(N))

ans = float('inf')
XY.sort()

for i in range(N):
    lx = XY[i][0]
    for j in range(i+1,N):
        rx = XY[j][0]
        for k in range(N):
            dy = XY[k][1]
            for l in range(N):
                uy = XY[l][1]
                hoge = 0
                for x,y in XY:
                    if lx <= x and rx >= x and uy >= y and dy <= y:
                        hoge += 1
                if hoge >= K:
                    ans = min(ans,(rx-lx)*(uy-dy))
print(ans)