Nội dung Bài tập
- Mã:
- OLP17.SC2.GOAT
- Tên:
- Con dê
- Dạng thi:
- oi
- Thang điểm:
- 100 điểm
- Giới hạn thời gian:
- 1 giây
- Giới hạn bộ nhớ:
- 256 MB
- Nguồn bài tập:
- Olympic tin học 2017
- Được tạo bởi:
- admin

Khi học chương trình Toán lớp 9 Bờm rất thích bài toán số 80 về hai con dê trong vườn cỏ. Biết vậy, để thách đố Bờm, Cuội đã cải biên bài toán đó thành bài toán chỉ với một con dê (mà thoạt nhìn, có vẻ là dễ hơn bài toán với hai con dê) sau đây:
Trên một cánh đồng cỏ rộng mênh mông (đối với bài toán ở đây hãy coi là rộng vô hạn) có một khu biệt thự được bao bọc bởi một hệ thống tường bê tông cao ngất có dạng một hình đa giác lồi gồm n đỉnh. Tại một đỉnh của đa giác có đóng một cọc mà tại đó có sợi dây với độ dài L để buộc một con dê. Con dê có thể ăn cỏ ở bất cứ điểm nào nằm ngoài đa giác mà nó có thể đến được, nhưng không thể đi vào điểm nằm trong hình đa giác (khu biệt thự). Cần tính diện tích vùng đồng cỏ mà con dê có thể ăn được.
Yêu cầu: Giúp Bờm tính diện tích vùng đồng cỏ mà con dê có thể ăn được.
Dữ liệu input:
- Dòng đầu tiên chứa 3 số nguyên n t L được ghi cách nhau bởi dấu cách, trong đó n là số đỉnh của đa giác, t là chỉ số đỉnh của đa giác mà dê được buộc vào cọc đóng tại đó, còn L là độ dài của sợi dây buộc dê (1 ≤ n ≤ 10000, 1 ≤ L ≤ 100000);
- Dòng thứ i trong số n dòng tiếp theo chứa hai số nguyên xi, yi là tọa độ của đỉnh thứ i của đa giác, | xi | ≤ 10000, | yi | ≤ 10000, i = 1, 2, …, n. Các đỉnh được liệt kê theo một chiều đi vòng quanh đa giác.
Kết quả: xuất diện tích của vùng đồng cỏ mà con dê có thể ăn được với 8 chữ số sau dấu phảy.
Ví dụ:
Input Output 4 1 1 0 0 1 0 1 1 0 1 2.35619449
Hình minh họa cho ví dụ:

Giải thích: Trong hình vẽ minh họa cho ví dụ: Vùng tô màu đen là mô tả khu biệt thự, vùng tô màu xanh (tô màu đen nhạt – trong bản in đen-trắng) là vùng cánh đồng cỏ mà con dê có thể ăn được.
Theme :
Mời bạn soạn code
Ai có thể xem bài này :
Thông tin
Phần thảo luận