GANNHAT - Closest distance
The manhattan distance between two points A(x1,y1) and B(x2,y2) is defined as following:
D(A,B) = |x1 - x2| + |y1 - y2|
Given N points A1, A2, ..., AN, for each point Ai you need to calculate the minimum D(Ai , Aj) (j ≠ i).
- The first line contains a positive integer N (1 ≤ N ≤ 200000).
- The i-th line of the next N lines contains two integers x and y which are co-ordinates of the i-th point(0 ≤ x, y ≤ 107)
- Print N lines, in which the i-th line contains the minimum distance for the i-th point.
Input: 4 0 0 0 1 1 0 1 1 Output: 1 1 1 1
Time limit is very strict.
any hints for the problem...cant get a start
For those who don't like this sample test case (like @c0d3junki3 below), here is an other one:
Worst sample case ever.
@Khanh There is no test for that (I got AC and my output for N=1 is random.)Last edit: 2012-11-25 09:49:34
hey please increase time limit for java as there are no currently accepted solutions
If N=1 what's the result?