Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Clear category for Rectangles Union by pokosasa
from typing import List, Tuple
from itertools import combinations,product
def rectangles_union(recs: List[Tuple[int]]) -> int:
rects={tuple(rect) for rect in recs}
def intersect(rect1,rect2):
left1,top1,right1,bottom1=rect1
left2,top2,right2,bottom2=rect2
if right1<=left2 or right2<=left1 or bottom1<=top2 or bottom2<=top1:
return False
return True
def split_rects(rect1,rect2):
left1,top1,right1,bottom1=rect1
left2,top2,right2,bottom2=rect2
v_lines=sorted([left1,right1,left2,right2])
h_lines=sorted([top1,bottom1,top2,bottom2])
mini_rects=set()
for i,j in product(range(3),repeat=2):
left,right=v_lines[j],v_lines[j+1]
top,bottom=h_lines[i],h_lines[i+1]
rect3=(left,top,right,bottom)
if intersect(rect1,rect3) or intersect(rect2,rect3):
mini_rects.add(rect3)
return mini_rects
while True:
rect1,rect2=None,None
for rect_i,rect_j in combinations(rects,2):
if intersect(rect_i,rect_j):
rect1,rect2=rect_i,rect_j
break
if rect1==None:
break
rects.remove(rect1)
rects.remove(rect2)
rects.update(split_rects(rect1,rect2))
continue
res=sum((right-left)*(bottom-top) for left,top,right,bottom in rects)
return res
if __name__ == '__main__':
print("Example:")
print(rectangles_union([[6,3,8,10],[4,8,11,10],[16,8,19,11],[6,8,8,12]]))
# These "asserts" are used for self-checking and not for an auto-testing
assert rectangles_union([[6,3,8,10],[4,8,11,10],[16,8,19,11],[6,8,8,12]]) == 37
assert rectangles_union([
(16, 8, 19, 11)
]) == 9
assert rectangles_union([
(16, 8, 19, 11),
(16, 8, 19, 11)
]) == 9
assert rectangles_union([
(16, 8, 16, 8)
]) == 0
assert rectangles_union([
]) == 0
print("Coding complete? Click 'Check' to earn cool rewards!")
June 1, 2020
