Visible Squares

Time limit2sMemory limit128 MB

Summary

Given up to 1000 non-overlapping axis-aligned integer squares, count how many are visible from the origin by angular occlusion reasoning.

Level: Hard8 of 10
Topics: Geometry, Sorting, Intervals
Solved: No attempts yet

Problem

There are N axis-aligned squares on a plane. Every vertex of every square has integer coordinates, and no two squares touch or overlap.

Count how many squares are visible from the origin O(0, 0).

A square is considered visible from the origin if there exist two distinct points A and B on its boundary such that the interior of triangle OAB, excluding the boundary of the triangle, is not crossed by any other square.

Input

The first line contains the number of squares N (1 <= N <= 1,000).

Each of the next N lines contains three integers X, Y, and L (1 <= X, Y, L <= 10,000), describing one square. Its lower-left vertex is (X, Y), and its side length is L.

Output

Print the number of squares visible from the origin.

Examples2

Example 1
Input
```
3
2 6 3
1 4 1
3 4 1
```
Expected output
```
3
```
Example 2
Input
```
4
1 2 1
3 1 1
2 4 2
3 7 1
```
Expected output
```
2
```