Problem p03576 (python)

Fixed submission:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations,groupby
import sys
import bisect
import string
import math
import time
import random
def S_():
    return input()
def LS():
    return [i for i in input().split()]
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)]
        rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
#sys.setrecursionlimit(10**5)
input=lambda: sys.stdin.readline().rstrip()

def ran_input():
    import random
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

show_flg=False
show_flg=True

ans=1

n,k=LI()
a=[]

for i in range(n):
    x,y=LI()
    a.append((x,y))

a.sort()

ans=inf

for lx in range(n):
    for rx in range(lx+1,n):
        for ly in range(n):
            for ry in range(ly+1,n):
                c=0
                x1,x2,y1,y2=a[lx][0],a[rx][0],a[ly][1],a[ry][1]
                if y1>y2:
                    y1,y2=y2,y1
                for i in range(lx,rx+1):
                    x,y=a[i]
                    if x1<=x<=x2 and y1<=y<=y2:
                        c+=1
                
#                show(c,(lx,rx),(ly,ry),(x1,x2,y1,y2))
                if c>=k:
                    ans=min(ans,(x2-x1)*(y2-y1))

print(ans)

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(1000000)
def input():
    return sys.stdin.readline()[:-1]

'''
n=int(input())
for i in range(n):
    a[i]=int(input())
    a[i],b[i]=map(int,input().split())
a=[int(x) for x in input().split()]
n,m=map(int,input.split())
from operator import itemgetter
a = [(1, "c", 1), (1, "b", 3), (2, "a", 0), (1, "a", 2)]
print(sorted(a))  # 0 番目の要素でソート、先頭の要素が同じなら 1 番目以降の要素も見る
print(sorted(a, key=itemgetter(0)))  # 0 番目の要素だけでソート
print(sorted(a, key=itemgetter(0, 2)))  # 0 番目と 2 番目の要素でソート
print(sorted(a, key=lambda x: x[0] * x[2]))  # 0 番目の要素 * 2 番目の要素でソート
print(sorted(a, reverse=True))  # 降順にソート
a.sort()  # 破壊的にソート、sorted() よりも高速
try: # エラーキャッチ list index out of range
    for i in range():
        k=b[i]
except IndexError as e:
    print(i)
'''

test_data1 = '''\
4 4
1 4
3 3
6 2
8 1
'''

test_data2 = '''\
4 2
0 0
1 1
2 2
3 3
'''

test_data3 = '''\
4 3
-1000000000 -1000000000
1000000000 1000000000
-999999999 999999999
999999999 -999999999
'''
td_num=3

def GetTestData(index):
    if index==1:
        return test_data1
    if index==2:
        return test_data2
    if index==3:
        return test_data3

if False:
    with open("../test.txt", mode='w') as f:
        f.write(GetTestData(td_num))
    with open("../test.txt") as f:
        # Start Input code ---------------------------------------
        
        n,k=map(int,f.readline().split())
        x=[0]*n
        y=[0]*n
        for i in range(n):
            x[i],y[i]=map(int,f.readline().split())
            
        # End Input code ---------------------------------------
else:
    for i in range(1):
        # Start Input code ---------------------------------------
        n,k=map(int,input().split())
        x=[0]*n
        y=[0]*n
        for i in range(n):
            x[i],y[i]=map(int,input().split())
        # End Input code ---------------------------------------
#print('n,k,x,y=',n,k,x,y)
ans=10**20
for x1 in range(n):
    for x2 in range(x1,n+1):
        for y1 in range(n):
            for y2 in range(y1,n+1):                
                cnt=0
                for i in range(n):
                    if min(x[x1],x[x2])<=x[i] and x[i]<=max(x[x1],x[x2]) and min(y[y1],y[y2])<=y[i] and y[i]<=max(y[y1],y[y2]):
                        cnt+=1
                        
                if cnt>=k:
                    ans=min(ans,abs(x[x2]-x[x1])*abs(y[y2]-y[y1]))
                    #print(x1,x2,y1,y2,ans)
print(ans)

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(1000000)
#def input():
#    return sys.stdin.readline()[:-1]

'''
n=int(input())
for i in range(n):
    a[i]=int(input())
    a[i],b[i]=map(int,input().split())
a=[int(x) for x in input().split()]
n,m=map(int,input.split())
from operator import itemgetter
a = [(1, "c", 1), (1, "b", 3), (2, "a", 0), (1, "a", 2)]
print(sorted(a))  # 0 番目の要素でソート、先頭の要素が同じなら 1 番目以降の要素も見る
print(sorted(a, key=itemgetter(0)))  # 0 番目の要素だけでソート
print(sorted(a, key=itemgetter(0, 2)))  # 0 番目と 2 番目の要素でソート
print(sorted(a, key=lambda x: x[0] * x[2]))  # 0 番目の要素 * 2 番目の要素でソート
print(sorted(a, reverse=True))  # 降順にソート
a.sort()  # 破壊的にソート、sorted() よりも高速
try: # エラーキャッチ list index out of range
    for i in range():
        k=b[i]
except IndexError as e:
    print(i)
'''

test_data1 = '''\
4 4
1 4
3 3
6 2
8 1
'''

test_data2 = '''\
2 3 0
4 5 6
7 8 9
-1 2 -5
'''

test_data3 = '''\

'''
td_num=1

def GetTestData(index):
    if index==1:
        return test_data1
    if index==2:
        return test_data2
    if index==3:
        return test_data3

if True:
    with open("../test.txt", mode='w') as f:
        f.write(GetTestData(td_num))
    with open("../test.txt") as f:
        # Start Input code ---------------------------------------
        
        n,k=map(int,f.readline().split())
        x=[0]*n
        y=[0]*n
        for i in range(n):
            x[i],y[i]=map(int,f.readline().split())
            
        # End Input code ---------------------------------------
else:
    for i in range(1):
        # Start Input code ---------------------------------------
        n,k=map(int,input().split())
        x=[0]*n
        y=[0]*n
        for i in range(n):
            x[i],y[i]=map(int,input().split())
        # End Input code ---------------------------------------
#print('n,k,x,y=',n,k,x,y)
ans=10**10
for x1 in range(n):
    for x2 in range(n):
        for y1 in range(n):
            for y2 in range(n):                
                cnt=0
                for i in range(n):
                    if min(x[x1],x[x2])<=x[i] and x[i]<=max(x[x1],x[x2]) and min(y[y1],y[y2])<=y[i] and y[i]<=max(y[y1],y[y2]):
                        cnt+=1
                        
                if cnt>=k:
                    ans=min(ans,abs(x[x2]-x[x1])*abs(y[y2]-y[y1]))
                    #print(x1,x2,y1,y2,ans)
print(ans)

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(1000000)
#def input():
#    return sys.stdin.readline()[:-1]

'''
n=int(input())
for i in range(n):
    a[i]=int(input())
    a[i],b[i]=map(int,input().split())
a=[int(x) for x in input().split()]
n,m=map(int,input.split())
from operator import itemgetter
a = [(1, "c", 1), (1, "b", 3), (2, "a", 0), (1, "a", 2)]
print(sorted(a))  # 0 番目の要素でソート、先頭の要素が同じなら 1 番目以降の要素も見る
print(sorted(a, key=itemgetter(0)))  # 0 番目の要素だけでソート
print(sorted(a, key=itemgetter(0, 2)))  # 0 番目と 2 番目の要素でソート
print(sorted(a, key=lambda x: x[0] * x[2]))  # 0 番目の要素 * 2 番目の要素でソート
print(sorted(a, reverse=True))  # 降順にソート
a.sort()  # 破壊的にソート、sorted() よりも高速
try: # エラーキャッチ list index out of range
    for i in range():
        k=b[i]
except IndexError as e:
    print(i)
'''

test_data1 = '''\
4 4
1 4
3 3
6 2
8 1
'''

test_data2 = '''\
2 3 0
4 5 6
7 8 9
-1 2 -5
'''

test_data3 = '''\

'''
td_num=1

def GetTestData(index):
    if index==1:
        return test_data1
    if index==2:
        return test_data2
    if index==3:
        return test_data3

if True:
    with open("../test.txt", mode='w') as f:
        f.write(GetTestData(td_num))
    with open("../test.txt") as f:
        # Start Input code ---------------------------------------
        
        n,k=map(int,f.readline().split())
        x=[0]*n
        y=[0]*n
        for i in range(n):
            x[i],y[i]=map(int,f.readline().split())
            
        # End Input code ---------------------------------------
else:
    for i in range(1):
        # Start Input code ---------------------------------------
        n=int(input())
        n,m=map(int,input().split())
        for i in range(n):
            x,y=map(int,input().split())
            a[i]=int(input())
            a[i],b[i]=map(int,input().split())
            a=[int(x) for x in input().split()]
        # End Input code ---------------------------------------
#print('n,k,x,y=',n,k,x,y)
ans=10**10
for x1 in range(n):
    for x2 in range(n):
        for y1 in range(n):
            for y2 in range(n):                
                cnt=0
                for i in range(n):
                    if min(x[x1],x[x2])<=x[i] and x[i]<=max(x[x1],x[x2]) and min(y[y1],y[y2])<=y[i] and y[i]<=max(y[y1],y[y2]):
                        cnt+=1
                        
                if cnt>=k:
                    ans=min(ans,abs(x[x2]-x[x1])*abs(y[y2]-y[y1]))
                    #print(x1,x2,y1,y2,ans)
print(ans)