GANNHAT - Closest distance

no tags 

Khoảng cách Manhattan giữa 2 điểm A(x1,y1) và B(x2,y2) được định nghĩa như sau:

D(A,B) = |x1 - x2| + |y1 - y2|

Cho N điểm A1, A2, ..., AN trên mặt phẳng, với mỗi điểm Ai ta cần tìm D(Ai , Aj) nhỏ nhất với j ≠ i.

Dữ liệu

  • Dòng đầu ghi số nguyên dương N (1 ≤ N ≤ 200000).
  • N dòng sau dòng thứ i ghi 2 số x và y là tọa độ của điểm thứ i. (0 ≤ x , y ≤ 107)

Kết quả

  • Gồm N dòng, dòng thứ i ghi khoảng cách nhỏ nhất cần tìm đối với điểm thứ i.

Ví dụ

Dữ liệu:
4
0 0
0 1
1 0
1 1

Kết quả:
1
1
1
1

hide comments
Harsh Gupta: 2015-12-07 09:33:49

Time limit is very strict.
Getting TLE for O(nlogn) solution.

Pagan Min: 2015-05-19 05:21:17

any hints for the problem...cant get a start

aristofanis: 2014-03-17 19:33:45

For those who don't like this sample test case (like @c0d3junki3 below), here is an other one:

Input:
-------------

7
81 48
78 50
47 13
70 43
61 28
73 56
58 21

Output:
-------------

5
5
19
15
10
11
10

Last edit: 2014-03-17 19:35:01
Dragan Markoviæ: 2013-08-01 12:22:00

Worst sample case ever.
Not to mention to allowing latest gcc...

Nic Roets: 2012-11-25 09:49:08

@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
karan173: 2012-09-30 23:01:20

hey please increase time limit for java as there are no currently accepted solutions

Khanh Quynh: 2009-04-14 17:10:31

If N=1 what's the result?


Added by:Kaiel
Date:2008-05-02
Time limit:0.100s-1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:CPP JAVA PAS-GPC PAS-FPC
Resource:Mr Taek