GANNHAT - Closest distance
English | Vietnamese |
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.
|
|
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:
|
|
Dragan Markoviæ:
2013-08-01 12:22:00
Worst sample case ever.
|
|
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 |