Distance to the nearest point P28079
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++