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ụ:

InputOutput
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.


    Quảng cáo
       Ngôn ngữ : 

       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