2949 - Drawing Circles

Created by Orlenys López Pintado
Added by kko (2014-06-10)
Limits
Total Time: 20000 MS | Test Time: 6000 MS |Memory: 62 MB | Output: 64 MB | Size: 14 KB
Enabled languages
Available in

Description

You are given the coordinates of the centers of 1 <= N <= 10^5 circles in the plane; those are drawn in increasing order according to the dimensions of their radii. By that reason some of them are hidden by others with bigger radius. To guarantee that all points that are drawn have a visible portion at least, if a circle is completely covered by another one, then the smaller circle is not drawn; but only should be removed the circles whose area is completely overlapped by a circle with bigger radius. Also, if there are several circles with equal radii and center, then only one of them should be visible.

Your task is to find how many circles will be drawn after applying the strategy described previously.
You are given the coordinates of the centers of 1 <= N <= 10^5 circles in the plane; those are drawn in increasing order according to the dimensions of their radii. By that reason some of them are hidden by others with bigger radius. To guarantee that all points that are drawn have a visible portion at least, if a circle is completely covered by another one, then the smaller circle is not drawn; but only should be removed the circles whose area is completely overlapped by a circle with bigger radius. Also, if there are several circles with equal radii and center, then only one of them should be visible.

Your task is to find how many circles will be drawn after applying the strategy described previously.
You are given the coordinates of the centers of 1 <= N <= 10^5 circles in the plane; those are drawn in increasing order according to the dimensions of their radii. By that reason some of them are hidden by others with bigger radius. To guarantee that all points that are drawn have a visible portion at least, if a circle is completely covered by another one, then the smaller circle is not drawn; but only should be removed the circles whose area is completely overlapped by a circle with bigger radius. Also, if there are several circles with equal radii and center, then only one of them should be visible.

Your task is to find how many circles will be drawn after applying the strategy described previously.

Input specification

Line 1: The number N of circles.
Lines 2 … N + 1: Each line represent a circle in the initial configuration, given by three integers: the coordinates (X, Y) of its center (|X| <= 100, |Y| <= 100) and its radius R,1 <= R <= 10.
Line 1: The number N of circles.
Lines 2 … N + 1: Each line represent a circle in the initial configuration, given by three integers: the coordinates (X, Y) of its center (|X| <= 100, |Y| <= 100) and its radius R,1 <= R <= 10.
Line 1: The number N of circles.
Lines 2 … N + 1: Each line represent a circle in the initial configuration, given by three integers: the coordinates (X, Y) of its center (|X| <= 100, |Y| <= 100) and its radius R,1 <= R <= 10.

Output specification

A single line with a integer number: the amount of circles that will be drawn.
A single line with a integer number: the amount of circles that will be drawn.
Line 1: The number N of circles.
Lines 2 … N + 1: Each line represent a circle in the initial configuration, given by three integers: the coordinates (X, Y) of its center (|X| <= 100, |Y| <= 100) and its radius R,1 <= R <= 10.

Sample input

4
5 5 5
4 4 1
6 6 2
1 1 3

Sample output

2

Hint(s)

The answer for the following case (picture) is four...
4
3 4 2
3 2 1
1 1 2
5 1 3



But, the answer for the following case is only 3.
4
3 4 2
4 0 1
1 1 2
5 1 3
The answer for the following case (picture) is four...
4
3 4 2
3 2 1
1 1 2
5 1 3



But, the answer for the following case is only 3.
4
3 4 2
4 0 1
1 1 2
5 1 3
The answer for the following case (picture) is four...
4
3 4 2
3 2 1
1 1 2
5 1 3



But, the answer for the following case is only 3.
4
3 4 2
4 0 1
1 1 2
5 1 3