Snippets

vaibhav sharma Chef and Square Problem Solution

Created by vaibhav sharma
#import sys,time
def check_if_one(lis):
    n=len(lis)
    if(n<3):
            return [4-n,n]
    else:
        return [1,n]     
n=input()
set1=set()
set2=set()
#tm=time.time()
for k in range(n):
    x,y=[int(x) for x in raw_input().split()]
    set1.add((x,y,(x/2.0)+(y/2.0),(x/2.0)-(y/2.0)))
    set2.add((x,y))
#print time.time()-tm    
value=check_if_one(set1)
n=value[1]
value=value[0]
if((value<2)&(value!=0)):
    my_lis=list(set1)
    count=0
    for i in range(n):
        x1,y1=my_lis[i][2],my_lis[i][3]
        if(count==2):
            break
        for j in range(i+1,n):
            x2,y2=my_lis[j][2],my_lis[j][3]
            count1=((x2+y1,x1-y2) in set2)+((x1+y2,x2-y1) in set2)
            if(count1>count):
                    count=count1
    print 2-count
else:
    print value
#print time.time()-tm

Comments (0)

HTTPS SSH

You can clone a snippet to your computer for local editing. Learn more.