Diễn đàn tin học Nguyễn Văn Linh

The second house for every one
 
IndexTrợ giúpTìm kiếmThành viênĐăng kýĐăng Nhập

Share | 
 

 Ông vua tham lam

Xem chủ đề cũ hơn Xem chủ đề mới hơn Go down 
Tác giảThông điệp
littlelee
Admin
Admin


Tổng số bài gửi : 415
Join date : 20/12/2009
Age : 21
Đến từ : Nghĩa địa

Bài gửiTiêu đề: Ông vua tham lam   Fri 19 Mar 2010, 18:19

Vua Midas thích vàng
Mã bài: MIDAS

Trong thần thoại Hy Lạp, do có công giúp đỡ người thầy của thần Dyonysus, nhà vua Midas được vị thần thưởng cho bằng cách đưa ngài đến một hòn đảo có dạng một đa giác lồi N cạnh. Hòn đảo đã được chia thành các vùng bởi M đường rào là các đoạn thẳng nối một số cặp đỉnh của đa giác. Biết rằng các đoạn rào chỉ có điểm chung tại các đầu mút (các đỉnh).
Thần Dyonysus nói với Midas rằng, nhà vua có thể chọn K mảnh bất kì trong số các mảnh đã được tạo ra bởi đường biên của đảo và các đường rào, miễn sao K mảnh đó phải ghép lại thành một miền liên tục.
Yêu cầu: Hãy giúp vua Midas tham lam chọn ra K mảnh sao cho miền thu được có diện tích lớn nhất.
Input

Dòng đầu tiên ghi 3 số nguyên dương N, M, K (K ≤ M ≤ 100, N ≤ 1000).
N dòng tiếp theo, dòng thứ i ghi hai số nguyên xi, yi ( |xi|, |yi| <= 1000000) là tọa độ của đỉnh thứ i của đa giác lồi (theo chiều ngược kim đồng hồ).
Cuối cùng là M dòng, mỗi dòng mô tả một đường rào, gồm 2 số u, v cho biết đường rào nối hai đỉnh u và v.
Output

1 Dòng duy nhất ghi S là diện tích lớn nhất tìm được, chính xác đến 2 chữ số sau dấu phẩy.
Example

Input:
8 4 2
0 0
0 2
1 4
3 5
5 5
6 4
6 2
4 0
1 3
3 8
4 7
4 8

Output:
13.50
Về Đầu Trang Go down
 
Ông vua tham lam
Xem chủ đề cũ hơn Xem chủ đề mới hơn Về Đầu Trang 
Trang 1 trong tổng số 1 trang
 Similar topics
-
» Ghi danh tham gia lớp thơ Đường Luật
» thơ tình cùng vào tham khảo nhé
» Điểm mặt những "anh tài" tham gia vòng Chung kết toàn quốc cuộc thi Chinh Phụ Vũ Môn lần thứ II
» mình anh
» GÓC N.ÁNH

Permissions in this forum:Bạn không có quyền trả lời bài viết
Diễn đàn tin học Nguyễn Văn Linh :: Góc tin học :: Lớp chuyên tin-
Chuyển đến