NEAREST - Cặp điểm gần nhất

Giới hạn
  • Thời gian: 0.138s
  • Bộ nhớ: 1536MB
  • Mã nguồn: 50000 bytes

Cho n (2 <= n <= 100,000) điểm trên mặt phẳng, hãy tìm cặp điểm có khoảng cách nhỏ nhất.

Input

- Dòng đầu tiên chứa số n.

- n dòng tiếp theo mỗi dòng chứa một cặp số thực (giá trị tuyệt đối không lớn hơn 10 7 ) biểu diễn tọa độ một điểm.

Output

Một số duy nhất (ghi chính xác đến 3 chữ số thập phân sau dấu phẩy) là khoảng cách nhỏ nhất tìm được.

Example 

Input:
5
1 1
2 2
3 3
4 4
5 5

Output:
1.414

  • Người up: anhdq
  • Nguồn bài: Hình học cơ bản