Nubes Ácidas P68792


Statement
 

pdf   zip

thehtml

Uno de los próximos proyectos que la NASA llevará a cabo más allá del 2013 será ejecutado por una nave a la que llaman MAVEN. Ésta se encargará de la exploración de la atmósfera de Marte proporcionando información válida a los investigadores sobre el planeta.

Una de las misiones más importantes de la nave es la de recoger gotas de lluvia ácida (esto no se ajusta demasiado a la verdad, pero nuestros colegas en la NASA descubrieron que si decían que esta era la misión conseguían más titulares de prensa). Para ello, el robot debe desplazarse hasta aquellos lugares donde sospecha que lloverá.

Se parte de información de satélite que indica en qué posiciones (pares de coordenadas X e Y) ha ocurrido anteriormente el fenómeno a estudiar. Además, se ha observado que estos puntos están distribuidos sobre el mapa en forma aproximada de línea. Por ello, se ha decidido obtener una recta de regresión lineal (ver, por ejemplo,
http://www.sc.ehu.es/sbweb/fisica/cinematica/regresion/regresion.htm) a partir de dichos puntos.

El director de la NASA, Charles Bolden, te pide que hagas un programa que guíe a MAVEN hacia esta recta donde parece más probable que vaya a llover. En concreto se te pide que, dado un valor para la coordenada X, tu programa devuelva cuál es el correspondiente valor de Y que posicionaría a la nave sobre dicha recta de regresión.

¡Ayuda a MAVEN a encontrar sus nubes ácidas!

Entrada

La entrada está formada por un número indeterminado de casos. Cada uno de ellos empezará con una N, el número de puntos de lluvias anteriores, seguido de N líneas con dos números reales cada una con las coordenadas X e Y. Los valores de todas las coordenadas están situados entre 0 y 1000. A continuación un número P en una línea con el número de preguntas a resolver. Cada pregunta se da en una línea y consta de la coordenada X a la que la nave desea desplazarse.

El programa termina cuando se da una N menor que 2.

Salida

Para cada pregunta, escribe la salida Y correspondiente en una línea, con una precisión de 3 decimales. En caso de que el caso de pruebas sea tal que no haya solución, imprime por pantalla una única vez ‘IMPOSSIBLE’. Deja una línea en blanco entre casos.

Puntuación

  • Test1:  ‍ Entradas donde X≤ 100, Y≤ 100, N≤ 200 y P≤ 200.  ‍10 Puntos ‍
  • Test2:  ‍ Entradas donde X≤ 1000, Y≤ 1000, N≤ 2000 y P≤ 2000.  ‍30 Puntos ‍
  • Test3:  ‍ Entradas donde X≤ 1000, Y≤ 1000, N≤ 100000 y P≤ 4000.  ‍60 Puntos ‍
Public test cases
  • Input

    5
    536 1000
    435 756
    142 1000
    124 431
    600 731
    3
    601
    700
    1
    2
    2 2
    2 2
    2
    2
    2
    -2
    

    Output

    854.020
    883.864
    673.147
    
    IMPOSSIBLE
    
  • Information
    Author
    Javier Segovia
    Language
    Spanish
    Official solutions
    C++
    User solutions
    C++