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++