Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
4th solution in Clear category for Four To The Floor by pokosasa
def is_covered(room, sensors):
W,H=room[0],room[1]
delta=10e-7
def serch_neighbor(point,direction):
x,y=point
dx,dy=direction
dx,dy=delta*dx/(dx**2+dy**2),delta*dy/(dx**2+dy**2)
if not(0<=x+dx<=W and 0<=y+dy<=H):
return True
for x1,y1,r1 in sensors:
if (x+dx-x1)**2+(y+dy-y1)**2<=r1**2:
return True
return False
intersections=[]
for x_i,y_i,r_i in sensors:
for x_j,y_j in ((0,0),(W,0),(0,H),(W,H)):
if (x_j-x_i)**2+(y_j-y_i)**2>r_i**2:
break
else:
return True
for lx in (0,W):
det=r_i**2-(lx-x_i)**2
if det>=0:
intersections.extend([((lx,y_i-det**.5),(0,-1)),((lx,y_i+det**.5),(0,1))])
for ly in (0,H):
det=r_i**2-(ly-y_i)**2
if det>=0:
intersections.extend([((x_i-det**.5,ly),(-1,0)),((x_i+det**.5,ly),(1,0))])
for i in range(len(sensors)-1):
x_i,y_i,r_i=sensors[i]
for j in range(i+1,len(sensors)):
x_j,y_j,r_j=sensors[j]
x0,y0=x_j-x_i,y_j-y_i
dist=x0**2+y0**2
a=(dist+r_i**2-r_j**2)/2
det=dist*r_i**2-a**2
if det>=0:
point1=((a*x0-y0*det**.5)/dist+x_i,(a*y0+x0*det**.5)/dist+y_i)
point2=((a*x0+y0*det**.5)/dist+x_i,(a*y0-x0*det**.5)/dist+y_i)
if det==0:
(dx,dy)=(y0,-x0)
else:
(dx,dy)=(point2[0]-point1[0],point2[1]-point1[1])
intersections.append((point1,(-dx,-dy)))
intersections.append((point2,(dx,dy)))
intersections=[((x,y),direction) for (x,y),direction in intersections if 0<=x<=W and 0<=y<=H]
if not intersections:
return False
for point,direction in intersections:
if not serch_neighbor(point,direction):
return False
return True
if __name__ == '__main__':
print("Example:")
print(is_covered([200, 150], [[100, 75, 130]]))
# These "asserts" are used for self-checking and not for an auto-testing
assert is_covered([200, 150], [[100, 75, 130]]) == True
assert is_covered([200, 150], [[50, 75, 100], [150, 75, 100]]) == True
assert is_covered([200, 150], [[50, 75, 100], [150, 25, 50], [150, 125, 50]]) == False
assert is_covered([200, 150], [[100, 75, 100], [0, 40, 60], [0, 110, 60], [200, 40, 60], [200, 110, 60]]) == True
assert is_covered([200, 150], [[100, 75, 100], [0, 40, 50], [0, 110, 50], [200, 40, 50], [200, 110, 50]]) == False
assert is_covered([200, 150], [[100, 75, 110], [105, 75, 110]]) == False
assert is_covered([200, 150], [[100, 75, 110], [105, 75, 20]]) == False
assert is_covered([3, 1], [[1, 0, 2], [2, 1, 2]]) == True
assert is_covered([30, 10], [[0, 10, 10], [10, 0, 10], [20, 10, 10], [30, 0, 10]]) == True
assert is_covered([30, 10], [[0, 10, 8], [10, 0, 7], [20, 10, 9], [30, 0, 10]]) == False
print("Coding complete? Click 'Check' to earn cool rewards!")
Dec. 21, 2019