GANNHAT - Closest distance

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

Được gửi lên bởi:Kaiel
Ngày:2008-05-02
Thời gian chạy:0.100s-1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:CPP JAVA PAS-GPC PAS-FPC
Nguồn bài:Mr Taek

hide comments
2016-08-19 16:39:31


Last edit: 2016-08-21 13:48:57
2015-01-01 14:15:04 Hướng Thái Dương
vái cả xiết time =))) tối ưu 1 đống thứ ms tránh khỏi tle :((
2013-08-16 13:31:15 Chuyên Triết Tổng Hợp
dùng thuật toán random
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.