FIRE - Phòng cháy

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

Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.

Link đọc đề trên VNOJ

Để đối phó với tình hình biến động của giá xăng dầu, nước X quyết định xây dựng một kho dự trữ dầu với quy mô cực lớn. Kho chứa dầu sẽ bao gồm N bể chứa dầu hình trụ tròn mà ta sẽ biểu diễn trên bản đồ bằng N hình tròn, hình tròn thứ i có tọa độ là (X i , Y i ) và bán kính R i , các hình tròn không có điểm chung trong với nhau (nhưng có thể tiếp xúc).

Để đảm bảo an toàn phòng cháy chữa cháy, người ta cần xác định 2 bể chứa dầu gần nhau nhất để tăng cường cách ly khi xảy ra hỏa hoạn.

Biết rằng khoảng cách giữa 2 bể chứa dầu thứ i và thứ j chính bằng khoảng cách giữa 2 đường tròn tương ứng và bằng D ij – R i – R j , trong đó D ij là khoảng cách Euclide giữa 2 điểm (X i , Y i ) và (X j , Y j ).

Bạn hãy giúp những người quản lý tìm ra 2 bể chứa dầu này.

Input

Dòng thứ nhất ghi số nguyên dương N là số bể chứa dầu.

Dòng thứ i trong N dòng tiếp theo ghi 3 số nguyên X i , Y i , R i là tọa độ và bán kính bể chứa dầu thứ i.

Output

Gồm 1 dòng duy nhất là khoảng cách của 2 bể chứa dầu bé nhất tìm được.

Example 

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

Output:
0.0990

Giới hạn:
2 ≤ N ≤ 10000. 
|Xi|, |Yi| ≤ 106.
0 < Ri ≤ 106. 
Kết quả ghi chính xác đến 4 chữ số sau dấu phẩy.

  • Người up: cun
  • Nguồn bài: Ioicamp - Marathon 06 - 07