4161 - Circles and Aliens 4161 - Circles and Aliens 4161 - Circles and Aliens

Estadísticas Env: 108 | AC: 20 | %AC: 18,52 | Puntuación: 3,57
Creado por SIO2 Online Judge - Tomasz Idziaszek
Adicionado por ralcolea (2019-03-18)
Límites
Tiempo Total: 30000 MS | Tiempo Caso: 5000 MS |Memoria: 128 MB | Salida límite (mb): 64 MB | Tamaño: 9 KB
Lenguajes activados
Disponible en

Descripción

The farmers of Byteland will remember the last summer for a long time. Usually a summer burns into one’s memory due to plentiful harvest, severe drought or hail. However the last summer was so extraordinary because of strange shapes, which appeared at several wheat fields. As a Bytean expert in all unusual problems, Byteasar decided to explain this phenomenon on the ground of science. In order to do this, he thoroughly inspected each wheat field and noticed that each shape was made by crumbling all wheat belonging to a circular region. Every two circles touch in at most one point (in particular no circle can be contained in a different circle).

Byteasar suspects that the circles describe messages sent by aliens. Unfortunately, understanding their language is very hard. At this point Byteasar collected all the information about the shapes he found and he is going to use some tools of statistical analysis. The more interesting data he collects, the better. Byteasar asked you to write a program, which given the description of all the circles computes the number of pairs of circles having a common point.
The farmers of Byteland will remember the last summer for a long time. Usually a summer burns into one’s memory due to plentiful harvest, severe drought or hail. However the last summer was so extraordinary because of strange shapes, which appeared at several wheat fields. As a Bytean expert in all unusual problems, Byteasar decided to explain this phenomenon on the ground of science. In order to do this, he thoroughly inspected each wheat field and noticed that each shape was made by crumbling all wheat belonging to a circular region. Every two circles touch in at most one point (in particular no circle can be contained in a different circle).

Byteasar suspects that the circles describe messages sent by aliens. Unfortunately, understanding their language is very hard. At this point Byteasar collected all the information about the shapes he found and he is going to use some tools of statistical analysis. The more interesting data he collects, the better. Byteasar asked you to write a program, which given the description of all the circles computes the number of pairs of circles having a common point.
The farmers of Byteland will remember the last summer for a long time. Usually a summer burns into one’s memory due to plentiful harvest, severe drought or hail. However the last summer was so extraordinary because of strange shapes, which appeared at several wheat fields. As a Bytean expert in all unusual problems, Byteasar decided to explain this phenomenon on the ground of science. In order to do this, he thoroughly inspected each wheat field and noticed that each shape was made by crumbling all wheat belonging to a circular region. Every two circles touch in at most one point (in particular no circle can be contained in a different circle).

Byteasar suspects that the circles describe messages sent by aliens. Unfortunately, understanding their language is very hard. At this point Byteasar collected all the information about the shapes he found and he is going to use some tools of statistical analysis. The more interesting data he collects, the better. Byteasar asked you to write a program, which given the description of all the circles computes the number of pairs of circles having a common point.

Especificación de entrada

The first line of input contains a single integer n (1 ≤ n ≤ 500000), the number of circles. Each of the following n lines describes a circle. In the i-th of those lines there are three integers xi, yi, ri (−109xi, yi109, 1 ≤ ri109), meaning that the center of the i-th circle has coordinates (xi, yi) while its radius equals ri.
The first line of input contains a single integer n (1 ≤ n ≤ 500000), the number of circles. Each of the following n lines describes a circle. In the i-th of those lines there are three integers xi, yi, ri (−109xi, yi109, 1 ≤ ri109), meaning that the center of the i-th circle has coordinates (xi, yi) while its radius equals ri.
The first line of input contains a single integer n (1 ≤ n ≤ 500000), the number of circles. Each of the following n lines describes a circle. In the i-th of those lines there are three integers xi, yi, ri (−109xi, yi109, 1 ≤ ri109), meaning that the center of the i-th circle has coordinates (xi, yi) while its radius equals ri.

Especificación de salida

Your program should output the number of pairs of circles having a common point.
Your program should output the number of pairs of circles having a common point.
The first line of input contains a single integer n (1 ≤ n ≤ 500000), the number of circles. Each of the following n lines describes a circle. In the i-th of those lines there are three integers xi, yi, ri (−109xi, yi109, 1 ≤ ri109), meaning that the center of the i-th circle has coordinates (xi, yi) while its radius equals ri.

Ejemplo de entrada

4
0 0 5
8 6 5
-6 8 5
2 14 5

Ejemplo de salida

4

Sugerencia(s)