Perimeter of a Rectangle Union

Time limit2sMemory limit128 MB

Summary
Compute the total outer perimeter of the union of up to 5000 axis-aligned rectangles using a sweep-line approach.
Level

Hard8 of 10

Topics
Sorting, Geometry, Segment tree
Solved
No attempts yet

Problem

Given N axis-aligned rectangles on a two-dimensional plane, find the total length of the outer boundary of their union. Parts where rectangles overlap or share an edge are not counted when they become internal to the union. If N is 0, the union is empty and the answer is 0.

Input

The first line contains the number of rectangles N (0 ≤ N ≤ 5,000). Each of the next N lines contains four integers x1, y1, x2, y2. The points (x1, y1) and (x2, y2) are opposite vertices of one rectangle. Every coordinate is between -10,000 and 10,000, inclusive.

Output

Print one line containing the perimeter length of the union of the rectangles.

Examples1

  1. Example 1

    Input
    7
-15 0 5 10
-5 8 20 25
15 -4 24 14
0 -6 16 4
2 15 10 22
30 10 36 20
34 0 40 16
    Expected output
    228