Envíos

2949 - Drawing Circles

Criado por Orlenys López Pintado
Adicionado por kko (2014-06-10)
Límiteis
Tempo Total: 20000 MS | Tempo Caso: 6000 MS |Memória: 62 MB | Saída límite (mb): 64 MB | Tamanho: 14 KB
Lenguagens activados
Disponivel em

Descripção

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.

Especificação de entrada

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.

Especificação de saída

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.

Exemplo de entrada

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

Exemplo de saída

2

Sugestões(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