Similar statements (6) P34848


Statement
 

pdf   zip

html

Consider two infinite horizontal lines A and B, separated ℓ units apart. The line A has m points at the abscissae a1, …, am. The line B has n points at the abscissae b1, …, bn. Given p different indices i1, …, ip choosen from {1 … m}, and p different indices j1, …, jp choosen from {1 … n}, define dk as the Euclidean distance between aik and bjk, that is,

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

You are given ℓ, p, and the points in A and in B. Peek i1, …, ip and j1, …, jp in order to



maximize  maxk=1..p   dk

Input

Input consists of several cases, each one with only integer numbers. Every case begins with four strictly positive numbers ℓ, p, m and n. Follow a1a2 ≤ … ≤ am−1am. Follow b1b2 ≤ … ≤ bn−1bn. Assume ℓ ≤ 106, p ≤ min(m, n), and that the absolute value of each abscissa is at most 106.

Additionally, assume that m and n are at most 105.

Output

For every case, print the result with four digits after the decimal point. If you use the long double type, the input cases have no precision issues.

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

    15.0333
    15.0333
    1280624.8475
    11.4018
    
  • Information
    Author
    Salvador Roura
    Language
    English
    Other languages
    Spanish
    Official solutions
    C++
    User solutions
    C++
    Event
    Catorzè Concurs de Programació de la UPC - Semifinal
    Date
    2016-06-29