#format python
import unittest
"""
Seminar:FourBoxes problem in [yong27/2003-01-10]

Wrong approach --> [yong27/2003-01-12] correct. performance improvement
"""
import unittest

def intersect(*args):
    result=[]
    for x in args[0]:
        for other in args[1:]:
            if x not in other: break
        else:
            result.append(x)
    return result

def combo(aList, size=2): 
    if size==0 or not aList: 
        return [aList[:0]] 
    else: 
        result = [] 
        for i in range(0, (len(aList)-size)+1): 
            pick = aList[i:i+1] 
            rest = aList[i+1:] 
            for x in combo(rest, size-1): 
                result.append(pick+x) 
        return result 

class Rect:
    def __init__(self, x1,y1, x2, y2):
        self.x1=x1; self.y1=y1
        self.x2=x2; self.y2=y2
        self.xr=range(x1,x2)
        self.yr=range(y1,y2)
    def area(self):
        return (self.x2-self.x1) * (self.y2-self.y1)
    def getPileArea(self, *aRect):
        xrList=[self.xr]; yrList=[self.yr]
        for rect in aRect:
            xrList.append(rect.xr)
            yrList.append(rect.yr)
        xIts = intersect(*xrList)
        yIts = intersect(*yrList)
        if xIts and yIts:
            return len(xIts) * len(yIts)
        else:
            return 0

def main(a,b,c,d):
    totalArea = a.area()+b.area()+c.area()+d.area()
    for pair in combo([a,b,c,d]):
        totalArea -= pair[0].getPileArea(pair[1])
    for three in combo([a,b,c,d],3):
        totalArea += three[0].getPileArea(three[1],three[2])
    totalArea -= a.getPileArea(b,c,d)
    return totalArea

def myProblem():
    a=Rect(1,2,4,4)
    b=Rect(2,3,5,7)
    c=Rect(3,1,6,5)
    d=Rect(7,3,8,6)
    return main(a,b,c,d)

class RectTest(unittest.TestCase):
    def testIntersect(self):
        a = [1,2,3,4]
        b = [3,4,5,6]
        self.assertEquals([3,4], intersect(a,b))
    def testIntersectMultiArgu(self):
        a = [[1,2],[0]]
        self.assertEquals([], intersect(*a))
    def testIntersectThree(self):
        a = [1,2,3,4]
        b = [3,4,5,6]
        c = [4,5,6,7]
        self.assertEquals([4], intersect(a,b,c))
    def testCombination(self):
        self.assertEquals([[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]],
                          combo([1,2,3,4]))
        self.assertEquals([[1,2],[1,3],[2,3]],combo([1,2,3]))

    def testOneArea(self):
        a = Rect(1,2,4,4)
        self.assertEquals(6, a.area())
    def testIsPile1(self):
        a = Rect(0,0,1,1)
        b = Rect(1,0,2,1)
        self.assertEquals(0, a.getPileArea(b))
    def testIsPile2(self):
        a = Rect(0,0,2,2)
        b = Rect(1,1,3,3)
        self.assertEquals(1, a.getPileArea(b))
    def testIsPileThree(self):
        a = Rect(0,0,2,1)
        b = Rect(1,0,3,2)
        c = Rect(1,0,2,3)
        self.assertEquals(1, a.getPileArea(b,c))
    def testMain(self):
        self.assertEquals(26, myProblem())

def specialProblem():
    a=Rect(1,2,800,600)
    b=Rect(2,3,700,900)
    c=Rect(3,1,666,666)
    d=Rect(7,3,1000,888)
    return main(a,b,c,d)

if __name__=='__main__':
    #unittest.main(argv=('','-v'))
    print specialProblem()