GANNHAT - Closest distance
Giới hạn- Thời gian: 0.35s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Khoảng cách Manhattan giữa 2 điểm A(x 1 ,y 1 ) và B(x 2 ,y 2 ) được định nghĩa như sau:
D(A,B) = |x 1 - x 2 | + |y 1 - y 2 |
Cho N điểm A 1 , A 2 , ..., A N trên mặt phẳng, với mỗi điểm A i ta cần tìm D(A i , A j ) 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 ≤ 10 7 )
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
- Người up: aukcwe
- Nguồn bài: Mr Taek