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

Bài tập huấn luyện: Đĩa bay

 

Đã từ lâu, người ta cho rằng Roswell là nơi được nhiều vị khách từ vũ trụ ghé thăm. Qua những dấu vết để lại, các cư dân khẳng định rằng cách đây hơn 200 năm, đĩa bay đã hạ cánh xuống khu rừng ở đây và họ muốn các nhà khoa học xác minh lại điều này. Vì vậy mà BB, một nhà nghiên cứu vật thể bay không xác định đã được cử đến Roswell cùng với một nhóm nghiên cứu.

BB nhanh chóng khoanh vùng khu vực được cho rằng đĩa bay đã hạ cánh, đây là một vùng hình chữ nhật có kích thước X x Y. Trên khu vực này có N cây, cây thứ i có tọa độ (xi, yi) và độ cao hi.

BB biết rằng thông thường các cây nằm ở vùng đĩa bay hạ cánh sẽ khó phát triển được bình thường nên dấu vết mà đĩa bay để lại là một vùng hình tròn không có cây mọc. Tuy nhiên đôi khi cũng có ngoại lệ, một số cây vẫn có thể phát triển trong vùng này. Vì vậy để cho chính xác, BB định nghĩa vùng mà đĩa bay hạ cánh phải là một vùng thỏa mãn:

  • Là một hình tròn nằm hoàn toàn trong vùng hình chữ nhật được khảo sát.
  • Có điểm phạt không quá P. Điểm phạt được tính bằng tổng điểm phạt của tất cả các cây nằm trong vùng đĩa bay hạ cánh. Điểm phạt của mỗi cây nằm trong vùng đường tròn đó bằng (d x h)2 với d là khoảng cách từ cây đến đường tròn và h là độ cao của cây.

Sau khi thu thập được tất cả các tọa độ và độ cao của các cây nằm trong vùng khảo sát, BB muốn bạn viết một chương trình để tìm ra vùng đĩa bay đã hạ cánh có bán kính lớn nhất.

Input: UFO.INP

  • Dòng đầu tiên ghi 2 số nguyên X và Y là kích thước của vùng cần khảo sát.
  • Dòng thứ hai ghi 2 số nguyên N và P là số cây và điểm phạt lớn nhất.
  • Dòng thứ i trong N dòng cuối ghi 3 số nguyên xi, yi và hi lần lượt là tọa độ và độ cao của cây thứ i.

Output: UFO.OUT

Ghi 3 số thực XU, YU, RU lần lượt là tọa độ và bán kính của vùng đĩa bay hạ cánh tìm được. Kết quả phải được ghi chính xác đến 5 chữ số sau dấu phẩy.

Giới hạn:

  • 1 ≤ N ≤ 10000
  • 0 ≤ P ≤ 109
  • 0 ≤ xi ≤ X ≤ 106 ; 0 ≤ yi ≤ Y ≤ 106
  • 1 ≤ hi ≤ 1000
  • Thời gian: 2 s/test
  • Bộ nhớ: 16 MB

Ví dụ:

UFO.INP UFO.OUT
5 5

3 1

1 2 1

2 4 5

4 2 7

2.00000 2.00000 2.00000
Advertisements

About pascalteacher

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

Thảo luận

Không có bình luận

Trả lờ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ả

Chuyên mục

Tháng Mười 2016
H B T N S B C
« Th9   Th11 »
 12
3456789
10111213141516
17181920212223
24252627282930
31  

NCT Computer

Flickr Photos

lost

Lookkk deeeply into my eyes....

Cimitero San Michele

More Photos

Thống kê

  • 115,518 lượt xem

pascalteacher.nct@gmail.com


Trang huấn luyện học sinh giỏi Tin học

%d bloggers like this: