3657 - Coverage 3657 - Cobertura 3657 - Coverage

Statistics Sub: 23 | AC: 11 | AC%: 47,83 | Score: 4,55
Created by 2015 Northwest Pacific Regional Contest
Added by kko (2016-06-01)
Limits
Total Time: 12000 MS | Test Time: 3000 MS |Memory: 512 MB | Output: 64 MB | Size: 9 KB
Enabled languages
Available in

Description

A cellular provider has installed n towers to support their network. Each tower provides coverage in a 1 km radius, and no two towers are closer than 1 km to one another. The coverage region of this network is therefore the set of all points that are no more than 1 km away from at least one tower. The provider wants as much of this region as possible to be connected, in the sense that a user at any point within a connected subregion can travel to any other point within the connected subregion without having to exit the subregion. Their current installation of towers may or may not already form a single connected region, but they have the resources to build one more tower wherever they want, including within 1 km of an existing tower.

Given that the provider is able to build one more tower, what is the maximum number of towers (including the one just built) that can be included within a single connected subregion of coverage?
Un proveedor de telefonía celular ha instalado N torres para dar soporte a su red. Cada torre ofrece cobertura en un radio de 1 KM y nunca dos torres se encontrarán a una distancia inferior a 1 KM una de otra. La región de cobertura de esta red es, por lo tanto, el conjunto de todos los puntos que están a no más de 1 KM de al menos una torre. El proveedor quiere que esta región se encuentre conectada tanto como sea posible, en el sentido de que un usuario en cualquier punto dentro de una subregión conectada pueda viajar a cualquier otro punto dentro de la subregión conectada sin tener que abandonar la subregión. La instalación actual de las torres puede formar o no una única región conectada, pero se dispone de los recursos para construir una torre más en cualquier lugar que se quiera, inclusive dentro de 1 KM de una torre existente.

Considerando que el proveedor puede construir una torre más. ¿Cuál es el mayor número de torres (incluyendo la nueva a construir) que pueden ser incluidas en una misma región conectada de cobertura?
A cellular provider has installed n towers to support their network. Each tower provides coverage in a 1 km radius, and no two towers are closer than 1 km to one another. The coverage region of this network is therefore the set of all points that are no more than 1 km away from at least one tower. The provider wants as much of this region as possible to be connected, in the sense that a user at any point within a connected subregion can travel to any other point within the connected subregion without having to exit the subregion. Their current installation of towers may or may not already form a single connected region, but they have the resources to build one more tower wherever they want, including within 1 km of an existing tower.

Given that the provider is able to build one more tower, what is the maximum number of towers (including the one just built) that can be included within a single connected subregion of coverage?

Input specification

The first line consists of a single integer n (1 <= n <= 5000), denoting the number of existing towers. Next follow n lines each with 2 space-separated real numbers x_i, y_i (0 <= x_i; y_i <= 10^5), denoting the location of tower i in km. It is guaranteed that the optimal number of towers will not change even if the coverage radius of all the towers is increased or decreased by one millimeter.
La primera línea consiste de un entero N (1 <= N <= 5000), denotando el número de torres existentes. Seguidamente, se suceden N líneas, cada una con 2 números reales separados por espacio x_i, y_i (0 <= x_i; y_i <= 10^5), denotando la ubicación de la torre i en KM. Se garantiza que el número óptimo de torres no cambiará, incluso si el radio de cobertura de todas las torres se incrementa o decrementa en 1 milímetro.
The first line consists of a single integer n (1 <= n <= 5000), denoting the number of existing towers. Next follow n lines each with 2 space-separated real numbers x_i, y_i (0 <= x_i; y_i <= 10^5), denoting the location of tower i in km. It is guaranteed that the optimal number of towers will not change even if the coverage radius of all the towers is increased or decreased by one millimeter.

Output specification

Print, on a single line, a single integer denoting the maximum number of towers that can be within a single connected subregion of the network after installing one additional tower.
Imprima en una línea simple, un entero denotando el máximo número de torres que pueden estar dentro de una misma subregión conectada de la red después de instalada una torre adicional.
The first line consists of a single integer n (1 <= n <= 5000), denoting the number of existing towers. Next follow n lines each with 2 space-separated real numbers x_i, y_i (0 <= x_i; y_i <= 10^5), denoting the location of tower i in km. It is guaranteed that the optimal number of towers will not change even if the coverage radius of all the towers is increased or decreased by one millimeter.

Sample input

5
1.0 1.0
3.1 1.0
1.0 3.1
3.1 3.1
4.2 3.1

Sample output

6

Hint(s)

Sample Input 2
5
1.0 1.0
3.1 1.0
1.0 3.1
3.1 3.1
10.0 10.0

Sample Output 2
5
Sample Input 2
5
1.0 1.0
3.1 1.0
1.0 3.1
3.1 3.1
10.0 10.0

Sample Output 2
5
Sample Input 2
5
1.0 1.0
3.1 1.0
1.0 3.1
3.1 3.1
10.0 10.0

Sample Output 2
5

Recommendation

We have carefully selected several similar problems: 1873 | 2824 | 1946 | 2305 | 4111 | 2756