3381 - AM/FM 3381 - AM/FM 3381 - AM/FM

Statistics Sub: 262 | AC: 71 | AC%: 27,10 | Score: 2,38
Created by Torneo Argentino de Programación ACM-ICPC 2015 - Pablo Ariel Heiber
Added by fidels (2015-10-12)
Limits
Total Time: 3000 MS | Test Time: 1000 MS |Memory: 256 MB | Output: 64 MB | Size: 16 KB
Enabled languages
Available in

Description

Amelia has decided to retire from programming competitions and move to a more peaceful place, away from the noisy city. She dreams of sitting in front of her house to see the sunset over the countryside, while listening on the radio to one of her beloved soap operas. However, before fulfilling her dreams she must solve one last problem, which consists in choosing where she should move.

The countryside where Amelia wants to move to is very large and flat, so much so that it can be represented by an infinite plane on which we imagine a Cartesian coordinate system (X, Y). In this countryside there are N radio stations numbered 1 through N. The i-th radio station transmits its signal from an antenna placed at point (X[i], Y[i]), having said signal a range of R[i]. This radio station can be tuned in to from any point (X, Y) whose distance to the antenna is less or equal to the corresponding range, i.e. satisfying:

(X - X[i])² + (Y - Y[i])² <= R[i]²

The signals from different radio stations can overlap, but will never interfere with each other. In order to listen to as many soap operas as possible, Amelia wants to place her house at some point within the range of the maximum possible number of radio stations. Now Amelia wants to know, given the description of the countryside, what is the maximum number of radio stations she will be able to tune in to as she sees the sunset over the countryside sitting in front of her house.
Amelia ha decidido retirarse de las competencias de programación y mudarse a un lugar más tranquilo, alejado del bullicio de la ciudad. Su sueño es poder sentarse frente a su casa a ver el atardecer sobre el campo, mientras escucha alguna de las radionovelas que tanto le gustan. Sin embargo, antes de poder cumplir su sueño debe resolver un último problema, que es elegir a dónde debe mudarse.

El campo al que quiere mudarse Amelia es muy grande y llano, tanto que puede representarse mediante un plano infinito sobre el que imaginamos un sistema cartesiano de coordenadas (X; Y). En este campo hay N estaciones de radio numeradas desde el 1 hasta el N. La i-ésima estación emite su señal desde una antena ubicada en el punto (Xi; Yi), teniendo la señal un rango de alcance Ri. Dicha estación puede ser sintonizada desde cualquier punto (X; Y) cuya distancia a la antena emisora sea menor o igual al rango de alcance correspondiente, es decir que satisfaga:

(X - X[i])² + (Y - Y[i])² <= R[i]²

Las señales de las distintas estaciones de radio pueden superponerse, pero no interfieren entre sí. Para poder escuchar la mayor cantidad de radionovelas distintas, Amelia desea ubicar su casa en un punto que esté dentro del rango de alcance de la mayor cantidad posible de estaciones de radio. Ahora Amelia quiere saber, dada la descripción del campo, cuál es el máximo número de estaciones de radio que va a poder sintonizar mientras ve el atardecer sobre el campo sentada al frente de su casa.
Amelia has decided to retire from programming competitions and move to a more peaceful place, away from the noisy city. She dreams of sitting in front of her house to see the sunset over the countryside, while listening on the radio to one of her beloved soap operas. However, before fulfilling her dreams she must solve one last problem, which consists in choosing where she should move.

The countryside where Amelia wants to move to is very large and flat, so much so that it can be represented by an infinite plane on which we imagine a Cartesian coordinate system (X, Y). In this countryside there are N radio stations numbered 1 through N. The i-th radio station transmits its signal from an antenna placed at point (X[i], Y[i]), having said signal a range of R[i]. This radio station can be tuned in to from any point (X, Y) whose distance to the antenna is less or equal to the corresponding range, i.e. satisfying:

(X - X[i])² + (Y - Y[i])² <= R[i]²

The signals from different radio stations can overlap, but will never interfere with each other. In order to listen to as many soap operas as possible, Amelia wants to place her house at some point within the range of the maximum possible number of radio stations. Now Amelia wants to know, given the description of the countryside, what is the maximum number of radio stations she will be able to tune in to as she sees the sunset over the countryside sitting in front of her house.

Input specification

The first line contains an integer N representing the number of radio stations in the countryside (1 <= N <= 100). Each of the following N lines contains three integers X[i], Y[i] and R[i] representing respectively the coordinates of the antenna and the range of the i-th radio station (-1000 <= X[i], Y[i] <= 1000 and 1 <= R[i] <= 1000 for i = 1, 2, ..., N).
La primera línea contiene un entero N, que representa la cantidad de estaciones de radio que hay en el campo (1 <= N <= 100). Cada una de las siguientes N líneas contiene tres enteros Xi, Yi y Ri, que representan respectivamente las coordenadas de la antena emisora y el rango de alcance de la i-ésima estación (-1000 <= Xi; Yi <= 1000 y 1 <= Ri <= 1000 para i = 1, 2,..., N).
The first line contains an integer N representing the number of radio stations in the countryside (1 <= N <= 100). Each of the following N lines contains three integers X[i], Y[i] and R[i] representing respectively the coordinates of the antenna and the range of the i-th radio station (-1000 <= X[i], Y[i] <= 1000 and 1 <= R[i] <= 1000 for i = 1, 2, ..., N).

Output specification

Print one line containing an integer representing the maximum number of radio stations Amelia will be able to tune in to if she optimally chooses where to move to.
Imprimir en la salida una línea conteniendo un entero que representa la máxima cantidad de estaciones de radio que Amelia puede sintonizar si elige adecuadamente el punto a donde mudarse.
The first line contains an integer N representing the number of radio stations in the countryside (1 <= N <= 100). Each of the following N lines contains three integers X[i], Y[i] and R[i] representing respectively the coordinates of the antenna and the range of the i-th radio station (-1000 <= X[i], Y[i] <= 1000 and 1 <= R[i] <= 1000 for i = 1, 2, ..., N).

Sample input

5
-1 0 2
1 0 2
0 -2 1
0 0 1
0 2 1

Sample output

4

Hint(s)

http://coj.uci.cu/24h/
http://coj.uci.cu/24h/
http://coj.uci.cu/24h/

Recommendation

We have carefully selected several similar problems: 3473 | 2176 | 3165 | 1211 | 2853 | 1847