//
you're reading...
Bài tập huấn luyện

Bài tập huấn luyện: Phòng cháy

 

Để đố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à (Xi, Yi) và bán kính Ri, 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 Dij – Ri – Rj, trong đó Dij là khoảng cách Euclide giữa 2 điểm (Xi, Yi) và (Xj, Yj).

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

InputFIRE.INP

  • 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 Xi, Yi, Ri là tọa độ và bán kính bể chứa dầu thứ i.

Output:            FIRE.OUT

  • Ghi ra số thứ tự của 2 bể chứa dầu có khoảng cách gần nhất (theo như thứ tự đã được cho trong file Input).

Giới hạn:

  • 2 ≤ N ≤ 10000. Có 30% số test với N ≤ 1000 và 70% số test với N > 1000.
  • |Xi|, |Yi| ≤ 106 ; 0 < Ri ≤ 106
  • Thời gian: 1 s/test
  • Bộ nhớ: 4 MB

Ví dụ:

FIRE.INP FIRE.OUT
30 0 14 0 25 5 3 2 3

About pascalteacher

Trang thông tin Toán học và Tin học

Thảo luận

Chưa có phản hồi.

Gửi phản hồi

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s

Các tác giả

Tháng Mười 2016
M T W T F S S
« Sep   Nov »
 12
3456789
10111213141516
17181920212223
24252627282930
31  

NCT Computer

Flickr Photos

Fast-flying Falcon

sunset and fishing nets

Force of Life - Pushing Boundaries I

More Photos

Thống kê

  • 81,544 lượt xem

%d bloggers like this: