Enunciados similares (3) P14177


Statement
 

pdf   zip

thehtml

Considerad dos rectas horizontales infinitas A y B, separadas entre sí ℓ unidades. La recta A tiene m puntos en las abscisas a1, …, am. La recta B tiene n puntos en las abscisas b1, …, bn. Dados p índices diferentes i1, …, ip escogidos de {1 … m}, y p índices diferentes j1, …, jp escogidos de {1 … n}, sea dk la distancia euclidea entre aik y bjk, esto es,

dk = 
(aik − bjk)2 + ℓ2
⁠ ⁠ .

Dados ℓ, p, y los puntos en A y en B, escoged i1, …, ip y j1, …, jp para



minimizar ⁠ ⁠mink=1..p ⁠ ⁠ dk

Entrada

La entrada consiste en diversos casos, sólo con números enteros. Cada caso empieza con cuatro números estrictamente positivos ℓ, p, m y n. Siguen a1a2 ≤ … ≤ am−1am. Siguen b1b2 ≤ … ≤ bn−1bn. Asumid ℓ ≤ 106, p ≤ min(m, n), y que el valor absoluto de cada abscisa es como mucho 106.

Adicionalmente, asumid que m y n valen como mucho 105.

Salida

Para cada caso, escribid el resultado con cuatro dígitos decimales. Los juegos de prueba no tienen problemes de precisión si se usa el tipo long double.

Public test cases
  • Input

    1 1 2 2
    5 10
    9 20
    
    1 2 2 2
    5 10
    9 20
    
    1000000 4 5 4
    300000 300000 300000 300000 300000
    -500000 -500000 -500000 -500000
    
    3 2 7 4
    0 2 4 6 8 10 12
    1 4 7 10
    

    Output

    1.4142
    1.4142
    1280624.8475
    3.0000
    
  • Information
    Author
    Salvador Roura
    Language
    Spanish
    Translator
    Salvador Roura
    Original language
    English
    Other languages
    English
    Official solutions
    C++
    User solutions
    C++