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:
n,k=map(int,input().split())
xy=[list(map(int,input().split())) for i in range(n)]
x,y=[[xy[i][0],i] for i in range(n)],[[xy[i][1],i] for i in range(n)]
x.sort()
y.sort()
ans=(10**18)*5
for i1 in range(n):
    i1_sub=n-i1
    for l1 in range(i1_sub,1,-1):
        for i2 in range(n):
            i2_sub=n-i2
            for l2 in range(i2_sub,1,-1):
                x_sub1=x[i1][0]
                x_sub2=x[i1+l1-1][0]
                y_sub1=y[i2][0]
                y_sub2=y[i2+l2-1][0]
                z=[0]*n
                for i in range(n):
                    if x_sub1<=xy[i][0]<=x_sub2 and y_sub1<=xy[i][1]<=y_sub2:
                        z[i]=1
                if sum(z)>=k:
                    ans=min((x_sub2-x_sub1)*(y_sub2-y_sub1),ans)
                else:
                    break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
x,y=[[0,0] for i in range(n)],[[0,0] for i in range(n)]
xy=[list(map(int,input().split())) for i in range(n)]
for i in range(n):
    x_sub,y_sub=xy[i]
    x[i][0]=x_sub
    x[i][1]=i
    y[i][0]=y_sub
    y[i][1]=i
x.sort()
y.sort()
ans=(10**18)*5
for i1 in range(n):
    i1_sub=n-i1
    for l1 in range(i1_sub,1,-1):
        for i2 in range(n):
            i2_sub=n-i2
            for l2 in range(i2_sub,1,-1):
                x_sub1=x[i1][0]
                x_sub2=x[i1+l1-1][0]
                y_sub1=y[i2][0]
                y_sub2=y[i2+l2-1][0]
                z=[0]*n
                for i in range(n):
                    if x_sub1<=xy[i][0]<=x_sub2 and y_sub1<=xy[i][1]<=y_sub2:
                        z[i]=1
                s=0
                for i in range(n):
                    s+=z[i]
                    if s>=k:
                        ans=min((x_sub2-x_sub1)*(y_sub2-y_sub1),ans)
                        break
                else:
                    break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
x,y=[[0,0] for i in range(n)],[[0,0] for i in range(n)]
xy=[list(map(int,input().split())) for i in range(n)]
for i in range(n):
    x_sub,y_sub=xy[i]
    x[i][0]=x_sub
    x[i][1]=i
    y[i][0]=y_sub
    y[i][1]=i
x.sort()
y.sort()
ans=(10**18)*5
for i1 in range(n):
    i1_sub=n-i1
    for l1 in range(i1_sub,1,-1):
        for i2 in range(n):
            i2_sub=n-i2
            for l2 in range(i2_sub,1,-1):
                x_sub1=x[i1][0]
                x_sub2=x[i1+l1-1][0]
                y_sub1=y[i2][0]
                y_sub2=y[i2+l2-1][0]
                z=[0]*n
                for i in range(n):
                    z[i]=x_sub1<=xy[i][0]<=x_sub2 and y_sub1<=xy[i][1]<=y_sub2
                if sum(z)>=k:
                    ans=min((x_sub2-x_sub1)*(y_sub2-y_sub1),ans)
                else:
                    break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
x,y=[[0,0] for i in range(n)],[[0,0] for i in range(n)]
xy=[list(map(int,input().split())) for i in range(n)]
for i in range(n):
    x_sub,y_sub=xy[i]
    x[i][0]=x_sub
    x[i][1]=i
    y[i][0]=y_sub
    y[i][1]=i
x.sort()
y.sort()
ans=(10**18)*5
for i1 in range(n):
    i1_sub=n-i1
    for l1 in range(i1_sub,1,-1):
        for i2 in range(n):
            i2_sub=n-i2
            for l2 in range(i2_sub,1,-1):
                x_sub1=x[i1][0]
                x_sub2=x[i1+l1-1][0]
                y_sub1=y[i2][0]
                y_sub2=y[i2+l2-1][0]
                z=[0]*n
                for i in range(n):
                    if x_sub1<=xy[i][0] and xy[i][0]<=x_sub2 and y_sub1<=xy[i][1] and xy[i][1]<=y_sub2:
                        z[i]=1
                if sum(z)>=k:
                    ans=min((x_sub2-x_sub1)*(y_sub2-y_sub1),ans)
                else:
                    break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
x,y=[[0,0] for i in range(n)],[[0,0] for i in range(n)]
xy=[list(map(int,input().split())) for i in range(n)]
for i in range(n):
    x_sub,y_sub=xy[i]
    x[i][0]=x_sub
    x[i][1]=i
    y[i][0]=y_sub
    y[i][1]=i
x.sort()
y.sort()
ans=(10**18)*5
for i1 in range(n):
    i1_sub=n-i1
    for l1 in range(i1_sub,1,-1):
        for i2 in range(n):
            i2_sub=n-i2
            for l2 in range(i2_sub,1,-1):
                x_sub1=x[i1][0]
                x_sub2=x[i1+l1-1][0]
                y_sub1=y[i2][0]
                y_sub2=y[i2+l2-1][0]
                z=[0]*n
                for i in range(n):
                    if x_sub1<=xy[i][0]<=x_sub2 and y_sub1<=xy[i][1]<=y_sub2:
                        z[i]=1
                if sum(z)>=k:
                    ans=min((x_sub2-x_sub1)*(y_sub2-y_sub1),ans)
                else:
                    break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
x,y=[[0,0] for i in range(n)],[[0,0] for i in range(n)]
xy=[list(map(int,input().split())) for i in range(n)]
for i in range(n):
    x_sub,y_sub=xy[i]
    x[i][0]=x_sub
    x[i][1]=i
    y[i][0]=y_sub
    y[i][1]=i
x.sort()
y.sort()
ans=(10**18)*5
for i1 in range(n):
    i1_sub=n-i1
    for l1 in range(i1_sub,1,-1):
        for i2 in range(n):
            i2_sub=n-i2
            for l2 in range(i2_sub,1,-1):
                x_sub1=x[i1][0]
                x_sub2=x[i1+l1-1][0]
                y_sub1=y[i2][0]
                y_sub2=y[i2+l2-1][0]
                z=[0]*n
                for i in range(n):
                    if x_sub1<=xy[i][0]<=x_sub2 and y_sub1<=xy[i][1]<=y_sub2:
                        if z[i]==0:
                            z[i]=1
                if sum(z)>=k:
                    ans=min((x_sub2-x_sub1)*(y_sub2-y_sub1),ans)
                else:
                    break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
x,y=[[0,0] for i in range(n)],[[0,0] for i in range(n)]
xy=[list(map(int,input().split())) for i in range(n)]
for i in range(n):
    x_sub,y_sub=xy[i]
    x[i][0]=x_sub
    x[i][1]=i
    y[i][0]=y_sub
    y[i][1]=i
x.sort()
y.sort()
ans=(10**18)*5
for i1 in range(n):
    for l1 in range(n-i1,1,-1):
        for i2 in range(n):
            for l2 in range(n-i2,1,-1):
                x_sub1=x[i1][0]
                x_sub2=x[i1+l1-1][0]
                y_sub1=y[i2][0]
                y_sub2=y[i2+l2-1][0]
                z=[0]*n
                s=0
                for i in range(n):
                    if x_sub1<=xy[i][0]<=x_sub2 and y_sub1<=xy[i][1]<=y_sub2:
                        if z[i]==0:
                            z[i]=1
                            s+=1
                if s>=k:
                    ans=min((x_sub2-x_sub1)*(y_sub2-y_sub1),ans)
                else:
                    break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
x,y=[[0,0] for i in range(n)],[[0,0] for i in range(n)]
xy=[list(map(int,input().split())) for i in range(n)]
for i in range(n):
    x_sub,y_sub=xy[i]
    x[i][0]=x_sub
    x[i][1]=i
    y[i][0]=y_sub
    y[i][1]=i
x.sort()
y.sort()
ans=(10**18)*5
for i1 in range(n):
    for l1 in range(n-i1,1,-1):
        for i2 in range(n):
            for l2 in range(n-i2,1,-1):
                x_sub1=x[i1][0]
                x_sub2=x[i1+l1-1][0]
                y_sub1=y[i2][0]
                y_sub2=y[i2+l2-1][0]
                z=[0]*n
                for i in range(n):
                    if x_sub1<=xy[i][0]<=x_sub2:
                        if y_sub1<=xy[i][1]<=y_sub2:
                            z[i]=1
                if sum(z)>=k:
                    ans=min((x_sub2-x_sub1)*(y_sub2-y_sub1),ans)
                else:
                    break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
x,y=[[0,0] for i in range(n)],[[0,0] for i in range(n)]
xy=[list(map(int,input().split())) for i in range(n)]
for i in range(n):
    x_sub,y_sub=xy[i]
    x[i][0]=x_sub
    x[i][1]=i
    y[i][0]=y_sub
    y[i][1]=i
x.sort()
y.sort()
w=[[(i1,l1) for l1 in range(n-i1,1,-1)] for i1 in range(n)]
v=[[(i2,l2) for l2 in range(n-i2,1,-1)] for i2 in range(n)]
#print(w)
#print(v)
ans=(10**18)*5
for w_sub in w:
    for v_sub in v:
        for i1l1 in w_sub:
            for i2l2 in v_sub:
                i1,l1=i1l1
                i2,l2=i2l2
                if l1*l2<k:
                    continue
                x_sub1=x[i1][0]
                x_sub2=x[i1+l1-1][0]
                y_sub1=y[i2][0]
                y_sub2=y[i2+l2-1][0]
                z=[0]*n
                for i in range(n):
                    if x_sub1<=xy[i][0]<=x_sub2 and y_sub1<=xy[i][1]<=y_sub2:
                        z[i]=1
                if sum(z)>=k:
                    ans=min((x_sub2-x_sub1)*(y_sub2-y_sub1),ans)
                else:
                    break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
x,y=[[0,0] for i in range(n)],[[0,0] for i in range(n)]
xy=[list(map(int,input().split())) for i in range(n)]
for i in range(n):
    x_sub,y_sub=xy[i]
    x[i][0]=x_sub
    x[i][1]=i
    y[i][0]=y_sub
    y[i][1]=i
x.sort()
y.sort()
w=[[(i1,l1) for l1 in range(n-i1,1,-1)] for i1 in range(n)]
v=[[(i2,l2) for l2 in range(n-i2,1,-1)] for i2 in range(n)]
#print(w)
#print(v)
ans=(10**18)*5
for w_sub in w:
    for v_sub in v:
        for i1l1 in w_sub:
            for i2l2 in v_sub:
                i1,l1=i1l1
                i2,l2=i2l2
                if l1*l2<k:
                    continue
                x_sub1=x[i1][0]
                x_sub2=x[i1+l1-1][0]
                y_sub1=y[i2][0]
                y_sub2=y[i2+l2-1][0]
                z=[0]*n
                for i in range(n):
                    if x_sub1<=xy[i][0]<=x_sub2 and y_sub1<=xy[i][1]<=y_sub2:
                        z[i]=1
                if sum(z)>=k:
                    ans=min((x_sub2-x_sub1)*(y_sub2-y_sub1),ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
x,y=[[0,0] for i in range(n)],[[0,0] for i in range(n)]
xy=[list(map(int,input().split())) for i in range(n)]
for i in range(n):
    x_sub,y_sub=xy[i]
    x[i][0]=x_sub
    x[i][1]=i
    y[i][0]=y_sub
    y[i][1]=i
x.sort()
y.sort()
ans=(10**18)*5
for i1 in range(n):
    for l1 in range(n-i1,1,-1):
        for i2 in range(n):
            for l2 in range(n-i2,1,-1):
                if l1*l2<k:
                    break
                x_sub1=x[i1][0]
                x_sub2=x[i1+l1-1][0]
                y_sub1=y[i2][0]
                y_sub2=y[i2+l2-1][0]
                z=[0]*n
                for i in range(n):
                    if x_sub1<=xy[i][0]<=x_sub2 and y_sub1<=xy[i][1]<=y_sub2:
                        z[i]=1
                if sum(z)>=k:
                    ans=min((x_sub2-x_sub1)*(y_sub2-y_sub1),ans)
                else:
                    break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
x,y=[[0,0] for i in range(n)],[[0,0] for i in range(n)]
xy=[list(map(int,input().split())) for i in range(n)]
for i in range(n):
    x_sub,y_sub=xy[i]
    x[i][0]=x_sub
    x[i][1]=i
    y[i][0]=y_sub
    y[i][1]=i
x.sort()
y.sort()
w=[(i1,l1) for i1 in range(n) for l1 in range(n-i1,1,-1)]
v=[(i2,l2) for i2 in range(n) for l2 in range(n-i2,1,-1)]
#print(w)
#print(v)
ans=(10**18)*5
for w_sub in w:
    for v_sub in v:
        i1,l1=w_sub
        i2,l2=v_sub
        if l1*l2<k:
            continue
        x_sub1=x[i1][0]
        x_sub2=x[i1+l1-1][0]
        y_sub1=y[i2][0]
        y_sub2=y[i2+l2-1][0]
        z=[0]*n
        for i in range(n):
            if x_sub1<=xy[i][0]<=x_sub2 and y_sub1<=xy[i][1]<=y_sub2:
                z[i]=1
        if sum(z)>=k:
            ans=min((x_sub2-x_sub1)*(y_sub2-y_sub1),ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
x,y=[[0,0] for i in range(n)],[[0,0] for i in range(n)]
xy=[list(map(int,input().split())) for i in range(n)]
for i in range(n):
    x_sub,y_sub=xy[i]
    x[i][0]=x_sub
    x[i][1]=i
    y[i][0]=y_sub
    y[i][1]=i
x.sort()
y.sort()
w=[(i1,l1) for i1 in range(n) for l1 in range(n-i1,1,-1)]
v=[(i2,l2) for i2 in range(n) for l2 in range(n-i2,1,-1)]
#print(w)
#print(v)
ans=(10**18)*5
for w_sub in w:
    for v_sub in v:
        i1,l1=w_sub
        i2,l2=v_sub
        x_sub1=x[i1][0]
        x_sub2=x[i1+l1-1][0]
        y_sub1=y[i2][0]
        y_sub2=y[i2+l2-1][0]
        z=[0]*n
        for i in range(n):
            if x_sub1<=xy[i][0]<=x_sub2 and y_sub1<=xy[i][1]<=y_sub2:
                z[i]=1
        if sum(z)>=k:
            ans=min((x_sub2-x_sub1)*(y_sub2-y_sub1),ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
x,y=[[0,0] for i in range(n)],[[0,0] for i in range(n)]
xy=[list(map(int,input().split())) for i in range(n)]
for i in range(n):
    x_sub,y_sub=xy[i]
    x[i][0]=x_sub
    x[i][1]=i
    y[i][0]=y_sub
    y[i][1]=i
x.sort()
y.sort()
ans=(10**18)*5
for i1 in range(n):
    for l1 in range(n-i1,1,-1):
        for i2 in range(n):
            for l2 in range(n-i2,1,-1):
                x_sub1=x[i1][0]
                x_sub2=x[i1+l1-1][0]
                y_sub1=y[i2][0]
                y_sub2=y[i2+l2-1][0]
                z=[0]*n
                for i in range(n):
                    if x_sub1<=xy[i][0]<=x_sub2 and y_sub1<=xy[i][1]<=y_sub2:
                        z[i]=1
                if sum(z)>=k:
                    ans=min((x_sub2-x_sub1)*(y_sub2-y_sub1),ans)
                else:
                    break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
x,y=[[0,0] for i in range(n)],[[0,0] for i in range(n)]
xy=[list(map(int,input().split())) for i in range(n)]
for i in range(n):
    x_sub,y_sub=xy[i]
    x[i][0]=x_sub
    x[i][1]=i
    y[i][0]=y_sub
    y[i][1]=i
x.sort(key=lambda z:z[0])
y.sort(key=lambda z:z[0])
ans=(10**18)*5
ra=range(n)
for i1 in ra:
    for l1 in range(n-i1,0,-1):
        for i2 in ra:
            for l2 in range(n-i2,0,-1):
                if l1*l2<k:
                    break
                z=[0]*n
                for i in range(i1,i1+l1):
                    l=x[i][1]
                    z[l]=1
                for i in range(i2,i2+l2):
                    l=y[i][1]
                    z[l]=1
                if sum(z)>=k:
                    x_sub1,y_sub1=10**9+1,10**9+1
                    x_sub2,y_sub2=-10**9-1,-10**9-1
                    for i in range(n):
                        if z[i]==1:
                            x_sub1=min(xy[i][0],x_sub1)
                            x_sub2=max(xy[i][0],x_sub2)
                            y_sub1=min(xy[i][1],y_sub1)
                            y_sub2=max(xy[i][1],y_sub2)
                    ans=min((x_sub2-x_sub1)*(y_sub2-y_sub1),ans)
                else:
                    break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
x,y=[[0,0] for i in range(n)],[[0,0] for i in range(n)]
xy=[list(map(int,input().split())) for i in range(n)]
for i in range(n):
    x_sub,y_sub=xy[i]
    x[i][0]=x_sub
    x[i][1]=i
    y[i][0]=y_sub
    y[i][1]=i
x.sort(key=lambda z:z[0])
y.sort(key=lambda z:z[0])
ans=(10**18)*5
for i1 in range(n):
    for l1 in range(n-i1,0,-1):
        for i2 in range(n):
            for l2 in range(n-i2,0,-1):
                x_sub1,y_sub1=10**9+1,10**9+1
                x_sub2,y_sub2=-10**9-1,-10**9-1
                z=[0]*n
                for i in range(i1,i1+l1):
                    l=x[i][1]
                    x_sub1=min(xy[l][0],x_sub1)
                    x_sub2=max(xy[l][0],x_sub2)
                    y_sub1=min(xy[l][1],y_sub1)
                    y_sub2=max(xy[l][1],y_sub2)
                    z[l]=1
                for i in range(i2,i2+l2):
                    l=y[i][1]
                    x_sub1=min(xy[l][0],x_sub1)
                    x_sub2=max(xy[l][0],x_sub2)
                    y_sub1=min(xy[l][1],y_sub1)
                    y_sub2=max(xy[l][1],y_sub2)
                    z[l]=1
                if sum(z)>=k:
                    ans=min((x_sub2-x_sub1)*(y_sub2-y_sub1),ans)
                else:
                    break

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
x,y=[[0,0] for i in range(n)],[[0,0] for i in range(n)]
xy=[list(map(int,input().split())) for i in range(n)]
for i in range(n):
    x_sub,y_sub=xy[i]
    x[i][0]=x_sub
    x[i][1]=i
    y[i][0]=y_sub
    y[i][1]=i
x.sort(key=lambda z:z[0])
y.sort(key=lambda z:z[0])
ans=(10**18)*5
for i1 in range(n-1):
    for i2 in range(i1+1,n):
        for j1 in range(n-1):
            for j2 in range(j1+1,n):
                x_sub1,y_sub1=10**9+1,10**9+1
                x_sub2,y_sub2=-10**9-1,-10**9-1
                z=[0]*n
                for i in range(i1,i2+1):
                    l=x[i][1]
                    x_sub1=min(xy[l][0],x_sub1)
                    x_sub2=max(xy[l][0],x_sub2)
                    y_sub1=min(xy[l][1],y_sub1)
                    y_sub2=max(xy[l][1],y_sub2)
                    z[l]=1
                for i in range(j1,j2+1):
                    l=y[i][1]
                    x_sub1=min(xy[l][0],x_sub1)
                    x_sub2=max(xy[l][0],x_sub2)
                    y_sub1=min(xy[l][1],y_sub1)
                    y_sub2=max(xy[l][1],y_sub2)
                    z[l]=1
                if sum(z)>=k:
                    ans=min((x_sub2-x_sub1)*(y_sub2-y_sub1),ans)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    import itertools
    n,k=map(int,input().split())
    xy=[list(map(int,input().split())) for i in range(n)]
    t=[i for i in range(n)]
    s=list(itertools.permutations(t,k))
    #print(s)
    l=len(s)
    inf=10000000000
    x_min=inf
    y_min=inf
    x_max=-inf
    y_max=-inf
    for i in range(n):
        x,y=xy[i]
        if x<x_min:x_min=x
        if y<y_min:y_min=y
        if x>x_max:x_max=x
        if y>y_max:y_max=y
    area=(x_max-x_min)*(y_max-y_min)
    #print(area)
    for i in range(l):
        x_min=inf
        y_min=inf
        x_max=-inf
        y_max=-inf
        for j in range(k):
            x,y=xy[s[i][j]]
            if x<x_min:x_min=x
            if y<y_min:y_min=y
            if x>x_max:x_max=x
            if y>y_max:y_max=y
        #print(area)
        area=min((x_max-x_min)*(y_max-y_min),area)
    print(area)
main()

Submission status: Time Limit Exceeded

Solution code:
import itertools
n,k=map(int,input().split())
xy=[list(map(int,input().split())) for i in range(n)]
t=[i for i in range(n)]
s=list(itertools.permutations(t,k))
#print(s)
l=len(s)
inf=10000000000
x_min=inf
y_min=inf
x_max=-inf
y_max=-inf
for i in range(n):
    x,y=xy[i]
    if x<x_min:x_min=x
    if y<y_min:y_min=y
    if x>x_max:x_max=x
    if y>y_max:y_max=y
area=(x_max-x_min)*(y_max-y_min)
#print(area)
for i in range(l):
    x_min=inf
    y_min=inf
    x_max=-inf
    y_max=-inf
    for j in range(k):
        x,y=xy[s[i][j]]
        if x<x_min:x_min=x
        if y<y_min:y_min=y
        if x>x_max:x_max=x
        if y>y_max:y_max=y
    #print(area)
    area=min((x_max-x_min)*(y_max-y_min),area)
print(area)

Submission status: Time Limit Exceeded

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

Mlst=set()

if N>=2:
    for s1 in range(N-1):
        for s2 in range(s1,N):
            x1,y1=XY[s1]
            x2,y2=XY[s2]
            x1,x2=min(x1,x2),max(x1,x2)
            y1,y2=min(y1,y2),max(y1,y2)
            if sum([x1<=X<=x2 and y1<=Y<=y2 for X,Y in XY])>=K:
                Mlst.add((y2-y1)*(x2-x1))
if N>=3:
    for s1 in range(N-2):
        for s2 in range(s1,N-1):
            for s3 in range(s2,N):
                x1,y1=XY[s1]
                x2,y2=XY[s2]
                x3,y3=XY[s3]
                x1,x2=min(x1,x2,x3),max(x1,x2,x3)
                y1,y2=min(y1,y2,y3),max(y1,y2,y3)
                if sum([x1<=X<=x2 and y1<=Y<=y2 for X,Y in XY])>=K:
                    Mlst.add((y2-y1)*(x2-x1))
if N>=4:
    for s1 in range(N-3):
        for s2 in range(s1,N-2):
            for s3 in range(s2,N-1):
                for s4 in range(s3,N):
                    x1,y1=XY[s1]
                    x2,y2=XY[s2]
                    x3,y3=XY[s3]
                    x4,y4=XY[s4]
                    x1,x2=min(x1,x2,x3,x4),max(x1,x2,x3,x4)
                    y1,y2=min(y1,y2,y3,y4),max(y1,y2,y3,y4)
                    if sum([x1<=X<=x2 and y1<=Y<=y2 for X,Y in XY])>=K:
                        Mlst.add((y2-y1)*(x2-x1))
print(min(Mlst))

Submission status: Time Limit Exceeded

Solution code:
n,K=map(int,input().split())
lists=[]
for i in range(n):
    x,y=map(int,input().split())
    lists.append((x,y))
anslist=[]
for i in range(n):
    for j in range(i+1,n):
        for k in range(n):
            for l in range(k+1,n):       
                a=lists[i][0]
                b=lists[j][0]
                c=lists[k][1]
                d=lists[l][1]
                counter=0
                for s in range(n):
                    p,q=lists[s][0],lists[s][1]
                    if min(a,b)<=p<=max(a,b) and min(d,c)<=q<=max(c,d):
                        counter+=1
                    if counter>=K:
                        anslist.append(abs(a-b)*abs(c-d))
print(min(anslist))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
N, K = map(int, input().split(' '))
points = [list(map(int, input().split(' '))) for i in range(N)]

X = list(set([x for x, y in points]))
Y = list(set([y for x, y in points]))


ans = float('inf')
import itertools
all_indices = list(range(N))
for part_x in itertools.combinations(X, 2):
    for part_y in itertools.combinations(Y, 2):
        max_x = max(part_x)
        min_x = min(part_x)
        max_y = max(part_y)
        min_y = min(part_y)

        m = (max_x - min_x) * (max_y - min_y)
        internal_points = [(x, y) for x, y in points if min_x <= x <= max_x and min_y <= y <= max_y]
        if len(internal_points) >= K:
            ans = min(ans, m)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split())
x = []
y = []
for i in range(n):
    a,b = map(int,input().split())
    x.append(a)
    y.append(b)
ans = 10 ** 40
for i in range(n):
    for j in range(n):
        for l in range(n):
            for h in range(n):
                lx = min(x[i],x[j])
                rx = max(x[i],x[j])
                uy = max(y[l],y[h])
                dy = min(y[l],y[h])
                cnt = 0
                for ii in range(n):
                    if lx <= x[ii] <= rx and dy <= y[ii] <= uy:
                        cnt += 1
                if cnt >= k:
                    ans = min(ans,(rx-lx)*(uy-dy))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split())
x = []
y = []
for i in range(n):
	a,b = map(int,input().split())
	x.append(a)
	y.append(b)
ans = 10 ** 100
for j in range(n):
	for f in range(n):
		for h in range(n):
			for g in range(n):
				cou = 0
				for t in range(n):
					if x[j] <= x[t] <= x[f] and y[h] <= y[t] <= y[g]:
						cou += 1
				if cou >= k:
					ans = min(ans,abs(x[j] - x[f]) * abs(y[h] - y[g]))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, atan, degrees
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, K = MAP()
xy = [LIST() for _ in range(N)]
X = sorted([x[0] for x in xy])
Y = sorted([x[1] for x in xy])

ans = INF
for p in combinations(X, 2):
	x_min = p[0]
	x_max = p[1]
	for q in combinations(Y, 2):
		y_min = q[0]
		y_max = q[1]
		
		cnt = 0
		for x, y in xy:
			if x_min <= x <= x_max and y_min <= y <= y_max:
				cnt += 1
		if cnt >= K:
			ans = min(ans, (x_max-x_min)*(y_max-y_min))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
graph = []
Y = []
X = []
for _ in range(n):
    x, y = map(int, input().split())
    graph.append([x, y])
    Y.append(y)
    X.append(x)

Y.sort()
X.sort()
ans = []
for sx in range(n):
    for ex in range(n-1, sx, -1):
        for sy in range(n):
            for ey in range(n-1, sy, -1):
                x1, x2, y1, y2 = X[sx], X[ex], Y[sy], Y[ey]
                count = len([True for x, y in graph if x1 <= x <= x2 and y1 <= y <= y2])
                if count >= k:
                    ans.append((x2-x1)*(y2-y1))
                else:
                    break

print(min(ans))

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
ps = []
x = []
y = []
for _ in range(n):
    x_i, y_i = map(int, input().split())
    ps.append([x_i, y_i])
    x.append(x_i)
    y.append(y_i)

x.sort()
y.sort()

ans = (x[-1] - x[0]) * (y[-1] - y[0])

for xi in range(n):
    for xj in range(xi+1, n):
        for yi in range(n):
            for yj in range(yi+1, n):
                num = 0
                lx = x[xi]
                rx = x[xj]
                by = y[yi]
                uy = y[yj]

                for p in ps:
                    if lx <= p[0] and p[0] <= rx and by <= p[1] and p[1] <= uy:
                        num += 1
                if num >= k:
                    ans = min(ans, (rx - lx) * (uy - by))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#n,kが小さい
#xi,yi全て試す

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

p = []
x = []
y = []
for i in range(n):
    xi,yi = map(int, input().split( ))
    p.append((xi,yi))
    x.append(xi)
    y.append(yi)

y = list(set(y))
x = list(set(x))
x.sort()
y.sort()
lx = len(x)
ly = len(y)
ans = 10**20
for ix in range(lx):
    for jx in range(i):
        for iy in range(ly):
            for jy in range(iy):
                cnt = 0
                for xk,yk in p:
                    if x[ix]>= xk and xk>=x[jx] and y[iy]>=yk and yk>=y[jy]:
                        cnt += 1
                if cnt >= k:
                    ans = min(ans, (x[ix]-x[jx])*(y[iy]-y[jy]))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
# 20億^2で10^18を超えるので19乗で
INF = 10 ** 19
MOD = 10 ** 9 + 7

N, K = MAP()
XY = []
for i in range(N):
    x, y = MAP()
    XY.append((x, y))

ans = INF
# 4点組み合わせ全部試す
for i in range(N):
    x1, y1 = XY[i]
    for j in range(i, N):
        x2, y2 = XY[j]
        for k in range(j, N):
            x3, y3 = XY[k]
            for l in range(k, N):
                x4, y4 = XY[l]
                xl, xr = min(x1, x2, x3, x4), max(x1, x2, x3, x4)
                yl, yr = min(y1, y2, y3, y4), max(y1, y2, y3, y4)
                # 4点の内側にいくつ点があるか数える
                cnt = 0
                for x5, y5 in XY:
                    if xl <= x5 <= xr and yl <= y5 <= yr:
                        cnt += 1
                if cnt >= K:
                    ans = min(ans, (xr-xl) * (yr-yl))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
# 20億^2で10^18を超えるので19乗で
INF = 10 ** 19
MOD = 10 ** 9 + 7

N, K = MAP()
XY = []
for i in range(N):
    x, y = MAP()
    XY.append((x, y))

ans = INF
# 4点組み合わせ全部試す
for i in range(N):
    x1, y1 = XY[i]
    for j in range(i, N):
        x2, y2 = XY[j]
        for k in range(j, N):
            x3, y3 = XY[k]
            for l in range(k, N):
                x4, y4 = XY[l]
                xl, xr = min(x1, x2, x3, x4), max(x1, x2, x3, x4)
                yl, yr = min(y1, y2, y3, y4), max(y1, y2, y3, y4)
                # 4点の内側にいくつ点があるか数える
                k = 0
                for x5, y5 in XY:
                    if xl <= x5 <= xr and yl <= y5 <= yr:
                        k += 1
                if k >= K:
                    ans = min(ans, (xr-xl) * (yr-yl))
print(ans)