3927 - Saving Springfield

Created by Marcelo Fornet Fornés
Added by MarX (2017-07-06)
Limits
Total Time: 10000 MS | Test Time: 1000 MS |Memory: 512 MB | Output: 64 MB | Size: 16 KB
Enabled languages
Available in

Description

For decades, Springfield has been a messy town. The main troublemakers in town are Bart and Homer. Today is not the exception. Bart has pranked and offended aliens of another planet. How does he manage to do that? What can he possibly do to disturb an entire race/species? We prefer not disclose that in this problem.

The most urgent issue right know is that Springfield will be under attack soon. Due to this alien threat, the mayor of Springfield has fled far away and appointed Homer to be the man in charge of the town's defense. To prepare for the invasion, do you know what Homer has done so far? Yes, you are right, he has done absolutely nothing. Since you believe that the Simpson family deserves to be saved despite Bart and Homer's actions, you decide to help them.

The best protection from aliens is glass, so your plan is to cover Springfield with a big semi sphere made of glass. All buildings of the town are lined up on Springfield's main street and each one has a position on the street and some particular height. You need to find the smallest radius of a semi sphere that contains all the buildings completely inside of it. The base of the semi sphere must be placed at some point on the street. All buildings have width of 1 and should be completely covered in the semicircle.

The invasion will be soon, so you have 4 hours to accomplish this task. Help Marge, Maggie and Lisa.

Por décadas, Springfield ha sido un pueblo desordenado. Los principales culpables del desorden en el pueblo son Bart y Homer. Hoy no es la excepción. Bart ha jugado una broma pesada y ha ofendido a alienígenas de otro planeta. ¿Cómo logró eso? ¿Qué habrá hecho para insultar una raza/especie entera de otro planeta? Preferimos no divulgar esto en este ejercicio.

La cuestión más urgente ahora mismo es que Springfield estará bajo el ataque muy pronto. Debido a la amenaza alienígena, el alcalde de Springfield se ha dado a la fuga. Antes de huir, él nombró a Homer para ser el nombre a cargo de la defensa del pueblo de Springfield. ¿Sabes que ha hecho Homer para preparar al pueblo contra la invasión? Adivinaste correctamente: él no ha hecho absolutamente nada. Puesto que usted cree que la familia Simpson merece ser salvada a pesar de las acciones de Bart y Homer, tú decides ayudarlos.

La mejor protección contra alienígenas es el vidrio. Por lo tanto, tu plan es cubrir a Springfield con una semi esfera grande hecha de vidrio. Todos los edificios de Springfield están alineados en la calle principal y cada uno tiene una posición en la calle y una altura. Necesitas encontrar el radio más pequeño de la semi esfera que contengan todos los edificios completamente dentro. La base de la semi esfera debe ser colocada en un punto en la calle principal. Todos los edificios tienen 1 unidad de ancho y deben estar completamente cubiertos bajo el semi círculo.

La invasión llegará pronto, por lo tanto, tienes cuatro horas para completar esta tarea. Ayuda a Marge, Maggie y Lisa.

For decades, Springfield has been a messy town. The main troublemakers in town are Bart and Homer. Today is not the exception. Bart has pranked and offended aliens of another planet. How does he manage to do that? What can he possibly do to disturb an entire race/species? We prefer not disclose that in this problem.

The most urgent issue right know is that Springfield will be under attack soon. Due to this alien threat, the mayor of Springfield has fled far away and appointed Homer to be the man in charge of the town's defense. To prepare for the invasion, do you know what Homer has done so far? Yes, you are right, he has done absolutely nothing. Since you believe that the Simpson family deserves to be saved despite Bart and Homer's actions, you decide to help them.

The best protection from aliens is glass, so your plan is to cover Springfield with a big semi sphere made of glass. All buildings of the town are lined up on Springfield's main street and each one has a position on the street and some particular height. You need to find the smallest radius of a semi sphere that contains all the buildings completely inside of it. The base of the semi sphere must be placed at some point on the street. All buildings have width of 1 and should be completely covered in the semicircle.

The invasion will be soon, so you have 4 hours to accomplish this task. Help Marge, Maggie and Lisa.

Input specification

The first line contain one integer N (1 ≤ N ≤ 104) that represent the number of buildings in Springfield.

The next N lines contain two integers each, X and H (1 ≤ X, H ≤ 104) representing the position on the street and the height of a building. No two buildings share the same position on the street. Note that if a building is at position X it means the base of the building is between (X - 0.5, X + 0.5).
La primera línea contiene un número entero N (1 ≤ N ≤ 104), el cual representa la cantidad de edificios en Springfield.

Cada una de las siguientes N líneas contienen dos números enteros, X y H (1 ≤ X, H ≤ 104), los cuales representan a la posición de un edificio en la calle y su altura. Ningún edificio ocupa la misma posición que otra. Note que, si el edificio se encuentra en la posición X, quiere decir que la base del edificio está entre (X - 0.5, X + 0.5).
;jsessionid=3A20304F8287E420E696A1F5CD8FEEF9
The first line contain one integer N (1 ≤ N ≤ 104) that represent the number of buildings in Springfield.

The next N lines contain two integers each, X and H (1 ≤ X, H ≤ 104) representing the position on the street and the height of a building. No two buildings share the same position on the street. Note that if a building is at position X it means the base of the building is between (X - 0.5, X + 0.5).

Output specification

Output a single number R, representing the radius of the smallest semi sphere that can cover all the buildings. The answer will be accepted if the absolute error against the correct answer is less than 10-5.
Imprima un solo número R, el cual representa el radio de la semi esfera más pequeña que cubra todos los edificios. Su respuesta será aceptada si el error absoluto contra la respuesta correcta es menor que 10-5.
;jsessionid=3A20304F8287E420E696A1F5CD8FEEF9
The first line contain one integer N (1 ≤ N ≤ 104) that represent the number of buildings in Springfield.

The next N lines contain two integers each, X and H (1 ≤ X, H ≤ 104) representing the position on the street and the height of a building. No two buildings share the same position on the street. Note that if a building is at position X it means the base of the building is between (X - 0.5, X + 0.5).

Sample input

2
1 1
2 1

Sample output

1.414213562

Hint(s)