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

N, K = map(int, input().split())
point = [tuple(map(int, input().split())) for i in range(N)]

ans = float('inf')

for i, j, k, l in itertools.product(point, repeat=4):
    x1, x2, y1, y2 = i[0], j[0], k[1], l[1]
    if x2 <= x1 or y2 <= y1:
        continue
    print(x1, x2, y1, y2)
    count = 0
    for p in point:
        if x1 <= p[0] <= x2 and y1 <= p[1] <= y2:
            count += 1
    if count >= K:
        ans = min((x2-x1) * (y2-y1), ans)

print(ans)

Submission status: Wrong Answer

Solution code:
N,K = map(int, raw_input().split(" "))

points = []
pointsx = []
pointsy = []

smin = 0

for i in range(N):
    x,y = map(int, raw_input().split(" "))
    pointsx.append(x)
    pointsy.append(y)

spx = sorted(pointsx)

for i in range(N-K+1):
    for h in range(N-K-i+1):
        yneed = []
        for k in range(N):
            if pointsx[k]>=spx[i] and pointsx[k]<=spx[i+K+h-1]:
                yneed.append(pointsy[k])
        spy = sorted(yneed)
        ylength = 0
        xlength = spx[i+K+h-1]-spx[i]
        for k in range(len(spy) - K + 1):
            if ylength < spy[k+K-1]-spy[k]: ylength = spy[k+K-1]-spy[k]
        if smin == 0: smin = ylength * xlength
        elif smin > ylength * xlength:
            smin = ylength * xlength
            #print smin


print smin

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
point=[]
ans=10**18

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

    
for i in range(N-1):
    for j in range(i+1,N):

        count=0

        for k in point:

            if (k[0]-point[i][0])*(k[0]-point[j][0]) <=0 and (k[1]-point[i][1])*(k[1]-point[j][1]) <= 0:
                count += 1

    if count >= K:
        ans = min(ans,abs(point[i][0]-point[j][0])*abs(point[i][1]-point[j][1]))


print(ans)

Submission status: Wrong Answer

Solution code:
N,K = map(int, raw_input().split(" "))

points = []
pointsx = []
pointsy = []

smin = 0

for i in range(N):
    x,y = map(int, raw_input().split(" "))
    pointsx.append(x)
    pointsy.append(y)

spx = sorted(pointsx)

for i in range(N-K+1):
    for h in range(N-K-i+1):
        yneed = []
        for k in range(N):
            if pointsx[k]>=spx[i] and pointsx[k]<=spx[i+K+h-1]:
                yneed.append(pointsy[k])
        spy = sorted(yneed)
        ylength = 0
        xlength = spx[i+K+h-1]-spx[i]
        for k in range(len(spy) - K + 1):
            if ylength < spy[k+K-1]-spy[k]: ylength = spy[k+K-1]-spy[k]
        if smin == 0: smin = ylength * xlength
        elif smin > ylength * xlength:
            smin = ylength * xlength
            print smin


print smin

Submission status: Wrong Answer

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

sx = sorted(ps) #xの順にソート
nx = list(enumerate(sx)) #それぞれの点に番号をつける0〜
ans = 5e18

print(nx[:n - k + 1])
for l, (x1, y1) in nx[:n - k + 1]: #4つ中3つなら先頭2つまで見ればいい
    for r, (x2, y2) in nx[l + k - 1:]: #0番目を見てる時は2番目以降、
        dx = x2 - x1
        sy = sorted(y for x, y in sx[l:r + 1])

        for y3, y4 in zip(sy, sy[k - 1:]):
            print(y3,y4)
            if y3 <= y1 and y2 <= y4:
                ans = min(ans, dx * (y4 - y3))
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python



def main():
    N, K = map(int, input().split(" "))

    xary = []
    yary = []
    for _ in range(N):
        x, y = map(int, input().split(" "))
        xary.append(x)
        yary.append(y)

    xary.sort()
    yary.sort()

    ans = (xary[N - 1] - xary[0]) * (yary[N - 1] - yary[0])

    for xi in range(len(xary)):
        for xj in range(xi + 1, len(xary)):
            for yi in range(len(yary)):
                for yj in range(yi + 1, len(yary)):
                    lx = xary[xi]
                    rx = xary[xj]
                    by = yary[yi]
                    uy = yary[yj]

                    num_k = 0
                    for i in range(N):
                        if lx <= xary[i] and xary[i] <= rx and uy >= yary[i] and yary[i] >= by:
                            num_k += 1
                    if num_k >= K:
                        area = (rx - lx) * (uy - by)
                        ans = min([ans, area])
    print(ans)
       

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
area=19000000000000000000
def check(x1,y1,x2,y2,x3,y3,x4,y4,k):
    global area
    atot = abs((x1-x3)*(y1-y3))
    cnt=0
    for i,j in a:
        a1=abs((x1-i)*(y1-j))
        a2 = abs((x2 - i) * (y2 - j))
        a3 = abs((x3 - i) * (y3 - j))
        a4 = abs((x4 - i) * (y4 - j))
        if a1+a2+a3+a4==atot:
            cnt+=1
    if cnt>=k:
        area=min(area,atot)
n,k1=[int(i) for i in input().split()]
a=[]

for _ in range(n):
    a.append([int(i) for i in input().split()])
for i in range(n):
    for j in range(n):
        la=0
        check(a[i][0],a[i][1],a[j][0],a[i][1],a[j][0],a[j][1],a[i][0],a[j][1],k1)

for i in range(n):
    for j in range(n):
        la=0
        for k in range(n):
            x1=min(a[i][0],a[j][0],a[k][0])
            x2=max(a[i][0],a[j][0],a[k][0])
            y1=min(a[i][1],a[j][1],a[k][1])
            y2=max(a[i][1],a[j][1],a[k][1])

            check(x1,y1,x2,y1,x2,y2,x1,y2,k1)


print(area)

Submission status: Wrong Answer

Solution code:
area=19000000000000000000
def check(x1,y1,x2,y2,x3,y3,x4,y4,k):
    global area
    atot = abs((x1-x3)*(y1-y3))
    cnt=0
    for i,j in a:
        a1=abs((x1-i)*(y1-j))
        a2 = abs((x2 - i) * (y2 - j))
        a3 = abs((x3 - i) * (y3 - j))
        a4 = abs((x4 - i) * (y4 - j))
        if a1+a2+a3+a4==atot:
            cnt+=1
    if cnt>=k:
        area=min(area,atot)
n,k=[int(i) for i in input().split()]
a=[]

for _ in range(n):
    a.append([int(i) for i in input().split()])
for i in range(n):
    for j in range(n):
        la=0
        check(a[i][0],a[i][1],a[j][0],a[i][1],a[j][0],a[j][1],a[i][0],a[j][1],k)
print(area)

Submission status: Wrong Answer

Solution code:
area=19000000000000000000
def check(x1,y1,x2,y2,x3,y3,x4,y4,k):
    global area
    atot = abs((x1-x3)*(y1-y3))
    cnt=0
    for i,j in a:
        a1=abs((x1-i)*(y1-j))
        a2 = abs((x2 - i) * (y2 - j))
        a3 = abs((x3 - i) * (y3 - j))
        a4 = abs((x4 - i) * (y4 - j))
        if a1+a2+a3+a4==atot:
            cnt+=1
    if cnt>=k:
        area=min(area,atot)
n,k=[int(i) for i in input().split()]
a=[]

for _ in range(n):
    a.append([int(i) for i in input().split()])
for i in range(n):
    for j in range(n):
        la=0
        check(a[i][0],a[i][1],a[j][0],a[i][1],a[j][0],a[j][1],a[i][0],a[j][1],k)
print("1")

Submission status: Wrong Answer

Solution code:
area=19000000000000000000
def check(x1,y1,x2,y2,x3,y3,x4,y4,k):
    global area
    atot = abs((x1-x3)*(y1-y3))
    cnt=0
    for i,j in a:
        a1=abs((x1-i)*(y1-j))
        a2 = abs((x2 - i) * (y2 - j))
        a3 = abs((x3 - i) * (y3 - j))
        a4 = abs((x4 - i) * (y4 - j))
        if a1+a2+a3+a4==atot:
            cnt+=1
    if cnt>=k:
        area=min(area,atot)
n,k=[int(i) for i in input().split()]
a=[]

for _ in range(n):
    a.append([int(i) for i in input().split()])
for i in range(n):
    for j in range(n):
        la=0
        check(a[i][0],a[i][1],a[j][0],a[i][1],a[j][0],a[j][1],a[i][0],a[j][1],k)
print("0")

Submission status: Wrong Answer

Solution code:
def count(x1,y1,x2,y2):
    res = 0
    for i in range(N):
        s1 = x[i]
        s2 = y[i]
        if x1 <= s1 <= x2 and y1 <= s2 <= y2:
            res += 1
    return res 

    
N,K = map(int,input().split())
x = []
y = []
y_dict = {}
for i in range(N):
    a,b = map(int,input().split())
    x.append(a)
    y.append(b)
    y_dict[a] = (b)

x = sorted(x)
y = sorted(y)
ans = 10**20

for i in range(len(x)-1):#長方系の左の辺をx座標を取得し,固定
    for j in range(i+1,len(x)):#長方形の右の辺のx座標を取得し,固定

        y_list = []

        for k in range(i,j+1):#区間内にある点のy座標を取得しy_listに入れる
            y_list.append(y_dict[x[k]])
        
        y_list = sorted(y_list)
        

        if 2 <= len(y_list):
            for l in range(len(y_list)-1):#yの大きい値から順に組み合わせを試す
                for m in range(l+1,len(y_list)):
                
                    x1 = x[i]
                    y1 = y_list[l]
                    x2 = x[j]
                    y2 = y_list[m]
                    point = count(x1,y1,x2,y2)#区間内の点の数

                    if K <= point :
                        ans = min(ans,(x2-x1)*(y2-y1))    

                
print(ans)

Submission status: Wrong Answer

Solution code:
def count(x1,y1,x2,y2):
    res = 0
    for i in range(N):
        s1 = x[i]
        s2 = y[i]
        if x1 <= s1 <= x2 and y1 <= s2 <= y2:
               res += 1
               
    return res 

    
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)

x = sorted(x)
y = sorted(y)
ans = 10**20
for i in range(len(x)-1):
    #長方系の左の辺をx座標を取得し,固定
    for j in range(i+1,len(x)):
        #長方形の右の辺のx座標を取得し固定
        for k in range(len(y)-1):
            #長方形の下の辺のy座標を取得し固定
            for l in range(k+1,len(y)):
                #長方形の上の辺のy座標を取得し固定
                x1 = x[i]
                y1 = y[k]
                x2 = x[j]
                y2 = y[l]
                point = count(x1,y1,x2,y2)
                if K <= point :
                    ans = min(ans,abs(x2-x1)*abs(y2-y1))            
                                

                
print(ans)

Submission status: Wrong Answer

Solution code:
def count(x1,y1,x2,y2):
    res = 0
    for i in range(N):
        s1 = x[i]
        s2 = y[i]
        if x1 <= s1 <= x2 and y1 <= s2 <= y2:
               res += 1
               
    return res 

    
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)

x = sorted(x)
y = sorted(y)
ans = 10**20
for i in range(len(x)-1):
    #長方系の左の辺をx座標を取得し,固定
    for j in range(i+1,len(x)):
        #長方形の右の辺のx座標を取得し固定
        for k in range(len(y)-1):
            #長方形の下の辺のy座標を取得し固定
            for l in range(k+1,len(y)):
                #長方形の上の辺のy座標を取得し固定
                x1 = x[i]
                y1 = y[k]
                x2 = x[j]
                y2 = y[l]
                point = count(x1,y1,x2,y2)
                if point <= K :
                    ans = min(ans,abs(x2-x1)*abs(y2-y1))            
                                

                
print(ans)

Submission status: Wrong Answer

Solution code:
def count(x1,y1,x2,y2):
    res = 0
    for i in range(N):
        s1 = x[i]
        s2 = y[i]
        if x1 <= s1 <= x2 and y1 <= s2 <= y2:
               res += 1
               
    return res 

    
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)

x = sorted(x)
y = sorted(y)
ans = 10**20
for i in range(len(x)-1):
    #長方系の左の辺をx座標を取得し,固定
    for j in range(i+1,len(x)):
        #長方形の右の辺のx座標を取得し固定
        for k in range(len(y)-1):
            #長方形の下の辺のy座標を取得し固定
            for l in range(k+1,len(y)):
                #長方形の上の辺のy座標を取得し固定
                x1 = x[i]
                y1 = y[k]
                x2 = x[j]
                y2 = y[l]
                point = count(x1,y1,x2,y2)
                if point == K :
                    ans = min(ans,abs(x2-x1)*abs(y2-y1))            

                                

                
print(ans)

Submission status: Wrong Answer

Solution code:
def count(x1,y1,x2,y2):
    res = 0
    for i in range(N):
        s1 = x[i]
        s2 = y[i]
        if x1 <= s1 <= x2 and y1 <= s2 <= y2:
               res += 1
    return res 

    
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)

x = sorted(x)
y = sorted(y)
ans = 10**20
for i in range(len(x)-1):
    #長方系の左の辺をx座標を取得し,固定
    for j in range(i+1,len(x)):
        #長方形の右の辺のx座標を取得し固定
        for k in range(len(y)-1):
            #長方形の下の辺のy座標を取得し固定
            for l in range(k+1,len(y)):
                #長方形の上の辺のy座標を取得し固定
                x1 = x[i]
                y1 = y[k]
                x2 = x[j]
                y2 = y[l]
                
                if count(x1,y1,x2,y2) == K and x2-x1 != 0 and y2 - y1 != 0:
                    ans = min(ans,(x2-x1)*(y2-y1))

                                
                
print(ans)

Submission status: Wrong Answer

Solution code:
def count(x1,y1,x2,y2):
    res = 0
    for i in range(N):
        s1 = x[i]
        s2 = y[i]
        if x1 <= s1 <= x2 and y1 <= s2 <= y2:
               res += 1
    return res 

    
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)

x = sorted(x)
y = sorted(y)
ans = 10**50
for i in range(len(x)-1):
    #長方系の左の辺をx座標を取得し,固定
    for j in range(i+1,len(x)):
        #長方形の右の辺のx座標を取得し固定
        for k in range(len(y)-1):
            #長方形の下の辺のy座標を取得し固定
            for l in range(k+1,len(y)):
                #長方形の上の辺のy座標を取得し固定
                x1 = x[i]
                y1 = y[k]
                x2 = x[j]
                y2 = y[l]
                if count(x1,y1,x2,y2) == K:
                    ans = min(ans,(x2-x1)*(y2-y1))
                    break
                
print(ans)

Submission status: Wrong Answer

Solution code:
def count(x1,y1,x2,y2):
    res = 0
    for i in range(N):
        s1 = x[i]
        s2 = y[i]
        if x1 <= s1 <= x2 and y1 <= s2 <= y2:
               res += 1
    return res 

    
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)

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

ans = 10**50
for i in range(len(x)-1):
    #長方系の左の辺をx座標を取得し,固定
    for j in range(i+1,len(x)):
        #長方形の右の辺のx座標を取得し固定
        for k in range(len(y)-1):
            #長方形の下の辺のy座標を取得し固定
            for l in range(k+1,len(y)):
                #長方形の上の辺のy座標を取得し固定
                x1 = x[i]
                y1 = y[k]
                x2 = x[j]
                y2 = y[l]

                if count(x1,y1,x2,y2) == K:
                    ans = min(ans,(x2-x1)*(y2-y1))
            
print(ans)

Submission status: Wrong Answer

Solution code:
def count(x1,y1,x2,y2):
    res = 0
    for i in range(N):
        s1 = x[i]
        s2 = y[i]
        if x1 <= s1 <= x2 and y1 <= s2 <= y2:
               res += 1
    return res 

    
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)

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

res = 10**50
#x座標の点を左から右へ移動していく
for i in range(len(x)-1):
    for j in range(i+1,len(x)):
        for k in range(len(y)-1):
            for l in range(k+1,len(y)):
                if count(x[i],y[k],x[j],y[l]) == K:
                    res = min(res,(x[j]-x[i])*(y[l]-y[k]))
            
print(res)

Submission status: Wrong Answer

Solution code:
import itertools

N,K=list(map(int,raw_input().split()))
x=[]
y=[]
sx=[]
sy=[]
for i in range(N):
	a1,a2=map(int,raw_input().split())
	x.append(a1)
	sx.append(a1)
	y.append(a2)
	sy.append(a2)

#print "# x,y"
#print x
#print y


#print "# sx,sy"
sx.sort()
sy.sort()
#print sx
#print sy

ans=10**20
#print ans
for i in range(N):
	for j in range(i,N):
		for k in range(N):
			for l in range(k,N):
				cnt=0
				#print sy.index(y[l])-sy.index(y[k])+1
				if sx.index(x[j])-sx.index(x[i])+1>=K:
					#print i,j,k,l,x[i],y[k],x[j],y[l],sx.index(x[i]),sx.index(x[j]),abs(x[i]-x[j])*abs(y[k]-y[l])
					for m in range(N):
						x_t=x[m]
						y_t=y[m]
						if (x_t>=x[i] and x_t<=x[j]) or (x_t>=x[j] and x_t<=x[i]):
							if (y_t>=y[k] and y_t<=y[l]) or (y_t>=y[l] and y_t<=y[k]):
								cnt+=1
					
				
				#print cnt
				if cnt>=K:
					#print x[i],y[k],x[j],y[l],cnt,abs(x[i]-x[j])*abs(y[k]-y[l])
					ans=min(ans,abs(x[i]-x[j])*abs(y[k]-y[l]))


print ans

Submission status: Wrong Answer

Solution code:
import itertools

N,K=list(map(int,raw_input().split()))
x=[]
y=[]
sx=[]
sy=[]
for i in range(N):
	a1,a2=map(int,raw_input().split())
	x.append(a1)
	sx.append(a1)
	y.append(a2)
	sy.append(a2)

#print "# x,y"
#print x
#print y


#print "# sx,sy"
#sx.sort()
#sy.sort()
#print sx
#print sy

ans=10**20
#print ans
for i in range(N):
	for j in range(i,N):
		for k in range(N):
			for l in range(k,N):
				cnt=0
				#print sy.index(y[l])-sy.index(y[k])+1
				if sx.index(x[j])-sx.index(x[i])+1>=K:
					#print i,j,k,l,x[i],y[k],x[j],y[l],sx.index(x[i]),sx.index(x[j]),abs(x[i]-x[j])*abs(y[k]-y[l])
					for m in range(N):
						x_t=x[m]
						y_t=y[m]
						if (x_t>=x[i] and x_t<=x[j]) or (x_t>=x[j] and x_t<=x[i]):
							if (y_t>=y[k] and y_t<=y[l]) or (y_t>=y[l] and y_t<=y[k]):
								cnt+=1
					
				
				#print cnt
				if cnt>=K:
					#print x[i],y[k],x[j],y[l],cnt,abs(x[i]-x[j])*abs(y[k]-y[l])
					ans=min(ans,abs(x[i]-x[j])*abs(y[k]-y[l]))


print ans

Submission status: Wrong Answer

Solution code:
import itertools

N,K=list(map(int,raw_input().split()))
x=[]
y=[]
sx=[]
sy=[]
for i in range(N):
	a1,a2=map(int,raw_input().split())
	x.append(a1)
	sx.append(a1)
	y.append(a2)
	sy.append(a2)

#print "# x,y"
#print x
#print y


#print "# sx,sy"
#sx.sort()
#sy.sort()
#print sx
#print sy

ans=10**20
#print ans
for i in range(N):
	for j in range(i,N):
		for k in range(N):
			for l in range(k,N):
				cnt=0
				if sx.index(x[j])-sx.index(x[i])+1==K or sy.index(y[l])-sy.index(y[k])+1==K:
					#print i,j,k,l,x[i],y[k],x[j],y[l],sx.index(x[i]),sx.index(x[j]),abs(x[i]-x[j])*abs(y[k]-y[l])
					for m in range(N):
						x_t=x[m]
						y_t=y[m]
						if (x_t>=x[i] and x_t<=x[j]) or (x_t>=x[j] and x_t<=x[i]):
							if (y_t>=y[k] and y_t<=y[l]) or (y_t>=y[l] and y_t<=y[k]):
								cnt+=1
					
				
				#print cnt
				if cnt>=K:
					#print x[i],y[k],x[j],y[l],cnt,abs(x[i]-x[j])*abs(y[k]-y[l])
					ans=min(ans,abs(x[i]-x[j])*abs(y[k]-y[l]))


print ans

Submission status: Wrong Answer

Solution code:
import itertools

N,K=list(map(int,raw_input().split()))
x=[]
y=[]
sx=[]
sy=[]
for i in range(N):
	a1,a2=map(int,raw_input().split())
	x.append(a1)
	sx.append(a1)
	y.append(a2)
	sy.append(a2)

#print "# x,y"
#print x
#print y


#print "# sx,sy"
#sx.sort()
#sy.sort()
#print sx
#print sy

ans=10**20
#print ans
for i in range(N):
	for j in range(i,N):
		for k in range(N):
			for l in range(k,N):
				cnt=0
				if sx.index(x[j])-sx.index(x[i])+1==K or sy.index(y[l])-sy.index(y[k])+1==K:
					print i,j,k,l,x[i],y[k],x[j],y[l],sx.index(x[i]),sx.index(x[j]),abs(x[i]-x[j])*abs(y[k]-y[l])
					for m in range(N):
						x_t=x[m]
						y_t=y[m]
						if (x_t>=x[i] and x_t<=x[j]) or (x_t>=x[j] and x_t<=x[i]):
							if (y_t>=y[k] and y_t<=y[l]) or (y_t>=y[l] and y_t<=y[k]):
								cnt+=1
					
				
				#print cnt
				if cnt>=K:
					#print x[i],y[k],x[j],y[l],cnt,abs(x[i]-x[j])*abs(y[k]-y[l])
					ans=min(ans,abs(x[i]-x[j])*abs(y[k]-y[l]))


print ans

Submission status: Wrong Answer

Solution code:
import itertools

N,K=list(map(int,raw_input().split()))
x=[]
y=[]
sx=[]
sy=[]
for i in range(N):
	a1,a2=map(int,raw_input().split())
	x.append(a1)
	sx.append(a1)
	y.append(a2)
	sy.append(a2)

#print "# x,y"
#print x
#print y


#print "# sx,sy"
sx.sort()
sy.sort()
#print sx
#print sy

ans=10**20
#print ans
for i in range(N):
	for j in range(i,N):
		for k in range(N):
			for l in range(k,N):
				cnt=0
				if sx.index(x[j])-sx.index(x[i])+1==K:
					#print i,j,k,l,x[i],y[k],x[j],y[l],abs(x[i]-x[j])*abs(y[k]-y[l])
					for m in range(N):
						x_t=x[m]
						y_t=y[m]
						if (x_t>=x[i] and x_t<=x[j]) or (x_t>=x[j] and x_t<=x[i]):
							if (y_t>=y[k] and y_t<=y[l]) or (y_t>=y[l] and y_t<=y[k]):
								cnt+=1
					
				
				#print cnt
				if cnt>=K:
					#print x[i],y[k],x[j],y[l],cnt,abs(x[i]-x[j])*abs(y[k]-y[l])
					ans=min(ans,abs(x[i]-x[j])*abs(y[k]-y[l]))


print ans

Submission status: Wrong Answer

Solution code:
import itertools

N,K=list(map(int,raw_input().split()))
x=[]
y=[]
sx=[]
sy=[]
for i in range(N):
	a1,a2=map(int,raw_input().split())
	x.append(a1)
	sx.append(a1)
	y.append(a2)
	sy.append(a2)

#print "# x,y"
#print x
#print y


#print "# sx,sy"
sx.sort()
sy.sort()
#print sx
#print sy

ans=10**20
#print ans
for i in range(N):
	for j in range(i,N):
		for k in range(N):
			for l in range(k,N):
				cnt=0
				if sx.index(x[j])-sx.index(x[i])+1==K:
					#print i,j,k,l,x[i],y[k],x[j],y[l],abs(x[i]-x[j])*abs(y[k]-y[l])
					for m in range(N):
						x_t=x[m]
						y_t=y[m]
						if (y_t>=y[k] and y_t<=y[l]) or (y_t>=y[l] and y_t<=y[k]):
							cnt+=1
					
				
				#print cnt
				if cnt>=K:
					#print x[i],y[k],x[j],y[l],cnt,abs(x[i]-x[j])*abs(y[k]-y[l])
					ans=min(ans,abs(x[i]-x[j])*abs(y[k]-y[l]))


print ans

Submission status: Wrong Answer

Solution code:
import sys
def LI(): return [int(x) for x in sys.stdin.readline().split()]
 
N,K = LI()
p = []
for i in range(N):
    a,b = LI()
    p.append((a,b))
sx = sorted(p)
ans = 10**50
for x,y in sx:
    for x2,y2 in sx:
        if x2 <= x:
            continue
        points = sx.index((x2,y2)) - sx.index((x,y)) + 1
        if points < K:
            continue
        sy = sorted(sx[sx.index((x,y)):sx.index((x2,y2))+1],key=lambda coor: coor[1])
        for j in range(len(sy)-K, -1, -1):
            if sy[j][1] <= y and y2 <= sy[j+K-1][1]:
                ans = min(ans, (x2 - x) * (sy[j+K-1][1]-sy[j][1])) 
                break
print(ans)

Submission status: Wrong Answer

Solution code:
def inside (x, y, A, B):
	xmin = min(A[0], B[0])
	xmax = max(A[0], B[0])
	ymin = min(A[1], B[1])
	ymax = max(A[1], B[1])
	return xmin <= x and x <= xmax and ymin <= y and y <= ymax

def area(A, B):
	return abs(A[0]-B[0])*abs(A[1]-B[1])

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

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

answer = 2**64
for i in range(N):
	for j in range(N):
		if i != j:
			cnt = 0
			for k in range(N):
				x,y = points[k]
				if inside(x, y, points[i], points[j]):
					cnt += 1
			if cnt >= K:
				answer = min(answer, area(points[i], points[j]))

print(int(answer))

Submission status: Wrong Answer

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

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

x_order = {}
for xo,p in enumerate(xs):
    x,y,i = p
    x_order[i] = xo

cums = [[0 for j in range(N+1)] for i in range(N+1)]
for i in range(N):
    y,x,pi = ys[i]
    xo = x_order[pi]
    for j in range(N+1):
        cums[i+1][j] = cums[i][j] + (1 if j > xo else 0)
print(cums)

ans = float('inf')
for x1 in range(N-1):
    for x2 in range(x1+1,N):
        for y1 in range(N-1):
            for y2 in range(y1+1,N):
                if cums[y2+1][x2+1] - cums[y2+1][x1] - cums[y1][x2+1] + cums[y1][x1] < K:
                    continue
                area = (xs[x2][0] - xs[x1][0]) * (ys[y2][0] - ys[y1][0])
                ans = min(ans, area)
print(ans)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
z = [list(map(int, input().split())) for i in range(N)]
zx = sorted(z)
zy = sorted(z,key=lambda x:x[1])
ans = float('inf')
for i in range(N):
    for j in range(N):
        x1 = zx[i][0]
        x2 = zx[j][0]
        if abs(i - j) + 1 < K:continue
        w = abs(x1-x2)
        for k in range(N):
            for l in range(N):
                if abs(k - l) + 1 < K:continue
                y1 = zy[k][1]
                y2 = zy[l][1]
                h = abs(y1-y2)
                ans = min(ans, w*h)
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools

N,K=list(map(int,raw_input().split()))
x=[]
y=[]
for i in range(N):
	a1,a2=map(int,raw_input().split())
	x.append(a1)
	y.append(a2)

x.sort()
y.sort()
#print x
#print y

ans=100000000000000000000
for i in range(N):
	for j in range(i,N):
		for k in range(N):
			for l in range(k,N):
				cnt=0
				for m in range(N):
					x_t=x[m]
					y_t=y[m]
					if x_t>=x[i] and x_t<=x[j]:
						if y_t>=y[k] and y_t<=y[l]:
							cnt+=1
				#print i,j,k,l,x[i],y[k],x[j],y[l],cnt,abs(x[i]-x[j])*abs(y[k]-y[l])
				#print cnt
				if cnt>=K:
					#print x[i],y[k],x[j],y[l],cnt,abs(x[i]-x[j])*abs(y[k]-y[l])
					ans=min(ans,abs(x[i]-x[j])*abs(y[k]-y[l]))


print ans

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
z = [list(map(int, input().split())) for i in range(N)]
zx = sorted(z)
zy = sorted(z,key=lambda x:x[1])
ans = float('inf')
for i in range(N):
    for j in range(i+1, N):
        x1 = zx[i][0]
        x2 = zx[j][0]
        if abs(i - j) + 1 < K: continue
        w = max(x1,x2) - min(x1,x2)
        for k in range(N):
            for l in range(k+1, N):
                if abs(k - l) + 1 < K: continue
                y1 = zy[k][1]
                y2 = zy[l][1]
                h = max(y1,y2) - min(y1,y2)
                ans = min(ans, w*h)
print(ans)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
z = [list(map(int, input().split())) for i in range(N)]
zx = sorted(z)
zy = sorted(z,key=lambda x:x[1])
ans = float('inf')
for i in range(N):
    for j in range(i+1, N):
        x1 = zx[i][0]
        x2 = zx[j][0]
        if abs(i - j) + 1 < K: continue
        w = max(x1,x2) - min(x1,x2)
        for k in range(N):
            for l in range(k+1, N):
                if abs(k - l) + 1 < K: continue
                y1 = zy[k][1]
                y2 = zy[l][1]
                h = max(y1,y2) - min(y1,y2)
                print(w,h,w*h)                
                ans = min(ans, w*h)
print(ans)

Submission status: Wrong Answer

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

    x = [0] * N
    y = [0] * N
    for i, (j, k) in enumerate(XY):
        x[i] = j
        y[i] = k
    x.sort()
    y.sort()

    ans = float('inf')
    for xi in range(N - 1):
        for xj in range(xi + 1, N):
            for yi in range(N - 1):
                for yj in range(yi + 1, N):
                    cnt = 0
                    for i in range(N):
                        if x[xi] <= x[i] <= x[xj] and y[yi] <= y[i] <= y[yj]:
                            cnt += 1
                    if cnt >= K:
                        ans = min(ans, (x[xj] - x[xi]) * (y[yj] - y[yi]))
    print(ans)

main()

Submission status: Wrong Answer

Solution code:
import itertools

N,K=list(map(int,raw_input().split()))
a = []
for i in range(N):
    a.append(map(int,raw_input().split()))
#print "# a"
#print a

b=list(itertools.combinations(a, 2))
#print "# b"
#print b

area=[]
for i in range(len(b)):
	area.append(abs(b[i][0][0]-b[i][1][0])*abs(b[i][0][1]-b[i][1][1]))

#print area

for i in range(len(b)):
	cnt=0
	x1=b[i][0][0]
	x2=b[i][1][0]
	y1=b[i][0][1]
	y2=b[i][1][1]
	#print x1,y1,x2,y2
	for j in range(len(a)):
		#print a[j][0],a[j][1]
		if (a[j][0]>=x1 and a[j][0]<=x2) or (a[j][0]>=x2 and a[j][0]<=x1):
			if (a[j][1]>=y1 and a[j][1]<=y2) or (a[j][1]>=y2 and a[j][1]<=y1):
				cnt+=1
	#print cnt
	if cnt<K:
		area[i]=-1

#print area

min=0
for i in range(len(area)):
	if area[i]==-1:
		continue
	elif min==0:
		min=area[i]
	elif area[i]<min:
		min=area[i]

print min

Submission status: Wrong Answer

Solution code:
inputs = input().split()
N = int(inputs[0])
K = int(inputs[1])

input_list = []

for i in range(N):
    inputs = input().split()
    x = int(inputs[0])
    y = int(inputs[1])
    input_list.append([x, y])

ans = 10 * 19 
for upper in input_list:
    for bottom in input_list:
        for left in input_list:
            for right in input_list:
                count = 0
                for inner in input_list: 
                    if upper[1] >= inner[1] and bottom[1] <= inner[1] and left[0] <= inner[0] and right[0] >= inner[0] :
                        count += 1
                if count >= K:
                    if ans < (upper[1] - bottom[1]) * (right[0]-left[0]):
                        ans = (upper[1] - bottom[1]) * (right[0]-left[0])

print(ans)

Submission status: Wrong Answer

Solution code:
import math,heapq,collections,sys,numpy
sys.setrecursionlimit(10**7)

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()

N,K = LI()
p = []
for i in range(N):
    a,b = LI()
    p.append((a,b,i))
sx = sorted(p)
sy = sorted(p,key=lambda sp2: sp2[1])
ans = 10**50
for x,y,i in sx:
    for x2,y2,i2 in sx:
        if x2 <= x:
            continue
        #print(x,y,i,x2,y2,i2)
        points = sx.index((x2,y2,i2)) - sx.index((x,y,i)) + 1
        if points >= K:
        #    print(points)
            sy2 = sorted(sx[i:i2+1],key=lambda sx: sx[1])
            for j in range(len(sy2)-K+1):
                if sy2[j][1] <= y and sy2[j+K-1][1] >= y2:          
                    ans = min(ans, (x2 - x) * (sy2[j+K-1][1]-sy2[j][1])) 
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]


class EndLoop(Exception):
    pass


def debug_print(L):
    for col in L:
        print(col)


def debug_print_joined(L):
    for col in L:
        print("".join(col))


def transpose_matrix(L):
    transposed = list(map(list, zip(*L)))
    return transposed


def solve():
    N, K = map(int, input().split())
    x_coordinates = []
    y_coordinates = []
    for _ in range(N):
        x, y = map(int, input().split())
        x_coordinates.append(x)
        y_coordinates.append(y)

    x_coordinates_comb = []
    y_coordinates_comb = []
    for ele in itertools.combinations(x_coordinates, 2):
        x_coordinates_comb.append(ele)

    for ele in itertools.combinations(y_coordinates, 2):
        y_coordinates_comb.append(ele)

    min_area = 10e10
    for x in x_coordinates_comb:
        for y in x_coordinates_comb:
            cnt = 0
            for i in range(N):
                if min(x) <= x_coordinates[i] <= max(x) and min(y) <= y_coordinates[i] <= max(y):
                    cnt += 1

            if cnt >= K:
                min_area = min(min_area, (max(x) - min(x)) * (max(y) - min(y)))

    print(min_area)


solve()