Union Area of Right Isosceles Triangles

Time limit2sMemory limit128 MB

Summary
Compute the total area covered by the union of up to 2000 axis-aligned right isosceles triangles with integer coordinates.
Level

Hard8 of 10

Topics
Geometry, Sorting, Divide and conquer
Solved
No attempts yet

Problem

You are given (n) right isosceles triangles on a plane. Each triangle is described by three integers (x), (y), and (m) ((m>0)); its vertices are ((x, y)), ((x+m, y)), and ((x, y+m)).

The triangles may overlap. Write a program that computes the area covered by at least one triangle.

Input

The first line contains an integer (n). ((1 \le n \le 2{,}000))

Each of the next (n) lines contains three integers (x), (y), and (m), describing one triangle. The absolute values of (x) and (y) do not exceed (10{,}000{,}000), and (m) is between (1) and (1{,}000), inclusive.

Output

Print the area covered by all triangles on the first line. The output must always include exactly one digit after the decimal point.

Hint

Because all coordinates and side lengths are integers, the area is always representable in units of (0.5).

Examples1

  1. Example 1

    Input
    5
-5 -3 6
-1 -2 3
0 0 2
-2 2 1
-4 -1 2
    Expected output
    24.5