Under construction

Still being built. Things may change

Overplanting

Interview

Time limit1sMemory limit128 MB

Summary
Given up to 10 axis-aligned rectangles, find the total area of their union.
Level

Medium4 of 10

Topics
Geometry, Implementation, Brute force
Solved
No attempts yet

Problem

Farmer John has bought a new machine that can plant grass in any axis-aligned rectangular region of his farm (a rectangle whose sides are vertical and horizontal). One day the machine malfunctions and plants grass in not one but NN (1≤N≤101 \le N \le 10) rectangular regions, some of which may overlap.

Given the rectangular regions that were planted with grass, help Farmer John compute the total area of his farm that is now covered with grass.

Input

  • Line 1: the integer NN.
  • Lines 2 to N+1N+1: each line contains four space-separated integers x1 y1 x2 y2x_1\ y_1\ x_2\ y_2 describing a rectangular region with upper-left corner (x1,y1)(x_1, y_1) and lower-right corner (x2,y2)(x_2, y_2). All coordinates satisfy −10000≤x,y≤10000-10000 \le x, y \le 10000.

Output

  • Line 1: the total area covered by grass.

Examples1

  1. Example 1

    Input
    2
    0 5 4 1
    2 4 6 2
    
    Expected output
    20