Radar Station Lattice Coverage

MediumArrayHash tableMathGeometryEnumerationLattice points2 sample tests5 hidden tests

A coastal-defense network places n radar stations on an integer grid map. Station i sits at grid coordinates (x_i, y_i) and sweeps a circular detection zone of radius r_i, measured in whole grid units: it detects every grid intersection point (px, py) satisfying (px - x_i)^2 + (py - y_i)^2 <= r_i^2, including points exactly on the boundary of the zone. Because the zones of different stations frequently overlap, command wants to know how many distinct grid intersections are detected by at least one station — not the sum of each station's individual count, which would double-count overlapping ground.

Input format

Line 1: a single integer n, the number of radar stations.
Each of the next n lines contains three integers x y r describing one station: its coordinates (x, y) and its detection radius r.

Output format

A single integer: the number of distinct integer-coordinate points (px, py) that lie within or on the boundary of at least one station's detection circle.

Constraints

1 <= n <= 200
1 <= x, y <= 100
1 <= r <= 100
All input values are integers.

Examples

Example 1

Input

1
2 2 1

Expected

Explanation

The single station at (2,2) with radius 1 detects the 5 points forming a diamond around its center: (2,1), (1,2), (2,2), (3,2), and (2,3). No other integer point satisfies (px-2)^2+(py-2)^2<=1, so the answer is 5.

Example 2

Input

2
2 2 2
3 4 1

Expected

Explanation

The first station covers the 13 integer points within distance 2 of (2,2). The second station covers the 5 points within distance 1 of (3,4): (2,4), (3,3), (3,4), (3,5), and (4,4). Two of those five points, (2,4) and (3,3), also lie inside the first station's circle, so the union has 13 + 5 - 2 = 16 distinct points.

Ready to solve this?