Distance to the nearest point P28079


Statement
 

pdf   zip

html

Given two sets S and Q of points on the plane, determine, for each point in Q, the minimum of the Manhattan distances to the points in S.

Input

Input consists of a natural n, the coordinates of the n points in S, a natural m, and the coordinates of the m points in Q. Assume 1 ≤ n ≤ 105 and 0 ≤ m ≤ 105. The coordinates are real numbers. Points can be repeated.

Output

For every point in Q, print the Manhattan distance to its closest point in S.

Observation

This problem tolerates an error of 10−7 for each output.

Public test cases
  • Input

    5
        0 0
        0 1
        1 0
        1 1
        1 0
    3
        0.1 0.1
        0.5 0.5
        1.0 1.0
    

    Output

    0.20000000
    1.00000000
    0.00000000
    
  • Input

    3
        2057.54368732 7224.84142068
        6754.64655994 7907.85575136
        9678.10748947 4968.45548394
    4
        6628.69040481 8947.34821279
        747.4327363 8300.22431512
        8784.52986333 4373.37802232
        7170.45535426 6464.09159581
    

    Output

    1165.44861656
    2385.49384546
    1488.65508776
    1859.57294987
    
  • Input

    5
        0 0
        0 1
        1 0
        1 1
        1 0
    3
        0.1 0.1
        0.5 0.5
        1.0 1.0
    

    Output

    0.20000000
    1.00000000
    0.00000000
    
  • Information
    Author
    Jordi Petit
    Language
    English
    Official solutions
    C++
    User solutions
    C++
    Event
    Onzè Concurs de Programació de la UPC - Semifinal
    Date
    2013-06-19